next »

[Belimoth]

A topic in Technical that isn't a question, crazy right?

Once upon a time I was a young lad coding rectangular collisions for the first time. I became frustrated with the way they are usually done-checking to see if two objects overlap and then pushing them apart-because of things like tunneling and the ambiguity involved in evaluating multiple collisions at once.

The result is an algorithm for the other kind of collision detection, which I am going to talk about.

Since we all code in different languages here I am going to make some diagrams and pseudocode to describe things, in the meantime here is a DEMO of my platformer engine that uses this strategy.

Please discuss below if you have any experience with this kind of thing or opinions about it.

[Belimoth]

Okay! I'm going to describe how entity-to-grid collisions work in this system, from the ground up.

First you have a world.

Properties:

• width, in pixels
• height, in pixels

Next you have a grid made up of tiles.

Properties:

• cell size, some divisor of the world's width and height
• width, in cells
• height, in cells

Thirdly, an entity. Let's call it the player.

Properties:

• (x, y) describing the upper-left corner, in pixels
• width, in pixels
• height, in pixels

At this point you would want to have a method of converting between pixel coordinates and grid coordinates. My choice to use the upper-left corner of the player entity as its handle is completely arbitrary.


Finally, some terrain on the grid for the player to collide with.

Each tile is either solid or empty. No slopes for now.

[Belimoth]

Just by looking at the last picture you can tell how far the player could move straight in any of the four directions before hitting something. Now to figure it out algorithmic-ally.


Using the aforementioned method to convert between pixel and grid coordinates, determine the grid-square that the player inhabits.



Pick a direction (east) and starting from each tile on that side of the square, step in that direction until you reach a solid tile (or go off the grid). The near side of that tile is the farthest the player could move in that row, in that direction.



You can do this in all four directions to get a bounding box.

[Belimoth]

After you have that, the rest is straight-forward.
Instead of moving the player like each step like this:

Code:

x = x + xv
y = y + yv

...you would do something like this:

Code:

if (xv > 0) {
	x = minimum(x + xv, boundary.x + boundary.width - width - 1);
} else {
	x = maximum(x + xv, boundary.x + 1);
}
//likewise for y, using height instead of width

[s_l_m]

Certainly interesting, I like the use of min/max to move a character to the edge of a boundary instead of "pushing" the character out of a collision area. Its a pretty simple concept but I am glad that people write tutorials like this

[s_l_m]

I don't understand, I wrote sthg similar in a platforming code without even thinking about it, what is there more to it?

Not really, its just a pretty basic tutorial on slightly more advanced collision detection than beginning programmers would realize. I don't see anything especially groundbreaking but its always good to have these kinds of tutorials around

[Belimoth]

I wrote sthg similar

Great! You should share what you've accomplished

its always good to have these kinds of tutorials around

I agree, also I forgot the Tutorial sub-forum existed.
I probably should've posted this there.

[moi]

okay, but my platformer code is such a mess, I don't think it would be a good idea

[EDIT]I've deleted my useless post

[motorherp]

Your algorithm fails if the player is allowed to move along both axes at once, for example:



The blue box shows the bounds your algorithm would constrict the player too, but the player should be able to move unrestricted along the green line I've drawn which ends outside of the blue box.

The correct way to deal with collision detection when you dont want to deal with resolving object penetration from using discrete collision checks is to instead use continuous collision detection techniques (sometimes called swept tests).  There's plently of tutorials out there, have a look on google.

[Belimoth]

Finding the boundary is just the beginning, I have only described the simplest implementation so far.

A slightly more in-depth way of doing it is to:

• update the boundary in the x direction
• move the player in the x direction
• update the boundary in the y direction
• move the player in the y direction
• repeat until:
• the player has moved the maximum amount described by their velocity
• OR the player's position hasn't changed since the last step

This is a kind of sweep, and can be made optional for low-priority (non-player) entities to cut down on computation costs.

Also the specific way this is done can be biased to either favor either less or more collisions with corners, which can be preferable for the high-speed diagonal situations in which it applies.

This kind of movement handling becomes more important with entity-to-entity collisions, which I will cover later.

[motorherp]

Finding the boundary is just the beginning, I have only described the simplest implementation so far.

A slightly more in-depth way of doing it is to:

• update the boundary in the x direction
• move the player in the x direction
• update the boundary in the y direction
• move the player in the y direction
• repeat until:
• the player has moved the maximum amount described by their velocity
• OR the player's position hasn't changed since the last step

This kind of movement handling becomes more important with entity-to-entity collisions, which I will cover later.

This doesn't seem to be the most efficient solution and would be very slow in the worst case scenario when the player is moving along a diagonal slope which would result in a large number of iterations of your algorithm to resolve.  A simple swept collision test would solve all these issues.

PS:  Just realised there's also the problem that your algo would fail to find collision against floating islands of terrain that lie in a diagonal direction to the player along the direction they wish to move but dont overlap the players x or y axis projections.  I can draw a diagram if you dont see what I'm getting at, let me know. 

[Belimoth]

It is actually significantly faster because the projection results for each cell in each direction can be cached and/or pre-calculated for the entire map very easily, where as a sweep would still require a rectangle-collision check each step.

Also I haven't talked about slopes yet because they are best done with a more detailed height-map checking system for each tile, and also because the behavior of an entity moving along a slope is extremely specific to the genre of whatever game is being made.

[motorherp]

Well the point I'm making is that using a swept test you would only have to perform the collision test once for each object per frame that object moves and you would be garaunteed that one test would work in all scenarios and provide a correct answer.

Trying to reliably prevent object penetration using discrete collision checks without missing any collisions will always result in lots of edge cases to deal with, lots of special cases that need writing for different collision types such as slopes, and lots of situations where you'll end up having to perform many iterations each frame to resolve an objects movement.

Ultimately discrete collision checks just aren't suitable for solving these kinds of problems which can be resolved more easily and reliably using continuous collision algorithms.

Maybe this is a special case though since you're dealing with a fairly well defined grid environment, I'll be interested to see what you come up with.



Edit - Just realised I took a bit of a tangent there, the issue isn't one of discrete versus continuous.  You are in-fact trying to do continuous collision detection of sorts but just doing it incorrectly by splitting your continuous collision test into seperate x and y axis components rather than dealing with it once along the true direction.  My point still holds though, trying to do it this way rather than using a true continuous test will result in all the same issues I described.

[motorherp]

Please discuss below if you have any experience with this kind of thing or opinions about it.

If we're discussing alterantive collision methods you might be interested in this tutorial I wrote a while back for ShmupDev.  It goes into continuous collision techniques as well as a special time filter collision optimisation I designed specificaly for bullet hell style shoot-em-ups.  You might find it interesing:

Art Of Collision [part 2] : Circles, Dynamic Testing, and Time Filtering

PS: Unfortunately it seems all the images with that tutorial have dissapeared since the forum was archived.  Sorry about that, hopefully you can still understand what I'm getting at.

[st33d]

Eh. I just split collision into x and y, doing a sweep on x and then y separately.

The benefit of this is that it's really simple. And because most platformer characters aren't using both axis all the time, you don't have to test both axis all the time. And you slide off walls in a pleasant way.

[motorherp]

Eh. I just split collision into x and y, doing a sweep on x and then y separately.

The benefit of this is that it's really simple. And because most platformer characters aren't using both axis all the time, you don't have to test both axis all the time. And you slide off walls in a pleasant way.

Well to be fair, doing proper continuous collision testing is hardly difficult either.  The algorithms are well documented online and if anything I would say it ends up being simpler since you wont have to deal with edge cases.  I've not written a 2d platformer myself though so I could be wrong.