Mai tii minte jocul de labirint de aici? Scopul jucatorului era sa mute (folosind drept “sageti” tastele ‘a’, ‘s’, ‘d’ si ‘w’) omuletul verde pana cand acesta ajunge la cutia rosie. Te-ai intrebat cumva daca ar fi posibil sa programezi omuletul sa isi gaseasca singur drumul prin labirint? Sigur ca se poate. Iata aici cum am facut asta cu ajutorul unei tehnici de programare numita backtracking.
Ideea e urmatoarea: In fiecare pozitie omuletul are patru directii posibile pe care le poate urma. Le va urma pe rand in ordinea (0) sus, (1) stanga, (2) jos, (3) dreapta. Va urma o directie daca asta nu presupune intoarcerea in pozitia vizitata imediat inainte si daca nu e zid in noua pozitie. Folosesc o stiva pentru a memora alegerea directiei de mers din pozitia curenta. La deplasarea intr-o noua pozitie introduc un nou element in stiva si pun in el valoarea 0 (adica se va incerca mai intai deplasarea in sus). In momentul in care pentru o pozitie s-au incercat toate cele 4 directii posibile, scot un element din stiva si intorc omuletul in pozitia imediat anterioara.
Iata programul in actiune! 🙂 (Apasa butonul “Reseteaza…” pentru a incarca programul in caseta din stanga, iar apoi apasa butonul “Executa…” pentru a vedea cum omuletul verde incearca toate drumurile posibile din labirint.)
// +----------------------------+
// | Cautare drum prin labirint |
// +----------------------------+
// –> Definire variabile:
// omuletul
var ox;
var oy;
// destinatia
var dx;
var dy;
// traseul si peretii
var mp = Matrice(12, 12);
// variabile ajutatoare
var l;
var c;
// stiva pentru memorarea directiilor incercate
var stack;
var top;
// –> Initializari variabile:
// omuletul
ox = 1;
oy = 1;
// destinatia
dx = 10;
dy = 10;
// traseul si peretii
l = 1;
while (l<=10)
{
c = 1;
while (c<=10)
{
mp[l][c] = 0;
c = c+1;
}
l = l+1;
}
l = 0;
while (l<=11)
{
mp[0][l] = 1;
mp[l][11] = 1;
mp[11][l] = 1;
mp[l][0] = 1;
l = l+1;
}
mp[1][1]=1; mp[2][1]=1; mp[3][1]=1; mp[4][1]=1;
mp[5][1]=1; mp[6][1]=1; mp[7][1]=1; mp[8][1]=1;
mp[9][1]=1; mp[2][2]=1; mp[6][2]=1; mp[9][2]=1;
mp[2][3]=1; mp[4][3]=1; mp[6][3]=1; mp[8][3]=1;
mp[9][3]=1; mp[4][4]=1; mp[8][4]=1; mp[9][2]=1;
mp[2][5]=1; mp[3][5]=1; mp[4][5]=1; mp[5][5]=1;
mp[6][5]=1; mp[8][5]=1; mp[10][5]=1; mp[2][6]=1;
mp[4][6]=1; mp[8][6]=1; mp[2][7]=1; mp[4][7]=1;
mp[5][7]=1; mp[6][7]=1; mp[8][7]=1; mp[9][7]=1;
mp[2][8]=1; mp[9][8]=1; mp[2][9]=1; mp[4][9]=1;
mp[5][9]=1; mp[6][9]=1; mp[7][9]=1; mp[8][9]=1;
mp[9][9]=1; mp[2][10]=1;
// stiva pentru directiile incercate
stack = Vector(101);
top = 0;
stack[top] = 3;
top = top+1;
stack[top] = 0;
// –> Desenare interfata:
// desenare pereti
l = 1;
while (l<=10)
{
c = 1;
while (c <= 10)
{
if (mp[l][c] == 0)
{
Stinge(c, 11-l);
}
else
{
Aprinde(c, 11-l, NEGRU);
}
c = c+1;
}
l = l+1;
}
// desenare destinatie
Aprinde(dx, dy, ROSU);
// desenare omulet
Aprinde(ox, oy, VERDE);
// –> Definire functie animatie:
// (Cautare drum labirint)
function FunctieDesenare()
{
if (TimpScurs(1000/7) == 1)
{
var ok = 0;
while (ok != 1)
{
if (stack[top] == 0) // mergi in sus
if (stack[top-1] != 2)
{
if (mp[11-(oy+1)][(ox)] != 1)
{
Stinge(ox, oy); oy = oy+1; Aprinde(ox, oy, VERDE);
top = top+1; stack[top] = 0;
ok = 1;
}
else stack[top] = stack[top]+1;
}
else stack[top] = stack[top]+1;
else if (stack[top] == 1) // mergi la stanga
if (stack[top-1] != 3)
{
if (mp[11-(oy)][(ox-1)] != 1)
{
Stinge(ox, oy); ox = ox-1; Aprinde(ox, oy, VERDE);
top = top+1; stack[top] = 0;
ok = 1;
}
else stack[top] = stack[top]+1;
}
else stack[top] = stack[top]+1;
else if (stack[top] == 2) // mergi in jos
if (stack[top-1] != 0)
{
if (mp[11-(oy-1)][(ox)] != 1)
{
Stinge(ox, oy); oy = oy-1; Aprinde(ox, oy, VERDE);
top = top+1; stack[top] = 0;
ok = 1;
}
else stack[top] = stack[top]+1;
}
else stack[top] = stack[top]+1;
else if (stack[top] == 3) // mergi la dreapta
if (stack[top-1] != 1)
{
if (mp[11-(oy)][(ox+1)] != 1)
{
Stinge(ox, oy); ox = ox+1; Aprinde(ox, oy, VERDE);
top = top+1; stack[top] = 0;
ok = 1;
}
else stack[top] = stack[top]+1;
}
else stack[top] = stack[top]+1;
else if (stack[top] == 4) // intoarce-te cu un pas inapoi
{
if (top > 1)
{
top = top-1;
Stinge(ox, oy);
if (stack[top] == 0)
{oy = oy-1; Aprinde(ox, oy, VERDE); stack[top] = stack[top]+1;}
else if (stack[top] == 1)
{ox = ox+1; Aprinde(ox, oy, VERDE); stack[top] = stack[top]+1;}
else if (stack[top] == 2)
{oy = oy+1; Aprinde(ox, oy, VERDE); stack[top] = stack[top]+1;}
else if (stack[top] == 3)
{ox = ox-1; Aprinde(ox, oy, VERDE); stack[top] = stack[top]+1;}
else Aprinde(ox, oy, GRI); // will never happen.
}
else Aprinde(ox, oy, ALBASTRU);
ok = 1;
}
else
{
Aprinde(ox, oy, GRI); // will never happen.
ok = 1; // but just in case...
}
}
}
Animeaza(FunctieDesenare);
}
StartAnimatie(FunctieDesenare);
Te-ai fi gandit ca e asa de simplu sa gasesti drumul printr-un labirint? 🙂
(Glumesc — stiu ca nu e chiar simplu. Dar cu un pic de efort si multa pasiune iti vei gasi repede drumul personal prin “labirintul” programarii.)
Alatura-te celor peste 5000 de oameni din armata noastra de creiere cu muschi si vei primi testul care iti va spune daca ai sau nu minte de programator.
In plus, vei fi mereu la curent cu tot ce pun la cale.
Cu drag,
Florin Bîrleanu
Ai creier de PROGRAMATOR? Hai în
