Recursive Backtracker Maze Generator

Algoritmul de backtracker recursiv este într-adevăr o căutare generală în profunzime. Când este folosit pentru generarea labirintului, acesta s-a modificat ușor pentru a alege calea la întâmplare, în timp ce dacă este folosit în scopuri de căutare efective, de obicei ar căuta doar fiecare nivel în ordine liniară. Are tendința de a produce labirinturi cu coridoare lungi și întortocheate și o soluție foarte lungă, răsucitoare.

Un labirint perfect este un labirint în care există exact o singură cale de la orice punct din labirint la orice alt punct. Aceasta înseamnă că nu puteți ajunge să vă învârtiți în cerc, dar veți întâlni adesea fundături, forțându-vă să vă întoarceți.

Hărțile labirintului generate aici includ o versiune implicită fără poziții de început și de sfârșit, astfel încât să le puteți decide singuri: va exista o soluție din orice punct al labirintului către orice alt punct. Dacă doriți să vă inspirați, puteți activa o poziție de început și de sfârșit sugerată - și chiar să vedeți soluția între cele două.

Algoritmul de backtracker recursiv este o metodă de căutare în profunzime pentru a genera labirinturi perfecte (labirinturi fără bucle și o singură cale între oricare două puncte). Este simplu, eficient și produce labirinturi atrăgătoare din punct de vedere vizual, cu coridoare lungi și întortocheate.

În ciuda numelui său, nu trebuie neapărat implementat folosind recursiunea. Este adesea implementat într-o abordare iterativă folosind o coadă LIFO (adică o stivă). Pentru labirinturile foarte mari, utilizarea recursiunii are mai multe șanse să ducă la depășirea stivei de apeluri, în funcție de limbajul de programare și de memoria disponibilă. O coadă LIFO poate fi adaptată mai ușor pentru a gestiona cantități mari de date, chiar păstrând coada pe disc sau într-o bază de date dacă memoria disponibilă este insuficientă.

Cum funcționează

Algoritmul funcționează folosind o abordare de căutare bazată pe stivă, în primul rând în profunzime. Iată defalcarea pas cu pas:

1. Alegeți o celulă de pornire și marcați-o ca vizitată.
2. În timp ce există celule nevizitate:
   • Uită-te la celulele învecinate care nu au fost încă vizitate.
   • Dacă există cel puțin un vecin nevizitat:
     • Alegeți la întâmplare unul dintre vecinii nevizitați.
     • Îndepărtați peretele dintre celula curentă și vecinul ales.
     • Treceți la vecinul ales și marcați-l ca vizitat.
     • Împingeți celula curentă pe stivă.
   • Dacă nu există vecini nevizitați:
     • Întoarceți-vă înapoi prin scoaterea ultimei celule din stivă.
3. Continuați acest proces până când stiva este goală.

Un fapt interesant despre acest algoritm este că funcționează atât ca generator de labirint, cât și ca rezolvator de labirint. Dacă îl rulați pe un labirint deja generat și doar vă opriți când atingeți punctul final decis, stiva va conține soluția labirintului.

De fapt, am două versiuni ale acestui algoritm în joc pe acest site: o coadă LIFO pentru generarea de labirinturi pe această pagină și una bazată pe recursivitate pentru rezolvarea labirinturilor, de asemenea labirinturi generate de alți algoritmi (așa se fac hărțile cu soluțiile). A avea două versiuni diferite este doar pentru sport pentru că sunt un tocilar căruia îi pare interesant, oricare ar fi putut funcționa pentru ambele ;-)