# How to check for collisions in "diagonal" tiles?

I want to create a tiled map in the following scheme:

The player should be able to walk on the blue line (street). Now, what is the best way to solve collision detection in this case? For example, in the case of tiles C1 and C2: If I make them walkable, then the player could also move in on those black parts of the tiles that should not be walkable.

On the other hand, if I make both C1 and C2 blocked, then the player would not be able to walk on these tiles (and therefore on the street) at all.

Any best practices?
Thanks.

• Why not allow the pathfinder to find a path between D1 and B even if C1 and C2 are blocked? Jul 7 '14 at 21:18
• Well, if C1 and C2 are blocked, then I don't want the player to move between them. The thing is: in my example these tiles are not fully blocked, they can be traversed. Jul 7 '14 at 21:45
• You should use the 'right' tile size, in this case your tiles should be half as big, this way you'll have far less special cases to handle (4 tiles would be enough for your slope i guess). Jul 16 '14 at 10:14

## 2 Answers

Several possibilities :

1) use small collision maps for each different tile. It does not need to be very precise, small maps like 8x8 might be enough (depending what you need). You can do some interpolation to smooth it out.

Here is an example :

Instead of using only occupied / non-occupied state for the collision map, you might also consider using other states : half-full to bottom left, half-full top right, etc..

The blue line in example you give might be reworked a little bit to fit perfectly with that pattern.

Check this answer : How did LoZ: A Link to the Past handle sub-tile collisions?

2) do not use collision maps, but create specific code that will check for collisions : first, it finds out in which tile player is and depending that, it performs some simple math to check for collision, with code specific to each tile. It probably easy to do because most of the tiles you show have vertical, horizontal or diagonal patterns (or a combination).

Some pseudo code :

currentTile = //find out on which tile player is, depending position
tileType = tileMap[currentTile];

tileX = //convert player position to local position inside tile (between 0.0 and 1.0)
tileY = //

switch(tileType)
{
case A1:
collided = (tileY > 0.25) && (tileY < 0.75);
break;

case A2:
collided = (tileX > 0.25) && (tileX < 0.75);
break;

case B:
//... same as A1 but need to checks diagonally
break;
}


Treat the tilemap as purely graphical data, and use some other structure to resolve collisions.

In your case, you can define the boundaries of your roads using edges (segments). You have a vector (line) representing the player's movement, and you want to know if this line will intersect some wall during this timestep. Since these walls are represented by edges, the problem breaks down into line-segment intersection. Pseudocode:

for(edge in walls) {
intersectionPoint = intersect(movement, edge);
relative = intersectionPoint - playerPos;

//Ensure that we intersected a wall in the right direction,
// and that we hit the wall on this frame
if(sign(relative.x) == sign(movement.x) &&
sign(relative.y) == sign(movement.y) &&
magnitude(relative) < playerSpeed) {
//hit wall
}
}


In the above code, intersect() finds the point where a line and a segment intersect, sign() returns the sign of a scalar, and magnitude() returns the magnitude of a vector. The part where you intersect the movement vector with every wall can be optimized with a broad-phase approach, but doing it for every edge is often fast enough (it was for me).

The harder part with this method is figuring out how to define the edges themselves. It's kind of ungainly to have to define these edges for every level (road) you create, but it's often the easiest solution. If you already have the road data stored in some way, you could probably construct the edges from the angles and widths of the roads.

This method will also work with shapes other than straight lines. You can abstract the intersect() method to support, for example, arcs, and store generic shapes in the walls data structure.