Archive for September, 2010

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.


Read Full Post »

Bresenham’s line algorithm is a fairly simple algorithm that takes two tile positions in a grid and returns a list of all tile positions that a line drawn between the two positions touches. It is well described along with easy-to-read pseudo code here.

When is this useful? According to what I’ve read, this algorithm and variations of it are useful in graphics programs. I’m sure you’ve seen programs that let you draw icons in a zoomed-in view. While you draw lines it just colors in boxes. It is likely this algorithm was used for that. However, I use this algorithm for game-related purposes. The last time I used it was probably 5 or 6 years ago in a Flash pool game. I set up a grid with an arbitrary tile size on the pool table (that the user can’t see). Every frame I determined in memory which tiles a ball covered as it moved (assuming no collisions). Then I would only run collision detection against balls that touched the same tiles. This let me cut down on the number of collision checks per frame.

I’m coming back to this algorithm again now because of a first person shooter game I’m working on. I hope to create a blog post on how the algorithm is used in that game (on the server) to keep the collision detection calculations to a minimum.

I created a Flash demo of Bresenham’s line algorithm that you can play with by clicking on the image. Or you can download the source files here.

click to view example (drag dots around)

Read Full Post »

This post is slightly related to my previous post, Referencing Classes Outside of Your Project in Visual Studio. What I describe here for Unity will also work for Visual Studio. I am very new to Unity development. By new, I mean that I’ve probably only invested about one day into it so far. That’s my disclaimer in case there is a vastly easier way to this.

Coming from a ActionScript/Flash background I’m used to being able to just add classpaths to a project that point to any arbitrary locations on my hard drive to reference code. My project code would generally be located right there with the project, but utility code that is used across many projects would be located in another location.

In Unity (as far as I can tell) the only classes that you can reference are those that exist within the [project]Assets/Scripts directory, or sub directory. I haven’t discovered anything that is similar to adding a classpath in Flash. Also, while Visual Studio let’s you add an existing item ‘as link’ (see this post) Unity doesn’t appear to have that feature.

So what is the solution? A solution in Windows Vista or Windows 7 is to use symbolic links to add the directories that contain the source files to your [project]Assets/Scripts directory. If you create a symbolic link to a directory then for all intents and purposes that directory is seen as existing in two places (obviously there really is only one version of it though).

You can create a symbolic link in a directory by using the command prompt, navigating to that directory, and then running a ‘mklink’ command. If you just run ‘mklink’ by itself you’ll see the options:

The option you want to use is /D for creating a link to a directory. Here is an example usage:

‘my_new_dir_name’ is the name that will show up in the current location when this command is run. ‘path_to_real_dir’ is the absolute path to the real directory you are linking to.

Read Full Post »

That title is a mouthful, but I couldn’t think of how to else to phrase it. Coming from a pure Flash development background I’m new to C# and Visual Studio/Web Developer. And there was something about Visual Studio that was driving me nuts for the first few weeks. In Flash I’m used to being able to have a project which would contain source files and may reference SWCs (compiled code like DLLs). And I’m used to being to reference source code from anywhere on my computer that is outside of my project by simply adding that location as a classpath. This would allow me to work on my current project, but still suck in the source code to other APIs and utilities as a code so that I can work on them all at the same time.

In Visual Studio I wasn’t able to figure out how to reference code that lives in some arbitrary location outside of my project. Doing this is actually pretty easy, but it was weeks before someone filled me in. Here is what you do (see images below also) :

  • Right-click on your project (or on a directory in your project) and choose Add > Existing Item
  • Then browse to find one or more source files, select them and….
  • In the bottom right-hand part of the dialog you’ll see an Add button, but it has a little drop-down next to it. Click that and choose Add as Link.

If you do the above you’ll be able to edit and reference the added code without the classes actually being copied into your application!

Read Full Post »