Hunt jeung maéhan Maze generator

Algoritma Hunt and Kill sabenerna mangrupikeun vérsi modifikasi tina Recursive Backtracker. Modifikasi ieu diwangun ku cara nyeken sacara sistematis (atanapi "moro") sél énggal pikeun diteruskeun nalika teu tiasa langkung jauh, sabalikna tina pamilarian rekursif anu leres, anu bakal salawasna uih deui ka sél sateuacana dina tumpukan.

Kusabab kitu, algoritma ieu tiasa gampang diadaptasi pikeun ngahasilkeun labirin kalayan tampilan sareng rasa anu béda, ngan ukur ku milih langkung sering lebet kana mode "moro" atanapi numutkeun aturan khusus. Vérsi anu diimplementasikeun di dieu ngan ukur lebet kana mode "moro" nalika teu tiasa langkung jauh tina sél ayeuna.

Maze sampurna nyaéta Maze dimana aya persis hiji jalur ti titik mana waé dina Maze ka titik séjén. Éta hartina anjeun moal bisa mungkas nepi ka sabudeureun dina bunderan, tapi anjeun bakal mindeng sapatemon dead ends, forcing anjeun ngahurungkeun sabudeureun tur balik.

Peta Maze anu dihasilkeun di dieu kalebet versi standar tanpa posisi awal sareng akhir, ku kituna anjeun tiasa mutuskeun pikeun diri anjeun: bakal aya solusi ti mana waé dina maze ka titik anu sanés. Upami anjeun hoyong inspirasi, anjeun tiasa ngaktipkeun posisi mimiti sareng bérés anu disarankeun - komo ningali solusi antara dua.

Ngeunaan Algoritma Hunt and Kill

Algoritma Hunt and Kill mangrupikeun metode anu saderhana tapi efektif pikeun ngahasilkeun labirin. Ieu rada mirip sareng pamilarian jero-heula (nyaéta algoritma Recursive Backtracker), kecuali nalika teu tiasa langkung jauh tina posisi ayeuna, éta sacara sistematis nyeken (atanapi "moro") di luhur labirin pikeun mendakan sél énggal pikeun diteruskeun. Algoritma ieu diwangun ku dua fase utama: leumpang sareng moro.

Kumaha Algoritma Hunt and Kill Gawéna pikeun Generasi Labirin

Léngkah 1: Mimitian ti sél acak

• Panggihan sél acak dina grid teras tandai salaku parantos didatangan.

Léngkah 2: Fase Leumpang (Leumpang Acak)

• Pilih tatangga acak anu teu acan didatangan.
• Pindah ka tatangga éta, tandai salaku nu geus dilongok, terus jieun jalan antara sél saméméhna jeung sél anyar.
• Balikan deui dugi ka teu aya tatangga anu teu didatangan.

Léngkah 3: Fase Moro (Mundur ngalangkungan Scanning)

• Pindai grid baris demi baris (atawa kolom demi kolom).
• Panggihan sél munggaran anu teu acan didatangan anu sahenteuna aya hiji tatangga anu didatangan.
• Sambungkeun sélulér éta ka tatangga anu parantos didatangan pikeun nuluykeun fase leumpang.
• Balikan deui dugi ka sadaya sél parantos didatangan.

Bacaan salajengna

Upami anjeun resep kana tulisan ieu, anjeun ogé tiasa resep saran ieu:

• Rekursif Backtracker Maze generator
• Generator Labirin Algoritma Eller
• Algoritma Maze generator Wilson urang