Roguelike Field of View With Shadowcasting in Haskell

Most hobby roguelikes I review on weekends have the same visible flaw within the first room. Stand next to a pillar and look past it, and the shadow behind the pillar is lumpy: a tile that should be hidden is lit, or a tile in plain sight stays dark. Walk one step sideways and the pattern jumps. Players notice this immediately, even if they cannot name it, and it makes the dungeon feel unreliable in a genre where knowing exactly what you can see decides whether you live.

The cause is almost always the field of view algorithm. Usually it is a ray casting loop written in an afternoon. The fix is a well-studied algorithm called recursive shadowcasting, and it happens to translate into Haskell unusually cleanly, with one detail, exact slopes, that Haskell makes trivial and most languages make awkward.

Why naive ray casting looks wrong

The obvious approach is to draw a line from the player to every tile on the edge of the visible radius, using Bresenham's line algorithm, and mark tiles visible until the line hits a wall. It is easy to write and it is wrong in two ways.

First, rays fan out. Near the player, many rays pass through each tile. Far away, rays spread apart and some tiles fall between them, so you get dark specks in open rooms. You can cast more rays, but that only shrinks the specks.

Second, Bresenham lines are not symmetric around corners. A line that grazes the corner of a pillar might pass on one side going one way and the other side coming back. That produces the lumpy shadows I described, and worse, it can mean a monster sees you while you cannot see it.

How shadowcasting works instead

Recursive shadowcasting was described by Björn Bergström in a RogueBasin article in 2001, and it remains the default choice in a lot of roguelike code. Rather than casting rays, it scans the map row by row outward from the player and keeps track of which range of angles is still unblocked.

The map around the player is split into eight octants, triangular slices of 45 degrees each. Within one octant, the algorithm walks out one row at a time. For each row, it knows a start slope and an end slope, the edges of the region still visible. Every tile in that row whose centre falls between the slopes gets marked visible. When the scan meets a wall, it does two things: it recurses into the next row with the slope range narrowed to stop at that wall, and it continues past the wall with a new start slope once it finds an open tile again. Shadows are simply the slope ranges that never get scanned.

Because it visits each tile at most once per octant and never casts redundant rays, it is fast, and because it works in continuous slopes rather than discrete lines, the shadows are smooth.

Writing it in Haskell

The shape of the function falls out naturally. Visibility depends on the map, the player's position and the radius, and produces a set of positions, so the signature I used is roughly fov :: (Pos -> Bool) -> Int -> Pos -> Set Pos. The first argument answers "does this tile block light?" Passing a function rather than a concrete map type means the algorithm works with any map representation and is trivial to test with a hand-written blocking function.

Eight octants, one implementation

Rather than writing eight versions of the scan, I wrote the scan once for a single canonical octant and defined the eight octants as coordinate transforms, functions of type (Int, Int) -> (Int, Int) that flip and swap axes. The scan works in local coordinates; each transform maps them back to the real map. In an imperative language this is often done with a table of multipliers. In Haskell it is just a list of eight small functions, and mapping the scan over that list gives the whole field of view.

Exact slopes with Rational

This is the part I most want to recommend. Slopes in shadowcasting are ratios like 3/7 or 5/11, and the algorithm compares them constantly to decide whether a tile centre lies inside the visible range. Using floating point, a tile exactly on the boundary may land on either side depending on rounding, and you get rare flickering tiles that are maddening to reproduce.

Haskell's Data.Ratio gives you exact rational numbers out of the box. I defined slopes as Rational and the boundary problem vanished. Every comparison is exact, so the same map and position always produce the same field of view, byte for byte. That also made property tests possible, which I come back to below.

The laziness trap

My first version accumulated visible tiles with foldl over rows, inserting into a Set. On a radius of 8 it was instant. When I tried radius 60 on an open cave map, memory use climbed sharply, because foldl built a long chain of unevaluated insertions before forcing any of them. Switching to foldl' from Data.List fixed it immediately. We have a longer explanation of why this happens in lazy evaluation in Haskell; field of view code is a textbook case.

For very large radii or real-time games, a mutable unboxed array inside ST is faster than a Set. For a turn-based roguelike with a radius under 20, the pure version computes in well under a millisecond in my tests, and I would not bother optimising further.

The symmetry problem shadowcasting still has

Classic recursive shadowcasting is not perfectly symmetric. There are configurations, usually involving diagonal walls, where tile A can see tile B but B cannot see A. In a game where monsters use the same field of view as the player, that asymmetry means a monster can attack from a spot the player cannot see.

Albert Ford published a variant called symmetric shadowcasting that addresses this by changing which tiles count as visible at the edges of a slope range. I have not ported it yet, so I cannot vouch for its performance in Haskell, but if your game has ranged enemies, it is worth reading before you commit.

A property test catches this whole class of bug quickly. With QuickCheck, I generate random small maps and two random open positions, and assert that if B is in the field of view from A, then A is in the field of view from B. My classic implementation fails this property within a few hundred cases. That failure is useful: it tells you precisely what kind of game you are building.

Where to start this week

Write the transform list for the eight octants first, and test it on its own: applying each transform to a single offset should produce eight distinct positions around the player. Then implement the scan for one octant with Rational slopes, check it against a hand-drawn map with one pillar, and only then combine the octants. If you are also generating the dungeons themselves, our piece on procedural generation pairs well with this, and there is more in the games section.