Generación de laberintos
Algoritmos — recursive backtracker, Prim, Kruskal, Wilson — que tallan una cuadrícula hasta formar un laberinto perfecto con exactamente un camino entre dos puntos cualesquiera.
Un laberinto "perfecto" es un árbol de expansión sobre la cuadrícula: totalmente conexo, sin bucles, con exactamente una ruta entre cada par de celdas. El recursive backtracker (un recorrido en profundidad) produce corredores largos y sinuosos; los algoritmos de Prim y Kruskal dan otros más cortos y ramificados; el de Wilson (recorrido aleatorio con borrado de bucles) genera un laberinto completamente insesgado. Cada método imprime su propio carácter en cómo se sienten los pasillos.
Si el laberinto debe tener bucles o salas, se derriban muros a propósito después. Los artículos de Jamis Buck convirtieron estos algoritmos en conocimiento común entre quienes hacen juegos.