Che cosa è un buon algoritmo per generare un labirinto?

Question

Si supponga che si desideri un semplice labirinto a N da M griglia, con un percorso attraverso, e un buon numero di vicoli ciechi, ma che sembra "giusto" (cioècome qualcuno ha fatto con le mani, senza troppi piccoli vicoli ciechi e tutto ciò che).C'è un modo per fare questo?

Answer 1

Da http://www.astrolog.org/labyrnth/algrithm.htm

Ricorsiva backtracker:Questo è in qualche modo legato alla ricorsiva backtracker solving metodo descritto di seguito, e richiede stack fino alla dimensione del Labirinto.Quando carving, essere goloso quanto possibile, e sempre di ritagliarsi in un sfatto sezione se uno è accanto alla cella corrente.Ogni volta che si sposta in una nuova cella, premere l'ex cella della pila.Se non ci sono disfatti cellule vicino alla posizione corrente, pop stack alla posizione precedente.Il Labirinto è fatto quando si pop il tutto lo stack.Questo algoritmo risultati in Labirinti con circa alto un "fiume" fattore possibile, con un minor numero ma più morti estremità, e di solito un molto lungo e tortuoso soluzione.Si corre abbastanza veloce, anche se l'algoritmo di Prim è un po ' più veloce.Ricorsiva backtracking non funziona come un muro adder, perché così facendo tende a tradursi in un percorso di soluzione che segue il bordo esterno, dove l'intero interno del Labirinto è collegata al limite da un unico stelo.

Producono solo il 10% finisce morto

è un esempio di un labirinto generato da tale metodo.

Answer 2

Si scopre ci sono 12 algoritmi classici per generare "perfetto" labirinti.Un labirinto è perfetto se si ha una e una sola soluzione.Ecco alcuni link per ogni algoritmo, in ordine approssimativo di mia preferenza.

1. Test di Kruskal s
2. La
3. Ricorsiva Backtracker
4. Aldous-Broder
5. Albero Che Cresce
6. Caccia e Uccidere
7. Wilson
8. Eller s
9. Automa Cellulare (Facile)
10. Ricorsiva Divisione (Molto Facile)
11. Sidewinder (Prevedibile)
12. Albero Binario (Imperfetto)

Per ulteriori informazioni, il check-out mazelib su GitHub, una libreria Python attuazione di tutti gli standard labirinto di generazione/risoluzione di algoritmi.

Answer 3

Una bella soluzione semplice potrebbe essere quella di assegnare casuale pesi per i bordi del grafico e applicare L'algoritmo di Kruskal per trovare un minimo spanning tree.

Migliori discussione sempre sul labirinto algoritmi di generazione: http://www.jamisbuck.org/presentations/rubyconf2011/index.html (era sul HN un paio di giorni fa).

Answer 4

Stranamente, modificando leggermente il 'canonica' e regole a partire da una configurazione random, Conway Gioco della Vita sembra generare bel labirinti!

(Non mi ricordo la regola precisa, ma è molto semplice modifica che tende a "intensificare" la popolazione di cellule...)

Answer 5

Il mio metodo preferito è quello di utilizzare l'algoritmo di Kruskal, ma quando casualmente la scelta e bordo per rimuovere, il peso, la scelta in base ai tipi di bordi a cui è collegato.

Variando i pesi per i diversi tipi di bordi, è possibile generare labirinti con un sacco di caratteristiche distinte o "personalità".Vedi il mio esempio qui:

https://mtimmerm.github.io/webStuff/maze.html

Answer 6

Uno dei metodi per generare un labirinto è randomizzati versione di Prim algoritmo.

Iniziare con una griglia piena di mura.Scegli un cellulare, segno di come una parte del labirinto.Aggiungere i muri della cella al muro elenco.Mentre ci sono pareti in elenco:

Scegliere un casuale muro dall'elenco.Se la cella sul lato opposto non è nel labirinto di sicurezza:

(i) Effettuare la parete di un passaggio che segnano la cella sul lato opposto di una parte del labirinto.

(ii) Aggiungere le vicine pareti della cella a parete elenco.

Se la cella sul lato opposto era già nel labirinto, rimuovere il muro dall'elenco.

Per maggiori informazioni clicca qui

Answer 7

Ecco l'algoritmo DFS scritto come pseudocodice:

creare un CellStack (LIFO) tenere un elenco di cella posizioni
set TotalCells = numero di celle della griglia
scegliere una cella a caso e chiamare CurrentCell
set VisitedCells = 1

mentre VisitedCells < TotalCells trova tutti i vicini di casa di CurrentCell con tutti i muri intatti
se uno o più trovato scegliere uno a caso
abbattere il muro tra di esso e CurrentCell
spingere CurrentCell posizione sulla CellStack
rendere il nuovo cellulare CurrentCell
aggiungere 1 a VisitedCells altro pop l'ultima cella voce fuori CellStack
rendere CurrentCell endIf endWhile