Jahti ja Tappa Labürindi Loodur

Hunt and Kill algoritm on tegelikult rekursiivse tagasijälgija modifitseeritud versioon. Modifikatsioon seisneb süstemaatilises uue lahtri skaneerimises (või "jahtimises"), et leida sealt, kust edasi minna ei saa, erinevalt tõelisest rekursiivsest otsingust, mis alati naaseb pinu eelmise lahtri juurde.

Seetõttu saab seda algoritmi hõlpsalt kohandada erineva välimuse ja tundega labürintide loomiseks, valides lihtsalt sagedamini või vastavalt kindlatele reeglitele "jahi" režiimi sisenemise. Siin rakendatud versioon lülitub "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.

Jahtimise ja tapmise algoritmi kohta

Jahi ja tapa algoritm on lihtne, kuid tõhus meetod labürintide genereerimiseks. See sarnaneb mõnevõrra sügavuspõhise otsinguga (st rekursiivse tagasijälgija algoritmiga), välja arvatud see, et kui praegusest asukohast kaugemale minna ei saa, skannib (või "jahib") see süstemaatiliselt üle labürindi, et leida uus lahter, kust edasi liikuda. Algoritm koosneb kahest põhifaasist: kõndimisest ja otsimisest.

Kuidas jahi- ja tapmisalgoritm labürindi genereerimisel töötab

1. samm: alusta juhuslikust lahtrist

• Leia ruudustikust suvaline lahter ja märgi see külastatuks.

2. samm: kõndimisfaas (juhuslik kõndimine)

• Vali suvaline külastamata naaber.
• Liiku selle naabri juurde, märgi see külastatuks ja raada tee eelmise ja uue lahtri vahele.
• Korda seni, kuni külastamata naabreid pole enam.

3. samm: jahifaas (tagasijälgimine skaneerimise teel)

• Skanneeri ruudustikku rida-realt (või veerg-veerult).
• Leia esimene külastamata rakk, millel on vähemalt üks külastatud naaber.
• Kõndimisfaasi jätkamiseks ühenda see rakk külastatud naabriga.
• Korda, kuni kõik lahtrid on külastatud.

Lisalugemist

Kui see postitus teile meeldis, võivad teile meeldida ka need soovitused:

• Elleri algoritmi labürindi generaator
• Rekursiivne Backtracker labürindi generaator
• Wilsoni algoritmi labürindi generaator