Bresenham's or Raycasting for Vision

Two similar algorithms are commonly used to check for line of sight in tile-based games. Which should you use?

Common to Roguelikes and other tile-based games is the need for a visibility system of some kind. Only tiles that can be seen from where the player is stood are displayed, or all the tiles are visible but ranged attacks can only hit tiles that are not blocked from the caster's view. Either way you need a line of sight algorithm.

The Line

There's several ways to go about finding if a tile is visible, but for the purposes of this we'll stick with the line method. We simply draw a line from the player's position to the place we're interested in. If that line hits a wall or other vision blocking element then we know the player cannot see there. Simple.

But a line is a geometric construct and isn't immediately compatible with the grid squares of our game map. We need to convert that line into a series of tile positions that we can then check for vision-blocking. If none of those tiles block vision then we know the player can see along the line.

Rival Algorithms

This is where Bresenham's line algorithm comes in. It appears to do exactly what we want, turning the geometric concept of a line into a series of squares on a regular grid (technically it gives points that can be represented as squares). But it was designed to nicely display a line to human eyes via a computer screen. It is not intended to indicate what locations a line passes through and it's generally that property we want for our line of sight test.

We'll be putting it up against simple raycasting. Raycasting on a grid finds every square tile that a given geometric line will pass through.

Bresenham's
Raycast

Click and drag the line end-points to try different arrangements. Bresenham's line algorithm is compared to a standard raycast. Note that my raycast algorithm allows diagonal movement if the line passes perfectly through a corner.

Notice how Bresenham often allows the geometric line (drawn over the tiles in blue) to pass through some cells without marking them. That means your line of sight test would be able to see through the corners of some walls. But let's actually try it out.

Visibility

With our line algorithms ready, we can use them to determine if each tile is visible from a given position. We simply step along the grid cells given by each line algorithm and if we hit a wall before reaching the target we know it is out of sight.

Bresenham's
Raycast

You can drag the blue player around and observe what areas would be visible or hidden by the green walls.

Differences

Both algoritms give results that look generally correct. Bresenham's tends to be more generous with what is considered visible. That generosity makes sense with what we know about the line being able to pass through some cells without marking them. In a few specific situations Bresenham's shows itself to not be symmetrical - that is the player can see a tile which wouldn't be able to see the player (or vice versa). That asymmetry is eliminated in the raycast version.

Conclusions

While making these demos I've changed my mind several times over which algorithm I prefer. I tend to prefer Bresenham's more generous vision areas. But I find the asymmetry worrying as a source of exploits in a game. More generally I prefer to use an algorithm where its results are more understandable. The raycast returns every tile that a geometric line passes through, while Bresenham's returns a set of tiles that looks right but isn't as easily defined.

It's also worth considering a variation on the raycast that marks a tile as visible if any of its corners can be reached by the ray, that would make for larger visible areas while still having a basis in physical reality. The roguelike community has created several other algorithms with a range of performance, physical correctness, and usefulness for game mechanics.

What algorithm you use is up to you. Like many seemingly technical aspects of a game, this ends up being a design decision.

Source

I avoided explaining the internals of how the two algorithms work as that's outside the scope of this article. You can find many implementations online, and the full Javascript source for the demos is available. The two line algorithms are found in the makeRay and makeBresenham functions. When performing vision checks there's room for performance optimisation by ending a line check early when it's sufficiently similar to one that has already failed.

Comments are plaintext only and may be ruthlessly moderated.