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.

  • Can't you just calculate the distance to the obstacle for each grid point? Instead of setting the grid points based off of the grid point next to them, just use the pythagorean theorem to calculate the distance. There are also breadth first search algorithms you could use (in a backwards fashion). Further, with a grid already in place, you could easily implement some kind of spatial partitioning to quickly find the nearest obstacle and get the distance to it. – MichaelHouse Apr 13 '14 at 19:13
  • There would be a large number of "obstacle" grid points, such as impassable terrain, or constructed buildings. Any grid point could potentially become an obstacle. I've updated my question to hopefully make this clearer. – Nairou Apr 13 '14 at 19:33
  • Can you clarify what you mean by "a single pass"? – MichaelHouse Apr 13 '14 at 19:36
  • By single pass, I mean modifying each point on the grid only once. Right now I make multiple passes, incrementing each point on the grid to the correct distance value. – Nairou Apr 13 '14 at 19:38
  • I think BFS would work here. Calculating distance means you alredy know where the closest obstacle is which you may or may not. – wolfdawn Apr 13 '14 at 20:29
up vote 2 down vote accepted

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.

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.

Screenshot of breadth first search demo

  • Very nice demo and article, thanks! – Nairou Apr 15 '14 at 4:26

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.