Generazione di labirinti
Algoritmi (recursive backtracker, Prim, Kruskal, Wilson) che scavano una griglia fino a ottenere un labirinto perfetto, con un solo percorso tra due punti qualsiasi.
Un labirinto «perfetto» è un albero di copertura sulla griglia: completamente connesso, senza anelli, con esattamente un percorso tra due celle qualsiasi. Il recursive backtracker (una visita in profondità) produce corridoi lunghi e tortuosi; Prim e Kruskal ne danno di più corti e ramificati; l'algoritmo di Wilson (random walk con cancellazione dei cicli) genera un labirinto del tutto privo di bias. Ogni metodo imprime il proprio carattere ai passaggi.
Se il labirinto deve avere anelli o stanze, si abbattono deliberatamente alcuni muri in un secondo momento. Gli articoli di Jamis Buck hanno reso questi algoritmi patrimonio comune tra chi sviluppa giochi.