Distance to Selected Points

from Red Blob Games
Apr 2014, updated Feb 2015, May 2020

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

  1. 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.
    River example
    Breadth First Search, one room at a time
  2. 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.
    Dungeon example
    Breadth First Search, one room at a time

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

Email me , or tweet @redblobgames, or comment: