Breadth first search: early exits

 from Red Blob Games
10 Aug 2020

On the A* page I introduced Breadth First Search to search an entire graph, and then early exit to stop searching early. If you’re looking for a path A→B, then the thing to do is to exit when you find B. Here are some more ideas of things you can do with early exit, with either Breadth First Search or with Dijkstra’s Algorithm.

Example 1: your knight can move 5 steps this turn, and you want to show the player every place the knight can move:

Stop at distance N

Example 2: in an RTS like Age of Empires, you have 3 villagers and want to assign them to the nearest 3 rock quarries. You could first search all rock quarries, and then pick 3 of them, and then use A* to find a path individually for each one. Or you could calculate all the paths simultaneously using BFS/Dijkstra’s, and set the early exit condition to stop when you’ve found 3 rock quarries. (It’s not clear that this is actually faster than running A* multiple times but it may be simpler and more flexible.)

Stop when N goals reached

Example 3: in a SimCity-style game where you have to buy land, you want to get the nearest tiles to a starting point. A variant would be starting with multiple start points and growing them simultaneously to assign land to each city.

Stop when N tiles reached

Combine these ideas with multiple start points and you have a flexible algorithm that can be used for much more than pathfinding.

Email me , or tweet @redblobgames, or comment: