You might want to read my first post on the Bresenham Line Algorithm.
The setup
I’m currently building a shooter game. There are lots of walls and at any time there may be lots of bullets. For the sake of simplicity, think of this game as 2D (with a top-down view). For collision detection purposes the walls have no thickness. The walls can be visualized as thin lines drawn anywhere at any angle. This does not restrict the position or movement of anything based on tiles.
Since there are bullets and walls I had to figure out the best approach for bullet-wall collision detection. The basic approach is easy to understand.
- Imagine a line that a bullet would draw as it moves from one time step (or frame) to the next.
- Take this line and do a line-to-line collision check against all of the walls.
- Collect a list of all collision points that were found.
- Do a distance check against the position of the bullet last time step (or frame) against the collision points found, and take the smallest distance as the true collision.
The above works great. However, the bigger the map and the more bullets on-screen the more time it takes to perform the collision detection. What I wanted to do was to find a way to run the collision check steps just described above, but instead of running it against all walls on the map, just run it against a small subset of the walls – the ones most likely to have been hit. Essentially, I wanted to find a way to cut down from what could be thousands of checks to a small handful of checks.
Initial attempt at culling
Imagine for a moment that there are tiles of an arbitrary size used to cover the entire map. Nothing is restricted by these tiles, and the user cannot see the tiles, they are just used as a convenience for us to cull walls. First we want to pre-process the map:
- When the map initializes
- Run a Bresenham line search against the grid with the two points that make up every wall.
- For every tile that a wall touches, push a reference to that wall into an array stored in that tile.
Then for a specific bullet that is in motion:
- Take the line that the bullet made between the last time step (or frame) and this one, and run a Bresenham line search against the grid.
- Loop through every tile that is returned and check to see if any walls are referenced within it.
- Use this collection of walls with the collision detection described at the top of this post.
The problem
Bresenham’s line algorithm is intended to give a best approximation of which tiles a line drawn between the center of any two tiles touches. This presents a problem for us because the line a bullet makes can originate and end at any point within a tile. In the image below you can see that Bresenham’s line algorithm gives us most of the tiles that the bullet travels through, but not all of them.
The fix
To fix the above problem we just add to what the search does. Instead of doing the search one time, we do it 5 times. Assume that the line originates on tile (x1, y1) and ends on tile (x2, y2). We run this search against:
- (x1, y1), (x2, y2)
- (x1-1, y1), (x2-1, y2)
- (x1+1, y1), (x2+1, y2)
- (x1, y1-1), (x2, y2-1)
- (x1, y1+1), (x2, y2+1)
Run all of the searches listed above and then filter the results by:
- Removing any tile duplicates.
- Removing any tile that lies beyond the bounding box made up of (x1, y1) , (x2,y2)
And then sort the results based on tiles that would be touched by the line moving from the originating tile to the destination tile (see source code for sorting logic). The end result is a list of tiles that could be touched by a line drawn from any point within the starting and ending tiles. In many cases you’ll have extra tiles that the line will not have passed through. That is fine. The benefits far outweigh the check against an excess tile.
It seems like there is a lot going on to perform the search and sort the results. That is because there is. But the search is very fast. Only integers are used, no trig functions used, and there are no square roots. Running this search against a bullet that crosses a large map in a single frame is might take 2 milliseconds. And you are left with a small subset of all the walls in the map to run your collision math against.
There is another benefit here I didn’t mention yet, and you can see by the numbered tiles above. The tiles are returned in order of the possibility of them being touched by the line. That means that you can run the actual collision detection against the walls found within a tile as you loop through the tiles. If you find a collision within a tile – you can stop processing any more tiles. You still have to finish processing the current tile because there may be more than one wall in that tile, and the walls within the tile are unordered. So that is a nice advantage! If you have a line that crosses an entire map, it could still have dozens or hundreds of tiles returned. But you might only have to process a few of them.
Download source
Final notes – over-drawing
I just wanted to point out one final thing. As mentioned above, this approach can return more tiles that the line actually passes through. But it doesn’t always. Vertical lines and horizontal lines return the exact tiles touched, and 45 degree angles return the most excess.
Jobe Makar's Blog 
