Running Breadth First Search with **multiple start points** can do some cool things.

## Distance to nearest obstacle#

Nairou on StackExchange asked how to calculate the distance to the nearest obstacle^{[1]} 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)
```

Here’s another demo, showing how it works in mazes (based on this^{[2]}). 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:

## Region growth#

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)
```

The same technique works on a polygon mesh.

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

## Dungeon rooms#

Instead of running Breadth First Search in parallel across all seeds, we can run it serially, one seed at a time, but put limits on how far it grows.

I don’t have a demo on this page *yet* but see this project where I built a dungeon map this way.