Log In  

Hi pico8'ers, it's me again. Sorry!

Today I am wondering what the best approach would be to check if a sprite/object has touched a line and act accordingly.

Take the following example:
Let's say I made this 45 degree slope and I have a character that can walk to it or jump to it from wherever. I want that line to be "solid" and affect the character's behavior.

Illustrated:

How would I go at this, I have no idea.
I have a collision system in place in my game, but it checks bounding boxes.
Of course I don't want to make bounding boxes of 1x1 and check against all of them, that sounds slow and stupid.

I think maybe what I need here is "raycasting" but I never in my life have done anything like that and have no idea where to begin. I don't even know if that is what I am looking for.

I don't want to make slopes of varying angles, it will always be a 45 degree slope. I Am hoping this also would make things easier.

I didn't find any cart on the BBS that does exactly what I want from where I could look at some code. Maybe I didn't look hard enough.

Any help appreciated!

P#51954 2018-04-24 14:32 ( Edited 2018-04-27 21:00)

Say you have a floating point coordinate system (a la collide sample cart), tile width is 1 unit.
Height is is given by frac(x) for / slopes, 1-frac(x) for \ slopes.

function frac(x) return x-flr(x) end
P#51955 2018-04-24 14:45 ( Edited 2018-04-24 18:45)

OK, but I still don't understand how that translates to a collision system.

The way I am thinking this, is that I have the line's two extreme points, and with these, I should be able to calculate the location of any point in between.

I could check at any X position of the bottom left corner of the sprite, if the X and Y coincide with that of the line at that particular X position.

Still unsure how to translate it to code, but does that sound any logic?

P#51957 2018-04-24 14:57 ( Edited 2018-04-24 18:58)

I believe a decent number of classic platformers would watch the tiles under the player, (you could flag them in pico8,) and then just added some extra math to adjust vertical accordingly depending on how far along the tile the player is.

quick and dirty like
if walkingon(slope_r) player.y-=player.x%8
if walkingon(slope_l) player.y+=player.x%8

edit:Note that some extra math also has to be added to vertical tile collisions.

P#51958 2018-04-24 15:02 ( Edited 2018-04-24 19:05)

Well I am not using tiles, imagine this is a vector game then, or rather, that I am not using sprites or tiles. Just some simple shape-generated characters. "player" is a rect, the line is, well, a line.

One more thing: don't assume I am a decent coder with a decent level of math/algebra in my brain. I'm neither.

I thought following with the above logic I posted, "if I can make a function that draws a line between two given points, I would have the code that also allows me to know the coords to any point within that line", and now I am pulling my hair and thinking "why did I block from my mind all my past algebra learning?" :P

I found this info here to refresh my mind:
https://math.stackexchange.com/questions/175896/finding-a-point-along-a-line-a-certain-distance-away-from-another-point

Now I'm really going bananas at trying to implement a simple solution in pico-8 to draw a line using pset(). I feel like if I can do that I can basically figure this one out because I'd be able to single out any point within a line given two initial coordinates to start/end that line, and then checking if my rect's bottom left corner intersects with that point should be easy peasy.

Sorry if I sound dumb: I am :P

[edit] PROGRESS!

I managed to make a function that plots a line between two points:

diag={  x0=0,
        y0=0,
        x1=20,
        y1=20
}

function draw_line(lin)
    length_h=lin.x1-lin.x0
    length_v=lin.y1-lin.y0
    unit=length_v/length_h

    for i=0,length_h do
        for j=1,unit do
            pset(lin.x0+i,lin.y0+1+j+(unit*i),2)
        end
    end
end

(that took embarrassingly longer than I wanted ;_;)

Now if I exchange the pset() line with some variable assignment, I should be able to calculate all points of the line and put them in a vector, or just modify this function to just give me one set of coords at a specific point, instead of iterating through every point.

Now I don't know how close to the math I linked above this is to, but so far I feel like it serves its purpose. If there's any flaw with this train of thought, please comment and correct me! Let's remember I am a moron coder :P

[edit 2] of course this wouldn't have gone without a problem ;___; this function only works while X ><= Y so if my slope looks like \ it's fine, but I can't if it looks like / . Will try to make it work for both I know there's something silly in here.

P#51960 2018-04-24 15:55 ( Edited 2018-04-24 20:49)

Hum... if you don’t grok at least some basic vector math, then, that’s going to be difficult.

Couple of remarks:

  • pico has a line function
  • line/line intersection (of segment/segment) is well documented (see wiki). You don’t need to iterate over points to find the exact solution.
  • if you need more than that, look up ‘point/convex polygon’ intersection (but again, basic vector math required)
P#51967 2018-04-24 16:51 ( Edited 2018-04-24 20:53)

I know pico8 has a line function, but that wasn't the point of the exercise above, I made that so I could learn how to make one myself and via it, be able to access all points of a line between two points. This is how I solve many of my problems, I try to make a function that has the basic logic functionality to solve the problem, and when that works, I build upon it.

Which wiki is that you are pointing me to, this one?
http://pico-8.wikia.com/wiki/Pico-8_Wikia
I use it often but I did not see code examples within that could help me with this problem.
Line to line would not work though, I need to do a point to line(point in line) collision. Which is basically a point to point collision. Which I am thinking, from the code above, I almost have, without the bother of vector math.
I feel like line-to-line is what you would call a raycaster, right? Probably overkill.

Once upon a time, in a land far far away, I learned all the vector math needed for stuff like this. I since blocked it off and don't remember it. So I am struggling to get acquainted with it again.

In brief: if I can calculate the exact coords of a point in a line, I can easily solve this problem. I would only need to calculate its Y position if I already have an X to compare to (the X of the colliding object's point). I feel like the code above is near, I am basically figuring out every point between the two fixed points and plotting them.

P#51968 2018-04-24 17:03 ( Edited 2018-04-24 21:06)

Thing is, your collider is likely to move faster than than 1 pixel per update. You’ll never have a perfect 0 distance to line.
Hence the need to calculate intersection between slope (segment 1) and (previous pos, current pos) eg. segment 2.

Sorry, I meant Wikipedia or better yet for all intersection logic:
http://www.realtimerendering.com/intersections.html
(aka ‘the bible’ ;)

P#51971 2018-04-24 17:13 ( Edited 2018-04-24 21:15)

Noted, since this is a slope, I can check for everything "behind" it too, right?
Also as I said before, I hope this is made a bit easier by the slopes being always 45 degrees.

I'm gonna have a good long read at that intersection bible! I know I have to up my math game, but my brain is still reluctant to come back to it.

Thanks so much for your help so far!

P#51972 2018-04-24 17:31 ( Edited 2018-04-24 21:31)

Thought of another idea to use what I already have (box to box collision detection):

After being able to extract the point of the line that coincides with the character's X position, I can draw a bounding box the size of the character behind that point and check for collision with that

Dunno how efficient this is though but I hardly am at the point where routine efficiency should be a problem for me.

P#51973 2018-04-24 17:49 ( Edited 2018-04-24 21:49)

A bounding box is a vertical rectangle, so it's easy to test whether a line intersects with a side. For a vertical side, plug the x coord of the side into the equation for the line, solve for y, then test whether y is between the side's y1 and y2. For a horizontal side, plug the y coord in and solve for x, then test between x1 and x2.

You can get the equation for a line from its start and end coordinates. If you want slope-intercept form y=mx+b, the slope m is (y2-y1)/(x2-x1). You can then solve for b by inserting x1,y1 (a point on the line) for x and y. If all slopes are 45-degree slopes then you can optimize this faster than a division.

That's the basic idea. I don't know the common simplifications and optimizations off the top of my head, but it's common enough that you can find them online (and possibly elsewhere on this forum's history, iirc).

You didn't say, or I overlooked, how these slopes are represented in your code. There might be a faster way if these are on tile boundaries.

P#51977 2018-04-24 20:51 ( Edited 2018-04-25 00:51)

dddaaannn that's I think basically what my poor brains tried to explain above! :D
I think that's what I am going to do at this point, as any other solution has left me rather confused. Seems easy enough. I think the point made by freds is that just checking against 1px-wide boxes can lead to issues if the character goes too fast and passes that tiny 1px margin, so that is why I suggested creating a box at that point, to try to catch as much of the sprite as possible.

So far as on the example above, my line is an array with 4 coordinates, {(x0,yx),(y1,y1)}, that gives me start and end point of the line. I can calculate any point in between given one coordinate, indeed.

At the moment, the way I laid this out, they are not on tile boundaries. The line I want to intercept is from the middle of a tile to the middle of another.

I'm going to try to make the code above work on any kind of line and see if I can implement this collision. Thanks everyone so far!

P#52001 2018-04-25 10:06 ( Edited 2018-04-25 14:08)

Mucho simpler:

  • slopex/y/0/1 are slope segment coordinates (as you don’t have tiles)
  • cornerx/y are coordinates of a corner of your collider
  • define v1={x=slopex1-slopex0,y=slopey1-slopey0}
  • define v2={x=cornerx-slopex0,y=cornery-slopey0}

Calculate:

d=-v1.y * v2.x + v1.x * v2.y

(that is, dot produt of slope normal and corner)
if d is negative, corner is ‘behind’ slope, if positive, in front.
(if d==0 point is exactly on the slope)
Repeat that for all corners and you have an exact collision check, working regardless of collider speed.

P#52003 2018-04-25 10:20 ( Edited 2018-04-25 14:21)

Interesting solution! Although I have a hard time understanding what is going on (this is why I usually draw a graph displaying what is going on).

Is "slope segment coordinates" what I already have?

diag={  x0=0,
        y0=0,
        x1=20,
        y1=20
}

And does the order matter?
v1 sounds similar to what I did here:

    length_h=lin.x1-lin.x0
    length_v=lin.y1-lin.y0

But I don't fully understand what v2 is. Seems to be "distance from corner to one of the points".

Why did you change the sign of v1?

Given my game structure, collision can come only from one side, so only one corner check would be enough!
If you look at the graphic above, for example, think that there's no other way the character can touch the slope, and that leaves 3 corners out of the question. I would never approach the same slope from the opposite side (on the top), only head on towards the slope, and going upwards only.

P#52005 2018-04-25 11:02 ( Edited 2018-04-25 15:02)

Yes - slope coords are your diag structure.

Sign question:
Given vector (x,y), (-y,x) is an orthogonal vector.

P#52013 2018-04-25 13:42 ( Edited 2018-04-25 17:42)

hey freds, Without really understanding much of what was described in your code, I implemented it and it's not working for me, so I am not sure this was the right solution.
It's doing "something" on a slope that is / (D changes value weirdly), but absolutely nothing when the slope is \ .

I understand dannnn's solution better and will try to implement that now and see what happens.

P#52073 2018-04-27 15:36 ( Edited 2018-04-27 19:39)

Hacked a sample cart with a basic vector terrain and a square player model:

Cart #52074 | 2018-04-27 | Code ▽ | Embed ▽ | No License

P#52075 2018-04-27 17:00 ( Edited 2018-04-27 21:00)

[Please log in to post a comment]

Follow Lexaloffle:        
Generated 2021-12-06 10:54:06 | 0.018s | Q:41