[Algoritmo] Controllare l'unione di 2 estremi

[Giupoz]

Ragazzi colgo l'occasione per augurarvi un buon Natale.
Sto creando un gioco in C che si chiama Twixt. Vi spiego brevemente la situazione:
il campo di gioco è una matrice di caratteri 24x24 inizializzata con i caratteri "-".
Ci sono 2 giocatori, a cui vengono assegnati la pedina "O" e la pedina "X".
Devo fare l'algoritmo (che poi comunque dovrò tradurre in codice) che definisco di "controllo", ovvero devo far si che il programma riconosca che il lato superiore e quello inferiore siano collegati da una linea continua di caratteri "X" (in questo caso vince il giocatore a cui viene assegnata la pedina X) oppure riconosca che il lato sinistro e destro siano uniti dai caratteri "O" (vince il secondo giocatore).

Come devo fare? Devo inserire tutti i probabili e possibili collegamenti? Non riesco a ideare un algoritmo più generico, datemi qualche idea :(

PS:**Cosa intendo per collegare 2 estremi? Che ad esempio la riga 0 della matrice venga collegata all'ultima riga della matrice attraverso una linea continua di caratteri uguali. Ogni pedina può essere collegata ai lati (sx,dx, up, down) oppure sui 4 estremi delle diagonali, quindi ogni pedina ha 8 possibili collegamenti.
Spero di essermi fatto capire :(

[Giupoz]

up :(

[clockover]

La tua "pedina" se parte da sopra vi ci può ritornare? Cioè può mettere la retromarcia?

[Giupoz]

Leggi qui, ho messo anche delle foto per farmi capire meglio: http://www.iprogrammatori.it/forum-programmazione/cplusplus/aiuto-algoritmo-t19086.html

ho a disposizione più pedine. E' più come forza quattro, non come dama dove le pedine si spostano. Qui restano fisse...

[clockover]

Una sola cosa: un giocatore può cominciare solo dall'alto andando verso il basso e da sx verso dx, o si può partire anche dal basso o da dx?

[Giupoz]

puoi partire anche dal centro, hai libero arbitrio :)

[clockover]

Come algoritmo di controllo puoi fare un metodo ricorsivo del tipo


boolean funzione_ricorsiva(matrice, riga, colonna, riga_pr, colonna_pr, giocatore){
if giocatore == "X" && ultima riga || giocatore == "O" && ultima colonna
return true; // vuol dire che ha raggiunto la fine
//controlli tutti i lati escluso quello da cui vieni altrimenti torni indietro(quindi riga_pr e colonna_pr)
//quindi dovrai prevedere almeno gli 8 casi nella funzione e scartare eventuali limiti di riga e colonna
//esempio
if( riga + 1 < max_righe && matrice[riga + 1][colonna] == giocatore )
return funzione_ricorsiva(matrice, riga + 1, colonna, riga, colonna, giocatore)
if( colonna + 1 <= max_colonne && matrice[riga][colonna + 1] == giocatore )
return funzione_ricorsiva(matrice, riga, colonna + 1, riga, colonna, giocatore)
..... //e così via tenendo conto ovviamente nei controlli
return false;

Ovviamente questo algoritmo è valido anche per quanto l'altro giocatore, basta usare una variabile giocatore che può essere X o O
Non so se funziona bene ma di sicuro ha bisogno di ritocchi, ma l'idea di base dovrebbe essere giusta

[Giupoz]

Ok ti ringrazio, in serata lo trasformo in codice e vedo se ho bisogno di qualcosa, sei stato gentilissimo! :)

[clockover]

Di nulla

Inviato dal mio Nexus 5 utilizzando Tapatalk

[Giupoz]

C'è un problema...
http://i41.tinypic.com/fpck8j.jpg

Se il programma deve controllare che ogni pedina sia seguita da un'altra pedina escludendo quella precedente, come faccio se il sentiero si biforca come nell'immagine? Bel problema :doh:
Mi sta mandando in crisi questo gioco... Agli altri studenti il prof ha assegnato giochi molto più facili di carte spiegati anche sul libro, quindi non devono fare praticamente nulla, e io mi sto uccidendo l'anima :muro:

[clockover]

C'è un problema...
http://i41.tinypic.com/fpck8j.jpg

Se il programma deve controllare che ogni pedina sia seguita da un'altra pedina escludendo quella precedente, come faccio se il sentiero si biforca come nell'immagine? Bel problema :doh:
Mi sta mandando in crisi questo gioco... Agli altri studenti il prof ha assegnato giochi molto più facili di carte spiegati anche sul libro, quindi non devono fare praticamente nulla, e io mi sto uccidendo l'anima :muro:

L'algoritmo che ti ho scritto è ricorsivo. Bisogna solo modificarlo un pochino. Se stai facendo questo tipo di progettino sai di cosa sto parlando giusto?

[Giupoz]

Si, so come farlo ricorsivo, sto spremendo le meningi ma trovo sempre falle... Domani a mente fresca vedo se riesco ad arrivarci... Ti tengo aggiornato :)

[wingman87]

A quell'algoritmo devi aggiungere una cosa: quando controlli una cella valida devi contrassegnarla in modo da non passarci più, altrimenti potresti generare dei cicli infiniti. Basta tenere una matrice di supporto inizialmente vuota in cui segni le celle visitate. Poi lanci l'algoritmo su ogni cella della prima riga/colonna (a seconda del giocatore) e vedi se ritorna true almeno una volta.

[Giupoz]

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);
}
}

[clockover]

Guarda non ho letto il tuo codice, ma a primo impatto non mi sembra andare bene. Per farti capire bene cosa devi fare, hai mai fatto un algoritmo per la visita di un albero n-ario? Questa cosa è molto simile.

[Giupoz]

no non ne abbiamo mai parlato con il prof :(