[c] labirinto...

[mic85rm]

salve ragazzi ho un problema con un progetto che consiste nel trovare l'uscita di un labirinto.

ho un entrata sulla "cornice" del labirinto mentre l'uscita puo trovarsi dappertutto tranne che negli "spigoli".

In poche parole mi sono creato una matrice allocata dinamicamente e riempita a random...

il mio "algoritmo" di soluzione pero' ha delle pecche...

1)se l'uscita è circondata da muri(ma non nelle celle adiacenti)come lo gestisco?
2)se dall'entrata all'uscita non esiste un percorso come faccio a far terminare l'algoritmo?

[lupoxxx87]

lavora con algoritmi di visita su grafi, come quello di dijkstra.
se arrivi all'uscita vuol dire che è raggiungibile, se non ci arrivi vuol dire che sei in uno dei due casi che hai scritto

[mic85rm]

grazie lupoxxx87...

altre soluzioni possibili?

io stavo utilizzando il principio della mano destra....

[banryu79]

Originariamente inviato da mic85rm

se dall'entrata all'uscita non esiste un percorso come faccio a far terminare l'algoritmo?

Originariamente inviato da mic85rm

io stavo utilizzando il pincipio della mano destra...

In tal caso, secondo quell'algoritmo, cito:

...nel caso particolare di una sola uscita, l'algoritmo conduce a un vicolo cieco, dal quale si ritorna al punto di partenza semplicemente continuando a seguire la parete prescelta.

Dove con "una sola uscita" intende che è presente solo l'entrata (che è quindi anche l'unica uscita).

In teoria, per ogni uscita che trovi con quet'algoritmo devi dunque verificare che non sia l'entrata. Se c'è solo un'uscita in tutto il labirinto per definizione coincide con l'entrata.

[mic85rm]

mi puoi dare il link con la spiegazione di questo algoritmo...sul mio libro è spiegato in modo sbrigativo...grazie

[tuccio`]

http://tinyurl.com/2bnsrkr

[banryu79]

Originariamente inviato da mic85rm

mi puoi dare il link con la spiegazione di questo algoritmo...sul mio libro è spiegato in modo sbrigativo...grazie

A dire il vero ho solo consultato il web: fatalità un link di wikipedia.
Guarda anche questo per altre idee: link, dovrebbe essere abbastanza per implementare un tuo metodo, ciao

[mic85rm]

ragazzi se vi posto il codice sorgente gli date un occhiata?

[mic85rm]

eccolo...accetto critiche consigli fatevi sotto

[tuccio`]

di sicuro ti consiglio di migliorare la leggibilità del codice

[mic85rm]

il codice è indentato..che altro posso fare?

[tuccio`]

indentato? :E

[mic85rm]

aggiornato...

[mic85rm]

buttateci un occhio e 2 minuti del vostro tempo

se qualcuno è di roma offro caffe' e birra a scelta

[Opcode]

Se hai modo di verificare se una dato nodo (zona in cui muovere) è transitabile oppure rappresenta il muro, ovvero zona non transitabile, potresti pensare ad un algoritmo di ricerca, che si scorre tutti i possibili nodi, e trovato quello transitabile procede a trovare quello successivo.

Un esempio è quello proposto da lupo ovvero Dijkstra, altrimenti ti propongo A*
Comunque di questo tipo di algoritmi ne esistono molti, su wikipedia o su google ne trovi sicuramente molti altri.

[mic85rm]

grazie opcode...

ma io chiedevo se potevate dare uno sguardo al mio codice al fine di ripulirlo migliorarlo ecc...

[mic85rm]

int percorso(char **m,int x,int y,int p_lrig,int p_lcol)
{
 // printf("[%d][%d]",x,y);
 int inizio=0,exit=0;
 int i,j;
 if ((x==0)&&(m[x+1][y]!=SIMBOLO_MURO))
  {
   x++;
   m[x][y]=SIMBOLO_CAMMINO;
   inizio=1;
  }//cerco di capire dove è l'entrata in modo da forzare il primo passo nell'unica direzione possibile
 if ((y==0)&&(m[x][y+1]!=SIMBOLO_MURO))
  {
   y++;
   m[x][y]=SIMBOLO_CAMMINO;
   inizio=2;
  }
 if ((y==p_lcol-1)&&(m[x][y-1]!=SIMBOLO_MURO))
  {
   y--;
   m[x][y]=SIMBOLO_CAMMINO;
   inizio=3;
  }
 if ((x==p_lrig-1)&&(m[x-1][y]!=SIMBOLO_MURO))
  {
   x--;
   m[x][y]=SIMBOLO_CAMMINO;
   inizio=4;
  }
  //getch(); //per controllare se il primo passaggio è ok
    //printf("f[%d]f[%d]-%d",x,y,inizio);
 while((exit==0)&&(!(GetAsyncKeyState(27) < 0))) //mi serve solo per provare a salvare i file
  {
   switch(inizio)
    {
     case 1://da su a giu
          switch(m[x+1][y]){
                            case SIMBOLO_VUOTO:
                                 m[x+1][y]=SIMBOLO_CAMMINO;
                                 x++;
                                 inizio=1;
                                 break;
                            case SIMBOLO_MURO:
                                 inizio=3;
                                 break;
                            case SIMBOLO_CAMMINO:
                                 m[x+1][y]=SIMBOLO_NUOVO;
                                 x++;
                                 inizio=1;
                                 break;
                            case SIMBOLO_USCITA:
                                 printf("Uscita Trovata");
                                 exit=1;
                                 break;
                            case SIMBOLO_NUOVO:
                                 inizio=3;
                                 break;
                            case SIMBOLO_ENTRATA:
                                 inizio=3;
                                 break;     
                            }

     break;
     case 2:
          switch(m[x][y+1]){//da sx a dx
                            case SIMBOLO_VUOTO:m[x][y+1]='*';y++;inizio=2;break;
                            case SIMBOLO_MURO:inizio=1;break;
                            case SIMBOLO_CAMMINO:m[x][y+1]='@';y++;inizio=2;break;
                            case SIMBOLO_USCITA:printf("Uscita Trovata");exit=1;break;
                            case SIMBOLO_NUOVO:inizio=1;break;
                            case SIMBOLO_ENTRATA:
                                 inizio=1;
                                 break;     
                            }
              break;
     case 3:
          switch(m[x][y-1]){//da dx a sx
                            case SIMBOLO_VUOTO:m[x][y-1]='*';y--;inizio=3;break;
                            case SIMBOLO_MURO:inizio=4;break;
                            case SIMBOLO_CAMMINO:m[x][y-1]='@';y--;inizio=3;break;
                            case SIMBOLO_USCITA:printf("Uscita Trovata");exit=1;break;
                            case SIMBOLO_NUOVO:inizio=4;break;
                            case SIMBOLO_ENTRATA:
                                 inizio=4;
                                 break;     
                            }

     break;

                    case 4:   switch(m[x-1][y]){//da giu a su
                            case SIMBOLO_VUOTO:m[x-1][y]='*';x--;inizio=4;break;
                            case SIMBOLO_MURO:inizio=2;break;
                            case SIMBOLO_CAMMINO:
                                 m[x-1][y]='@';
                                 x--;
                                 inizio=4;
                                 break;
                            case SIMBOLO_USCITA:printf("Uscita Trovata");exit=1;break;
                            case SIMBOLO_NUOVO:inizio=2;break;
                            case SIMBOLO_ENTRATA:
                                 inizio=2;
                                 break;     
                            }
     break;



                    case 0:printf("Sei circondato da muri...GameOver");exit=1;break;
                    }
          
mostra_labirinto(m,p_lrig,p_lcol);

system("PAUSE");
                    }
     return 0;
     }