Medīt un nogalināt labirinta ģenerators
Publicēts: 2025. gada 16. februāris 20:54:46 UTC
Labirints ģenerators, izmantojot Hunt and Kill algoritmu, lai izveidotu perfektu labirintu. Šis algoritms ir līdzīgs Recursive Backtracker, bet mēdz ģenerēt labirintus ar nedaudz mazāk gariem, līkumotiem koridoriem.Hunt and Kill Maze Generator
Algoritms Hunt and Kill patiešām ir modificēta Recursive Backtracker versija. Modifikācija sastāv no sistemātiskas jaunas šūnas skenēšanas (vai "medīšanas"), lai turpinātu, kad tā nevar tikt tālāk, pretstatā patiesai rekursīvai meklēšanai, kas vienmēr atgriezīsies iepriekšējā steka šūnā.
Šī iemesla dēļ šo algoritmu var viegli pielāgot, lai ģenerētu labirintus ar atšķirīgu izskatu un sajūtu, vienkārši izvēloties biežāk pāriet "medību" režīmā vai saskaņā ar īpašiem noteikumiem. Šeit ieviestā versija pāriet "medību" režīmā tikai tad, ja tā nevar iet tālāk no pašreizējās šūnas.
Ideāls labirints ir labirints, kurā ir tieši viens ceļš no jebkura labirinta punkta uz jebkuru citu punktu. Tas nozīmē, ka jūs nevarat nonākt apļveida ceļos, bet bieži sastapsieties ar strupceļiem, kas liks jums apgriezties un atgriezties atpakaļ.
Šeit ģenerētajās labirinta kartēs ir noklusējuma versija bez sākuma un beigu pozīcijām, lai jūs paši varētu tās noteikt: būs risinājums no jebkura labirinta punkta uz jebkuru citu punktu. Ja vēlaties iedvesmu, varat ieslēgt ieteikto sākuma un beigu pozīciju un pat apskatīt risinājumu starp šīm divām pozīcijām.
Par medību un nogalināšanas algoritmu
Algoritms Hunt and Kill ir vienkārša, bet efektīva metode labirintu ģenerēšanai. Tas ir nedaudz līdzīgs dziļuma meklēšanai (ti, Recursive Backtracker algoritmam), izņemot gadījumus, kad tas nevar iet tālāk no pašreizējās pozīcijas, tas sistemātiski skenē (vai "medī") pa labirintu, lai atrastu jaunu šūnu, no kuras turpināt. Algoritms sastāv no divām galvenajām fāzēm: pastaigas un medības.
Kā medību un nogalināšanas algoritms darbojas labirintu paaudzē
1. darbība. Sāciet ar nejaušu šūnu
- Atrodiet režģī nejaušu šūnu un atzīmējiet to kā apmeklētu.
2. darbība: iešanas fāze (izlases staigāšana)
- Izvēlieties nejauši neapmeklētu kaimiņu.
- Pārvietojieties uz šo kaimiņu, atzīmējiet to kā apmeklētu un izveidojiet ceļu starp iepriekšējo un jauno šūnu.
- Atkārtojiet, līdz nav palicis neviens neapmeklēts kaimiņš.
3. darbība: medību fāze (atkāpšanās, izmantojot skenēšanu)
- Skenējiet režģi pēc rindas (vai kolonnas pēc kolonnas).
- Atrodiet pirmo neapmeklēto šūnu, kurā ir vismaz viens apmeklēts kaimiņš.
- Savienojiet šo šūnu ar apmeklēto kaimiņu, lai atsāktu pastaigas fāzi.
- Atkārtojiet, līdz visas šūnas ir apmeklētas.