C#: 2D sub-Tile Line intersection

Question

Hi,
I have some problems getting an algorithm for my game to work and hope someone here can help me. Google didn't seem to be a good help as most solutions just work for full tiles.

In the game units can occupy different positions inside a tile, i.e. they can be in the upper left corner, center, bottom right, ... position of tile (2/3), i.e. (2.2/3.1), (2.5/3.5), (2.8/3.9).

If they move from position (2.2/3.1) to (5.7/4.1) i require a check to see if there is an obstacle in the path.

My current algorithm is:

1. Starting from (2.2/3.1)
2. Calculate the angle of the movement (i.e. 70 degree)
3. Move 0.1 steps in that direction
4. Check which tile i'm on (floor(p.X)/floor(p.Y))
5. Repeat from 2

This algorithm works but to me it doesn't look very efficient as an obstacle can be only a full tile, not a part of a tile (units don't collide). If i increase the step size i begin to miss tiles that are only crossed slightly (i.e. you only cross the lowest left corner). Even with a step size of 0.1 it's still possible to miss an obstacle.

I tried to find a solution to take the sub map (all tiles with the corners (floor(start.X)/floor(start.Y)) and (ceil(start.X)/ceil(start.Y)), move through every tile and check mathmatically if it gets crossed. Sadly i seem to lack the required math knowledge for this check.

My last idea was to take all 4 borders of a tile as a line and do line-intersection but that seems to be slower than my original approach.

Any hints?

Thanks.

Answer 1

Instead of tracing the path by stepping along the line - you want to jump right to the next possible tile (the border). This can be calculated fairly simply. I will use your sample numbers above.

1. Calculate the line eqn (y= .286x + 2.471)
2. You are starting on tile 2,3 and moving towards tile 5,4. So calculate the y value when x goes to 3 (the border to the tile immediately to the right). It is 3.329.
3. Then calculate the x value when y goes to 4 (the border to the tile immediately above). It is 5.346.
4. Starting at 2,3 and moving right gets to 3,3.329. Moving up gets to 5.346,4. You intersect on the right(moving 2 -> 3 on x doesn't move a tile on y). You don't intersect above until you are on tile 5 in the x.
5. The tile calculated in 4 becomes your new comparison (3,3). Repeat from step 2.

This process only incurs one calculation per tile moved (regardless of your precision or how big the tiles are) and is exact. Note that the values calculated can be stored and reused instead of blindly calculating both intersections over and over. In the above we know (step 4) that we don't move up a tile until x=5. So the entire path can be inferred without another calculation (2,3 -> 3,3 -> 4,3 -> 5,3 -> 5,4).

It is also possible to precalculate all the transistions instead of doing them stepwise although this would only be beneficial if you always need the entire path (you don't since you want to stop processing once you find an obstacle).

Two caveats. Be careful about signs and which way the line is going - many a bug happen by not paying close attention to negative slopes. Also, using reals you almost never will cross diagonally (two borders at once) but you should be aware of it (handle it in the code) just in case.

There is a name for this method but I can't remember it off the top of my head. I believe it might be from Game Programming Gems series but maybe someone else can provide a better reference.