Nairou on StackExchange asked how to calculate the distance to the nearest obstacle in a single pass. One answer is Breadth First Search. Usually in pathfinding we initialize the open set with a single start point, but when calculating the distance to the nearest obstacle, we consider each obstacle a start point. Here’s a quick & dirty demo. *Click to cycle among: open space (beige/blue), start point (green), and wall (gray)*

Here’s some Python code:

```
frontier = Queue()
cost_so_far = {}
# Set the distance to 0 at all start points
for s in start:
frontier.put(s)
cost_so_far[s] = 0
# Expand outwards from existing points
while not frontier.empty():
current = frontier.get()
for next in current.neighbors():
if next not in cost_so_far:
cost_so_far[next] = cost_so_far[current] + 1
frontier.put(next)
```

Also see: my explanation of how Breadth First Search is useful in Tower Defense games.

Here’s another demo, showing how it works in mazes (based on this). I marked intersections as start points (green) and then marked entrances to the big room on the left, but you can mark anything you want:

Here’s another demo, showing that if in addition to the distance, you keep track of *which* seed point that distance is based on, you end up with a L1 Voronoi diagram that tells you which seed is closest to each point. Unlike a Voronoi diagram, this can work with obstacles. For example you could set up an uncrossable river and calculate country boundaries based on distance to their capitals, but not crossing rivers.

```
frontier = Queue()
cost_so_far = {}
seed = {}
# Set the distance to 0 at all start points, and
# each start point is its own seed
for s in start:
frontier.put(s)
cost_so_far[s] = 0
seed[s] = s
# Expand outwards from existing points
while not frontier.empty():
current = frontier.get()
for next in current.neighbors():
if next not in cost_so_far:
cost_so_far[next] = cost_so_far[current] + 1
seed[next] = seed[current]
frontier.put(next)
```

There are other algorithms, some of them more easily parallelizable or GPU-friendly than Breadth First Search. See Distance Transform on Wikipedia. For Euclidean distance instead of Manhattan Distance, see 2D Euclidean Distance Transforms: A Comparative Study (PDF).