Allegro.cc - Online Community

Allegro.cc Forums » Programming Questions » Trying to figure out wall collision sliding

This thread is locked; no one can reply to it. rss feed Print
Trying to figure out wall collision sliding
André Silva
Member #11,991
May 2010
avatar

Hey everyone. I'm trying to wrap my head around how to handle collisions between an object and a wall, and making the object slide across said wall. Now, the basic case is pretty simple. Grab the wall's normal vector, the object's velocity vector, do a cross-product, yadda yadda.

To detect a collision, you move the object from its current position to the one its velocity is telling it to go. If it is intersecting with walls, that means it's an invalid move. So pick a wall out of those, and slide across that direction. My problem is deciding what wall to pick.

In a normal scenario, I pick the slide angle that is farthest away from the object's velocity angle. This works well for when the object slides from one wall to another. But now, please take a look at the attached file. It represents a few different scenarios for our object (a cylinder) moving in the game world, from a top-down perspective.

Legend:

  • Red circles are the object's current position and new position. The arrow is just the movement angle.

  • In black, you see the walls, with their normals poking out with a small branch. This also means that the side without the little prong is a higher floor than the side with the prong. Each wall is also named for convenience.

  • In cyan, you get the possible slide angles.

For case 1, the object hits a "spike". The object is slightly to the right, and as humans, we know that it'd make sense for it to slide on the right wall (wall B). But how can we know that in code?

For case 2, the object hits three walls. Although logically, it only reaches walls A and C, the reality is that it also intersects with wall B, and that's the wall it will slide with, considering that the change in angle for wall B's slide is larger than that of wall A's slide. We know that it really should slide off of wall A, though, but how can we tell, in code, that we should ignore wall B? We could probably use the vertex somehow, but...enter case 3.

For case 3, the object hits three walls that are really close to one another. Imagine a really thin flight of stairs. We know it should slide off of wall A, but the way I currently have it will make it slide off of wall B, since, again, it's a larger difference between the movement angle and the slide angle.

With all that said and done...there HAS to be some code that works for all of these scenarios and then some. FPS games have been doing collision checks and sliding mechanisms of the sort for ages now. Doom does this flawlessly (I checked), but I can't make heads or tails of its source code. I don't think adding special cases for every one of those scenarios is the way to go...not to mention the performance overhead in checking the scenarios. Can I get some advice here, folks? Thanks!

SiegeLord
Member #7,827
October 2006
avatar

So pick a wall out of those, and slide across that direction.

I think a better idea, since you're using a circle, is to pick the tangent vector to the circle at the collision point. This'll handle the case of what to do when you hit a point. In general, though, I'd probably backtrack if I found a collision until there's only one collision point, and then do what I said above.

"For in much wisdom is much grief: and he that increases knowledge increases sorrow."-Ecclesiastes 1:18
[SiegeLord's Abode][Codes]:[DAllegro5]:[RustAllegro]

André Silva
Member #11,991
May 2010
avatar

I suppose that makes sense. The backtracking makes me scared about performance issues, but I won't knock it till I tried it. Thank you.

EDIT: It seems as though that won't work for the basic cases, however. Consider the scenario in the attachment, in which the green X are the intersection points between the circle and the line segments. The object is sliding from one wall to another one in that scenario. If I try to get the "first" point of collision, be it by backtracking, checking the distance of each point, or whatever other method, the "first" point will always be the one from line A. If the object slides along line A, it will go inside wall B. In reality, we'd want the algorithm to make the object slide along line B and go up-left...

SiegeLord
Member #7,827
October 2006
avatar

The first part could be solved by altering the condition to saying that you'll get only 1 new collision point per movement. Since you start with 1 collision point, it's ok to get the second one. I don't know what exactly to do once you do get a second one. I feel like you'll have to solve some sort of constraint satisfaction problem. Like, get a set of possible movement directions from all the collision points and then make sure none of them make you go through one of the collision points.

I feel like at some point it might be easier to just look at how physics engines like box2d or chipmunk are written.

"For in much wisdom is much grief: and he that increases knowledge increases sorrow."-Ecclesiastes 1:18
[SiegeLord's Abode][Codes]:[DAllegro5]:[RustAllegro]

André Silva
Member #11,991
May 2010
avatar

I'll try to tinker around a bit with that idea.

>I feel like at some point it might be easier to just look at how physics engines like box2d or chipmunk are written.

I'm feeling the same too, now. As long as it goes better than my Doom source code adventure... Whichever way I decide, I'll update the thread with some solution. Thanks for the help.

SiegeLord
Member #7,827
October 2006
avatar

So I decided to look at how Doom does it too just now. Looks like it essentially does what I said, kinda. First it tries to move, and if that fails it backtracks until it finds the first collision. It backtracks so much that it actually stops colliding with what it was colliding with. This solves the two collision problem because the first collision gets forgotten. It then does a slide along that wall. If it collides with something, then it repeats the backtrack + slide process up to 3 times.

"For in much wisdom is much grief: and he that increases knowledge increases sorrow."-Ecclesiastes 1:18
[SiegeLord's Abode][Codes]:[DAllegro5]:[RustAllegro]

Johan Halmén
Member #1,550
September 2001

What do you mean by sliding across/with a wall? Isn't the ball bouncing off the wall?

I guess the standard way is to detect the collision point, find the tangent and normal of the circle at that point, divide the velocity vector into its tangent and normal components. Then negate the normal component and add it to the unaffected tangent component. If the ball should continue in the wall direction, zero out the normal component. In real world it would mean losing energy to the collision.

In your first image, case 1, as I see it, the ball hits a sharp corner. The directions of walls A and B have no meaning, other than forming the sharp edge, at which the ball bounces. The ball can never continue in the direction of either wall. There's just a collision point. And a tangent through that point. The tangent is like a wall. And if the ball loses all collision energy, it still moves along this tangent, not along walls A or B.

In your second attachment, the ball would probably first interact with A, then with B. But the collision point can't be in the corner of A and B!

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Years of thorough research have revealed that the red "x" that closes a window, really isn't red, but white on red background.

Years of thorough research have revealed that what people find beautiful about the Mandelbrot set is not the set itself, but all the rest.

André Silva
Member #11,991
May 2010
avatar

Doom might be using a different way to detect collisions. And to slide. Although the backtracking method it uses seems pretty genius, it also seems a bit heavy. But either way, I can't really see how it handles cases like hitting a "spike" wall dead on.

Johan: this is not a 2D engine with a ball and usual physics. More like a 3D top-down engine in which the circle is the object's hitbox as seen from above: the object is like a cylinder. I've also got the idea on how to detect the walls and slide across them, and it's working quite fine; the only problem is in the exact scenarios I described, where one game tick the object is outside of the walls, and on the next, it collides with multiple ones. Figuring out a good algorithm to pick the right wall to slide on is the main issue. In the second attachment, those are more or less where the collision points would be (the one further down isn't really on the vertex, but slightly below :-X ), considering the usual "here one frame, there the next" way objects move.

Bruce Pascoe
Member #15,931
April 2015
avatar

This is why physics engines are typically driven at a higher framerate than the game itself, to avoid the exact scenario you describe (going from "no collision" to "multiple collisions" in a single step, which can be seen as a form of tunneling). It's actually good practice to drive the physics independent from the renderer anyway, to avoid issues when, e.g. frames are skipped during slowdown.

André Silva
Member #11,991
May 2010
avatar

Ain't that the truth... Although separating the physics logic, and even making it tick at a far greater interval than everything else will not be enough to ensure only one collision at a time. If the walls are sufficiently close (they can easily be on scenario #2 of the first attachment), the object can still be inside multiple ones in the next frame. Plus, a lot of perfectly normal scenarios can trigger multiple collisions as well, such as walking into a hallway that gets progressively thinner. Regardless, I made a test real quick, with the physics ticking over 2 thousand times per second (over 30 times faster than what I used to have), and the rendering at something like 3FPS, and all of my problems persist.

I'll try to take a look on how some frameworks and other games do it. Something has to work...

Johan Halmén
Member #1,550
September 2001

For case 1, the object hits a "spike". The object is slightly to the right, and as humans, we know that it'd make sense for it to slide on the right wall (wall B).

What kind of object is it? As a human, I have no idea what the sliding along a wall means. I'm still stuck in the 2D physics that I described earlier, no matter if it's a 3D top view world. What happens in the collision? What causes the further movement of the object? Has it a built in power source for the movement?

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Years of thorough research have revealed that the red "x" that closes a window, really isn't red, but white on red background.

Years of thorough research have revealed that what people find beautiful about the Mandelbrot set is not the set itself, but all the rest.

André Silva
Member #11,991
May 2010
avatar

I'm not quite sure how else to explain it, but I can give examples. In most modern first person shooter games, if you make your character walk against a wall at an angle (i.e. not perpendicular to the wall), and keep the keys held down to walk in that direction, the character will eventually hit the wall, stop going in the direction they're going, and go in a new direction, where they slide along the wall.

Bruce Pascoe
Member #15,931
April 2015
avatar

Here's how I would do it, if you're not going to use a pre-made physics engine: When moving at an angle you would have to calculate the X and Y movements separately. So what you could do is, do your X and Y movements separately, i.e. with a collision check for each. This shouldn't cause any issues with normal (non-colliding) movement, since the two translations are mathematically the same as a union of both.

Johan Halmén
Member #1,550
September 2001

Ok, even I get it now. There's no bouncing off, right? I'd say you have to think frame by frame what happens and why. Visualize it in Inkscape, move the objects by hand and figure out how you represent the objects as data structures in your code.

In frame t the object is not intersecting with a wall. In frame t+1 it intersects. You probably have to calculate the fraction time when the collision happened, especially if there are two walls intersecting at t+1.

What happens to the velocity when the collision is perpendicular? Or when it is almost perpendicular? I'm asking, because I'd still use my bouncing collision approach, but without bouncing, which means I'd zero the normal component of the velocity vector and keep the tangent component, causing the object to slide along the wall. After an almost perpendicular collision with a wall, should the object accelerate instantly to its former speed in the new direction?

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Years of thorough research have revealed that the red "x" that closes a window, really isn't red, but white on red background.

Years of thorough research have revealed that what people find beautiful about the Mandelbrot set is not the set itself, but all the rest.

André Silva
Member #11,991
May 2010
avatar

I appreciate the help guys, but my problem is figuring out which of the multiple collisions to use when sliding. Not necessarily the sliding itself...

Mark Oates
Member #1,146
March 2001
avatar

You have to find all the possible collisions, then choose the one that occurs soonest. Step forward that amount of time.

Do the appropriate collision/reaction for that surface/object.

Continue with the remaining time.

Johan Halmén
Member #1,550
September 2001

By multiple collisions I assume you mean that in frame t you have no intersections between the circle and the walls, and in frame t+1 you have several intersections. You have to step into the exact "time" when the collisions would have appeared. Say you have three walls there and the circle intersects with w1, w2 and w3 in frame t+1. Calculate the exact time for each collision, let's call them d1, d2 and d3. Pick the smallest of them, say it's d2. So, in time t+d2 the circle touches w2 and starts sliding along it.

Now you have a new situation. The circle slides along w2 and in the immediate neighbourhood there are w1 and w3. The present time is t+d2, which is between t and t+1, assuming there's some constant frame rate for the game loop (perhaps separate from the graphics update rate). If it is important to adjust the movement so that the circle moves with constant speed (or a speed affected by the collision), you would have to yet calculate what happens during t+d2 ro t+1. At t+1, will the circle intersect with w1 and/or w3? It's the same situation, pick the least of d1 and d3.

If you don't mind small inaccuracies in the game loop rate, just think of t+d2 being t+1 and continue from there. But if you have a situation where you have a narrow corner of 45 degrees of two walls and the circle moves into this corner, what happens? The circle hits either wall first, then slides along it into the corner and gets stuck? It's your world, you define what happens and why. And how.

What, why and how! Important questions. I kind of was lost with the "what" and "why" things, which is why I tried to suggest the bouncing collision thing. I still don't get the "what" and "why" things when the circle hits a spike. Will it rotate around the vertex, then continue sliding? Or are you going to make a short cut to the sliding? As I mentioned, hitting a wall and continuing sliding along it is like a collision without a bouncing effect. But hitting a spike and continuing sliding along either wall requires the rotating around the collision point before sliding. A "natural" behaviour would be to continue in the tangent direction, not sliding along the wall. In your world, is there something that sucks the circle to the wall?

<edited /> Or what Mark said.

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Years of thorough research have revealed that the red "x" that closes a window, really isn't red, but white on red background.

Years of thorough research have revealed that what people find beautiful about the Mandelbrot set is not the set itself, but all the rest.

Go to: