Pathfinding Algorithm
Random Walk
“The Chaos Monkey”
History
The Random Walk (or "Drunkard's Walk") is a mathematical formalization of a path that consists of a succession of random steps. It dates back to Karl Pearson in 1905.
It is less of an algorithm and more of a cautionary tale. It represents entropy. In the context of Yield, it serves as the baseline control group: this is what happens when you have zero intelligence and zero strategy.
How It Works
It is exactly what it says on the tin. At every step, the algorithm rolls a die and picks a direction.
The Algorithm Step-by-Step
- Pick: Look at valid neighbors.
- Roll: Choose one randomly.
- Move: Go there.
- Repeat: Until you accidentally stumble upon the goal or the universe ends.
Why It's Here
To show you why we need A*. Watching a Random Walk try to solve a maze is a painful lesson in why heuristics matter. It has no memory of where it has been, so it frequently backtracks and walks in circles.
Theoretically, it can run forever. In practice, on a finite grid, it will eventually hit the goal, but the time taken is effectively random.
It doesn't need to remember anything. It lives in the moment.
The core data structure powering Random Walk.
How this algorithm appears during visualization.
Code Walkthrough
Real implementations in multiple programming languages. Select a language to view idiomatic code.
1import random23def random_walk(grid: list[list[int]], start: tuple[int, int], end: tuple[int, int], max_steps: int = 10000) -> list[tuple[int, int]] | None:4 """Random walk pathfinding. NO guarantee of finding or optimality."""5 rows, cols = len(grid), len(grid[0])6 directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]7 path = [start]8 current = start9 visited_first = {start: 0} # Track first visit index for path1011 for step in range(max_steps):12 if current == end:13 # Reconstruct minimal path through visited_first14 return path1516 row, col = current17 neighbors = []18 for dr, dc in directions:19 nr, nc = row + dr, col + dc20 if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == 0:21 neighbors.append((nr, nc))2223 if not neighbors:24 return None # Stuck2526 # Pick random neighbor27 next_pos = random.choice(neighbors)28 path.append(next_pos)2930 if next_pos not in visited_first:31 visited_first[next_pos] = len(path) - 13233 current = next_pos3435 return None # Exceeded max stepsReal World Use Cases
- 1Procedural Generation (creating organic tunnels)
- 2Stock Market modeling (financial theory)
- 3Brownian Motion simulations in physics
- 4Stress testing other systems
- 5Screensavers
- 6Simulating confused NPCs
Key Insights
- It has no strategy.
- It creates very organic, jagged shapes.
- It is statistically guaranteed to visit every node on a 2D infinite grid eventually (but don't wait up for it).
- It is the baseline for comparing 'intelligent' algorithms.
- It creates high-frequency noise in pathing.
When to Use
Use Random Walk for procedural generation (like digging worm tunnels) or for artistic visualizations. It can also be used for 'wandering' AI behavior when the NPC is idle.
When NOT to Use
Never use this if you actually need to get somewhere.