start     Articole     Despre mine    

Drumul spre iesirea din labirint

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.)

(Browserul tau nu suporta Canvas!…)

 

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.

(Nu trimit spam; email-ul tau e in siguranta.)

 

Cu drag,

Florin Bîrleanu





0 comments