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

Question

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.

Answer 1

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.