Bringing it Together
Four algorithms. One demo. Time to put everything together into something that actually feels like a game.
You’re the intruder. You have a 5-second head start before the guard wakes up. The guard uses A* to track your last known position — not your current position, because fair is fair and omniscient guards aren’t fun. Break line of sight, hide in the shadows, and get to the exit before you get caught.
Below the game you can switch the guard’s brain between all four algorithms you’ve learned, and watch how radically their behaviour changes. Greedy Best-First will beeline toward you but get confused by corners. Breadth-First will methodically comb every tile. Dijkstra’s will plot around the slower floors. A* will hunt you down with cold precision.
What This Chapter Covers:
- Wiring pathfinding into a real game loop
- Line-of-sight detection with raycasting
- Guard state machines (patrol → alert → chase)
- Dynamic replanning (the guard re-routes as you move)
- How algorithm choice shapes the player experience
What the Algorithm Switch Actually Changes
Try each algorithm and feel the difference:
BFS — The guard explores tiles like water spreading outward. It always finds the shortest route but doesn’t “look” toward you. On a large map with the guard across the building, it’ll scan a lot of irrelevant tiles before picking up your trail. Predictable but methodical.
Dijkstra’s — Nearly identical to BFS on a uniform-cost map (all tiles cost 1). The distinction shows up in the next chapter when you add terrain costs. On this map the guard behaves almost the same as BFS — a good baseline.
Greedy Best-First — The guard feels almost psychic in open corridors, lunging straight toward you. But watch what happens when a wall forces a detour — it can get stuck briefly, circling back before finding the way around. Great tension: fast but imperfect.
A* — The most dangerous guard. Finds you efficiently even through the maze, and re-routes instantly when you break line of sight. This is what shipping games use for good reason.
Wiring Pathfinding into a Game Loop
The key architectural decisions in the demo above:
1. Don’t Pathfind Every Frame
Pathfinding is expensive. The guard in this demo only replans every 30 frames (half a second). For a player moving at normal speed, this feels completely responsive — they don’t notice the lag.
guard.replanTimer++;
if (guard.replanTimer >= REPLAN_INTERVAL) {
guard.replanTimer = 0;
guard.path = findPath(algo, guard.x, guard.y, target.x, target.y);
guard.pathStep = 0;
}
For more complex games, stagger replans across multiple units so they don’t all recalculate on the same frame.
2. Smooth Movement Along a Tile Path
Pathfinding returns tile coordinates. Moving the sprite smoothly between them is a separate concern — lerping the pixel position toward the target tile:
// Each frame: nudge position toward the next waypoint
const speed = 0.1;
guard.px += (nextTile.x * TILE_SIZE - guard.px) * speed;
guard.py += (nextTile.y * TILE_SIZE - guard.py) * speed;
// When close enough, snap and advance to next waypoint
if (Math.abs(guard.px - nextTile.x * TILE_SIZE) < 1) {
guard.x = nextTile.x;
guard.pathStep++;
}
The lerp factor (0.1 above) controls how “snappy” movement feels. Lower values feel sluggish; higher feel robotic. Tune it per character type.
3. The Guard State Machine
Three states drive the guard’s behaviour:
// patrol: following waypoints around the map
// alert: moving to last known player position
// chase: actively tracking and replanning toward player
function updateGuardState(guard, player, canSee) {
if (canSee) {
guard.lastKnown = { x: player.x, y: player.y };
if (guard.state !== 'chase') {
guard.state = 'chase';
guard.replanTimer = REPLAN_INTERVAL; // replan immediately
}
} else if (guard.state === 'chase') {
// Lost sight: investigate last known position
guard.state = 'alert';
guard.path = findPath(algo, guard.x, guard.y,
guard.lastKnown.x, guard.lastKnown.y);
} else if (guard.state === 'alert' && guard.reachedDestination) {
// Searched last known position, back to patrol
guard.state = 'patrol';
}
}
State machines are the backbone of game AI. Even complex behaviours break down into a small number of states with clear transitions between them.
4. Line-of-Sight Detection
The guard shouldn’t know where you are unless it can see you. DDA raycasting checks whether a clear line exists between two tiles:
function hasLineOfSight(ax, ay, bx, by, map) {
const dx = bx - ax, dy = by - ay;
const steps = Math.max(Math.abs(dx), Math.abs(dy)) * 2;
if (steps === 0) return true;
let cx = ax + 0.5, cy = ay + 0.5;
const stepX = dx / steps, stepY = dy / steps;
for (let i = 0; i < steps; i++) {
const tx = Math.floor(cx), ty = Math.floor(cy);
if ((tx !== bx || ty !== by) && map[ty][tx] === WALL) return false;
cx += stepX; cy += stepY;
}
return true;
}
Combine this with a maximum sight radius (Manhattan distance check first, cheapest possible early exit) and you have a believable field of view.
Extending the System
Some directions to take this further on your own:
Multiple guards — Each guard runs the same pathfinding code independently. The interesting design problem is making them feel like they coordinate even when they don’t: staggered patrol waypoints naturally create overlapping coverage.
Alert propagation — When one guard spots the player, other guards in range transition to alert state immediately. One function call with a radius check.
Noise mechanics — Give certain tiles a noise rating (creaky floor, ventilation grate). Instead of binary line-of-sight, the guard can “hear” tiles above a threshold even without visual contact.
Pathfinding weights for risk — Guards will avoid certain tiles too. A guard under heavy suppression in a combat game might treat “exposed” tiles as high-cost, seeking cover just as your player does.
Next up: Going Further — Flow fields, Jump Point Search, and where pathfinding research is headed.