Getting an agent from A to B around obstacles is pathfinding. A* is the standard algorithm — it finds the shortest path efficiently by combining actual cost with a heuristic estimate of remaining distance.
Pathfinding operates on a graph of connected nodes: a grid of tiles, a navigation mesh of walkable polygons, or waypoints. Each node connects to its neighbors with a movement cost. Turning your level into this graph — deciding what a "node" is and which moves are allowed — is the first and most consequential pathfinding step, because the algorithm can only be as good as the graph it searches.
Pathfinding searches a GRAPH of nodes + costs. Common representations:
GRID tiles; each connects to 4 or 8 neighbors. Simple, common in 2D.
diagonal move cost ~1.41 (sqrt 2), straight ~1.
NAV MESH the walkable area as convex polygons; nodes = polygons.
fewer nodes, smoother paths -> standard for 3D games.
WAYPOINTS hand-placed points connected by designer-defined links.
# grid neighbors (8-directional):
def neighbors(x, y, walkable):
for dx, dy in [(-1,0),(1,0),(0,-1),(0,1),(-1,-1),(1,1),(-1,1),(1,-1)]:
nx, ny = x+dx, y+dy
if walkable(nx, ny): yield (nx, ny)
Get the graph right; A* then finds the shortest path through it.A* finds the shortest path by exploring nodes in order of f = g + h, where g is the known cost from the start and h is a heuristic estimate of the remaining cost to the goal. The heuristic guides the search toward the goal instead of expanding blindly like Dijkstra, making it far faster while still guaranteeing the shortest path (when h never overestimates). It is the pathfinding algorithm.
import heapq
def a_star(start, goal, neighbors, cost, heuristic):
open_set = [(0, start)] # priority queue by f = g + h
came_from = {}
g = {start: 0} # best known cost from start
while open_set:
_, current = heapq.heappop(open_set)
if current == goal:
return reconstruct(came_from, current)
for nxt in neighbors(current):
tentative = g[current] + cost(current, nxt)
if tentative < g.get(nxt, float("inf")):
came_from[nxt] = current
g[nxt] = tentative
f = tentative + heuristic(nxt, goal) # g + h -> priority
heapq.heappush(open_set, (f, nxt))
return None # no path
# explores toward the goal (h) while tracking real cost (g) -> shortest path, fast.The heuristic h estimates the remaining distance to the goal and steers A*’s efficiency. On a grid you use Manhattan distance for 4-directional movement and Euclidean or diagonal distance for 8-directional. The rule is that h must never overestimate the true cost (be "admissible") to guarantee the shortest path; a heuristic closer to the real cost searches fewer nodes and runs faster.
import math
def manhattan(a, b): # 4-directional grids (no diagonals)
return abs(a[0]-b[0]) + abs(a[1]-b[1])
def euclidean(a, b): # straight-line; good when any-angle movement
return math.hypot(a[0]-b[0], a[1]-b[1])
def diagonal(a, b): # 8-directional grids (allows diagonals)
dx, dy = abs(a[0]-b[0]), abs(a[1]-b[1])
return (dx + dy) + (math.sqrt(2) - 2) * min(dx, dy)
# RULE: h must NOT overestimate the real remaining cost (be "admissible")
# -> guarantees A* returns the shortest path.
# a tighter (but still admissible) h expands fewer nodes -> faster search.
# h = 0 makes A* degrade into Dijkstra (correct, but explores everything).A raw A* path on a grid is often zig-zaggy and unnatural, so games post-process it: string-pull / line-of-sight smoothing removes unneeded waypoints, and agents follow the path with steering (next lesson) rather than snapping node to node. For performance you also limit how many agents path per frame and reuse paths. These practical touches turn a correct path into believable movement.
A raw grid path zig-zags. Make it game-ready:
SMOOTHING "string pull": if there's a clear line of sight from waypoint
i to i+2, drop i+1. Removes staircase artifacts.
STEERING don't snap node-to-node — steer toward the next waypoint
(seek/arrive, next lesson) for smooth motion.
PERFORMANCE budget pathfinding: only N agents compute a path per frame;
cache/reuse paths; use a nav mesh (fewer nodes) for 3D;
hierarchical pathfinding for huge maps.
Correct path (A*) + smoothing + steering = natural-looking navigation.