Generazione di labirinti data all'intersezione dell'albero

2

Informazioni di base: Sto costruendo un generatore di labirinti 2D. Ho provato l'algoritmo di Prim, l'algoritmo di Wilson e un algoritmo di backtrack ricorsivo per generare il mio labirinto, tuttavia non ero soddisfatto della difficoltà di nessuno. Ho deciso di creare il mio. Ho deciso che due cose rendono difficile un labirinto. Innanzitutto, i labirinti possono avere molte intersezioni e scelte da fare. Secondo, possono essere disorientanti e farti perdere la strada. Ho deciso di creare un albero per rappresentare le intersezioni e i vicoli ciechi in un labirinto e connettere ogni nodo dell'albero con un percorso generato a caso per disorientare gli utenti.

Il problema: Se inizio a generare le celle nel labirinto dell'albero, potrei scoprire che un nodo non ha la stanza di cui ha bisogno per connettersi o creare i suoi figli. Come posso risolvere o evitare questo problema?

I miei pensieri: Sembra che ci potrebbe essere un modo per farlo dividendo il labirinto in sezioni e suddividendole, ma ciò non garantisce ancora spazio sufficiente alla fine della divisione. Potrei anche provare a iniziare in piccolo e lavorare su, suddividere aree più piccole e quindi creare connessioni tra di loro, ma che potrebbe ancora imbattersi in problemi di pathing con non avere abbastanza spazio per collegare le sezioni insieme o addirittura creare percorsi molto lunghi tra le sezioni .

Sto usando una griglia esagonale, ma qualsiasi soluzione che voi vieni per le griglie rettangolari dovrebbe essere facile da trasferire a una esagonale.

Non ero sicuro se questo dovesse essere pubblicato nella sezione di informatica teorica o qui, e ho optato per quello più generale.

    
posta user2035846 28.04.2014 - 06:02
fonte

1 risposta

1

Ci sono molte descrizioni di labirinti nell'articolo wikipedia algoritmo di generazione del labirinto , ma descriverò una che funziona per qualsiasi labirinto di forme con qualsiasi numero di dimensioni.

  1. Inizi a dare a ogni stanza del labirinto un numero distinto.
  2. Quindi trovi l'insieme di tutti i muri tra le stanze che hanno numeri diversi su entrambi i lati.
  3. Da questo set, selezioni un muro casuale e lo rimuovi.
  4. Per le due sale su entrambi i lati, cambi tutte le stanze con il valore numerico più alto al valore numerico inferiore.
  5. Ripeti i passaggi da 2 a 4 finché tutte le stanze hanno lo stesso valore (più basso).

Questo funziona per labirinti bidimensionali o tridimensionali (mai provato 4, ma non vedo ragioni per cui non lo sarebbe) e per labirinti rettangolari ed esagonali (ma potrebbe anche avere forme irregolari - niente in là detta la forma, numero di muri adiacenti, o anche che ogni stanza è la stessa).

Genererà un labirinto che ha un solo percorso da due punti qualsiasi e un solo percorso (non ci sono loop). Esteticamente, mi piacciono i labirinti generati da esso, perché trovo che alcuni degli altri conducono a muri lunghi o lunghi corridoi.

Un esempio di questa generazione di labirinti su un labirinto quadrato 3x3:

+---+---+---+
|   +   +   |
| 0 a 1 b 2 |
|   +   +   |
++c+-+d+-+e++
|   +   +   |
| 3 f 4 g 5 |
|   +   +   |
++h+-+i+-+j++
|   +   +   |
| 6 k 7 l 9 |
|   +   +   |
+---+---+---+

All'inizio, il set di muri è abcdefghijkl . Scegli un muro casuale, diciamo 'd'. Il labirinto diventa quindi:

+---+---+---+
|   +   +   |
| 0 a 1 b 2 |
|   +   +   |
++c++   ++e++
|   +   +   |
| 3 f 1 g 5 |
|   +   +   |
++h+-+i+-+j++
|   +   +   |
| 6 k 7 l 9 |
|   +   +   |
+---+---+---+

Il set di muri è ora abcefghijkl . Dopo altri due passaggi, per i muri b e g , il labirinto è:

+---+-------+
|   +       |
| 0 a 1   1 |
|   +       |
++c++   ++e++
|   +       |
| 3 f 1   1 |
|   +       |
++h+-+i+++j++
|   +   +   |
| 6 k 7 l 9 |
|   +   +   |
+---+---+---+

Nota che ora, dal momento che e ha un 1 su ciascun lato, non è più un candidato nel set di muri che può essere rimosso.

    
risposta data 28.04.2014 - 06:34
fonte

Leggi altre domande sui tag