Generatorul de labirint de vânătoare și ucidere

Algoritmul Hunt and Kill este, de fapt, o versiune modificată a algoritmului Recursive Backtracker. Modificarea constă în scanarea sistematică (sau „vânarea”) unei noi celule pentru a continua din momentul în care nu mai poate merge mai departe, spre deosebire de o căutare recursivă autentică, care va reveni întotdeauna la celula anterioară din stivă.

Din acest motiv, acest algoritm poate fi ușor adaptat pentru a genera labirinturi cu aspect și funcționalitate diferite, pur și simplu alegând să intre în modul „vânătoare” mai des sau conform unor reguli specifice. Versiunea implementată aici intră în modul „vânătoare” doar atunci când nu se poate deplasa mai departe de celula curentă.

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

Despre algoritmul Hunt and Kill

Algoritmul Hunt and Kill este o metodă simplă, dar eficientă, pentru generarea de labirinturi. Este oarecum similar cu o căutare în adâncime (adică algoritmul Recursive Backtracker), cu excepția faptului că, atunci când nu se poate deplasa mai departe de poziția curentă, scanează (sau „vânează”) sistematic labirintul pentru a găsi o nouă celulă de la care să continue. Algoritmul constă în două faze principale: mersul pe jos și vânătoarea.

Cum funcționează algoritmul Hunt and Kill pentru Maze Generation

Pasul 1: Începeți de la o celulă aleatorie

• Găsește o celulă aleatorie în grilă și marchează-o ca vizitată.

Pasul 2: Faza de mers (mergere aleatorie)

• Alegeți un vecin nevizitat la întâmplare.
• Mută-te la acel vecin, marchează-l ca vizitat și trasează o cale între celula anterioară și cea nouă.
• Repetați până când nu mai există vecini nevizitați.

Pasul 3: Faza de vânătoare (revenire prin scanare)

• Scanați grila rând cu rând (sau coloană cu coloană).
• Găsiți prima celulă nevizitată care are cel puțin un vecin vizitat.
• Conectează acea celulă la un vecin vizitat pentru a relua faza de mers.
• Repetați până când toate celulele au fost vizitate.

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 Kruskal
• Generatorul de labirint al algoritmului lui Wilson