Building a distance map from collision data on a 2d grid

user_7518617 0
Viewed 62

As the title says I have an array representing a 2d grid with walkable/nonwalkable data.

From that array, I want to create a new array with integers representing the number of steps to the nearest nonwalkable node.

What I do now is for every node in the grid to check all the neighbors in a radius of 1,2,3 and so on until we hit a nonwalkable node. But as I need to check all the nodes and multiple neighbors it is slow.

What I want to accomplish is the numbers in the image. Red representing the nonwalkable nodes. Grid example

Is there a fast way of doing this? If it matters I was doing this in c# but if I get an example in any other language I could probably figure it out.

monogame 2d arrays algorithm c#
2 Answers

Yes, run a BFS starting in all unwalkable cells.

You add all the unwalkable cells to a queue. While the queue is not empty you take the first element, compute the distance by looking at it's neighbors and adding 1 (if it's not walkable you can set it to 0). Then you add all it's unseen neighbors to the end of the queue and mark them as as seen.

This will be O(N*M) complexity both in time and in space. In this case, a grid where only neighbors are adjacent, this is O(N) since edges are capped at about 2N.

user_2410130

There is a efficient algorithm for this. Unfortunately I fail to find a reference to what it is called. It is essentially divided into two passes. Assuming the non walkable nodes have a value of zero, and the walkable have a max-value initially:

  1. Start at upper left corner
  2. Process each node left to right, top to bottom
  3. Take the minimum of the value to on top of and the value to the left
  4. Add one to the value
  5. If the value is smaller than the current node value, update the node with the value.

Repeat the process but starting at the bottom right, and processing nodes in reverse order, and checking the values to the right and underneath instead.

This assumes you do now allow diagonal traversal but the method could be adapted for this if that is a requirement.

user_123422380
Related