• entries
    743
  • comments
    1924
  • views
    580438

Pod Collisions

Sign in to follow this  

116 views

Discovered a major problem with the way map collisions are being handled in Pod.

I was messing about making the details of the main Pod load from a config file rather than be hard coded and randomly gave Pod a radius of greater than 24, so a diameter of more than 48, which is the size of a map cell.

My map sampling method, which basically returns shapes based on the cells within a 2x2 grid but welds certain pairs of shapes together into one shape, to avoid the problems I described a few weeks ago, now no longer works. Obviously.

So the current system can't cope with map collisions with anything larger than a map block, which is a bit rubbish.

Moving to sampling and welding from a 3x3 grid creates so many possible combinations of shapes that it would be horrible, and would just throw a 86x86 limit on the size of a moving entity, so isn't really a viable solution.

I think I might have to find a way to collide against edges rather than shapes, so standard SAT will be out of the question. Unless I can find some kind of hacky way to mark horizontal edges with rectangular regions somehow. But then it creates a lot of extra work at the level design stage.

Pain in the bum, all this. It is going to take some thinking about and possibly a complete rethink about how collision physics is handled.

Anyway, off out to a fireworks display now with the missus. Hopefully that might trigger some inspiration. Be more chance if I had a problem with particle systems I guess but you never know.

[EDIT]

Having slept on the problem, the most robust solution seems to be one that is going to mean a bit of extra work at the level design stage.

Basically after the visual look of the level has been laid out as a tilemap, I plan to then have the facility to define convex polygons around the level features that are solid. The game will then just check collisions against this list of polygons.

The extra work at level design stage is the only downside. If necessary, I can use a quadtree to save checking against every polygon in the level, although on another recent project I found that this was unnecessary even with hundreds of level polygons provided I did an AABB test first on each poly pair to reject any definate non-collisions.

So next step is to either update the existing generic map editor, or write a new one specific to Pod.
Sign in to follow this  


4 Comments


Recommended Comments

Collision are certainly a lot of work. Have you considered just pre-analysing the level geometry at runtime to auto-generate the convex hulls you need to define the collision geometry?

That would avoid you having to replicate this work at the level-design stage (which is both more work and another place you can get things out of sync/wrong).

Share this comment


Link to comment
I got interested in your problem after reading and thought about it. Here's what I came up with:

1. For each type of tile, store its convex hull as an array of 4 lines. In terms of storage you could do this by having a "tile template" file that specifies the bitmap the tile will display and include the convex hull info.

The best way to represent a 2D line is by using 1 point that lies on the line plus line's normal (the vector that points in the direction of line's positive halfspace). This representation is most optimal for collision detection. You can reduce the memory this will take by storing only 4 normals (2 floats for each), and then assuming that the first and the second line's point is the tile's top left corner and the third and fourth line's point is the tile's bottom right corner.

So for a simple square tile, you would store:
[0] = ( -1.0, 0.0) // left edge - normal points left (implicit point is tile top left)
[1] = ( 0.0, -1.0) // top edge - normal points up (implicit point is tile top left)
[2] = ( 1.0, 0.0) // right edge - normal points right (implicit point is tile bottom right)
[3] = ( 0.0, 1.0) // bottom edge - normal points down (implicit point is tile bottom right)

Notice that all normals are pointing "out" of the tile (away from center).

2. When doing collision detection:

For each tile that pod overlays,

Calculate 4 lines that define that tile's convex hull by using the stored normals and calculating the points based on current tile's AABB min & max (top left & bottom right). Thus, "decompressing" the hull info to prepare for collision testing.

Then for each "decompressed" hull line, check if the line faces toward the pod or away from pod. If it faces away, you can early-out of collision detection. This will prevent testing collision against the sides of tiles that face away from the pod and are not a part of the complex shape that defines pod's "immediate environment" that it's inside of.

To do this, you would probably take the dot product of the line's normal versus the vector difference of line's point and pod's center point (pod.center - line.point). If the dot product is negative or [close to] zero, the normal points away from the pod, so it would be on the "other side" of the tile. If on the other hand the result is positive, you proceed to test collision. You can work out the specifics, but it sounds about right.

To test collision, you would reuse the projection you just did. Compare the dot product result (if positive and non-zero) to the pod's radius. If less than radius, flag collision.

The last part is moving the pod out of intersection after detecting collision. To do this, keep a list of separation vectors and add to it every time a collision is detected. To calculate the separation vector from each collision, take the normal of the line that the pod collided with and multiply it by the penetration (the difference between pod's radius and the distance to the line's point along line's normal (that would be the dot product you took earlier). Don't do any separation just yet - only store those penetration vectors.

Once you finish testing against all close-by tiles, loop through the list of penetration vectors and choose the smallest one, or use some kind of biasing algorithm (based on pod's velocity) to choose one. The biasing algorithm way would work best if your pod sometimes has velocity with a magnitude that exceeds the size of a tile in your world.

Share this comment


Link to comment
Quote:
Original post by Milkshake
Collision are certainly a lot of work. Have you considered just pre-analysing the level geometry at runtime to auto-generate the convex hulls you need to define the collision geometry?

That would avoid you having to replicate this work at the level-design stage (which is both more work and another place you can get things out of sync/wrong).


It would be nice, but I don't really know of any algorithm for generating convex hulls that would bias towards smooth horizontal top edges, which is the main reason for needing to do this as that is where the false "catches" on edges is most noticeable.

To be honest, I think SAT is probably the wrong way to be handling collisions and I should be doing something more like described below and have a more edge-based collision system.

Share this comment


Link to comment
Quote:
Original post by ValMan
I got interested in your problem after reading and thought about it. Here's what I came up with:

1. For each type of tile, store its convex hull as an array of 4 lines. In terms of storage you could do this by having a "tile template" file that specifies the bitmap the tile will display and include the convex hull info.

The best way to represent a 2D line is by using 1 point that lies on the line plus line's normal (the vector that points in the direction of line's positive halfspace). This representation is most optimal for collision detection. You can reduce the memory this will take by storing only 4 normals (2 floats for each), and then assuming that the first and the second line's point is the tile's top left corner and the third and fourth line's point is the tile's bottom right corner.

So for a simple square tile, you would store:
[0] = ( -1.0, 0.0) // left edge - normal points left (implicit point is tile top left)
[1] = ( 0.0, -1.0) // top edge - normal points up (implicit point is tile top left)
[2] = ( 1.0, 0.0) // right edge - normal points right (implicit point is tile bottom right)
[3] = ( 0.0, 1.0) // bottom edge - normal points down (implicit point is tile bottom right)

Notice that all normals are pointing "out" of the tile (away from center).

2. When doing collision detection:

For each tile that pod overlays,

Calculate 4 lines that define that tile's convex hull by using the stored normals and calculating the points based on current tile's AABB min & max (top left & bottom right). Thus, "decompressing" the hull info to prepare for collision testing.

Then for each "decompressed" hull line, check if the line faces toward the pod or away from pod. If it faces away, you can early-out of collision detection. This will prevent testing collision against the sides of tiles that face away from the pod and are not a part of the complex shape that defines pod's "immediate environment" that it's inside of.

To do this, you would probably take the dot product of the line's normal versus the vector difference of line's point and pod's center point (pod.center - line.point). If the dot product is negative or [close to] zero, the normal points away from the pod, so it would be on the "other side" of the tile. If on the other hand the result is positive, you proceed to test collision. You can work out the specifics, but it sounds about right.

To test collision, you would reuse the projection you just did. Compare the dot product result (if positive and non-zero) to the pod's radius. If less than radius, flag collision.

The last part is moving the pod out of intersection after detecting collision. To do this, keep a list of separation vectors and add to it every time a collision is detected. To calculate the separation vector from each collision, take the normal of the line that the pod collided with and multiply it by the penetration (the difference between pod's radius and the distance to the line's point along line's normal (that would be the dot product you took earlier). Don't do any separation just yet - only store those penetration vectors.

Once you finish testing against all close-by tiles, loop through the list of penetration vectors and choose the smallest one, or use some kind of biasing algorithm (based on pod's velocity) to choose one. The biasing algorithm way would work best if your pod sometimes has velocity with a magnitude that exceeds the size of a tile in your world.


I really appreciate you taking the time to post all that. I have certainly been thinking for a while that some kind of edge-based rather than hull-based system would work better.

I need to ponder your post at length and have a proper think about it.

Anyway, have a rating cookie in the meantime [smile].

Share this comment


Link to comment

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now