Pathfinding

I am working on a project that connects blocks with non-overlapping paths. Because it needs to create many paths, the algorithm must run quickly.

In this post, I compare several pathfinding methods and their trade-offs in speed, memory use, and solution quality.

Common Elements

Each of the following algorithms requires two collections.

The first contains visited locations. I call it visited, and it is coloured blue below.

The second contains locations that remain to be checked. I call it queue. Each entry stores a location and the path that led to it. The order depends on the algorithm. This collection is coloured light blue below.

visited = set()

queue = [(board.start, [board.start])]

Examples

visited = {(0, 0), (1, 0), (2, 0)}
queue = [((0, 0), [(0, 0)]),
         ((0, 1), [(0, 0), (0, 1)]),
         ((0, 2), [(0, 0), (0, 1), (0, 2)])]

Depth-First Search

Take the most recently added location from the queue, then add its unvisited neighbours. Repeat until you reach the destination or the queue is empty. Randomizing the neighbour order changes which branch is explored first, but it does not turn the method into a random walk.

while queue:
    (vertex, path) = queue.pop()

    if vertex in visited:
        continue
    visited.add(vertex)

    if vertex == board.end:
        return path

    for neighbour in add_neighbours(vertex):
        if neighbour not in visited:
            queue.append((neighbour, path + [neighbour]))

This is effective for small problems where any path will do. It is simple to implement, uses relatively little memory, and may find a solution faster than breadth-first search. It does not guarantee the shortest path.

Breadth-First Search

When every move has the same cost, breadth-first search returns a shortest path. It explores locations in layers according to their distance from the start.

New neighbours go at the end of the queue, while locations are removed from the front. This ensures that all locations at one distance are visited before the algorithm moves to the next distance.

from collections import deque

queue = deque([(board.start, [board.start])])

while queue:
    (vertex, path) = queue.popleft()

    if vertex in visited:
        continue
    visited.add(vertex)

    if vertex == board.end:
        return path

    for neighbour in add_neighbours(vertex):
        if neighbour not in visited:
            queue.append((neighbour, path + [neighbour]))

The algorithm finds a shortest path by expanding one step in every available direction until it reaches the destination.

In some problems, however, moves have different costs. Dijkstra's algorithm handles these weighted paths.

Weighted Paths (Dijkstra's Algorithm)

As above, we track how far we have travelled, but now each move can have a different non-negative weight.

In the code below, each queue entry includes the accumulated cost. The lowest-cost location is checked next.

When every step costs 1, the result is the same as breadth-first search. Changing the move costs changes the order in which locations are visited.

queue = [(board.start, [board.start], 0)]
best_cost = {board.start: 0}

while queue:
    queue.sort(key=lambda item: item[2], reverse=True)

    (vertex, path, weight) = queue.pop()

    if weight > best_cost[vertex]:
        continue

    if vertex == board.end:
        return path

    for neighbour in add_neighbours(vertex):
        new_weight = weight + move_cost(vertex, neighbour)
        if new_weight < best_cost.get(neighbour, float("inf")):
            best_cost[neighbour] = new_weight
            queue.append((neighbour, path + [neighbour], new_weight))

Instead of taking a step in every direction, what if we could take a step in the direction towards our target?

With a Little Help from a Heuristic (Best-First)

In this algorithm, we choose the queued location that appears closest to the destination according to a heuristic. For a four-directional grid, Manhattan distance is a simple choice:

def distance(a, b):
    return abs(b[0] - a[0]) + abs(b[1] - a[1])

This can find a route quickly, but it does not guarantee a shortest path. If a wall lies between the start and destination, the search may head into the wall and then backtrack.

Unlike Dijkstra's algorithm, greedy best-first search orders the queue only by the estimated distance to the destination.

queue = [(board.start, [board.start])]

while queue:
    queue.sort(key=lambda item: distance(item[0], board.end), reverse=True)

    (vertex, path) = queue.pop()

    if vertex in visited:
        continue
    visited.add(vertex)

    if vertex == board.end:
        return path

    for neighbour in add_neighbours(vertex):
        if neighbour not in visited:
            queue.append((neighbour, path + [neighbour]))

Mix for Taste (A*)

A* combines Dijkstra's accumulated path cost with best-first search's estimate of the remaining distance.

The queue is ordered by the cost from the start plus the heuristic estimate to the destination.

queue = [(board.start, [board.start], 0)]
best_cost = {board.start: 0}

while queue:
    queue.sort(
        key=lambda item: item[2] + distance(item[0], board.end),
        reverse=True,
    )
    (vertex, path, weight) = queue.pop()

    if weight > best_cost[vertex]:
        continue

    if vertex == board.end:
        return path

    for neighbour in add_neighbours(vertex):
        new_weight = weight + move_cost(vertex, neighbour)
        if new_weight < best_cost.get(neighbour, float("inf")):
            best_cost[neighbour] = new_weight
            queue.append((neighbour, path + [neighbour], new_weight))

This balance directs the search towards the goal while preserving alternate routes. With non-negative edge costs and an admissible, consistent heuristic, A* returns an optimal path.

Graph Theory and Networks

Pathfinding connects two vertices in a network. Networks appear everywhere, from chemical-reaction pathways inside a cell to transportation systems and the trade and political relationships that shape our world.

These algorithms introduce several trade-offs that matter when solving real problems on those networks.

Thank you for reading.

If you enjoyed this post, I recommend Map Colouring. I have also posted all the code on GitHub.