Generatorul de labirint de vânătoare și ucidere
Publicat: 16 februarie 2025 la 20:56:27 UTC
Generator de labirint folosind algoritmul Hunt and Kill pentru a crea un labirint perfect. Acest algoritm este similar cu Recursive Backtracker, dar tinde să genereze labirinturi cu coridoare ceva mai puțin lungi și întortocheate.Hunt and Kill Maze Generator
Algoritmul Hunt and Kill este într-adevăr o versiune modificată a Recursive Backtracker. Modificarea constă în scanarea sistematică (sau „vânarea”) pentru ca o nouă celulă să continue din momentul în care nu poate merge mai departe, spre deosebire de o adevărată căutare recursivă, care va reveni întotdeauna la celula anterioară din stivă.
Din acest motiv, acest algoritm poate fi adaptat cu ușurință pentru a genera labirinturi cu aspect și senzație diferită, doar alegând să intrați mai des în modul „vânătoare” sau conform unor reguli specifice. Versiunea implementată aici intră în modul „vânătoare” doar atunci când nu poate merge 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 profunzime (adică algoritmul Recursive Backtracker), cu excepția cazului în care nu poate merge mai departe de poziția curentă, scanează (sau „vânează”) în mod sistematic peste labirint pentru a găsi o nouă celulă din care să procedeze. Algoritmul constă din 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ăsiți o celulă aleatorie în grilă și marcați-o ca vizitată.
Pasul 2: faza de mers (mers aleatoriu)
- Alegeți un vecin nevizitat la întâmplare.
- Mutați-vă la vecinul respectiv, marcați-l ca vizitat și faceți o cale între celula anterioară și cea nouă.
- Repetați până când nu au mai rămas vecini nevizitați.
Pasul 3: faza de vânătoare (backtracking 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.
- Conectați celula respectivă la un vecin vizitat pentru a relua faza de mers pe jos.
- Repetați până când toate celulele au fost vizitate.