Character catches on "cracks" between tiles
Author
This possibly belongs in the isometric forum, but there is a strong collision detection and response component to the problem, so I figured here would be the place to go.
I have written a rigid body physics engine, and recently decided to use it to do a tile based platformer (I'm a big Gish fan).
My tile map is an array of pointers. Each pointer points to a CTile class. CTile contains the graphic to render, various tile properties, and a convex polygon representing the shape of the tile. This shape is a 32*32 square for the most basic tile.
In the collision detection code, the game looks at the 8 tiles surrounding the character, then determines what polygon to use and moves that polygon to the centre of the tile. It then checks the character against the polygon.
The problem is when the character walks over the transition between two tiles. The engine registers a collision between the character and the top, horizontal surface of the tile it is standing on (correct), and a side, vertical surface of the tile it is walking onto (incorrect). A small collision takes place between the vertical surface, slowing the character and giving it a small vertical velocity. This gives the appearance of running over uneven ground. This also happens when running down a hill made of triangular "slope" tiles, and when falling while pushed hard up against a wall of square tiles.
Is there any good way to fix this? At the moment I check if two square tiles are next to each other, and then detect collisions against one long rectangle instead of two short squares (removing the crack). However, seeing as the problem applies to every tile type, it will be a lot of work to write special case collision code for every combination of tiles (eg, the four possible corner tile angles, corner + flat, etc).
[Edited by - CIJolly on November 23, 2006 8:10:02 PM]
I've bumped into this sort of problems, but never found a 100% solution for it. one way to do it...
You can flag tiles as being 'floor' only, or 'wall only', or define what surface they should react to (the top segment, the vertical left, ...). When a collision is found, check the intersection distance along the surfaces, and push.
Another way is to have a 'step up' function for your character, that checks if he is move some amount of pixels above the offending position, he would still be intersecting or not. If he is, the step is too steep, so dont move that way.
Another way is to build a smooth surface, calculate the normals at the vertices, and use the direction of the normals for the inteersection calculation instead of the MTD.
You can flag tiles as being 'floor' only, or 'wall only', or define what surface they should react to (the top segment, the vertical left, ...). When a collision is found, check the intersection distance along the surfaces, and push.
Another way is to have a 'step up' function for your character, that checks if he is move some amount of pixels above the offending position, he would still be intersecting or not. If he is, the step is too steep, so dont move that way.
Another way is to build a smooth surface, calculate the normals at the vertices, and use the direction of the normals for the inteersection calculation instead of the MTD.
I would offer two scenarios that have worked for me in the past, and one that works in other contexts:
1. If you are using floating point numbers for tiles, it may not be the best way to represent them. If you use integers, even if they are on a smaller scale than your pixels, then you should avoid those little catches.
2. Ignore any horizontal collisions on the bottom few pixels of your character sprite. This also allows a little forgiveness if the player doesn't jump at just the right spot.
3. As long as you already have tile meta data, why not include special collision parameters, which if done correctly, can let the tiles decide how to smoothly join with their neighbors.
1. If you are using floating point numbers for tiles, it may not be the best way to represent them. If you use integers, even if they are on a smaller scale than your pixels, then you should avoid those little catches.
2. Ignore any horizontal collisions on the bottom few pixels of your character sprite. This also allows a little forgiveness if the player doesn't jump at just the right spot.
3. As long as you already have tile meta data, why not include special collision parameters, which if done correctly, can let the tiles decide how to smoothly join with their neighbors.
What type off collision detection routine are you using?
It doesn't sound like it's recursive.
Are you implementing a slide-plane in your collision detection function?
It doesn't sound like it's recursive.
Are you implementing a slide-plane in your collision detection function?
Author
Thanks for the idea guys.
The method of flagging tiles as "floor only" and "wall only" sounds promising, especially seeing as tiles could look at their neighbours and determine for themselves which edges are free.
How would I go about telling the game to ignore collisions with the vertical edge of a floor only tile?
I tried comparing the x position of the collision point with the x position of the vertical edge. If the x position was less than -(0.5 * tilewidth)+0.000001 (eg, had collided with the left most vertical edge) then the collision would be ignored. However, this also meant that 0.000001 units of the top surface ignored collisions, which created a hole that the character would stick in.
The method of flagging tiles as "floor only" and "wall only" sounds promising, especially seeing as tiles could look at their neighbours and determine for themselves which edges are free.
How would I go about telling the game to ignore collisions with the vertical edge of a floor only tile?
I tried comparing the x position of the collision point with the x position of the vertical edge. If the x position was less than -(0.5 * tilewidth)+0.000001 (eg, had collided with the left most vertical edge) then the collision would be ignored. However, this also meant that 0.000001 units of the top surface ignored collisions, which created a hole that the character would stick in.
if you decide to use flags for which 'edge' is collidable, you can try to reduce the tile collision detection to segment collision detection. However, that could cause problems if you collide with two collidable edges (say, a corner tile). But that would be simple enough to implement.
The other solution is to keep the tile-collision as it is, but if the collision response is with a forbidden edge, just ignore the collision response. That means that you can 'upgrade' edges of the tile by simply flagging them, without doing any nasty work with adding segments into the collision map, and so forth. This might be useful when you have moving platforms, or breakable pieces.
I'm putting this in the context of the SAT algorithm. The SAT will tell you which face you collided with, and then you can ignore it or something, if it is not collidable.
The other solution is to keep the tile-collision as it is, but if the collision response is with a forbidden edge, just ignore the collision response. That means that you can 'upgrade' edges of the tile by simply flagging them, without doing any nasty work with adding segments into the collision map, and so forth. This might be useful when you have moving platforms, or breakable pieces.
I'm putting this in the context of the SAT algorithm. The SAT will tell you which face you collided with, and then you can ignore it or something, if it is not collidable.
Quote:Original post by oliii
if you decide to use flags for which 'edge' is collidable, you can try to reduce the tile collision detection to segment collision detection. However, that could cause problems if you collide with two collidable edges (say, a corner tile). But that would be simple enough to implement.
I think reducing tests from polygons to edges is simple and efficient.
In a concave corner one needs only test both sides to distinguish between side, vertical or corner collisions. An object can collide with both sides and not with the corner point itself.
Regarding implementation, one could neatly flag every tile with the set of segments that can collide with diferent groups of sprites: edges (4), diagonals (2) for 45° slopes, corners to edge midpoints (8) for two other slopes, maybe more slopes, possibly half edges (corner to edge midpoint, 8) and center to edge midpoint (4), etc. For example a secret passage on a slope can be solid on the diagonal (i.e. impassable slope) for monsters and solid on the lower side (i.e. walkable and aligned with a tunnel) for the hero.
Note that these tests aren't completely independent; testing if the object is completely on a certain side of a line can rule out some tests. For example, being on one side of a diagonal excludes the two edges on the other side.
There can also be a problem doing a diagonal collision when moving between tiles. If you imagine the following diagram represents 4 tiles
A|B Blank |Wall
-+- ------+----
C|D Floor |Blank
You can get a movement from A into D which can lead to a valid movement. This can also happen on a diagaonal slope
./ Blank | Slope
/. Slope | Blank
A work around this is to have a "push up" collision face. If this tile is encountered it acts as a floor tile and pushes the collision up a tile in the Y.
In the above examples you have
Blank | Wall
------+-----
Floor | PushUp
and
Bank | Slope
-----+------
Slope| PushUp
A|B Blank |Wall
-+- ------+----
C|D Floor |Blank
You can get a movement from A into D which can lead to a valid movement. This can also happen on a diagaonal slope
./ Blank | Slope
/. Slope | Blank
A work around this is to have a "push up" collision face. If this tile is encountered it acts as a floor tile and pushes the collision up a tile in the Y.
In the above examples you have
Blank | Wall
------+-----
Floor | PushUp
and
Bank | Slope
-----+------
Slope| PushUp
Assuming all rectangular tiles, if you know which way the object is moving, when you check for collision with a tile you check for a neighbor on the side that is opposite to the direction of movement, and if there is one there you cannot collide.
So for example if you are moving right, when you check collision with a tile, if there is a tile to the left of the one you are colliding with, you cannot possibly hit the right side.
Anyways i'll give you some C++ code that does this from an old game I made.
GetIndices returns the begining and ending xy indices of the tiles that can intersect the box passed in.
So for example if you are moving right, when you check collision with a tile, if there is a tile to the left of the one you are colliding with, you cannot possibly hit the right side.
Anyways i'll give you some C++ code that does this from an old game I made.
GetIndices returns the begining and ending xy indices of the tiles that can intersect the box passed in.
bool TileMap::CollisionRect(const AABB &aabb, const Vector2 &displacement, Contact &contact){int xbeg, xend, ybeg, yend;float xdist = FLT_MAX;float ydist = FLT_MAX;bool xcollision = false, ycollision = false;int numTilesCollided = 0;AABB aabbEnd = aabb;aabbEnd.Translate(displacement.x, displacement.y);AABB aabbSwept = aabb;if(aabbEnd.left < aabb.left) aabbSwept.left = aabbEnd.left;if(aabbEnd.right > aabb.right) aabbSwept.right = aabbEnd.right;if(aabbEnd.top < aabb.top) aabbSwept.top = aabbEnd.top;if(aabbEnd.bottom > aabb.bottom) aabbSwept.bottom = aabbEnd.bottom;GetIndices(aabbSwept, xbeg, xend, ybeg, yend);for (int x = xbeg; x < xend; x++){ for (int y = ybeg; y < yend; y++) { AABB aabbTile; aabbTile = Tile(x,y).GetAABB(); if ( Tile(x, y).blocked ) { if(displacement.y > 0 && !Tile(x,y-1).blocked) { float ydist2 = aabbTile.top - aabb.bottom; if(fabs(ydist2) < fabs(ydist)) { ydist = ydist2; ycollision = true; } } else if(displacement.y < 0 && !Tile(x,y+1).blocked) { float ydist2 = aabbTile.bottom - aabb.top; if(fabs(ydist2) < fabs(ydist)) { ydist = ydist2; ycollision = true; } } if(displacement.x > 0 && !Tile(x-1,y).blocked) { float xdist2 = aabbTile.left - aabb.right; if(fabs(xdist2) < fabs(xdist)) { xdist = xdist2; xcollision = true; } } else if(displacement.x < 0 && !Tile(x+1,y).blocked) { float xdist2 = aabbTile.right - aabb.left; if(fabs(xdist2) < fabs(xdist)) { xdist = xdist2; xcollision = true; } } } }}if(!xcollision && !ycollision) return false;Vector2 push = Vector2(0,0);float xtime = xdist / displacement.x;float ytime = ydist / displacement.y;if(xtime > 0.0f && xtime < 1.0f){ if(displacement.x < 0.0f) push.x = displacement.x - xdist - SEPERATION_EPSILON; else push.x = displacement.x - xdist + SEPERATION_EPSILON;}if(ytime > 0.0f && ytime < 1.0f){ if(displacement.y < 0.0f) push.y = displacement.y - ydist - SEPERATION_EPSILON; else push.y = displacement.y - ydist + SEPERATION_EPSILON;}contact.normal = push;contact.depth = Vec2Length(push);contact.normal /= contact.depth;return true;}This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
