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

## Distance to nearest intersection#

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:

## Distance to nearest wall#

Here’s the same algorithm with the *walls* as the start points. It tells you not only the size of the room but also how to move towards or away from the center. Click to toggle walls:

Walls, intersections, doorways, enemies, allies, resources, bosses, treasures — there are so many types of map analysis you might do with this.

## Region growth#

If in addition to the distance, we keep track of *which* seed point that distance is based on, we end up with a map that tells us which seed is closest to each point based on travel distance.

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

Run it again a second time, this time with the country borders as the start points, and you can find paths towards / away from the borders.

## More ideas#

The same algorithm works on a polygon mesh. Switch to Dijkstra’s Algorithm to extend this to work with variable movement costs. Take a look at this article^{[3]} for more ideas.

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

- In Mapgen4 I ran Breadth First Search from the coastline with some randomness instead of following the nodes in strict breadth first order. I used this to generate rivers.
- In this dungeon generator I ran Breadth First Search serially instead of in parallel across all seeds, and I also put limits on how far it grows. I used this to generate dungeon rooms.

Breadth First Search can run at around 1 million nodes per second.