Jahti ja Tappa Labürindi Loodur
Avaldatud: 16. veebruar 2025, kell 20:53:19 UTC
Labürindigeneraator, mis kasutab täiusliku labürindi loomiseks algoritmi Hunt and Kill. See algoritm sarnaneb Recursive Backtrackeriga, kuid kipub genereerima labürindid mõnevõrra lühemate käänuliste koridoridega.Hunt and Kill Maze Generator
Hunt and Kill algoritm on tõesti Recursive Backtrackeri muudetud versioon. Muudatus seisneb uue lahtri süstemaatilises skannimises (või "jahtimises"), et jätkata alates hetkest, mil see enam kaugemale minna ei saa, erinevalt tõelisest rekursiivsest otsingust, mis läheb alati tagasi virna eelmisesse lahtrisse.
Seetõttu saab seda algoritmi hõlpsasti kohandada erineva välimuse ja tunnetusega labürindide loomiseks, lihtsalt valides sagedamini jahirežiimi sisenemise või konkreetsete reeglite järgi. Siin rakendatud versioon siseneb "jahi" režiimi ainult siis, kui see ei saa praegusest lahtrist kaugemale minna.
Täiuslik labürint on labürint, kus on täpselt üks tee labürindi mis tahes punktist mis tahes teise punkti. See tähendab, et te ei saa sattuda ringiratastesse, kuid sageli satute ummikteedesse, mis sunnib teid ümber pöörama ja tagasi minema.
Siin genereeritud labürindi kaardid sisaldavad vaikimisi versiooni ilma algus- ja lõpp-punktideta, nii et saate need ise otsustada: labürindi mis tahes punktist mis tahes teise punkti on olemas lahendus. Kui soovite inspiratsiooni, saate lubada soovitatud algus- ja lõpupositsiooni - ja isegi näha lahendust nende kahe vahel.
Hunt and Kill algoritmi kohta
Hunt and Kill algoritm on lihtne, kuid tõhus meetod labürintide loomiseks. See sarnaneb mõneti sügavus-esimese otsinguga (st Recursive Backtrackeri algoritm), välja arvatud juhul, kui see ei saa praegusest asukohast kaugemale minna, skaneerib (või "jahib") süstemaatiliselt üle labürindi, et leida uus lahter, millest edasi minna. Algoritm koosneb kahest põhifaasist: kõndimine ja jaht.
Kuidas jahi ja tapmise algoritm labürindi genereerimise jaoks töötab
1. samm: alustage juhuslikust lahtrist
- Leidke ruudustikust juhuslik lahter ja märkige see külastatuks.
2. samm: kõndimise faas (juhuslik kõndimine)
- Valige juhuslikult külastamata naaber.
- Liikuge selle naabri juurde, märkige see külastatuks ja lõigake tee eelmise ja uue lahtri vahele.
- Korrake, kuni pole enam külastamata naabreid.
3. samm: jahifaas (tagasi jälgimine skannimise kaudu)
- Skannige ruudustikku ridade kaupa (või veergude kaupa).
- Leidke esimene külastamata lahter, millel on vähemalt üks külastatud naaber.
- Kõndimisfaasi jätkamiseks ühendage see rakk külastatud naabriga.
- Korrake, kuni kõik rakud on külastatud.