Newsgroup: it.comp.lang.c++
Titolo: Problemi con ricorsione

Sto tentando di fare un esercizio che ho trovato su "How to program C++" di
Deitel&Deitel. Si tratta di scrivere un algoritmo che permetta di trovare
l'uscita(qualora esista) di un labirinto, rappresentato per semplicità da un
array bidimensionale di caratteri ove il simbolo '#' rappresenta il muro e
lo spazio la strada. Il metodo si basa sul fatto che appoggiando la mano
destra al muro e senza mai staccarla si giungerà senza dubbio all'uscita,
oppure di nuovo all'entrata quando questa non esiste.
L'esercizio proponeva di risolvere il problema con una funzione ricorsiva,
tuttavia io sono riuscito ad ottenere il risultato con un ciclo while,
mentre quando tento di adottare la ricorsione, in fase di esecuzione viene
visualizzato il messaggio:
Exeption unhandled: Stack overflow.
Riporto sotto il codice funzionante seguito dalla sola funzione traversal
scritta ricorsivamente.
Spero che qualcuno sia così paziente da leggerlo e consigliarmi come
risolvere il dilemma.
Ho utilizzato la classe Maze per rappresentare il labirinto (forse in questo
caso bastava un oggetto globale) perchè, risolto il primo problema, dovrei
fare in modo di creare un labirinto di ogni dimensione e forma: per la
dimensione non credo di avere difficoltà(un costruttore al quale passare le
dimensioni che crei una matrice allocata dinamicamente), per la forma invece
sì. Come faccio a creare un labirinto casuale? Credo che una distribuzione
completamente random di spazi e muri non sia una soluzione ottimale. Mi
sbaglio?
Grazie
Marco
#include <iostream>
class Maze {
friend class Persona;
   static char _maze[12][12];
public:
 static void traversal(int posx, int posy);
 static void print();
};
class Persona {
private:
 int _x;
 int _y;
 enum { NORD, EST, SUD, OVEST } direzione;
 static char wall;
public:
 Persona(int x, int y) : _x(x), _y(y) { direzione = OVEST;};
 bool muro_destra();
 bool muro_avanti();
 bool muro_sinistra();
 void avanza();
 void inverti();
 void gira_destra();
 void gira_sinistra();
 bool fuori();
 int getx() { return _x; };
 int gety() { return _y; };
};
char Persona::wall = '#';
bool Persona::muro_destra() {
 switch(direzione) {
 case NORD: {
  if(Maze::_maze[_x][_y + 1] == wall)
   return true;
  break;
 }
 case EST: {
  if(Maze::_maze[_x + 1][_y] == wall)
   return true;
  break;
 }
 case SUD: {
  if(Maze::_maze[_x][_y - 1] == wall)
   return true;
  break;
 }
 case OVEST: {
  if(Maze::_maze[_x - 1][_y] == wall)
   return true;
  break;
 }
 }
 return false;
}
bool Persona::muro_avanti() {
 switch(direzione) {
 case NORD: {
  if(Maze::_maze[_x - 1][_y] == wall)
   return true;
  break;
 }
 case EST: {
  if(Maze::_maze[_x][_y + 1] == wall)
   return true;
  break;
 }
 case SUD: {
  if(Maze::_maze[_x + 1][_y] == wall)
   return true;
  break;
 }
 case OVEST: {
  if(Maze::_maze[_x][_y - 1] == wall)
   return true;
  break;
 }
 }
 return false;
}
bool Persona::muro_sinistra() {
 switch(direzione) {
 case NORD: {
  if(Maze::_maze[_x][_y - 1] == wall)
   return true;
  break;
 }
 case EST: {
  if(Maze::_maze[_x - 1][_y] == wall)
   return true;
  break;
 }
 case SUD: {
  if(Maze::_maze[_x][_y + 1] == wall)
   return true;
  break;
 }
 case OVEST: {
  if(Maze::_maze[_x + 1][_y] == wall)
   return true;
  break;
 }
 }
 return false;
}
void Persona::avanza() {
 switch(direzione) {
 case NORD: {
  --_x;
  break;
 }
 case EST: {
  ++_y;
  break;
 }
 case SUD: {
  ++_x;
  break;
 }
 case OVEST: {
  --_y;
  break;
 }
 }
 Maze::_maze[_x][_y] = '*';
}
void Persona::gira_destra() {
 switch(direzione) {
 case NORD: {
  direzione = EST;
  avanza();
  break;
 }
 case EST: {
  direzione = SUD;
  avanza();
  break;
 }
 case SUD: {
  direzione = OVEST;
  avanza();
  break;
 }
 case OVEST: {
  direzione = NORD;
  avanza();
  break;
 }
   }
}
void Persona::gira_sinistra() {
 switch(direzione) {
 case NORD: {
  direzione = OVEST;
  avanza();
  break;
 }
 case EST: {
  direzione = NORD;
  avanza();
  break;
 }
 case SUD: {
  direzione = EST;
  avanza();
  break;
 }
 case OVEST: {
  direzione = SUD;
  avanza();
  break;
 }
   }
}
void Persona::inverti() {
 switch(direzione) {
 case NORD: {
  direzione = SUD;
  avanza();
  break;
 }
 case EST: {
  direzione = OVEST;
  avanza();
  break;
 }
 case SUD: {
  direzione = NORD;
  avanza();
  break;
 }
 case OVEST: {
  direzione = EST;
  avanza();
  break;
 }
   }
}
bool Persona::fuori() {
 if(_x < 0 || _x > 11)
  return true;
 if(_y <= 0 || _x > 11)
  return true;
 return false;
}
char Maze::_maze[12][12]
 { '#','#','#','#','#','#','#','#','#','#','#','#' },
               { '#',' ',' ',' ','#',' ',' ',' ',' ',' ',' ','#' },
       { ' ',' ','#',' ','#',' ','#','#','#','#',' ','#' },
       { '#','#','#',' ','#',' ',' ',' ',' ','#',' ','#' },
       { '#',' ',' ',' ',' ','#','#','#',' ','#',' ',' ' },
       { '#','#','#','#',' ','#',' ','#',' ','#',' ','#' },
       { '#',' ',' ','#',' ','#',' ','#',' ','#',' ','#' },
       { '#','#',' ','#',' ','#',' ','#',' ','#',' ','#' },
       { '#',' ',' ',' ',' ',' ',' ',' ',' ','#',' ','#' },
       { '#','#','#','#','#','#',' ','#','#','#',' ','#' },
       { '#',' ',' ',' ',' ',' ',' ','#',' ',' ',' ','#' },
       { '#','#','#','#','#','#','#','#','#','#','#','#' } };
void Maze::traversal(int posx, int posy) {
 Persona walker(posx, posy);
 while(!walker.fuori()) {
  if(walker.muro_destra()) {
   if(!walker.muro_avanti())
    walker.avanza();
   else {
    if(walker.muro_sinistra())  walker.inverti();
    else walker.gira_sinistra();
   }
  }
  else walker.gira_destra();
 }
}
void Maze::print() {
 using std::cout;
 using std::endl;
 for(int i = 0; i < 12; i++) {
  for(int j = 0; j < 12; j++)
   cout << _maze[i][j];
  cout << endl;
 }
}
int main() {
 Maze labirinto;
 labirinto.print();
 labirinto.traversal(4, 11);
 labirinto.print();
 return 0;
}
==================================================
Funzione ricorsiva:
void Maze::traversal(int posx, int posy) {
 Persona walker(posx, posy);
 if(walker.fuori()) return;
 else
  if(walker.muro_destra()) {
   if(!walker.muro_avanti())
    walker.avanza();
   else {
    if(walker.muro_sinistra())  walker.inverti();
    else walker.gira_sinistra();
   }
  }
  else walker.gira_destra();
  traversal(walker.getx(), walker.gety());
 }
}
=====================================================

>Exeption unhandled: Stack overflow.
Se non ho capito male il sorgente la funzione ricorsiva viene richiamata ad ogni movimento ed e' quindi possibile che il problema sia semplicemente dovuto al fatto che lo stack e' troppo picoolo. Prova ad aumentarlo.
Sinceramente non mi sembra comunque una buona soluzione. Probabilmente la funzione ricorsiva deve essere attivata solo quando si sbatte contro un muro.
Antonio Donatiello

Sinceramente non mi sembra comunque una buona soluzione. >Probabilmente la
funzione ricorsiva deve essere attivata solo >quando si sbatte contro un
muro.
Supponi che nel labirinto ci sia un incrocio a quattro vie: da qualsiasi via
arrivo, non incontrando alcun muro, andrei dritto invece di girare a destra.
Da qui, credo, la necessità di chiamare ad ogni movimento la funzione per
controllare eventuali brecce sul lato destro.
Marco

 Come?
Devi cercare tra le opzioni del tuo compilatore.
EMG

Exeption unhandled: Stack overflow.
La ricorsione e` una tecnica elegante ma che puo` consumare
molto velocemente lo stack e questo e` cio` che sembra essere
successo a te. Prova ad aumentare la dimensione dello stack
(come fare dipende dal tuo compilatore)... occhio che un consumo
anomalo dello stack potrebbe avvenire per un errore nel
programma (che ora non ho il tempo di controllare).
Paolo
-----------------------------------------------------------------
  Paolo Marotta
  Computer Science, University of Pisa
  home:   
http://www.cli.di.unipi.it/~marotta
-----------------------------------------------------------------

>controllare eventuali brecce sul lato destro.
Giusto, allora forse ti basta attivare la ricorsione solo negli incroci. Il problema e' che se hai un labiritno 100x100 e attivi la ricorsione ad ogni passo raggiungi le migliaia di chiamate!
Per quanto riguarda come fare un labirinto (post precedente) puoi agire nel modo che segue.
- Si tratta di spostarsi casualmente nel labirinto di 2 posizioni alla volta in modo da lasciare sempre dei muri con strade di larghezza fissa.
- Quando ti sposti devi andare avanti solo se la posizione di arrivo non e' gia libera.
- Se la posizione scelta non e' libera ne scegli un'altra, etc.
- Quando arrivi ad un punto dove non ci sono piu' posizioni libere devi tornare indietro da dove sei arrivato di una posizione e ricominciare. Questo fino a quando non torni all'inizio. La posizione di partenza e' casuale (sempre scelta ogni due quadrati, cioe' ad esempio solo le posizioni dispari).
- Per sapere da dove arrivi o fai la cosa ricorsiva oppure memorizzi nel labirinto dei caratteri che ti dicono da dove sei arrivato (le molliche di una famosa favola) nel senso che ad ogni carattere corrisponde "arrivo da destra" o "arrivo da sinistra", etc.
- Se non ricodo male perche' il tutto venga bene il labiritno deve avere dimensioni di lunghezza dispari.
Spero ti essere stato abbastanza chiaro.
Antonio Donatiello

La mia impressione e' che nel tuo caso la soluzione ricorsiva non e' prorio
l'ideale.  Puoi si' aumentare lo stack per fare funzionare questo caso, ma
non puoi eliminare il problema; se la tua intenzione e' quella di scrivere un programma
in grado di risolvere un labirinto generico di N dimensioni, il problema
dello stack ce lo avrai sempre, visto che il numero di chiamate ricorsive
e' proporzionale alle dimensioni del labirinto.

l'ideale.
E' l' esercizio (preso da "How to program C++" di Deitel&Deitel) che
suggeriva di utilizzare la ricorsione. Avendo il problema con lo stack ho
quindi deciso di scriverlo iterativamente. Il mio problema era sapere se la
soluzione ricorsiva genera l'overflow per un problema di programmazione,
cioè se quest'ultima è esattamente speculare, in quanto al risultato finale
con quella iterativa.

Ho provato a "mimare" l'algoritmo che mi hai suggerito con carta e penna:
penso di aver capito e sembra funzionare. Tuttavia il labirinto in questione
avrà sicuramente un muro quando entrambe le coordinate sono dispari, mentre
negli altri punti ci possono essere casualmente muri o spazi secondo una
proporzione stabilita.
Non è forse più semplice prima riempire il labirinto di muri, quindi creare
gli spazi solo ove questi possono esistere. Io l'ho fatto così, anche se il
rapporto 1:1 tra spazi e muri raramente dà luogo a un labirinto con uscite:
   for(int i = 2; i < height; i++)
           for(int j = 2; j < width; j++) {
                  if(i%2) { //Riga dispari
                          if(j%2) maze[i][j] = (rand()%2)? '#':' '; //Col
disp
                  }
                  else maze[i][j] = (rand()%2)? '#':' ';
           }
    // posizione e direzione iniziale
   direzione = OVEST;
   _x = rand()%(height + 1);
   _y = width;
   maze[_x][_y] = ' ';
    // Uscita sul lato sinistro
   maze[rand()%(height + 1)][1] = ' ';
i cicli for cominciano da 2 perchè la matrice creata ha dimensioni (height +
2) * (width + 2) permettendomi di disporre intorno una cornice con un
simbolo diverso che indica quando si è fuori. Per semplicità l'entrata è
sempre posta sul lato a destra.
A parte il fatto che dovrei rendere l'"estrazione" di uno spazio più
probabile del 50% il risultato finale è veramente comparabile con quello
ottenibile dall'algoritmo da te suggeritomi?
Grazie ancora per la disponibilità
Marco

>rapporto 1:1 tra spazi e muri raramente dà luogo a un labirinto con uscite:
Effettivamente mi ero dimenticato di dirti di riempire all'inizio tutto il labirinto di muri.
Per quanto riguarda l'uscita se parti da posizione (1,1) e il campo ha dimensioni di lunghezza dispari sicuramente hai un punto bianco accessibile nella diagonale opposta.
Questo algoritmo e' quello che utilizzava un vecchio gioco da bar PENGO dove un pinguino spostava dei cubetti di ghiaccio (il labirinto) inseguito dai soliti cattivi.
Ciao
Antonio Donatiello