Hunt and Kill labirintus generátor

A Hunt and Kill algoritmus valójában a Recursive Backtracker módosított változata. A módosítás abból áll, hogy szisztematikusan pásztázza (vagy „vadászza”) a rendszer egy új cellát, ahonnan már nem mehet tovább, szemben a valódi rekurzív kereséssel, amely mindig a verem előző cellájára tér vissza.

Emiatt ez az algoritmus könnyen adaptálható különböző megjelenésű és érzetű labirintusok létrehozására, egyszerűen a „vadászat” módba való gyakoribb belépéssel vagy meghatározott szabályok szerint. Az itt megvalósított verzió csak akkor lép „vadászat” módba, ha nem tud továbbmenni az aktuális cellától.

A tökéletes labirintus olyan labirintus, amelyben a labirintus bármely pontjából pontosan egy út vezet bármely más pontba. Ez azt jelenti, hogy a végén nem járhatsz körbe-körbe, de gyakran fogsz zsákutcába jutni, ami arra kényszerít, hogy megfordulj és visszamenj.

Az itt generált labirintustérképek tartalmaznak egy alapértelmezett verziót kezdő és végpontok nélkül, így ezeket te magad döntheted el: a labirintus bármely pontjából bármelyik másik pontba el lehet jutni. Ha inspirációra vágysz, engedélyezhetsz egy javasolt kezdő- és célpozíciót - és még a kettő közötti megoldást is láthatod.

A Hunt and Kill algoritmusról

A Vadászat és Ölj algoritmus egy egyszerű, mégis hatékony módszer labirintusok létrehozására. Némileg hasonlít a mélységi kereséshez (azaz a Rekurzív Visszalépéses algoritmushoz), azzal a különbséggel, hogy amikor nem tud továbbmenni az aktuális pozíciótól, szisztematikusan átvizsgálja (vagy "vadászik") a labirintust, hogy új cellát találjon, ahonnan továbbléphet. Az algoritmus két fő fázisból áll: sétálásból és vadászatból.

Hogyan működik a Vadászat és Ölj algoritmus a labirintusgenerálásban?

1. lépés: Kezdés egy véletlenszerű cellánál

• Keress egy véletlenszerű cellát a rácsban, és jelöld meg látogatottként.

2. lépés: Gyaloglási fázis (véletlenszerű séta)

• Válassz egy véletlenszerű, még nem látogatott szomszédot.
• Menj át arra a szomszédos cellapontra, jelöld meg meglátogatottként, és vágj utat az előző és az új cella között.
• Ismételd addig, amíg már nincsenek meglátogatatlan szomszédok.

3. lépés: Vadászati fázis (visszakövetés szkenneléssel)

• Sorról sorra (vagy oszlopról oszlopra) pásztázd végig a rácsot.
• Keresd meg az első olyan meglátogatatlan cellát, amelynek van legalább egy meglátogatott szomszédja.
• Csatlakoztasd a cellát egy meglátogatott szomszédodhoz a gyaloglási fázis folytatásához.
• Ismételd, amíg az összes cellát meglátogattad.

További olvasmányok

Ha tetszett ez a bejegyzés, akkor ezek a javaslatok is érdekelhetik:

• Wilson algoritmus labirintus generátor
• Eller algoritmus labirintusgenerátora
• Rekurzív Backtracker labirintus generátor