[C] Labirinto cerca uscita

[N4tty]

Salve ragazzi, sto codando un programmino in c dove devo progettare un labirinto (matrice) con n righe, m colonne e tot % di muri. Un omino all'interno che cerca di uscire andando su, giu, destra e sinistra per le posizioni libere (non in diagonale)

Come un idiota ho scritto scritto e sono andato a controllare tutto dopo aver finito... Cmq, dopo aver risolto i problemini vari, il programma viene compilato ma dà segmentation fault sulla funzione searchExit.

Questo è il code, magari qualcuno di voi con un po' di pazienza e altruismo capisce lo sbaglio e mi corregge. Grazie in anticipo.

/*Progetto per Programmazione dei Calcolatori per il corso di laurea in informatica*/

//inclusione delle librerie standard per l'input, l'output, generazione numeri casuali, ...
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

//inclusione dei file contenenti i messaggi di risposta del programma
#include "message.h"

//definisco le funzioni randomize e random, rispettivamente per inizializzare il seme random e per prendere un numero compreso tra 0 e x-1
#define random(x) rand() % x
#define randomize srand(time(NULL))

//definisco la struttura nodo (passaggi dell'omino) contenente un array di due elementi con le coordinate e un puntatore ad una struttura dello stesso tipo (nodo)
//che conterrà le coordinate precedenti ed il puntatore al precedente passaggio e così via (struttura dati pila LIFO)
typedef struct etichetta {
    
    //array di due elementi e puntatore a struttura dati nodo
    int element[2];
    struct etichetta *next;
    
} nodo;

//definizione della funzione head, che dato un puntatore a nodo in input, ritorna l'array con le coordinate attuali
int *head(nodo *l) {
    
    return l->element;
    
}

//definizione della funzione tail, che dato un puntatore a nodo come input, ritorna il puntatore al nodo precedente
nodo *tail(nodo *l) {
    
    return l->next;
    
}

//definizione della funzione empty, che data una lista, libera la memoria da essa allocata senza ritornare nulla
void empty(nodo *l) {
    
    //se è l'ultimo elemento della lista lo libero ed esco dalla funzione
    if(l->next == NULL) {
        free(l);
        return;
    }
    
    //chiamo ricorsivamente la funzione sul prossimo della lista, poi libero la memoria allocata
    empty(tail(l));
    free(l);
    
    return;
}

//definizione della funzione mostraPercorso, che dato il labirinto ed il numero di righe e colonne, mostra il percorso "visuale"
void mostraLabirinto(int *labirinto, int numrighe, int numcolonne) {
    
    //variabili indici
    int i,j;
    
    //passo tutto il labirinto e mostro solo ingresso, uscita, muri e passaggio dell'omino
    for(i=0;i<numrighe;i++) {
        for(j=0;j<numcolonne;j++) {
            
            switch(labirinto[i*numcolonne+j]) {
                
                case 0:
                    printf("||\t");
                    break;
                
                case 1:
                    printf("   \t");
                    break;
                
                case 2:
                    printf("|x|\t");
                    break;
                
                case 3:
                    printf("U\t");
                    break;
                
                case 8:
                    printf("|X|\t");
                    break;
                
                case 9:
                    printf("I\t");
                    break;
            }
        }
        printf("\n");
    }
    printf("\n");
}

//definizione della funzione push, che dato in input un puntatore a nodo e due interi contenenti le coordinate da inserire nella pila, ritorna un nuovo puntatore a nodo
//con le coordinate date in input e il puntatore che punta al nodo passato in input
nodo *push(nodo *l, int elemento1, int elemento2) {
    
    //se la lista è vuota
    if(l == NULL) {
        
        //alloco memoria per la pila e inserisco solamente le coordinate e faccio puntare next a null
        l = (nodo*) malloc(sizeof(nodo));
        l->element[0] = elemento1;
        l->element[1] = elemento2;
        l->next = NULL;
        
    //se la pila non è vuota
    } else {
        
        //creo un puntatore a nodo e alloco la memoria
        nodo *niu = (nodo*) malloc(sizeof(nodo));
        
        //copio il valore della lista attuale nel nuovo puntatore
        //poi inserisco nella pila le coordinate del passo da effettuare e faccio puntare next al puntatore creato da poco, niu
        niu->element[0] = l->element[0];
        niu->element[1] = l->element[1];
        niu->next = l->next;
        l->element[0] = elemento1;
        l->element[1] = elemento2;
        l->next = niu;
    }
    
    //ritorna la pila
    return l;
    
}

//definizione della funzione viewTail, che dato un puntatore a nodo come input, stampa tutti i passaggi percorsi dall'omino senza ritornare niente
void viewTail(nodo *l) {
    
    //se la pila è vuota, ritorna void (finisce la funzione, non c'è nessuna coordinata/passo da stampare)
    if(l == NULL)
        return;
    
    //stampa le coordinate della pila e richiama ricorsivamente la funzione con in input la coda della pila (passaggio precedente).
    printf("(%d, %d)\n", l->element[0], l->element[1]);
    viewTail(tail(l));
    
}

//definizione della funzinoe searchExit, che dato in input un puntatore a nodo, un puntatore al labirinto, il numero delle righe e delle colonne del labirinto (matrice),
//ritorna 0 se non ci sono posizioni liberi adiacenti, 1 se ci sono e muove il passo verso la posizione libera
int searchExit(nodo *l, int *labirinto, int numrighe, int numcolonne) {
    
    //inizializzazioni variabili su, giu, sinistra e destra, le coordinate contenente le posizioni adiacenti all'omino
    //inizializzazione variabili indici i e j, variabile intera contenente il numero random per la decisione del passo,
    //e una matrice possibilita contenente le coordinate delle posizione adiacenti libere
    int destra=l->element[1]+1;
    int sinistra=l->element[1]-1;
    int giu=l->element[0]+1;
    int su=l->element[0]-1;
    int i=0, j=0;
    int random=4;
    int **possibilita;
    
    //allocazione memoria per la matrice
    possibilita = (int**) malloc(4*sizeof(int*));
    for(i=0;i<4;i++) {
        possibilita[i] = (int*) malloc(2*sizeof(int));
    }
    
    //controllo che le coordinate con le posizione adiacenti non siano fuori range ( su e sinistra < 0 e giu e destra > numero righe e colonne)
    if(giu >= numrighe)
        giu=(numrighe-1);
    
    if(su < 0)
        su=0;
    
    if(destra >= numcolonne)
        destra=(numcolonne-1);
    
    if(sinistra < 0)
        sinistra=0;
    
    //setto tutte le coordinate della matrice possibilita a -1
    for(i=0;i<4;i++) {
        for(j=0;j<2;j++) {
            possibilita[i][j] = -1;
        }
    }
    
    //verifico le coordinate adiacenti se sono libere o se sono uscite, se sono uscite le inserisco nella pila ed esco dalla funzione (ho svolto il compito),
    //se sono libere le inserisco nella matrice possibilita
    
    //i sarà l'indice della matrice possibilita
    i = 0;
    
    //se la posizione è l'uscita
    if(labirinto[su*numcolonne+l->element[1]] == 3) {
        
        //inserisco nella pila le coordinate e ritorno 1
        l = push(l, su, l->element[1]);
        return 1;
        
    //se invece è una posizione libera
    } else if(labirinto[su*numcolonne+l->element[1]] == 1) {
        
        //inserisco nella matrice possibilita le coordinate della posizione, ed incremento l'indice i
        possibilita[i][0] = su;
        possibilita[i][1] = l->element[1];
        i++;
        
    }
    
    if(labirinto[giu*numcolonne+l->element[1]] == 3) {
        l = push(l, giu, l->element[1]);
        return 1;
    } else if(labirinto[giu*numcolonne+l->element[1]] == 1) {
        possibilita[i][0] = giu;
        possibilita[i][1] = l->element[1];
        i++;
    }
    if(labirinto[l->element[0]*numcolonne+destra] == 3) {
        l = push(l, l->element[0], destra);
        return 1;
    } else if(labirinto[l->element[0]*numcolonne+destra] == 1) {
        possibilita[i][0] = l->element[0];
        possibilita[i][1] = destra;
        i++;
    }
    if(labirinto[l->element[0]*numcolonne+sinistra] == 3) {
        l = push(l, l->element[0], sinistra);
        return 1;
    } else if(labirinto[l->element[0]*numcolonne+sinistra] == 1) {
        possibilita[i][0] = l->element[0];
        possibilita[i][1] = sinistra;
        i++;
    }
    
    //se non sono stati trovati passaggi accessibili (l'indice i è ancora a 0)
    if(i == 0) {
        
        //disalloco la memoria per la matrice possibilita e ritorno 0
        for(j=0;j<4;j++) {
            free(possibilita[j]);
        }
        free(possibilita);
        return 0;
        
    }
    
    //prendo il numero random tra 0 e i-1, è l'indice della riga della matrice possibilita,
    //per il movimento vengono prese le coordinate con quell'indice all'interno di possibilita
    randomize;
    random = random(i);
    
    //la posizione attuale la metto nel labirinto come 2 = posizione già percorsa, mentre setto a 8 = posizione attuale le coordinate della posizione su cui muoverò il passo
    labirinto[l->element[0]*numcolonne+l->element[1]] = 2;
    labirinto[possibilita[random][0]*numcolonne+possibilita[random][1]] = 8;
    
    //effettuo il passo inserendo nella pila le coordinate della posizione scelta tra quelle libere a random
    l = push(l, possibilita[random][0], possibilita[random][1]);
    
    //disalloco la memoria per la matrice possibilità e ritorno 1
    for(j=0;j<4;j++) {
        free(possibilita[j]);
    }
    free(possibilita);
    return 1;

}

//definisco lista come un puntatore a nodo
typedef nodo* lista;

//inizio funzione main, il programma non terminerà fino a quando l'omino non ha trovato l'uscita o l'utente avrà voluto smettere di provare a cercarla
int main(int argc, char **argv) {
    
    //definisco le variabili da utilizzare nel programma
    int i=0, j=0;                                                   //indici generali
    int *labirinto;                                                 //matrice labirinto
    int nRighe=0, nColonne=0, percentualeMuri=0;                    //righe, colonne e percentuale muri
    int scelta=0, random=0;                                         //interi per il numero random e per la scelta tra righe e colonne per la posizione di entrata dell'omino
    int xEntrata=0, yEntrata=0, xUscita=0, yUscita=0;               //coordinate di entrata e uscita
    int finePassi=0, fineMura=0;                                    //finepassi è falsa fino a quando ci sono posizioni libere e non uscite, finemura conterrà il numero di muri da mettere
    char ritenta = 'y';                                             //variabile per ritentare in caso ci si trova in una posizione bloccata
    int distanzaDalluscita=0, maxR=0, minR=0, maxC=0, minC=0;       //variabile contenente la distanza dall'uscita rispetto le coordinate attuali
    
    //inizializzo a null la variabile percorso, contenente appunto le coordinate del percorso dell'omino
    lista percorso;
    percorso = NULL;
    
    //nel richiamare l'eseguibile, devono essere passati come parametri il numero di righe, colonne e la percentuale di muri nel labirinto
    //controllo che ci siano 4 parametri
    if(argc != 4) {
        
        //se non sono 4 stampo come richiamare l'eseguibile ed esco
        EXIT_HOWTOUSE;
        return 0;
        
    //se sono 4
    } else {
        
        //imposto il numero di righe e colonne e percentuale mura come impostate dall'utente
        nRighe = atoi(argv[1]);
        nColonne = atoi(argv[2]);
        percentualeMuri = atoi(argv[3]);
        
        //calcolo il numero di muri da inserire
        fineMura = (((nRighe-2)*(nColonne-2))*percentualeMuri)/100;
        
        //controllo che l'utonto non abbia inserito valori non numerici o 0 per righe o colonne o un parametro fuori range per la percentuale ( 0-100)
        //se qualche parametro è sballato
        if((!nRighe) || (!nColonne) || (percentualeMuri < 0) || (percentualeMuri > 100)) {
            
            //stampo il messaggio di errore e di esempio utilizzo ed esco
            printf("Numero righe inserite: %d\nNumero colonne inserite: %d\nPercentuale muri: %d\n", nRighe, nColonne, percentualeMuri);
            EXIT_HOWTOUSE;
            return 0;
            
        //parametri passati quasi sicuramente corretti, inizia il programma
        } else {
            
            //alloco memoria per il labirinto a seconda dei parametri passati dall'utente
            labirinto = (int*) malloc(nRighe*nColonne*sizeof(int));
            
            //legenda labirinto:
            //0 muro, 1 posizione libera, 2 posizionei già percorsa(il tragitto dell'omino),
            //3 = uscita, 9 = entrata, 8 = posizione attuale
            
            //i muri ricoprono il perimetro del labirinto, all'interno della matrice,quindi imposto i lati del labirinto a 0
            //prima colonna e ultima a 0
            for(i=0;i<nRighe;i++) {
                labirinto[i*nColonne] = 0;
                labirinto[i*nColonne+nColonne-1] = 0;
            }
            
            //prima riga e ultima a 0
            for(i=0;i<nColonne;i++) {
                labirinto[i] = 0;
                labirinto[(nRighe-1)*nColonne+i] = 0;
            }
            
            //imposto tutto il labirinto interno(non le mura) a -1
            for(i=1;i<(nRighe-1);i++) {
                for(j=1;j<(nColonne-1);j++) {
                    labirinto[i*nColonne+j] = -1;
                }
            }
            
            //inizializzo il seme per i numeri random
            randomize;
            
            //finchè non finiscono i muri da mettere
            while(fineMura>0) {
                
                //settaggio dei muri all'interno del labirinto in base alla percentuale passata come parametro di input
                for(i=1;i<(nRighe-1);i++) {
                    for(j=1;j<(nColonne-1);j++) {
                        
                        //se le mura da mettere sono finite esco dal ciclo
                        if(fineMura <= 0)
                            break;
                        
                        //se la posizione che sto controllando è già un muro, continuo passando alla coordinata successiva
                        if(labirinto[i*nColonne+j] == 0)
                            continue;
                        
                        //pesco il numero, se è maggiore della percentuale imposto la posizione a 0 (muro) e decremento il numero di mura rimanenti
                        random = random(100) + 1;
                        if(random < percentualeMuri) {
                            labirinto[i*nColonne+j] = 0;
                            fineMura--;
                        }
                    }
                }
            }
            
            //una volta finito il numero di muri, trasformo tutti i -1 del labirinto, in 1 (posizioni libere)
            for(i=1;i<(nRighe-1);i++) {
                for(j=1;j<(nColonne-1);j++) {
                    if(labirinto[i*nColonne+j] == -1)
                        labirinto[i*nColonne+j] = 1;
                }
            }
            
            //l'omino è su di un lato del labirinto, ma non sugli angoli
            //calcolo della posizione dell'omino
            randomize;
            
            //scelta a caso: 0 l'omino è su una riga, 1 l'omino è su una colonna
            scelta = random(2);
            switch(scelta) {
                
                //prima riga
                case 0:
                    
                    //coordinata x random e y = 0
                    xEntrata = random(nRighe);
                    yEntrata = 0;
                    
                    //se x = 0 o x = numero delle righe -1, l'omino si troverebbe ad un angolo del labirinto,
                    //quindi rispettivamente nei casi vengono incrementate e decrementate di uno
                    if(xEntrata == 0)
                        xEntrata++;
                    if(xEntrata == (nRighe-1))
                        xEntrata--;
                    
                    //setto l'intero a 9 in quelle coordinate (ingresso) ed esco
                    labirinto[xEntrata*nColonne] = 9;
                    break;
                
                //prima colonna
                case 1:
                    
                    //coordinata x = 0 e y random
                    yEntrata = random(nColonne);
                    xEntrata = 0;
                    
                    //stesso discorso, l'omino potrebbe trovarsi su un angolo, in tal caso incremento-decremento
                    if(yEntrata == 0)
                        yEntrata++;
                    if(yEntrata == (nColonne-1))
                        yEntrata--;
                    
                    //setto l'intero a 9 in quelle coordinate del labirinto (ingresso) ed esco
                    labirinto[yEntrata] = 9;
                    break;
                
            }
            
            //calcolo uscita labirinto
            randomize;
            
            //scelgo un x ed un y random
            xUscita = random(nRighe);
            yUscita = random(nColonne);
            
            //se l'uscita si trova ad un angolo, è iraggiungibile, quindi in tal caso incremento/decremento la x di 1
            //caso angolo in alto a sinistra
            if(xUscita == 0 && yUscita == 0)
                xUscita++;
            //caso angolo in alto a destra
            if(xUscita == 0 && yUscita == (nColonne-1))
                xUscita++;
            //caso angolo in basso a sinistra
            if(xUscita == (nRighe-1) && yUscita == 0)
                xUscita++;
            //caso angolo in basso a destra
            if(xUscita == (nRighe-1) && yUscita == (nColonne-1))
                xUscita++;
            
            //setto l'intero a 3 in quelle coordinate calcolate random del labirinto (uscita)
            labirinto[xUscita*nColonne+yUscita] = 3;
            
            //finchè l'utente non ha deciso di rifiutare il continuamento e finepassi è a 1 (non è stata trovata l'uscita precedentemente)
            do {
                
                //rimetto finepassi a 0 in caso è già stato provato di trovare l'uscita
                finePassi = 0;
                //primo passo del percorso
                percorso = NULL;
                percorso = push(percorso, xEntrata, yEntrata);
                
                //in caso abbia già provato a trovare l'uscita, ripristino il labirinto iniziale
                for(i=0;i<nRighe;i++) {
                    for(j=0;j<nColonne;j++) {
                        if(labirinto[i*nColonne+j] == 2 || labirinto[i*nColonne+j] == 8)
                            labirinto[i*nColonne+j] = 1;
                    }
                }
                labirinto[xEntrata*nColonne+yEntrata] = 9;
                
                //finchè non si trova l'uscita o non ci sono più mosse da effettuare
                while((percorso->element[0] != xUscita || percorso->element[1] != yUscita) && (finePassi != 1)) {
                    
                    //se non ci sono più movimenti
                    if(!searchExit(percorso, labirinto, nRighe, nColonne)) {
                        
                        //stoppo il ciclo while e annuncio l'impossibilità di continuare
                        finePassi = 1;
                        NOPASS;
                    }
                    
                    //calcolo la distanza dall'uscita
                    //calcolando il maggiore tra le coordinate attuali e le coordinate di uscita, sottraendo poi dal maggiore il minore, sia
                    //per x che per y, si avrà la distanza in passi "in linea d'aria"
                    if(percorso->element[0] > xUscita) {
                        maxR = percorso->element[0];
                        minR = xUscita;
                    } else {
                        minR = percorso->element[0];
                        maxR = xUscita;
                    }
                    
                    if(percorso->element[1] > yUscita) {
                        maxC = percorso->element[1];
                        minC = yUscita;
                    } else {
                        minC = percorso->element[1];
                        maxC = yUscita;
                    }
                    
                    //calcolo differenza righe + differenza colonne
                    distanzaDalluscita = (maxR - minR) + (maxC - minC);
                    
                    //stampa labirinto a video
                    mostraLabirinto(labirinto, nRighe, nColonne);
                    
                    //dichiara la distanza dall'uscita in passi, sleep di 4 secondi e poi pulisce lo schermo
                    printf("\nDistanza dall'uscita: %d\n\n", distanzaDalluscita);
                    sleep(4);
                    system("cls");
                }
                
                //se si è trovata l'uscita (finepassi viene settato a 1 quando non ci sono più movimenti possibili, altrimenti è 0,
                //se in questo momento finepassi = 0 vuol dire che ci si trova nell'uscita)
                if(!finePassi) {
                    
                    //congratulazioni e mostra del percorso
                    YOUWON;
                    printf("Percorso effettuato:\n\n");
                    viewTail(percorso);
                    mostraLabirinto(labirinto, nRighe, nColonne);
                    
                //altrimenti si può ritentare...
                } else {
                    
                    //stampo il messaggio di fallimento, mostro il percorso effettuato e libero la memoria da esso allocata
                    //dopodichè chiedo all'utente se vuole ritentare
                    YOULOSE;
                    viewTail(percorso);
                    printf("\n\nSei arrivato %d passi lontano dall'uscita!\n\n", distanzaDalluscita);
                    mostraLabirinto(labirinto, nRighe, nColonne);
                    empty(percorso);
                    RITENTA;
                    scanf("%c", &ritenta);
                }
            } while(ritenta != 'n' && finePassi == 1); 
        }
        
        //disalloco la memoria per il labirinto e finisco
        free(labirinto);
        return 1;
    }
}

per quel qualcuno che volesse richiare il debug, metto il codice di message.h:

#define EXIT_HOWTOUSE   printf("Parametri inseriti scorrettamente\n\nrichiamare l'eseguibile inserendo dopo il numero di righe, di colonne e la percentuale di muri in questo modo: $ eseguibile righe colonne percentualemuri\n\n")
#define NOPASS          printf("Fine delle possibili mosse da parte dell'omino, non è stata trovata una via d'uscita!\n")
#define YOUWON          printf("Congratulazioni, è stato trovato il passaggio che porta all'uscita del labirinto.\n\n")
#define YOULOSE         printf("Peccato, l'omino non ha trovato la via d'uscita...\nEcco il suo percorso;\n\n")
#define RITENTA         printf("Ritentare? (Y/n)")

[clockover]

Senza che mi leggo tutto.. mi spiega la logica che hai usato in searchExit... a parole tue (o anche uno pseudocodice molto discorsivo sarebbe meglio)

[N4tty]

Allora:

praticamente è la funzione che serve a muovere l'omino all'interno del labirinto, prende come parametri un puntatore a struttura dati di tipo lista, un puntatore alla matrice labirinto, le coordinate x e y attuali e il numero totali di righe e colonne, restituisce 1 se esistono passaggi liberi (labirinto[x][y] == 1; 1 è posizione libera, 0 è muro, 2 è posizione già percorsa, 3 è uscita) o 0 altrimenti (nessun movimento possibile).

Inizializzo le variabili su, giu, sinistra e destra ( le attuali coordinate con + e -1), controllo che non siano come il numero di righe totali o minori di 0, sennò altrimenti dopo si andrebbe a cercare di confrontare un elemento che non esiste all'interno di labirinto, e le decremento/incremento in caso. Inizializzo una matrice di 4 righe e 2 colonne, che mi servirà per inserire tutti i possibili passaggi dell'omino, settando ogni elemento con -1.
Vedo se si può andare su/giu/destra/sinistra ed ogni volta che si può, metto nella matrice le due coordinate corrispondenti. Calcolo in modo random un numero da 0 a i-1 (i = numero di passaggi accessibili) e scelgo quelle coordinate come prossima mossa, modificando la posizione attuale del labirinto ( da 1 a 2, posizione già percorsa) e aggiungendo le nuove coordinate alla lista che si occupa di gestire il percorso dell'omino (richiamando push con le nuove coordinate).

Se non si è capito qualcosa ditemelo che rispiego meglio.

[clockover]

e se esiste più di un percorso, tu ne scegli uno, però non è quello giusto... come torni indietro?

[N4tty]

praticamente il programma esce dal while, con finepassi == 1, quindi senza trovare l'uscita, prima stampo il messaggio di "sconfitta" insieme al percorso effettuato, poi chiedo se si vuole riprovare, se si c'è un goto (lo so è un goto ma in questo caso è comodo) che riporta all'inizio del while

[clockover]

Si ma non fai nulla di nuovo però.. non va a riprendere un vecchio percorso... anzi pushi di nuovo la stessa cosa (te lo sto dicendo alla buona perchè non ho letto approfonditamente)

Di solito queste cose si fanno molto facilmente ricorsivamente, o se vuoi farlo iterativamente usando una pila. Nella pila andrebbe inserito ogni passaggio effettuato, in modo da poter ripristinare un vecchio percorso. Per farti un'idea di come potresti implementare un semplice algoritmo ricorsivo invece potresti dare uno sguardo qui http://en.wikipedia.org/wiki/Depth-first_search
Giusto per farti un'idea

[N4tty]

fa qualcosa di nuovo perchè la scelta del percorso è random ( se le coordinate possibili libere sono 2, vengono inserite nella matrice possibilita e viene scelta una coordinata in modo random)...
da quando inizia a cercare l'uscita il percorso salva tutti i passaggi che l'omino fa.

EDITvviamente potrei implentare un algoritmo per la ricerca del percorso in base ad uno già svolto, come quello che mi hai consigliato tu, solo che è per un progetto dell'uni e non voglio sbattermici troppo, e visto che il prof ha detto che andava bene così........ quindi mi basterebbe correggere l'errore per farlo funzionare e per capire dove ho sbagliato

[Floris]

Ciao...non ho letto i post precedenti. Ma per trovare l'uscita di un labirinto l'algoritmo più semplice è quello in cui tu scegli uno dei due muri del corridoio di entrata e poi segui sempre quel muro. Ovviamente può non essere il migliore ma è il più semplice e trova di sicuro l'uscita. (spero di essermi spiegato bene!)

[clockover]

Quello che ti avevo detto era per uno spunto.. comunque se funziona anche il tuo va bene

[N4tty]

Il problema è che da segmentation fault, e non ne riesco a capire il motivo, a me sembra che sia tutto corretto

[Floris]

In questo caso dovresti utilizzare un debugger...oppure debugghi il codice da solo mettendo qua e là un pò di output...così da individuare il segmento di codice che provoca il segmentation fault.

[banryu79]

Originariamente inviato da Floris

In questo caso dovresti utilizzare un debugger...oppure debugghi il codice da solo mettendo qua e là un pò di output...così da individuare il segmento di codice che provoca il segmentation fault.

Oppure usi Valgrind, fai prima e ti risparmi un sacco di bestemmie, ora e per sempre

[N4tty]

sto utilizzando gdb e l'errore di segmentation fault avviene durante il controllo di un elemento della matrice labirinto nella funzione searchExit, alla funzione dò la locazione della variabile puntatore a puntatore della matrice. A me sembra che la passi in modo corretto, ma a quanto pare non è così.
Voi non vedete errori in quella porzione di codice?

Il segnale di segmentation fault avviene qui:

if(*labirinto[giu][y] == 1) {

[N4tty]

ho risolto il problema del segmentation fault, ora praticamente non mi modifica la pila contenente il percorso quando faccio la push all'interno della funzione searchExit. passo il puntatore alla struttura dati nodo come parametro alla funzione searchExit definita così:

int searchExit(nodo *l, int *labirinto, int numrighe, int numcolonne)

e richiamata nel main così:

risultatoRicerca = searchExit(percorso, labirinto, nRighe, nColonne);

percorso è un puntatore alla struttura dati nodo:

typedef struct etichetta {
    
    int element[2];
    struct etichetta *next;
    
} nodo;

all'interno della funzione searchExit richiamo la push in questo modo:

l = push(l,x,y)

uguale nel main:

percorso = push(percorso, xEntrata, yEntrata);

la funzione push è così dichiarata:

nodo *push(nodo *l, int elemento1, int elemento2) {
    
    //creo il nuovo puntatore a nodo e alloco la memoria
    nodo *niu = (nodo*) malloc(sizeof(nodo));
    
    //inserisco le coordinate passate in input nell'array element e next punta al nodo passato in input
    niu->element[0] = elemento1;
    niu->element[1] = elemento2;
    niu->next = l;
    l = niu;
    
    return l;
    
}

e dovrebbe essere corretta, però nel main lavora mentre all'interno della funzione searchExit la modifica solo in quello scope, come se non agisse direttamente sulla memoria, ma io lavoro con i puntatori, stessa cosa per il labirinto che viene modificato correttamente.
Non dovrebbe andare a modificare direttamente la zona di memoria???
Riaggiorno l'intero codice al primo post, spero capiate dove ho sbagliato

[Floris]

Ricorda che se il puntatore é passato per valore e lo modifichi (cioè modifichi l'indirizzo in esso contenuto), tale modifica rimane locale alla funzione!

[N4tty]

questo non lo sapevo, allora come faccio a modificare la pila con il percorso??

se nella funzione push creo un puntatore a nodo identico alla pila e modifico la pila attuale inserendo le coordinate future e faccio puntare next alla pila vecchia va bene giusto??

Perfetto ho risolto modificando la funzione push in questo modo, così che non cambio l'indirizzo di memoria del puntatore ma solo il valore di ciò che punta

//definizione della funzione push, che dato in input un puntatore a nodo e due interi contenenti le coordinate da inserire nella pila, ritorna un nuovo puntatore a nodo
//con le coordinate date in input e il puntatore che punta al nodo passato in input
nodo *push(nodo *l, int elemento1, int elemento2) {
    
    //se la lista è vuota alloco memoria per la pila e inserisco solamente le coordinate e faccio puntare next a null
    if(l == NULL) {
        
        l = (nodo*) malloc(sizeof(nodo));
        
        l->element[0] = elemento1;
        l->element[1] = elemento2;
        l->next = NULL;
        
    //se la pila non è vuota
    } else {
        
        //creo un puntatore a nodo e alloco la memoria
        nodo *niu = (nodo*) malloc(sizeof(nodo));
        
        //copio il valore della lista attuale nel nuovo puntatore
        //poi inserisco nella pila le coordinate del passo da effettuare e faccio puntare next al puntatore creato da poco, niu
        niu->element[0] = l->element[0];
        niu->element[1] = l->element[1];
        niu->next = l->next;
        l->element[0] = elemento1;
        l->element[1] = elemento2;
        l->next = niu;
    }
    
    //ritorna la pila
    return l;
    
}

grazie floris

[Mommolo]

Originariamente inviato da N4tty

Salve ragazzi, sto codando un programmino in c dove devo progettare un labirinto (matrice) con n righe

[OT]
io eviterei il neologismo CODARE, soprattutto se parli con qualche sardo, magari cagliaritano.
scusate ma non mi potevo trattenere dalle risate

[sic2]

usa l'algoritmo di BFS per trovare l'uscita.

troverai migliaia di informazioni nel web

[N4tty]

Originariamente inviato da sic2

usa l'algoritmo di BFS per trovare l'uscita.

troverai migliaia di informazioni nel web

Non decido io le specifiche del programma, ogni posizione già percorsa non può essere ripercorsa, a meno che si riprovi dall'inizio a cercare l'uscita.
Cmq l'ho finito, metto il codice intero al primo post.