next »

[Ben_Hurr]

Hey TIG guys, I'm new to the forums and I was hoping someone could help me with my programming quandary.

At the moment I'm trying to work out a way to get my platform games' objects to slide along and be stopped by solid walls.
The games' walls are tilebased, and I'm using good ol' AABB rects to detect collisions.

I can't seem to find anything about doing this, but surely this problems been solved since the dawn of game programming? 

[Glaiel-Gamer]

I can't seem to find anything about doing this, but surely this problems been solved since the dawn of game programming?  

nope, never. Von Neumann actually proved it to be an unsolvable problem

find the first tile in the direction of the movement vector, just consecutively check tiles till one is solid, them move the block to 1 tile before that one

[David Pittman]

The best* solution is to do a sweep test to avoid "phasing" through geometry at high speeds. Here's some pictures!



So you've got a guy moving with some velocity, and you've got some tiles. If you move the character by this velocity (multiplied by delta time) and test for collision at the end point, you'll end up here:



The guy is not colliding with any tiles here, so the move is considered valid. But look at the actual path of the character:



The lower right corner of his bounding box clearly cuts through the tile on this path. The actual point of collision is shown here:



So how do we test for this? Subdividing the movement vector and testing for collision at smaller intervals isn't a completely terrible choice, but it can't catch every case. Then you have to find an acceptable balance between allowing some edge cases or doing a ridiculous number of tests, and that can get expensive. There's a better way.

The next image is effectively the same initial scenario as the first image I posted, but I've reduced the character to a single point and expanded the world by the guy's dimensions (making a Minkowski sum, or difference, or something, of their geometries).



Now you can just find the exact point of intersection of the movement vector with the expanded world (with ray-triangle or ray-AABB tests). That will eventually locate this point:



And conveniently, that small offset from the starting point to the point of intersection is exactly the same as the distance the guy can move before he collides with that tile; so move him that far and you're done!

*This is the best solution in my experience, anyway. But really, whatever gets the job done efficiently and without bugs is the best for any game.

[Ben_Hurr]

The best* solution is to do a sweep test to avoid "phasing" through geometry at high speeds. Here's some pictures!



So you've got a guy moving with some velocity, and you've got some tiles. If you move the character by this velocity (multiplied by delta time) and test for collision at the end point, you'll end up here:



The guy is not colliding with any tiles here, so the move is considered valid. But look at the actual path of the character:



The lower right corner of his bounding box clearly cuts through the tile on this path. The actual point of collision is shown here:



So how do we test for this? Subdividing the movement vector and testing for collision at smaller intervals isn't a completely terrible choice, but it can't catch every case. Then you have to find an acceptable balance between allowing some edge cases or doing a ridiculous number of tests, and that can get expensive. There's a better way.

The next image is effectively the same initial scenario as the first image I posted, but I've reduced the character to a single point and expanded the world by the guy's dimensions (making a Minkowski sum, or difference, or something, of their geometries).



Now you can just find the exact point of intersection of the movement vector with the expanded world (with ray-triangle or ray-AABB tests). That will eventually locate this point:



And conveniently, that small offset from the starting point to the point of intersection is exactly the same as the distance the guy can move before he collides with that tile; so move him that far and you're done!

*This is the best solution in my experience, anyway. But really, whatever gets the job done efficiently and without bugs is the best for any game.

Ooooo, an illustrated example! <3

I can't say I've heard of the method where you shrink the player to a point before, it looks interesting!  Hoho, I'll have to see if I can implement it.

[Tycho Brahe]

I'm not actually sure he was saying to shrink your character, simply to test moving intersections of points on it, for example it's corners.

[powly]

The way David wrote it it seems he just uses the middle point of the character and works the magic on the tiles (adds character width to tile width), of course you could leave the tile boundaries like they are and check all corners.

I myself just move my objects directly, they won't go through any solid walls (maybe cut corners; not that you'd notice it with that speed) if I have some reasonable limits on their acceleration.

[Ben_Hurr]

"I myself just move my objects directly, they won't go through any solid walls..."
Move them directly? Do explain.

But yes, checking the corners might work as well.

[kometbomb]

I think Super Mario etc. do this simply by moving the guy and checking if the guy rectangle is inside a wall and if so they move it left or right by the depth of the collision. I don't think it's strictly even a bug if you can move diagonally over tile corners (and you could argue a game should allow that in the name of playability).

E.g. if your tiles are 16x16 and the guy can only move at a maximum speed of less than 16 pixels (so it doesn't completely skip over a tile), you will know that if after moving the guy to the left, the rectangle is inside a tile, you need to move the guy to the right by the depth of collision. It is easy to deduce the depth since you know the tile and guy coordinates (and you don't even need the tile coordinate because you know you need to align the guy to 16 pixel tiles).



You can then do the same whenever the guy is falling but for the Y coordinate. If the guy collides, set the feet firmly on the tile under the guy and stop the falling. Now, on every frame or when the guy moves you need to check if there's something under the guy and if not, falling starts again.

[bluescrn]

I think Super Mario etc. do this simply by moving the guy and checking if the guy rectangle is inside a wall and if so they move it left or right by the depth of the collision.

If all your tiles are square, this works pretty well - to implement it, do the X and Y updates separately - this will help avoid problems when you hit the corners of a tile:

Update player X position
If we're overlapping a tile
   - Correct our X position (and set the player's X velocity to 0?)

Update player Y position
If we're overlapping a tile
   - Correct our Y position (and cancel any jump that may be in progress?)

Then you won't have the case where it's overlapping, and you don't know whether you should be correcting X, Y, or both to resolve it.

(If you want slopes, things can get rather more complex, and you may end up dealing with line segment intersections, normal vectors, etc - and your may find it easier to treat the player as a circle, or a pair of circles, rather than a box?)

[kometbomb]

do the X and Y updates separately

Yes, I didn't stress this enough. The problem becomes extremely simple when you reduce it to two easy 90-degree movements.

I don't think slopes complicate stuff very much since the slope can be thought simply as a change in the floor height according to the X coordinate. Unless you're making a Sonic clone, it's just an extra few lines of code in the "has our falling guy hit the ground" check and adding an extra movement up or down when the guy runs left or right on a slope. Very steep slopes can then be though just as a vertical wall that can't be walked on (unless you're Sonic).

[Draknek]

Yes, definitely do x and y movement separately.

My problem with slopes is that you need to use the x-centre to determine the height of a slope at any point, but what happens when that centre point isn't touching the ground but part of the bounding box still is? You don't want to let the player fall straight down because then he'll be overlapping the wall, but you also can't just move him magically from one position to the other.

Reusing old diagram:


I have yet to implement a good solution to this.

[Tycho Brahe]

I've started using circles a lot more in collision detection and you'll probably find that you'll want this here. You could try having a circle based collision shape, as detection and resolution for this is still relatively simple.

[powly]

"I myself just move my objects directly, they won't go through any solid walls..."
Move them directly? Do explain.

But yes, checking the corners might work as well.

Just as others said, x and y separately, move the object along the axis -> check for collisions -> if collides, move back and set velocity to 0 (or multiply it by, say, -.7 to get a cool bounce effect if you want it)

[kometbomb]

Yes, definitely do x and y movement separately.

My problem with slopes is that you need to use the x-centre to determine the height of a slope at any point, but what happens when that centre point isn't touching the ground but part of the bounding box still is?

Make the sideways test completely skip slopes. In any case the slopes are not sideways blocking tiles (unless falling down) because, well, they are floors and not walls.

[Ben_Hurr]

"I myself just move my objects directly, they won't go through any solid walls..."
Move them directly? Do explain.

But yes, checking the corners might work as well.

Just as others said, x and y separately, move the object along the axis -> check for collisions -> if collides, move back and set velocity to 0 (or multiply it by, say, -.7 to get a cool bounce effect if you want it)

The only problem I see with that is moving diagonally very fast will screw you up. :X


But that's like, if the distance you're covering in one step is bigger than an entire tile;
and that would be ridiculously fast in a 2D game anyway.

[powly]

Well, I haven't actually done any calculations about this but my guess is I'll never move over a tenth of a tile per frame. Of course with great speeds this is a problem.

[Ben_Hurr]

Yeah, it'll probably be good enough for what I'm doing.
But the inaccuracy haunts me so. 

[kometbomb]

Yeah, it'll probably be good enough for what I'm doing.
But the inaccuracy haunts me so. 

At least to me, it's a thrill to create something really simple to achieve something relatively complex. I would even go as far as saying a complex solution with slightly better results is a much worse solution when you think about the cost of the code (not necessarily money but amount of work, debug time, frustration).

All the best games usually got to be the best games because they faked something. Otherwise they would never have been completed. Anyone can make plans but not everyone can execute the said plans etc.

(I'm not a great programmer but I'm a certified Zen master)

[powly]

Also a little cheaty approach is almost always a lot faster. (Euler approx. vs proper integration, anyone? )

[bluescrn]

Yeah, it'll probably be good enough for what I'm doing.
But the inaccuracy haunts me so. 

If you're moving fast (more than a few pixels in one update), just subdivide the move into several steps.  Even pixel-sized steps if you want.