Uncovering The Hidden Secrets Of Procedural Generation

Mathematicians from the California Institute of Technology have solved an age-old problem related to ‘random walks’, a mathematical process that traces a path based on random decisions at various junctions.

- Caroline Delbert

If you’ve played a procedurally generated video game such as Minecraft or Stardew Valley, you’ve encountered a random walk in the form of a dungeon or terrain. Biologists use random walks to model how animals move and behave, and physicists use them to describe how particles behave.

In a random walk, the ‘walker’ can move in any direction at any point, so there’s an assumption that the walker will eventually revert to the mean and end up near its place of origin (because it’s less likely that chance would urge the walker in a single, focused direction over and over). Some random walks seem to behave with this assumption in mind, ‘realising’ they’ve taken a detour before reverting back to what is expected – mathematicians say this behaviour is ‘path-dependent. Other walks, however, seem to ignore their histories. They just go rogue, persisting as outliers and converging with other random walks that had much different histories.