Pathfinding

Pathfinding is the foundation of game AI movement - enabling characters to navigate complex environments intelligently and efficiently.

Graph-Based Navigation

All pathfinding algorithms work on graphs - networks of connected nodes. In games, the game world is represented as a graph where nodes are locations and edges are paths between them. The three most common representations are:

• Grid-based: The world is divided into a 2D grid of cells. Simple to implement, common in tile-based games.
• Waypoint graphs: Manually placed navigation points connected by edges. Used in older FPS games.
• Navigation meshes (NavMesh): The walkable surface is decomposed into convex polygons. The modern standard for 3D games.

The A* Algorithm

A* (A-star) is the most widely used pathfinding algorithm in games. It combines the guaranteed shortest path of Dijkstra's algorithm with a heuristic that guides the search toward the goal, making it much faster in practice.

import heapq

def astar(grid, start, goal):
    """A* pathfinding on a 2D grid."""
    open_set = [(0, start)]
    came_from = {}
    g_score = {start: 0}

    while open_set:
        _, current = heapq.heappop(open_set)

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

        for dx, dy in [(-1,0),(1,0),(0,-1),(0,1)]:
            neighbor = (current[0]+dx, current[1]+dy)
            if not in_bounds(grid, neighbor):
                continue
            tentative_g = g_score[current] + 1
            if tentative_g < g_score.get(neighbor, float('inf')):
                came_from[neighbor] = current
                g_score[neighbor] = tentative_g
                f = tentative_g + heuristic(neighbor, goal)
                heapq.heappush(open_set, (f, neighbor))

    return []  # No path found

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

A* Components

Navigation Meshes (NavMesh)

A NavMesh is a mesh of convex polygons that defines the walkable surfaces in a 3D game. Characters pathfind on this simplified representation rather than the full game geometry.

• Generation: Tools like Recast automatically generate NavMeshes from level geometry.
• Path smoothing: Raw paths through polygon centers are smoothed using funnel algorithms for natural-looking movement.
• Dynamic obstacles: NavMeshes can be carved or updated at runtime when obstacles move.

Steering Behaviors

Once a path is computed, steering behaviors handle the low-level movement along that path:

• Seek: Move toward a target position at maximum speed.
• Flee: Move away from a threatening position.
• Arrive: Move toward a target and decelerate smoothly to a stop.
• Wander: Randomly vary heading for natural-looking idle movement.
• Flocking: Combine separation, alignment, and cohesion for group movement (birds, fish, crowds).

Optimization Techniques

• Hierarchical pathfinding: Use coarse-grained graphs for long-distance planning and fine-grained graphs for local navigation.
• Path caching: Store recently computed paths to avoid recalculation.
• Time-slicing: Spread pathfinding computation across multiple frames to avoid frame spikes.
• Jump Point Search: An optimization of A* for uniform grids that skips unnecessary nodes.