Archive for November, 2008

Sloped surfaces and moving platforms

Nov 29

Posted by Kael in Gruedorf | No Comments

I spent most of today getting sloped surfaces and moving platforms working with the new movement and collision code.

The first approach I tried was to extend my existing collision detection code to automatically figure out how to move up and down a slope. I spent a few hours struggling with this, coming up with lots of implementations that were almost right, but they all ended up having nasty edge cases or needing stupid hacks to work correctly. Even worse, they complicated the normal motion and collision detection code in ways I didn’t like (though one cute side effect was that the player character began naturally sliding down slopes when he stood still… heh.)

So after some prodding from a couple people on IRC, I tried to solve this problem a different way. I changed the representation of my level geometry to distinguish between different types of polygons – LevelGeometry objects became LevelTriangles and LevelRectangles. Then I did a bit of work to enable a LevelTriangle to automatically figure out which of its sides is the sloped one. Once I had those two things, it was straightforward to change the movement code:

Every frame, check to see if the player is standing on a piece of geometry.
If the player is standing on a piece of geometry, call its ComputeStandingY method and pass in the player’s new position (the player’s current position plus his current velocity) and width. The method will return a new Y coordinate for the player.
Apply the new Y coordinate to the player’s current position.
Perform motion and collision detection as usual. The previous ComputeStandingY call already took into account the player’s intended velocity and selected an appropriate Y coordinate for him, so he won’t intersect with the surface he’s walking on.

Once I figured out how to do this, it actually was really simple to code and worked just about right. There were a couple key details, though:

You need to make sure to take into account the width of the player. The right math for this on a sloped surface turned out to be something like: (playerWidth / slopeWidth) * (slopeMaximumY – slopeMinimumY). That knocks the player up just enough so that his left and right edges don’t intersect with the slope, so that motion is smooth and it still looks more or less like he’s standing on the surface.
The order of these operations matters a little bit. If you do the slope correction after doing motion and collision detection, you get glitchy movement because the player will intersect with the slope and then get moved up onto it, repeatedly.
Determining exactly where the player is standing can be a little tough. I’m using my normal collision detection code to do it and just offsetting the player’s Y by a couple pixels to see what’s below him. It more or less works, but I don’t think it’s the correct solution.

Much simpler than the previous solution I had, for sure, and it looks a bit nicer too since a lot of the glitchiness is gone.

Once I had this solution in place, moving platforms were really easy. Moving platforms are level geometry just like anything else, so they can have their own implementation of ComputeStandingY that ensures the player is standing right on top of them while he’s riding them. The only other missing detail is making the player automatically move along with the platform while he’s riding it. That turned out to be simple; you just add a step at the end of the existing algorithm:

…
Perform motion and collision detection as usual. The previous ComputeStandingY call already took into account the player’s intended velocity and selected an appropriate Y coordinate for him, so he won’t intersect with the surface he’s walking on.
If the surface the player is standing on is moving, add the surface’s velocity to the player’s current position.

Note that we do this after doing motion and collision detection – this is important for vertical platforms. If you do it before, the collision detection will sometimes prevent the player from moving with the platform, and he’ll get stuck. Also note that this has the downside of allowing a platform to push the player through a solid wall or other obstacle; I don’t consider this a problem for my implementation, and there are ways you could solve it.

Tags: collision, Gruedorf, motion, platformer, polygon, xna

Collision detection and motion

Nov 29

Posted by Kael in Gruedorf | No Comments

Initially I implemented collision detection and motion in this platformer prototype the same way I had done it previously in Fury², my game creation system project from a while back. Entities have a position and velocity, which are both pairs of floats (x, y). Every frame, I compute the new position of the entity – pos+vel – in a given axis (x or y), and then do a check to see if it’s obstructed. If it’s obstructed, I halve the velocity and try again, and I repeat that iteratively a few times until I give up. After doing that for both axes, I have a relatively good approximation of how far the entity can move in its desired direction.

It was good enough for me, and the performance wasn’t *terrible*, so I didn’t worry about it much. But I always had this nagging doubt in my mind – this solution is obviously a hack. Isn’t there a way to do this with pure math?

Well, I’m not very good at math, but it turns out there is a way to do it with pure math. So today I threw out all the motion and collision code I had written for the platformer and decided to try a pure math approach, and see if I could resolve collisions non-iteratively. Suprisingly enough, it wasn’t actually that hard.

Here’s a summary of how it works:

I already do my collision detection using the separating axis theorem (SAT). To check for collision between a pair of convex polygons, I compute a set of axes based on the polygons (a vector perpendicular to every edge of each polygon) and then for each axis in the set, I project both polygons onto that axis and see if they overlap. As soon as I find an axis in which the polygons are not overlapping, I know that they are not intersecting – no need to check all of them.

Pretty simple, and actually quite easy to code – Around 20 lines of C# for a relatively efficient implementation of the check itself, and another 20 lines to compute the list of axes without any duplicates, since there’s no point in checking the same axis twice.

With the algorithm described above, it’s actually quite simple to build motion on top of it. Once I’ve projected both polygons onto a given axis, and confirmed that they don’t intersect, I can do another projection – I can project the velocity of the moving polygon onto that same axis, and add that to the original projection of the moving polygon to get the projection of its new, desired location. At that point, I know whether the polygon will intersect on this axis as a result of moving, and not only that, I can compute the amount of intersection by determining how much the two intervals overlap. Once I have that value, I can use it to compute a vector that will separate the two polygons.

Once I iterate over all the axes and compute separating vectors, I can pick the smallest separating vector and add it to the original velocity of the polygon. At this point I can do some checks to see if the new velocity is acceptable – for example, did the separating vector cause the polygon to change directions entirely? In that case, it’s probably not acceptable, and we can just flat-out reject movement and say that the polygon cannot move in this direction at all. Likewise, if the separating vector is enormous, that means the polygon moved all the way through the obstruction to avoid collision, which we obviously don’t want either, so we can reject it.

The end result was essentially this:

For every axis, project movingPolygon and stationaryPolygon onto that axis. This produces two intervals – movingInterval and stationaryInterval.
Check to see if movingInterval and stationaryInterval overlap. This tells us whether or not the polygons were already colliding.
Project the velocity of movingPolygon onto the axis, and add that projected value to movingInterval. This gives us the new interval of the moving polygon – newInterval.
Check to see if newInterval and stationaryInterval overlap. If they overlap, determine how much they overlap by – overlapAmount. At this point we know whether or not the two objects would have collided.
If the newInterval is overlapping, we can now compute a vector that will separate the two polygons, by multiplying the current axis by the amount of overlap (the axis is a unit vector, and the amount of overlap is a distance).
Add the separating vector to the original velocity of the polygon, to compute the new candidate velocity – newVector.
Check to see if Magnitude(newVector) <= Magnitude(movingPolygonVelocity). If not, reject the new vector.
Check to see if Normalize(newVector) ·dot· Normalize(movingPolygonVelocity) >= 0. If not, reject the new vector. (This ensures that we don’t push the object in the opposite direction to resolve the potential collision – in this case, the magnitude would have still passed the previous check)
If the new vector was not rejected, we know that the two objects will not be colliding.
Once you’ve iterated over all the axes, select the largest non-colliding vector (if any). That’s your resultVector.

At the end of this algorithm, you have four outputs:

areColliding (right now, before applying the velocity)
wouldHaveCollided (if we applied the original velocity)
willCollide (if you apply the result velocity)
resultVelocity

In the case where the collision could not be resolved, the resultVelocity will be 0. In the case where there was no collision, the resultVelocity will be the input velocity. In every other case, the resultVelocity is a vector that safely moves the polygon in the desired direction, without producing a collision.

One detail to note is that the quality of the result velocity depends on the axes that you check. If you only check axes generated from the shapes of the colliding objects, you can get strange (though valid) results – for example, two boxes will not produce any axes except X and Y to check, so if the object is moving at an angle, the algorithm will miss the ideal axis to compute the resultVelocity from. There are a few ways to solve this – you can pre-compute a set of ‘basic axes’ to check in every case, or you can derive a set of axes from the velocity of the object. Either way, though, the algorithm seems to work quite well – it works as well as the old one did in the platformer, and passes all my unit tests.

It’s always nice to go from 100 lines of code to 10 lines of code. Unfortunately, I’m not done yet. My previous implementation supported walking up and down slopes in a natural manner, and it also supported moving platforms. The new implementation supports neither, so I have some more work to do. Hopefully I can solve both of those problems using pure math, too – I’m working on sloped surfaces right now, and it looks like I can make it work with pure math by improving on my existing algorithm.

You can see the source code for my implementation here. Note that there’s some commented out bits in there from my work on sloped surfaces.

Tags: Code, collision, csharp, Fury², Gruedorf, motion, platformer, polygon, xna

It’s a platformer!

Nov 28

Posted by Kael in Gruedorf | No Comments

After finishing Order of Ecclesia (small aside: utterly awesome game), I felt sufficiently inspired to finally start coding the platformer I’d been working on ideas for. A couple days ago I started writing the actual meat of the platforming mechanics and fiddling around with things like animation and collision detection, to start moving towards having an actual game!

After a couple days of work, so far I’ve got:

Basic player character animation (running, jumping, falling, etc) using a (stolen) sprite from Castlevania: Dawn of Sorrow.
Moving platforms (though vertical motion is a little busted)
Running up/down slopes
Falling when running off a ledge
Jumping

I even allowed myself to get distracted by shiny things, and got it to run smoothly on my XBox 360.

So far the most interesting bit has been figuring out how to properly implement moving platforms in a game like this without a bunch of hacks. Getting the details just right for things like falling off a platform, being pushed by a platform, and so on is actually quite difficult – there are lots of edge cases where the simplest possible solution just doesn’t work. Once I figure it out I’m planning to try and explain the details of my solution, since people rarely talk about this problem when building platformers.

Getting slopes working was also a bit of a challenge – so far I’m using a bit of a hack where, if the player’s next location is obstructed, I iteratively check to see if the location slightly above it is unobstructed, a fraction of a pixel at a time. This allows the player to run straight at a sloped surface and have his character automatically climb the slope, without too much hassle. Going down slopes wasn’t quite as hard, since the falling physics automatically took over there.

The next few items on my milestone list: