C, aiuto algoritmo

di il
9 risposte

C, aiuto algoritmo

Salve ragazzi, colgo l'occasione per augurarvi un buon natale.
Ieri ho scoperto questo forum nella disperata ricerca di un aiuto per una consegna da fare entro il 6 Gennaio (devo sostenere un'esame di C).
In pratica facendo il progetto con il professore devo sviluppare un gioco in C. Mi è stato assegnato il gioco Twixt
Ho sviluppato il codice, che potete trovare qui:
basta cliccare su "Scarica: Giusto.txt" se volete dare un'occhiata. L'ho messo sul txt così ognuno può copiarlo nel proprio compilatore.
Arriviamo al problema.
un possibile caso di vittoria è questo:
Come faccio a creare una funzione di controllo che riconosca che un giocatore abbia vinto?
Un giocatore vince quando collega 2 lati opposti della matrice (il giocatore 1 up-down con le pedine "X", il giocatore 2 sinistra e destra con la pedina "O")
Sto impazzendo, non riesco a trovare una soluzione!!!!

9 Risposte

  • Re: C, aiuto algoritmo


    In più l'algoritmo dovrebbe essere in grado di gestire 2 sentieri nel caso in cui questi si biforcano!!!
  • Re: C, aiuto algoritmo

    Quando viene inserita una pedina fai partire una funzione ricorsiva che chiama se stessa passandogli un primo puntatore int che sia settato a zero prima di richiamare la funzione per la prima volta,un secondo parametro che identifichi la casella nella posizione x e una nella posizione y.
    Tale funzione ritornerà 0 se non trova niente o 1 se trova un'altra pedina richiamandosi ricorsivamente.In caso che tocchi un suo bordo allora aggiungi 1 al valore.
    (forse mi spiego meglio con dello pseudo code)Otterrai circa una cosa cosi:
    
    void cercavittoria(int* okup,int* okdown,int x,int y)
    {
        if (mappa[y][x] != PLAYER1) return ;
        if (x + 1 < MAPPAWIDTH - 1 && mappa[y][x+1] == PLAYER1) cercavittoria(okup,okdown,x+1,y);
        if (x > 0 && mappa[y][x-1] == PLAYER1) cercavittoria(okup,okdown,x-1,y);
        if (y + 1 < MAPPAHEIGHT +1 &&  mappa[y+1][x] == PLAYER1) cercavittoria(okup,okdown,x,y+1);
        if (y -1 > 0 && mappa[y-1][x] == PLAYER1) cercavittoria(okup,okdown,x,y-1);
        if ( y == BORBOALTOPLAYER1) 
            *okup =1;
        else if ( y == BORBOBASSOPLAYER1)
            *okdown = 1; 
    }
    
    ....
    ....
    void mettipedina(...,x,y)
    {
        ....metto la pedina
        int bup = 0;
        int bdw = 0;
        cercavittoria(&bup,&bdw,x,y);
        if (bup && bdw)  ScatenaVittoria()
    }
    
    attenzione il codice postato può creare un loop infinito in base al disegno generatosi sulla mappa,questo vuole essere solo un indirizzamento alla risoluzione del problema.
  • Re: C, aiuto algoritmo

    Ok forse ho capito, provo a metterlo in pratica, gentilissimo
  • Re: C, aiuto algoritmo

    Dici che così andrebbe bene?
    
    	if campo [riga +1][colonna -1] == 'X'
    		{
    			if (riga == SIZE-1)
    				{
    					scatena_vittoria ();
    				}
    			else
    				{
    					campo [riga +1][colonna -1] == '*';
    					riga = riga + 1;
    					colonna = colonna -1;
    					controlla_vittoria (riga, colonna);
    				}		
    		}
    	if campo [riga + 1][colonna +1] == 'X'
    		{
    			if (riga == SIZE-1)
    				{
    					scatena_vittoria ();
    				}
    			else
    				{
    					campo [riga + 1][colonna +1] == '*';
    					riga = riga +1;
    					colonna = colonna +1;
    					controlla_vittoria (riga, colonna);
    				}
    		}
    	if campo [riga +1][colonna] == 'X'
    		{		
    			if (riga == SIZE-1)
    				{
    					scatena_vittoria ();
    				}
    			else
    				{
    				campo [riga +1][colonna] == '*';
    					riga = riga +1;
    					controlla_vittoria (riga, colonna);
    				}
    		}
    	if campo [riga][colonna -1] == 'X'
    		{
    			if (riga == SIZE-1)
    				{
    					scatena_vittoria ();
    				}
    			else
    				{
    					campo [riga][colonna -1] == '*';
    					colonna = colonna -1;
    					controlla_vittoria (riga, colonna);
    				}
    		}
    	if campo [riga][colonna +1] == 'X'
    		{
    			if (riga == SIZE-1)
    				{
    					scatena_vittoria ();
    				}
    			else
    				{
    					campo [riga][colonna +1] == '*';
    					colonna = colonna +1;
    					controlla_vittoria (riga, colonna);
    				}
    		}
    	if campo [riga-1][colonna -1] == 'X'
    		{
    			if (riga == SIZE-1)
    				{
    					scatena_vittoria ();
    				}
    			else
    				{
    					campo [riga-1][colonna -1] == '*';
    					riga = riga -1;
    					colonna = colonna -1;
    					controlla_vittoria (riga, colonna);
    				}
    		}
    	if campo [riga-1][colonna +1] == 'X'
    		{
    			if (riga == SIZE-1)
    				{
    					scatena_vittoria ();
    				}
    			else
    				{
    					campo [riga-1][colonna +1] == '*';
    					riga = riga -1;
    					colonna = colonna -1;
    					controlla_vittoria (riga, colonna);
    				}
    		}
    	if campo [riga-1][colonna +1] == 'X'
    		{
    			if (riga == SIZE-1)
    				{
    					scatena_vittoria ();
    				}
    			else
    				{
    					campo [riga-1][colonna +1] == '*';
    					riga = riga -1;
    					colonna = colonna +1;
    					controlla_vittoria (riga, colonna);
    				}
    		}
    
  • Re: C, aiuto algoritmo

    Posta l'intera funzione controlla_vittoria comprensiva di intestazione.

    mi sembra di capire che da quel codice scateni la vittoria avendo una pedina da un solo margine,invece la linea deve unire i due margini.
    cambiando effettivamente il valore di riga e colonna i sucessivi if avranno un valore diverso da quello aspettato.
    Manca anche una matrice su cui controllare il percorso fatto.
    
    void cercavittoria(int **walker,int* okup,int* okdown,int x,int y)
    {
        if (mappa[y][x] != PLAYER1) return ;
        if (walker[y][x]) return;
       walker[y][x] = 1;
        if (x + 1 < MAPPAWIDTH - 1 && mappa[y][x+1] == PLAYER1) cercavittoria(okup,okdown,x+1,y);
        if (x > 0 && mappa[y][x-1] == PLAYER1) cercavittoria(okup,okdown,x-1,y);
        if (y + 1 < MAPPAHEIGHT +1 &&  mappa[y+1][x] == PLAYER1) cercavittoria(okup,okdown,x,y+1);
        if (y -1 > 0 && mappa[y-1][x] == PLAYER1) cercavittoria(okup,okdown,x,y-1);
        if ( y == BORBOALTOPLAYER1) 
            *okup =1;
        else if ( y == BORBOBASSOPLAYER1)
            *okdown = 1; 
    }
    
    naturalmente la matrice walker dovrà essere azzerata prima del primo avvio della funzione ricorsiva.
  • Re: C, aiuto algoritmo

    Non riesco a copiare il contenuto della matrice "campo" su una matrice sulla quale far funzionare la funzione di controllo. Non so perchè, eppure mi sembra tutto giusto....
    Comunque la mia idea è quella (almeno per il giocatore "X", per l'altro andrà invertita) di cercare nella prima riga della matrice. Appena vede una pedina fa tutto il controllo, quindi verifica se vi sia un percorso. Se non vi è un percorso finisce la ricerca nella riga, aumentando di volta in volta la colonna. Appena trova un'altra pedina rifà tutto il controllo.
    PS: per escludere la pedina precedente durante il controllo l'unica idea che mi sia venuta è quella di trasformarla in un carattere diverso rispetto a quello della pedina!
    
    void controlla_vittoria (int riga, int colonna, char campo [][SIZE])
    {
    	char matrice[SIZE][SIZE];  //crea una copia del campo
    	char c;
    	if (riga == 0)
    		{
    			int x, y= 0;
    			while (x < SIZE)
    				{
    					while (y < SIZE)
    						{
    							c = campo [x][y];
    							matrice [x][y] = c;
    							y++;
    							system ("pause");
    						}
    					x++;
    				}
    		}
    
    		printf ("\n%3c *********", matrice [0][2]);
    		system ("pause");
    	while (matrice [riga][colonna] != 'X') 
    		{
    			colonna ++;
    		}
    			if (campo [riga +1][colonna -1] == 'X')
    				{
    					if (riga == SIZE-1)
    						{
    							scatena_vittoria ();
    						}
    					else
    						{
    							campo [riga +1][colonna -1] == '*';
    							riga = riga + 1;
    							colonna = colonna -1;
    							controlla_vittoria (riga, colonna, campo);
    						}		
    				}
    			if (campo [riga + 1][colonna +1] == 'X')
    				{
    					if (riga == SIZE-1)
    						{
    							scatena_vittoria ();
    						}
    					else
    						{
    							campo [riga + 1][colonna +1] == '*';
    							riga = riga +1;
    							colonna = colonna +1;
    							controlla_vittoria (riga, colonna, campo);
    						}
    				}
    			if (campo [riga +1][colonna] == 'X')
    				{
    							
    					if (riga == SIZE-1)
    						{
    							scatena_vittoria ();
    						}
    					else
    						{
    							campo [riga +1][colonna] == '*';
    							riga = riga +1;
    							controlla_vittoria (riga, colonna, campo);
    						}
    				}
    			if (campo [riga][colonna -1] == 'X')
    				{
    					if (riga == SIZE-1)
    						{
    							scatena_vittoria ();
    						}
    					else
    						{
    							campo [riga][colonna -1] == '*';
    							colonna = colonna -1;
    							controlla_vittoria (riga, colonna, campo);
    						}
    				}
    			if (campo [riga][colonna +1] == 'X')
    				{
    					if (riga == SIZE-1)
    						{
    							scatena_vittoria ();
    						}
    					else
    						{
    							campo [riga][colonna +1] == '*';
    							colonna = colonna +1;
    							controlla_vittoria (riga, colonna, campo);
    						}
    				}
    			if (campo [riga-1][colonna -1] == 'X')
    				{
    					if (riga == SIZE-1)
    						{
    							scatena_vittoria ();
    						}
    					else
    						{
    							campo [riga-1][colonna -1] == '*';
    							riga = riga -1;
    							colonna = colonna -1;
    							controlla_vittoria (riga, colonna, campo);
    						}
    				}
    			if (campo [riga-1][colonna +1] == 'X')
    				{
    					if (riga == SIZE-1)
    						{
    							scatena_vittoria ();
    						}
    					else
    						{
    							campo [riga-1][colonna +1] == '*';
    							riga = riga -1;
    							colonna = colonna -1;
    							controlla_vittoria (riga, colonna, campo);
    						}
    				}
    			if (campo [riga-1][colonna +1] == 'X')
    				{
    					if (riga == SIZE-1)
    						{
    							scatena_vittoria ();
    						}
    					else
    						{
    							campo [riga-1][colonna +1] == '*';
    							riga = riga -1;
    							colonna = colonna +1;
    							controlla_vittoria (riga, colonna, campo);
    						}
    				}
    
    }
  • Re: C, aiuto algoritmo

    Non riesco a copiare il contenuto della matrice "campo" su una matrice sulla quale far funzionare la funzione di controllo. Non so perchè, eppure mi sembra tutto giusto....
    Non devi copiare niente!
    Devi solo settarla a zero,la matrice che ho chiamato walker è una matrice di sicurezza che memorizza i passi fatti precedentemente in modo da non rifarli.Questo serve per evitare loop infiniti.
    Comunque la mia idea è quella (almeno per il giocatore "X", per l'altro andrà invertita) di cercare nella prima riga della matrice. Appena vede una pedina fa tutto il controllo, quindi verifica se vi sia un percorso. Se non vi è un percorso finisce la ricerca nella riga, aumentando di volta in volta la colonna. Appena trova un'altra pedina rifà tutto il controllo.
    Non è proprio un'idea ottima,anche se ti sembra di semplificare il progetto in realtà lo complichi inutilmente.
    PS: per escludere la pedina precedente durante il controllo l'unica idea che mi sia venuta è quella di trasformarla in un carattere diverso rispetto a quello della pedina!
    E come fai a tornare indietro?

    Avresti dovuto modificare il codice che ti ho postato,dato che è già un'ottima soluzione,forse non la piu efficiente ma almeno funzionale.
    
    void controlla_vittoria (int* upck,int* dwck,int r, int c,char walk [][SIZE])
    {
        if (campo[r][c] != 'X') return;
        if (walk[r][c]) return;
        walk[r][c] = 1;
        
        if (c + 1 < SIZE - 1 && campo[r][c + 1] == 'X') 
            controlla_vittoria(upck,dwck,r,c + 1,walk);
        
        if (c > 0 && campo[r][c - 1] == 'X')
            controlla_vittoria(upck,dwck,r,c - 1,walk);
            
        if (r + 1 < SIZE - 1 &&  campo[r + 1][c] == 'X') 
            controlla_vittoria(upck,dwck,r + 1,c,walk);
            
        if (r - 1 > 0 && campo[r - 1][c] == 'X')
            controlla_vittoria(upck,dwck,r + 1,c,walk);
            
        if ( r == 0)
            *upck = 1;
        else if ( r == SIZE - 1)
            *dwck = 1; 
    }
    
    //nella funzione che posiziona la pedina,dopo aver creato anche la riga di collegamento devi aggiungere
    ...
    ...
    ...
    
        char w[SIZE][SIZE];
        int ir,ix;
        //azzero walker
        for (ir = 0 ; ir < SIZE ; ir++ )
            for (ix = 0 ; ix < SIZE ; ix++ )
                w[ir][ix] = 0;
        
        //controlli raggiungimento bordi
        int ckup,ckdw;
        //r,c sono l'esatta posizione della pedina che ha posizionato il player
        controlla_vittoria(&ckup,&ckdw,r,c,w);
        if (ckup && ckdw)
            scatena_vittoria();
    
    Come vedi usando questa tecnica il codice rimane semplice e pulito.
    L'unica cosa da controllare che non ho capito è che realmente la riga di vittoria sia la 0,e SIZE-1, altrimenti dovrai modificarlo in base alle tue esigenze.
    Prima di fare un cut/paste inutile, prova a comprendere come funziona e se non sono riuscito a spiegarmi in qualche parte chiedi pure.
  • Re: C, aiuto algoritmo

    Sisi, ho capito quello che hai fatto, è più o meno quello che volevo fare io
    Thanks
  • Re: C, aiuto algoritmo

    Con tutte ste birre finisco per ubriacarmi
Devi accedere o registrarti per scrivere nel forum
9 risposte