Medīt un nogalināt labirinta ģenerators

Hunt and Kill" algoritms patiesībā ir modificēta rekursīvā atpakaļizsekotāja versija. Modifikācija sastāv no sistemātiskas jaunas šūnas skenēšanas (vai "medīšanas"), lai turpinātu, ja tā vairs nevar tikt tālāk, atšķirībā no patiesas rekursīvas meklēšanas, kas vienmēr atgriežas pie iepriekšējās šūnas kaudzē.

Šī 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 vai saskaņā ar konkrētiem noteikumiem pāriet "medību" režīmā. Šeit ieviestā versija pāriet "medību" režīmā tikai tad, ja tā nevar tikt 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

Medības un nogalināšanas" algoritms ir vienkārša, bet efektīva metode labirintu ģenerēšanai. Tas ir nedaudz līdzīgs dziļuma meklēšanai (t. i., rekursīvajam atpakaļejošā izsekošanas algoritmam), izņemot to, ka, ja tas nevar tikt tālāk no pašreizējās pozīcijas, tas sistemātiski skenē (jeb "medī") labirintu, lai atrastu jaunu šūnu, no kuras turpināt. Algoritms sastāv no divām galvenajām fāzēm: iešanas un medīšanas.

Kā medību un nogalināšanas algoritms darbojas labirintu ģenerēšanai

1. darbība. Sāciet ar nejaušu šūnu

• Atrodiet režģī nejaušu šūnu un atzīmējiet to kā apmeklētu.

2. solis: iešanas fāze (nejauša ieš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 vairs nav neviena neapmeklēta kaimiņa.

3. solis: medību fāze (atpakaļizsekošana, izmantojot skenēšanu)

• Pārlūkojiet režģi rindu pa rindai (vai kolonnu pa kolonnai).
• Atrodiet pirmo neapmeklēto šūnu, kurai ir vismaz viens apmeklēts kaimiņš.
• Savienojiet šo šūnu ar apmeklēto kaimiņu, lai atsāktu iešanas fāzi.
• Atkārtojiet, līdz visas šūnas ir apmeklētas.

Papildu lasāmviela

Ja jums patika šī ziņa, jums varētu patikt arī šie ieteikumi:

• Kruskal algoritma labirinta ģenerators
• Augošu koku algoritma labirinta ģenerators
• Rekursīvs Backtracker labirinta ģenerators