Python Pathfinding Algorithms — Core Concepts

What Pathfinding Solves

Pathfinding finds the best route between two points in a graph — a network of connected nodes. The “best” route can mean shortest distance, lowest cost, fewest turns, or any metric you define. It powers GPS navigation, game AI, robot motion planning, and network routing.

Graph Representation

Before running any algorithm, the world must be represented as a graph:

• Grid-based — each cell is a node connected to its neighbors (4-directional or 8-directional). Common in tile-based games.
• Waypoint graph — specific points placed by a designer, connected by edges. Used in 3D games where navigation meshes define walkable areas.
• Navigation mesh (navmesh) — the walkable surface is divided into convex polygons. The centers (or edges) of polygons form the graph nodes.

In Python, a grid can be a 2D list where 0 is walkable and 1 is a wall. A weighted graph can be a dictionary of adjacency lists with costs.

Breadth-First Search (BFS)

BFS explores nodes layer by layer — first all nodes one step away, then two steps, then three. It guarantees finding the shortest path when all edges have equal cost.

How it works:

1. Start at the source node. Add it to a queue.
2. Take the next node from the front of the queue.
3. For each unvisited neighbor, mark it as visited, record how you got there, and add it to the queue.
4. Stop when you reach the destination.

BFS is simple and correct for unweighted graphs, but inefficient for weighted ones because it ignores edge costs.

Dijkstra’s Algorithm

Dijkstra extends BFS to handle weighted edges. Instead of a regular queue, it uses a priority queue (min-heap) that always processes the node with the lowest total cost first.

How it works:

1. Assign distance 0 to the start node, infinity to all others.
2. Put the start node in the priority queue.
3. Pop the node with the smallest distance.
4. For each neighbor, calculate the distance through the current node. If it is shorter than the known distance, update it and add the neighbor to the queue.
5. Stop when the destination is popped from the queue.

Dijkstra guarantees the optimal path in any graph with non-negative edge weights. Its weakness is that it explores equally in all directions — it does not “aim” toward the goal.

A* (A-Star)

A* adds a heuristic — an educated guess of the remaining distance to the goal. The priority queue sorts by f(n) = g(n) + h(n):

• g(n) — actual cost from start to current node.
• h(n) — estimated cost from current node to goal.

If the heuristic never overestimates (called “admissible”), A* finds the optimal path while exploring far fewer nodes than Dijkstra.

Common heuristics for grids:

Heuristic	Formula	Best For
Manhattan distance	`	dx
Euclidean distance	sqrt(dx² + dy²)	Any-angle movement
Chebyshev distance	`max(	dx

Visual Comparison

On a 50×50 grid with a wall in the middle:

• BFS explores ~1,200 nodes to find the path (all directions equally).
• Dijkstra explores ~1,200 nodes (same as BFS on uniform grids).
• A* explores ~300 nodes — it heads straight for the goal and only detours around the wall.

The path quality is identical; the difference is how much work the computer does to find it.

Python Implementation Pattern

A typical A* in Python uses heapq for the priority queue:

import heapq

def astar(grid, start, goal):
    open_set = [(0, start)]
    came_from = {}
    g_score = {start: 0}

    while open_set:
        _, current = heapq.heappop(open_set)
        if current == goal:
            return reconstruct_path(came_from, current)

        for neighbor, cost in get_neighbors(grid, current):
            tentative_g = g_score[current] + cost
            if tentative_g < g_score.get(neighbor, float('inf')):
                g_score[neighbor] = tentative_g
                f = tentative_g + heuristic(neighbor, goal)
                heapq.heappush(open_set, (f, neighbor))
                came_from[neighbor] = current

    return None  # no path found

Python Libraries

• python-pathfinding — ready-made grid-based pathfinding with A*, Dijkstra, and BFS.
• networkx — general graph library with shortest_path() using Dijkstra and A*.
• tcod — roguelike game library with fast C-backed pathfinding.

Common Misconception

“A* is always the best choice.” A* requires a good heuristic. On graphs where no useful heuristic exists (arbitrary network topologies, non-spatial problems), Dijkstra is simpler and just as effective. A* shines specifically on spatial problems where you can estimate distance.

The one thing to remember: BFS works for equal-cost grids, Dijkstra handles weighted graphs, and A* adds a heuristic to focus the search toward the goal — choosing the right algorithm depends on your graph and what “cost” means.