[Botta&Risposta]Generatore di labirinti

[Homunculus]

Vi posto due generatori di labirinti creati in questi giorni. L'idea é generare in modo efficiente un labirinto, nel primo caso a muro piatto, mentre nel secondo caso con muri spessi. Gli esempi creano labirinti dove ogni zona é raggiungibile tramite una sola e unica strada, dove non ci sono zone non raggiungibili. Per questo motivo non ho messo una partenza o un'arrivo, perché possono essere messi ovunque (nel secondo labirinto, in qualsiasi cella con entrambi i numeri dispari, 1,1 ; 1,3 ... 3,7 ecc...).

Download 1
Esempio:

Spoiler

Download 2
Esempio:

Spoiler

[BaronVsCorsar]

da buon appassionato di roguelike pure io ho creato algoritmi per generazione di labirinti (che poi converto in ambienti 3D... in un progetto che finirò tra 15 anni credo...)

ovviamente il tutto parametrizzabile, ecco un esempio corridoi e stanze di piccola grandezza.
+ porta
#muro
. zona libera
! area non raggiungibile
@ punto di ingresso
> uscita
/ porta segreta

Spoiler

Codice: Seleziona tutto

!!!################!
!!!#.+..@.+...#...#!
!!!#.#...#...+...#!
!!!#.+...#...#...#!
!!!#.#...#...#...#!
!!!#.############+#!
!!!#.#!!!!!#...#.#!
!!!#.#!!!!!#...#.#!
!!!#/#####!#...+.#!
!!!#....########.#!
!!!#..../...#!#.#!
!!!#....#...#!#.#!
!!!#....#...#!###!
!!!#...>.#...#!!!!!
!!!#######...#!!!!!
!!!!!!!!!#...#!!!!!
!!!!!!!!!######!!!!!
!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!
!!!!!!!!!!!!!!!!!!!!

l'algoritmo che seguo è ricorsivo: da una stanza creata a caso cero di ottenere un corridoio per ogni lato, se lo spazio per costruirlo c'è ripeto l'operazione cercando di costruire una stanza per ogni lato e così via...

[Homunculus]

Baron piu che in labirinto in senso stretto il tuo é un dungeon, comunque sembra un buon lavoro. Mi sono reso conto che é piu complesso di quel che pensavo, il sistema utilizzato sopra non é particolarmente difficile, garantisce un'unica via tra un punto e un'altro del labirinto, e tutte le aree sono accessibili in qualche modo (quindi l'entrata e l'uscita possono essere fissate a caso anche a posteriori).

Tuttavia se voglio un labirinto con muri spessi devo tener conto del fatto che l'uscita deve essere accessibile, e che non ogni area sarà raggiungibile. Ci devo ancora studiare dietro un po' insomma...

[Homunculus]

Ho aggiornato il primo post, devo ringraziare Nightwish per l'aiuto che mi ha fornito nel risolvere alcuni problemi di logica e nel rispolverare concetti quali nodi, alberi, grafi ecc...

@night: alla fine il labirinto lo genero con un depth-first search.

[CaMpIoN]

Complimenti homunculus sono molto utili.

[nightwish88]

bhè si, credo sia equivalente. L'algoritmo di prim ( quello che ti ho proposto io ) non è nient'altro che una ricerca in ampiezza del grafo. Ricerche in ampiezza e in profondità si equivalgono quindi algoritmi simili sono del tutto validi. finita la competizione scriverò qualcosa a riguardo... sono concetti assai utili soprattutto per sviluppare e programmare qualcosa aldilà del solito platform a scorrimento orizzontale

[maz85]

Interessante, dovrò studiarmeli...

[guidox]

Davvero bello homu!
Ora cerco di capire come hai fatto (gentile da parte tua dare il gmk).

[Jak]

A parere mio non è conveniente fare solo vicoli ciechi ed una strada possibile. Un labirinto è molto più difficile e complesso se le vie sono intrecciate tra di loro. Anche io avevo fatto una cosa simile tempo fa per un labirinto in 3d ma con una logica più complessa(sia random che a blocchi)e con molta più roba. Ad ogni modo il tuo programma funziona bene! Complimenti!

[Homunculus]

A parere mio non è conveniente fare solo vicoli ciechi ed una strada possibile. Un labirinto è molto più difficile e complesso se le vie sono intrecciate tra di loro. Anche io avevo fatto una cosa simile tempo fa per un labirinto in 3d ma con una logica più complessa(sia random che a blocchi)e con molta più roba. Ad ogni modo il tuo programma funziona bene! Complimenti!

Si é vero ci sono diverse tipoligie di labirinto, ma alla fine questa é la base. Se vuoi strade che si incrociano puoi sempre elaborare un sistema che a posteriori elimina qualche muro, ma prima devi generare un labirinto come questo per poterlo fare.

[Jak]

Vero! ho provato in qualche modo ma il tuo è il sistema migliore. Comunque sei stato bravissimo ad eliminare i "quadrati" di 4 muri ed a farlo tutto collegato. Non è un semplice random cè una logica ben fatta. Complimenti!

[Homunculus]

Vero! ho provato in qualche modo ma il tuo è il sistema migliore. Comunque sei stato bravissimo ad eliminare i "quadrati" di 4 muri ed a farlo tutto collegato. Non è un semplice random cè una logica ben fatta. Complimenti!

Non é un sistema che ho inventato io, é uno standard per creare labirinti basato su alberi e nodi (http://en.wikipedia.org/wiki/Maze_generation_algorithm), almeno alla base. Poi ovviamente l'implementazione é farina del mio sacco.