A* on a grid

Implement A* pathfinding on a 2D tile grid using a heap-backed priority queue — returning an ordered list of tile coordinates.

A* is short and self-contained. It does not require pygame — just Python's standard library. This makes it straightforward to test in isolation before plugging it into a game.

The algorithm

import heapq

def astar(grid, start, goal):
    """
    Find the shortest path from start to goal on a 2D tile grid.

    Parameters
    ----------
    grid  : list[list[int]]  — 0 = passable, 1 = wall
    start : (row, col)       — starting tile
    goal  : (row, col)       — destination tile

    Returns
    -------
    list[(row, col)] from start to goal (inclusive), or [] if no path exists.
    """
    rows = len(grid)
    cols = len(grid[0])

    def h(node):
        """Manhattan distance heuristic."""
        return abs(node[0] - goal[0]) + abs(node[1] - goal[1])

    def neighbours(r, c):
        for dr, dc in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 0:
                yield (nr, nc)

    # Priority queue entries: (f_score, g_score, node)
    # g_score is included to break f_score ties consistently
    open_heap = [(h(start), 0, start)]
    came_from = {}              # node -> parent node
    g_score   = {start: 0}     # best known cost to reach each node

    while open_heap:
        f, g, current = heapq.heappop(open_heap)

        if current == goal:
            # Reconstruct path
            path = []
            while current in came_from:
                path.append(current)
                current = came_from[current]
            path.append(start)
            path.reverse()
            return path

        # Skip if we already found a better path to this node
        if g > g_score.get(current, float('inf')):
            continue

        for neighbour in neighbours(*current):
            tentative_g = g + 1      # uniform cost (all moves cost 1)
            if tentative_g < g_score.get(neighbour, float('inf')):
                g_score[neighbour]   = tentative_g
                came_from[neighbour] = current
                f_new = tentative_g + h(neighbour)
                heapq.heappush(open_heap, (f_new, tentative_g, neighbour))

    return []   # no path found

Walking through an example

# 0 = open, 1 = wall
#        col: 0  1  2  3  4
GRID = [
    [0, 0, 0, 0, 0],   # row 0
    [0, 1, 1, 1, 0],   # row 1  — wall in cols 1-3
    [0, 0, 0, 0, 0],   # row 2
]

start = (0, 0)
goal  = (0, 4)

path = astar(GRID, start, goal)
print(path)
# Expected: [(0,0), (1,0), (2,0), (2,1), (2,2), (2,3), (2,4), (1,4), (0,4)]
# The algorithm detours around the wall via the bottom row.

The wall in row 1 (columns 1–3) blocks the direct top route. A* detours via row 2, adding 6 extra steps versus the 4 steps of a straight path — the minimum possible detour.

Why the duplicate-check matters

if g > g_score.get(current, float('inf')):
    continue

When the same node is added to the heap multiple times with different g scores (because a better path was found later), stale entries remain in the heap. This guard discards them cheaply rather than re-expanding obsolete paths.

Connecting A* to your enemy

# Inside Enemy.update, when transitioning to CHASE:
def enter_chase(self, player_tile, tile_grid):
    """Recalculate path when entering CHASE or player moves significantly."""
    start = world_to_tile(self.pos)
    goal  = player_tile
    self.path      = astar(tile_grid, start, goal)
    self.path_idx  = 0   # index of the next waypoint to move toward

def move_along_path(self, dt):
    if not self.path or self.path_idx >= len(self.path):
        return
    target_tile = self.path[self.path_idx]
    target_world = tile_to_world(target_tile)
    to_target = target_world - self.pos
    if to_target.length() < 4:              # close enough — advance waypoint
        self.path_idx += 1
    elif to_target.length() > 0:
        self.pos += to_target.normalize() * CHASE_SPEED * dt

world_to_tile and tile_to_world are simple scale / offset conversions based on your tile size.

Do not call astar every frame for every enemy. Cache the path and invalidate it only when the player moves more than one tile, or at most once every 15–20 frames. On maps with hundreds of tiles the repeated search will stall your frame rate.

Where to go next

Next: lab — enemy AI — integrating A* and the FSM into the tile platformer so the enemy patrols, detects the player, paths toward them, and flees when low on health.

Finished reading? Mark it complete to track your progress.

The algorithm

Walking through an example

Why the duplicate-check matters

Connecting A* to your enemy

Where to go next

On this page