Casting Rays in Roguelikes

I’ve gotten back into building my rogue-like again. It’s good to be spending a little bit each day on the various parts of it. My main focus recently has been on implementing the fog of war / vision such since I’ve always found those to be the funnest parts of a rogue-like.

Raycasting in DoomRL

Most rogue-likes do a field of vision that has a maximum range and also allows you to into corridors. One of the ways this is implemented is using Ray Casting. The way this works is you choose a point (often the player) and cast rays from their position in all directions. When a ray hits an opaque object the ray stops, otherwise we mark that position on the map as seeable and keep casting the ray. Typically we’ll cast these rays in the various octants because we want our Field of Vision to be around the player.

My initial implementation was going to use Bresenham’s line algorithm but I wasn’t really getting any results and it was sort of tricky to debug (hint, I was getting stuck in loops). I hit up roguebasin to grab one of the Ray Casting algorithms that people had decided to share. One thing that really stood out for me was that it had a very old-school programmer feel to it. Maybe I’m bad at math, but the code was somewhat tricky to understand. I’m also not sure if media wiki nommed up some mathematical symbols because there were some really important mathematical functions missing. I want to really understand what is going on, and this is even more important since I’m implementing the game in Go not C, so I can’t even copypasta this. Understanding what is going on is key or I’d just end up with magic in my codebase and I hate magic.

After a bit of confusion and head-scratching I was able to get my implementation of the algorithm is working alright. There were a few parts in the roguebasin example that I skipped, mainly because I don’t think they were necessary and couldn’t actually understand what was going on. Considering the results I have, I am pretty happy to have avoided implementing that code.

My implementation of raycasting does make a few assumptions:

  1. The raycaster is initialized with the dungeon/maze/map
  2. The maze is what is responsible for fetching the tiles
  3. Tiles provide the information regarding their opacity

The meat of the algorithm is as follows (Note: I’ve reordered the code such that you can read it top to bottom):

func (r *Raycaster) flushOverlay() {
    for x := range r.overlay {
        for y := range r.overlay[x] {
            r.overlay[x][y] = false
        }
    }
}

var OCTANT_CALCULATIONS map[int][]int = map[int][]int{
    0:  {1, 1, 1, 0},
    1:  {1, -1, 1, 0},
    2:  {-1, 1, 1, 0},
    3:  {-1, -1, 1, 0},
    4:  {1, 1, 0, 1},
    5:  {1, -1, 0, 1},
    6:  {-1, 1, 0, 1},
    7:  {-1, -1, 0, 1},
    8:  {1, 0, 1, 0},
    9:  {0, 1, 1, 0},
    10: {-1, 0, 0, 1},
    11: {0, -1, 0, 1},
}

func (r *Raycaster) calculateFieldOfView(x, y, intensity int) {
    for _, values := range OCTANT_CALCULATIONS {
        sx, sy, dx, dy := values[0], values[1], values[2], values[3]
        r.doOctant(x, y, intensity, sx, sy, dx, dy)
    }
}

// Algorithm from Rogue Basin
// http://www.roguebasin.com/index.php?title=Ray-Tracing_Field-Of-View_Demo
func (r *Raycaster) doOctant(x, y, radius, sx, sy, dx, dy int) {
    for i := 0; i != radius; i++ {
        var lastTile *dungeon.Tile
        var lastAdjacentTile *dungeon.Tile
        for j := 0; j != radius; j++ {
            tileX := x + (sx * i)
            tileY := y + (sy * j)
            if tileX >= r.maze.Width || tileX < 0 || tileY >= r.maze.Height || tileY < 0 {
                break
            }
            tile := r.maze.FetchTile(tileX, tileY)

            adjacentTile := r.maze.FetchTile(tileX-(sx*dx), tileY-(sy*dy))
            if lastTile != nil {
                if lastTile.Name != "wall" {
                    r.overlay[tileX][tileY] = true
                } else {
                    if tileX <= 0 {
                        break
                    }

                    tileIsWall := tile != nil && tile.Name == "wall"
                    adjacentTileIsClear := adjacentTile != nil && adjacentTile.Name != "wall"
                    lastAdjacentTileIsClear := lastAdjacentTile != nil && lastAdjacentTile.Name != "wall"

                    if tileIsWall && adjacentTileIsClear && lastAdjacentTileIsClear {
                        r.overlay[tileX][tileY] = true
                    } else {
                        break
                    }
                }
            }
            lastTile = tile
            lastAdjacentTile = adjacentTile
        }
    }
}

// The public interface is the following
func (r *Raycaster) CastRays(x, y, intensity int) {
    r.flushOverlay()
    r.calculateFieldOfView(x, y, intensity)
}

func (r *Raycaster) IsLighting(x, y int) bool {
    return r.overlay[x][y]
}

Using the ray-caster is fairly straight-forward, I’m going to assume that the maze is already initialized:

raycaster := MakeRaycaster(maze)
raycaster := CastRays(5, 10, 10)

The result of using this in my game is the following.

Raycasting in Eugor

There are a few little bugs that need to be fixed, those primarily being able to see through walls and some walls being hidden when looking directly at them.

As always, you can peruse the source on github at your own pleasure.