Illumination

For some reason, I've found myself implementing bits of a text-mode rogue-like game. In a nutshell, this is a turn-based kind of game where the player moves on a grid which usually depicts a dungeon or a cave. Some cells of that grid/map might contain a wall/rock, in which case the player cannot see or walk through them. All this is rather straightforward to implement, but the computation of what the player sees deserves some attention.

I started thinking of casting rays, but only found clumsy, costly solutions. So I did a little research. Some people (including crawl) actually developed algorithms along these lines for computing what is called a permissive field of view:

A destination square is visible from a source square if there is any unobstructed line from some point in the source square to some point in the destination square.

It's apparently a modern notion of field of view, that has one advantage over older techniques: it ensures symmetry, i.e., if I can see you, you can see me.

The same article on roguebasin points to several algorithms, including the one implemented in crawl. They all seemed unsatisfyingly complicated to me. I eventually came up with a different idea that looks good and ensures symmetry. It might have been considered already and discarded for some of its funny aspects, but those are interested to look at.

The basic idea is to forget about those lines. We are talking about a discrete universe, let's try to make its physics discrete too. Geometrical optics is only a convenient metaphor, that is justified by more elementary principles such as Fermat's:

The path taken between two points of a ray of light is the path that can be traversed in the least time.

This is in fact a definition of a ray of light that we can take literally in our discrete rogue world:

A cell is visible from another if one of the shortest paths between them is unobstructed.

Let's look at a simple example. For now, suppose that the movements are only allowed along the axis (no diagonals):

.# 
@#y
.x.

The player is represented by @, and # are walls/rocks. The cell marked y is not visible: it is at distance 2, there is only one path of length 2 that connects it to the player but it is obstructed. Cell x is also at distance 2, but it is visible since one of the two paths of length 2 that connects it to the player is not obstructed.

A funny thing happens when you consider the traditional rogue movements which include diagonals: cell y becomes visible! Indeed, the light can take a path of length 2 through x.

I would tend to adopt rules where the topology is the same for players and light. Either embrace the diagonal movements but accept the surprising effect on light, or remove them both for the light and the player. I chose the less experimental way for now. But it is also possible to use different topologies for the two entities.

To finish, I will give the last reason why I like this solution: the code is stupid simple. Assuming that the radius of the field of view will always be within a fixed bound, we can compute once and for all the map of shortest paths with their dependencies.

(** The maps will be used to associate
  * the coordinates of the destination of a path
  * to the lists of the coordinates of possible previous step
  * in shortest paths leading to that destination. *)
module M = Map.Make (struct type t = int*int let compare = compare end)

let neighbors (x,y) =
  [ x-1,y ;
    x,y-1 ;
    x+1,y ;
    x,y+1 ]

let shortest_paths max =
  (** Map of distances to the center of the matrix. *)
  let dist = Array.make_matrix (2*max+1) (2*max+1) max_int in
  (** At each step we compute the shortests paths to cells
    * at distance [d=n+1] from those for distance [n]. *)
  let step d paths_n =
    M.fold
      (fun (x,y) _ m ->
         List.fold_left
           (fun m (x',y') ->
              if dist.(max+x').(max+y') < d then
                (* Seen in a previous iteration. *)
                m
              else if dist.(max+x').(max+y') = d then
                (* We already found a path of length n+1,
                 * but we need to keep track of this new one too. *)
                M.add (x',y') ((x,y)::M.find (x',y') m) m
              else begin
                (* First time we see it: first shortest path. *)
                dist.(max+x').(max+y') <- d ;
                M.add (x',y') [x,y] m
              end)
           m
           (neighbors (x,y)))
      paths_n
      M.empty
  in
  let rec aux d frontiers =
    if d=max then frontiers else
      aux (d+1) (step d (List.hd frontiers) :: frontiers)
  in
    List.rev (aux 1 [M.add (0,0) [] M.empty])

Then, it only remains to parse dependencies:

(** Takes a radius (d) and returns a field of view function
  * for that radius. *)
let fov d =
  let frontiers = shortest_paths d in
    (* The field of view function,
     * which takes a function and calls it on each visible cell.
     * The function [f] returns whether a cell is transparent or not. *)
    fun f ->
      let transparent = Array.make_matrix (2*d+1) (2*d+1) false in
        transparent.(d).(d) <- true ;
        List.iter
          (fun frontier ->
             M.iter
               (fun (x',y') deps ->
                  if
                    List.exists (fun (x,y) -> transparent.(d+x).(d+y)) deps
                  then
                    transparent.(d+x').(d+y') <- f x' y')
               frontier)
          (List.tl frontiers)

Hurray to (impure) functional programming! I leave it to you to glue this to whatever testing code you want. I'll finish with "screenshots".

Without diagonal moves, notice that it is possible to see through a wall on a diagonal:

              .
       .      ..
      ..    ##...
     #.. ###...# .
     #..#......##.#
     #.....@......#
     #...##........
     ...#.........
      ###........
        #.......
        ..####.
         .

With diagonal moves, we now have shadows along the diagonals, but we can see around walls placed along the axis:

        ..#..#...
         .......
   .######.....
   ...........
   .##.......
    #.......#
    #.......####   #
    #..........## ..
   .##..##.@....#...
   #...  ##...##..##
   ###    .......###
         ...........
        ............
       .............
      ###...........
        ............
       .##.####.....