Recursive Backtracker Maze Generator

Algoritmul recursiv de căutare inversă este, de fapt, o căutare generală în profunzime. Atunci când este utilizat pentru generarea de labirinturi, este ușor modificat pentru a alege calea la întâmplare, în timp ce, dacă este utilizat în scopuri de căutare reale, de obicei, fiecare nivel ar fi căutat în ordine liniară. Tinde să producă labirinturi cu coridoare lungi și întortocheate și o soluție foarte lungă și întortocheată.

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 recursiv backtracker este o metodă de căutare în profunzime pentru generarea de labirinturi perfecte (labirinturi fără bucle și cu o singură cale între oricare două puncte). Este simplu, eficient și produce labirinturi atractive din punct de vedere vizual, cu coridoare lungi și întortocheate.

În ciuda numelui său, nu trebuie neapărat să fie implementată folosind recursivitatea. Este adesea implementată într-o abordare iterativă folosind o coadă LIFO (adică o stivă). Pentru labirinturi foarte mari, utilizarea recursivității este mai probabil să ducă la depășirea stivei de apeluri, în funcție de limbajul de programare și de memoria disponibilă. O coadă LIFO poate fi mai ușor adaptată pentru gestionarea unor 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 în profunzime bazată pe stivă. Iată o defalcare pas cu pas:

1. Alegeți o celulă de pornire și marcați-o ca vizitată.
2. Cât timp există celule nevizitate: Priviți celulele vecine care nu au fost încă vizitate. Dacă există cel puțin un vecin nevizitat: Alegeți aleatoriu unul dintre vecinii nevizitați. Îndepărtați peretele dintre celula curentă și vecinul ales. Mutați-vă la vecinul ales și marcați-l ca vizitat. Împingeți celula curentă în stivă. Dacă nu există vecini nevizitați: Reveniți prin eliminarea 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 labirinturi, cât și ca rezolvitor de labirinturi. Dacă îl rulați pe un labirint deja generat și îl opriți pur și simplu când atingeți punctul final stabilit, stiva va conține soluția labirintului.

De fapt, am două versiuni ale acestui algoritm în lucru pe acest site: una bazată pe coadă LIFO pentru generarea de labirinturi pe această pagină și una bazată pe recursivitate pentru rezolvarea labirintului, dar și a labirintului generat de alți algoritmi (așa sunt realizate hărțile cu soluțiile). A avea două versiuni diferite este doar pentru sport, pentru că sunt un tocilar care găsește asta interesant, oricare dintre ele ar fi putut funcționa pentru ambele ;-)

Lectură suplimentară

Dacă ți-a plăcut această postare, s-ar putea să-ți placă și aceste sugestii:

• Generator de labirint al algoritmului de creștere a arborilor
• Generatorul de labirint al algoritmului lui Eller
• Generatorul de labirint al algoritmului lui Wilson