Generate a 2D distance grid in one pass

Question

I'm trying to generate a 2D grid, for use in navigation, where each grid point holds the distance to the nearest obstacle (such as impassable terrain, or a constructed building). So for example, a grid point containing an obstacle would be 0, the grid point next to it would be 1, the next one further away would be 2, etc.

So far I've been able to accomplish this using multiple passes. Each pass, for every grid point, I take the lowest value from all neighbors, and add one. If I want to measure out to a max distance of, say, 10 grid points, I have to make 10 passes, slowly incrementing the most distance grid points.

My question is, is there a way to generate this sort of grid in just a single pass? This grid will be periodically updated during gameplay, and could be very large, so I don't want to be looping over it multiple times if I don't have to.

Answer 1

You can use BFS to accomplish this exactly. You connect all obstacles as nodes (vertices) to the source node. Then simply connect each grid square to the it's neighbors.

You don't actually have to do the connecting. You could simply start with all obstacles in the Queue and keep adding neighbors.

Breadth-First-Search

Time complexity is O ( V + E) so in this case, grid squares plus grid edged = grid squares * 5.

Pseudo code:

  // First loop over array2d
 // and register that the distance on tiles with obstacles is 0
  procedure GridBfs(array2d, obstacles)
      create a queue Q
      create a set S //this is a 2d array of areas visited by the algorithm
      enqueue obstacles onto Q
      add obstacles to S
      while Q is not empty loop
         t ← Q.dequeue()
         for all neighbors n of t loop
            if n is not in S then
               add n to S
               enqueue n onto Q
               n->distance = t->distance + 1;
            end if
         end loop
     end loop
     return none
 end BFS

This is based on the original BFS code from wikipedia. To get the neighbors, simply look above, beloow and to the left and right of t and you'll get all neighboring tiles, represented each by n in the algorithm.

Answer 2

Yes, as Arthur Wulf White writes, Breadth First Search is what you want. I wrote a quick & dirty interactive demo showing how BFS expands out from each of your obstacles to assign distances.