[C] Generare un labirinto

[Yankoo]

Salve a tutti!!
Ultimamente mi sono imbattuto in un esercizio, il quale prevede di creare una funzione ricorsiva che, dato un labirinto contenuto in un array bidimensionale, riesca ad arrivare all'uscita. Fin qui tutto ok, ma mi sono letteralmente bloccato nell'esercizio successivo, ovvero creare una funzione che generi a caso un labirinto. Come potrei fare? Cioè per generare un labirinto, non posso mettere a caso muri e spazi percorribili! Qualcuno potrebbe illuminarmi?

[gila75]

Ciao, io in C avevo usato l'algoritmo DFS.
prova a vedere qui nel forum "labirinto in C" è una mia vecchia discussione con il programma (un po' rozzo e identato male, non lo sapevo fare all'epoca).
Detta in breve: inizializzavo un vettore bidimensionale di caratteri.
* Parti poi a "scavare" con direzioni a caso e così crei i "corridoi"
* se la posizione è valida e sei avanzato, memorizzi nello stack (esplicito o nello stack di sistema se usi la ricorsione)
* se ti sei chiuso la strada, torni indietro nello stack al primo punto dove non hai la strada chiusa e così via.
Ad un certo punto (quando il labirinto è completo e non hai più nessuna strada) inizierai ad andare a ritroso nello stack.
ma essendo appunto completato arriverai ad esaurire lo stack: labirinto pronto.
Ecco cosa esce più o meno:
https://www.youtube.com/watch?v=uaMTqsILuwU

[Yankoo]

Ciao, io in C avevo usato l'algoritmo DFS.
prova a vedere qui nel forum "labirinto in C" è una mia vecchia discussione con il programma (un po' rozzo e identato male, non lo sapevo fare all'epoca).
Detta in breve: inizializzavo un vettore bidimensionale di caratteri.
* Parti poi a "scavare" con direzioni a caso e così crei i "corridoi"
* se la posizione è valida e sei avanzato, memorizzi nello stack (esplicito o nello stack di sistema se usi la ricorsione)
* se ti sei chiuso la strada, torni indietro nello stack al primo punto dove non hai la strada chiusa e così via.
Ad un certo punto (quando il labirinto è completo e non hai più nessuna strada) inizierai ad andare a ritroso nello stack.
ma essendo appunto completato arriverai ad esaurire lo stack: labirinto pronto.
Ecco cosa esce più o meno:
https://www.youtube.com/watch?v=uaMTqsILuwU

Grazie, farò qualche prova

[gila75]

di nulla.
Se hai bisogno...se mi ricordo ancora come ho fatto sono qui

[stefano_carniel]

io recentemente ho implementato 3 algoritmi in c#: recursive backtracker, kruskal e Prim. Ci ho messo anche la generazione passo passo proprio per vedere le differenze tra i tre

[gila75]

Sarebbe bello vederli in azione @stefano

[Yankoo]

Ciao, io in C avevo usato l'algoritmo DFS.
prova a vedere qui nel forum "labirinto in C" è una mia vecchia discussione con il programma (un po' rozzo e identato male, non lo sapevo fare all'epoca).
Detta in breve: inizializzavo un vettore bidimensionale di caratteri.
* Parti poi a "scavare" con direzioni a caso e così crei i "corridoi"
* se la posizione è valida e sei avanzato, memorizzi nello stack (esplicito o nello stack di sistema se usi la ricorsione)
* se ti sei chiuso la strada, torni indietro nello stack al primo punto dove non hai la strada chiusa e così via.
Ad un certo punto (quando il labirinto è completo e non hai più nessuna strada) inizierai ad andare a ritroso nello stack.
ma essendo appunto completato arriverai ad esaurire lo stack: labirinto pronto.
Ecco cosa esce più o meno:
https://www.youtube.com/watch?v=uaMTqsILuwU

Il ragionamento l'ho capito, ma non ho capito cos'è lo stack. Per questo algoritmo è necessario utilizzarli o vi sono alternative?

[stefano_carniel]

Sarebbe bello vederli in azione @stefano

Eh, se riesco faccio un videetto e lo metto da qualche parte

[gila75]

@yankoo :
Domani con piu' calma cerco di spiegarti.
In poche parole tieni traccia dei movimenti che hai fatto, per eventualmente tornare indietro.
Si puo'per esempio implementare con un array uno stack.
Domani ti faccio esempi piu' dettagliati.
Non so altri metodi, puo' darsi. Con il backtracking (tecnica che ho usato io ) lo stack e' d'obbligo.
La discussione l'hai trovata ?

[Yankoo]

Si, l'utilizzo più o meno l'ho capito, ma non ho capito come implementarlo

[stefano_carniel]

Sarebbe bello vederli in azione @stefano

Trovate il video qui

Si vedono bene le differenze tra i tre algoritmi, ma non ti basterà per capire come implementarli. Io sono partito da qui, c'è la teoria che ti serve.

[gila75]

Complimenti stefano.
Il mio in confronto fa schifo.
Ma col c nudo e crudo senza grafica quello potevo fare.
Ora sto studiando python, quindi non riesco, ma metto in coda.

[gila75]

Faccio un altro post, mi scuso, ma l'edit potrebbe non essere notato.
Allora Yankoo.
Il backtracking lo puoi fare con la ricorsione di "sistema" cosa che io odio, e a dire il vero non sono bravo, oppure con stack espliciti.
Abbiamo detto: prepari un array bidimensionale di char per esempio 27x27
Ti piazzi in un punto a caso, poi a random scegli una direzione: nord,sud,est, ovest.
Se è libera ti muovi e memorizzi nello stack
es parti da 0,3
0,4 è buono quindi potresti fare 2 array uno per le x uno per le y
stack_array_x[0]=0
stack_array_y[0]=3

passo successivo che hai fatto:
stack_array_x[1]=0
stack_array_y[1]=4
contemporaneamente se incrementi aumenti la variabile che conta quanti elementi hai nell'array.
Per gli esempi sopra in tutto vale 1
prosegui
0,5 è buono:
stack_array_x[2]=0
stack_array_y[2]=5

continui fin che puoi e aumenti lo stack (operazione push)
Ad un certo punto ti chiudi la strada allora torni indietro al primo punto dove ti puoi muovere.
Cont (variabile che contava quanti elementi hai immesso nello stack) valeva 2 nel nostro esempio. Ma siamo bloccati.
Allora scalo: cont=1
a cont 1 cosa erano i valori ?
stack_array_x[1]=0
stack_array_y[1]=4

sono tornato un passo indietro.
Riparto e vedo se ho direzioni valide.
Si? allora incremento e salvo nello stack.
No, retrocedo ulteriormente.
In definitiva sono 2 banali array.
Spero di essere stato chiaro.

[Yankoo]

Faccio un altro post, mi scuso, ma l'edit potrebbe non essere notato.
Allora Yankoo.
Il backtracking lo puoi fare con la ricorsione di "sistema" cosa che io odio, e a dire il vero non sono bravo, oppure con stack espliciti.
Abbiamo detto: prepari un array bidimensionale di char per esempio 27x27
Ti piazzi in un punto a caso, poi a random scegli una direzione: nord,sud,est, ovest.
Se è libera ti muovi e memorizzi nello stack
es parti da 0,3
0,4 è buono quindi potresti fare 2 array uno per le x uno per le y
stack_array_x[0]=0
stack_array_y[0]=3

passo successivo che hai fatto:
stack_array_x[1]=0
stack_array_y[1]=4
contemporaneamente se incrementi aumenti la variabile che conta quanti elementi hai nell'array.
Per gli esempi sopra in tutto vale 1
prosegui
0,5 è buono:
stack_array_x[2]=0
stack_array_y[2]=5

continui fin che puoi e aumenti lo stack (operazione push)
Ad un certo punto ti chiudi la strada allora torni indietro al primo punto dove ti puoi muovere.
Cont (variabile che contava quanti elementi hai immesso nello stack) valeva 2 nel nostro esempio. Ma siamo bloccati.
Allora scalo: cont=1
a cont 1 cosa erano i valori ?
stack_array_x[1]=0
stack_array_y[1]=4

sono tornato un passo indietro.
Riparto e vedo se ho direzioni valide.
Si? allora incremento e salvo nello stack.
No, retrocedo ulteriormente.
In definitiva sono 2 banali array.
Spero di essere stato chiaro.

Grazie per la pazienza, spero di non doverti disturbare più

[gila75]

Nessun problema nel caso.
L'importante e' se hai capito.
Poi sviluppi un pezzo alla volta e vedrai che ci riesci