# Distance to Selected Points

from Red Blob Games

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 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). 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. For Euclidean distance instead of Manhattan Distance, see 2D Euclidean Distance Transforms: A Comparative Study (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.