Sto cercando un algoritmo di generazione di labirinti in grado di generare labirinti senza vicoli ciechi ma solo un inizio e una fine. Come questo:Algoritmo per la generazione di labirinti senza vicoli ciechi?
Immagine da http://www.astrolog.org/labyrnth/maze/unicursl.gif
Dove posso trovare o fare per la costruzione di un tale algoritmo di generazione labirinto?
suona come si desidera una curva di riempimento di spazio pseudo-casuale (per esempio, vedere Context-based Space Filling Curves -EUROGRAPHICS ’2000 (formato PDF, 1.1 MB ))
dare un'occhiata un Space-filling curve.
Sospetto che si possa applicare un po 'di casualità alla costruzione di uno di questi per ottenere ciò che si desidera.
Le curve di riempimento spaziale sono fantastiche, ma quelle in quella carta hanno un vicolo cieco, e non sono sicuro di come potresti liberartene. –
@j_random_hacker: Penso che l'idea sia che i "muri" in una curva che riempiono lo spazio siano un'unica linea lunga; quindi se inverti i neri e i bianchi allora dovresti avere un labirinto di una soluzione senza vicoli ciechi. –
@Lie: buon punto. –
non ho pensato questo attraverso, solo un'idea:
Il processo di selezione "arbitrario" per i nuovi frammenti di muro può iniziare tentando di "crescere" sezioni diritte perpendicolarmente al muro esterno, quindi a un certo punto passa al riempimento, ove possibile.
Probabilmente sarà necessario tornare indietro nel caso si blocchi.
Probabilmente non è troppo efficiente.
Penso che questo potrebbe comportare un vicolo cieco. – phimuemue
@phimuemue: Un vicolo cieco implica che ci sono blocchi che possono essere trasformati in muro senza che il muro non abbia soluzioni (ad esempio, l'algoritmo di individuazione dei percorsi dall'inizio alla fine non è riuscito). Finché è possibile aggiungere un blocco a muro senza bloccare la soluzione, aggiungere un muro. –
Mi piacerebbe suger iniziare con il quadrato completamente nero (completo) e provare a scavare il percorso. Durante lo scavo puoi facilmente assicurarti che non ci siano vicoli ciechi, semplicemente continua ad andare avanti. Usa il backtracking, l'algoritmo di prima ricerca della profondità. Fai una "passeggiata casuale" - in ogni passaggio, decidi casualmente se mantenere la direzione o cambiarla. Verifica la condizione di vicolo cieco - se rimani bloccato, puoi dire "beh, ho finito, sono al traguardo", oppure, se consideri il labirinto non ancora scavato abbastanza, torna indietro. Ricorda sempre cosa hai fatto prima e prova a caso qualche altra azione. Probabilmente usa un po 'di euristica per preferire determinate direzioni, come, ad esempio, mantenendo sempre uno spazio libero prima di schivare il muro, prova prima a camminare intorno ai muri ecc. In questo modo puoi trovare la soluzione desiderata che riempie tutto il quadrato molto più velocemente.
Nell'esempio viene indicato un solo percorso effettivo dall'inizio alla fine. Se è tutto ciò che vuoi, sto pensando che potresti usare passeggiate casuali!
Il concetto è semplice: dati i confini esterni del labirinto, un punto iniziale e un punto finale, scrivi una funzione per generare camminate casuali dal punto iniziale che alla fine terminerà nel punto finale. Le condizioni sarebbero che il nostro "random walker" può solo muoversi in alto, in basso, a destra o a sinistra rispetto al quadrato precedente e non può entrare in un quadrato di un quadrato precedentemente attraversato (questo crea muri).
Come vedo, ci sono due sfide algoritmiche qui. Il primo è accertare se siamo all'interno di un quadrato di un quadrato precedentemente attraversato (collisioni). Forse potremmo mantenere un elenco di quadrati attraversati (le loro coordinate) e confini del labirinto, e per ogni nuovo quadrato valutare la distanza da ogni quadrato nell'elenco. Questo non suona molto efficiente però.
L'altra sfida è in realtà raggiungere il punto finale con la nostra passeggiata casuale.Se le collisioni con i quadrati precedentemente attraversati non fossero un problema, alla fine saremmo destinati a raggiungere il nostro endpoint, ma con loro abbiamo il problema di poterci isolare dal punto finale. Il modo per evitare questo è controllare ed evitare l'inserimento di loop. Se evitiamo di inserire loop formati dal percorso attraversato e/o dai confini del labirinto, allora manteniamo un possibile percorso verso il punto finale. Per quanto sia effettivamente capire se siamo in un loop ... Meh è un po 'difficile.
Se si dispone già di un algoritmo di risoluzione del labirinto, è possibile eseguirlo ogni volta che si verifica una collisione per verificare se esiste un percorso dal quadrato corrente all'endpoint. Quando lo esegui, pensa che tutti i quadrati precedentemente attraversati siano muri, così come i loro confini.
Quando "camminare" mantiene le modifiche apportate su ogni passaggio in una pila, così in quel modo puoi guardare x passi avanti e poi in ogni fase in modo da non poter fare ulteriori passi (camminare in un angolo o una spirale come camminare) fai scoppiare la pila fino a quando non hai un percorso percorribile e continua a camminare da lì fino a quando lo stack non è vuoto (cioè fai scoppiare la pila fino in fondo perché ad ogni passo precedente non c'era un vicino praticabile). Quindi applica le trasformazioni alla struttura dei dati del labirinto.
Sto lavorando su questo al momento ... Partendo da un bordo, sto percorrendo a caso una serie quadrata, segnando celle con la lunghezza del percorso mentre le passo attraverso.
Quando rimani bloccato (e lo farai), crea una giunzione a T formando un anello con il percorso più recente adiacente (ma vedi sotto). Poi torno indietro lungo il percorso esistente dall'altra parte dell'incrocio a T e rompere il loop lì. Questa coda ciondolante forma quindi la tua nuova "testa" della camminata casuale (ricorda di ricalcolare le lunghezze del percorso dalla sorgente del percorso) e puoi continuare.
Gli esperimenti dimostrano che così facendo non ha (o non ha ancora - vedi sotto) un ciclo di creazione di nuove code, a patto che se la tua nuova "coda" sia intrappolata, non solo ricreare senza cervello un collegamento con la cella da cui sei appena uscito se è il più recente - scegli il secondo più recente in quel caso.
Il caso di chiusura è quando ti trovi "bloccato" su un elemento di spigolo e hai riempito l'array (la lunghezza del percorso è la stessa dell'area dell'array) - hai finito. Il tuo punto di partenza porta al tuo punto finale.
Sembrano esserci due possibili inefficienze e potenziali singhiozzi con questo (sto giocando con l'algoritmo al momento) - A volte camminerai in un angolo e l'UNICO modo per continuare è ricreare il ciclo link con quello che hai appena rotto. Quindi la sequenza esegue il back-track attraverso tutti i loop che hai precedentemente fatto fino al punto in cui ti sei bloccato. Se che non può andare da nessun'altra parte (è un altro angolo), allora rimbalzerai tra i due. C'è un modo per aggirare questo, ma significa mantenere una sorta di elenco di celle in loop, solo cancellandolo quando si stabilisce effettivamente un nuovo percorso.
L'altro è che sembra incline a lasciare un quadrato dispari non riempito, in particolare quando l'array è dispari per dispari. Non ho studiato a fondo perché questo è il caso, ed è quando ciò accade che il problema dell'angolo precedente sembra particolarmente diffuso.Il lavoro continua ...
Ahh - Ho trovato un modo molto più semplice di generare un labirinto unicursal. – Nick
Ahh - Ho trovato un modo molto più semplice di generare un labirinto unicursal.
Iniziare con una griglia vuota e riempirla con piccoli cicli 2x2. Se la griglia è dispari, è necessario mescolare alcuni loop 2x3 e, se è dispari, è necessario lasciare un solo quadrato libero. Normalmente, lascia un angolo vuoto.
Successivamente, unire arbitrariamente i loop per formare loop più grandi - così (per esempio) 2 loop 2x2 diventano un singolo loop 4x2. Continua a farlo, assicurandoti di non unirti a un loopback a se stesso.
Alla fine si finisce con un singolo ciclo che utilizza tutte le celle occupate dalla rete di loop originale. Rompi questo loop in qualsiasi posizione e hai un labirinto unicursal, in cui le posizioni di inizio e fine sono l'una accanto all'altra.
Ora puoi spostare i punti finali attorno alla griglia formando e spezzando piccoli anelli - aggancia l'estremità in un altro punto nel labirinto, quindi spezza l'incrocio a T sul lato opposto per riformare il tuo pezzo singolo di stringa con una nuova posizione finale.
Se stai lavorando su un labirinto dispari, usa questa ultima tecnica per avviluppare una delle tue estremità fino all'angolo vuoto per completare il tuo labirinto.
Penso di aver trovato un altro metodo, tuttavia non l'ho ancora testato in modo approfondito.
Vedi https://twitter.com/tdhooper/status/340853820584230915/photo/1
Da sinistra a destra:
generare un labirinto non unicursal come descritto qui https://en.wikipedia.org/wiki/File:Prim_Maze.svg, credo che questo sia l'algoritmo di Prim
Sigilla l'uscita
Disegna un percorso che visita ogni punto del labirinto (ad esempio prova a risolverlo)
Fare questo percorso un muro
Funziona: http://www.stainlessvision.com/lab/maze-generator/unicursal.html codice qui: https: // github.com/tdhooper/random-labirinto-generatore –
v'è alcuna restrizione, ad esempio no 2x2 black square? –
@Lie Ryan: No. Anche se sarebbe bello avere tali algoritmi tra le risposte. – Fejuto
Correlati: http://stackoverflow.com/questions/2641964/algorithm-to-generate-a-segment-maze – nico