Hunt jeung maéhan Maze generator
Diterbitkeun: 16 Pébruari 2025 jam 21.03.59 UTC
Generator Maze nganggo algoritma Hunt and Kill pikeun nyiptakeun maze anu sampurna. Algoritma ieu sami sareng Recursive Backtracker, tapi condong ngahasilkeun mazes kalayan koridor anu rada panjang, pungkal.Hunt and Kill Maze Generator
Algoritma Hunt and Kill mangrupikeun versi anu dirobih tina Recursive Backtracker. Modifikasi diwangun ku scanning sacara sistematis (atawa "moro") pikeun sél anyar neruskeun ti nalika eta teu bisa balik salajengna, sabalikna hiji pilarian recursive leres, nu salawasna bakal balik deui ka sél saméméhna dina tumpukan éta.
Kusabab ieu, algoritma ieu tiasa gampang diadaptasi pikeun ngahasilkeun mazes kalayan tampilan sareng raos anu béda-béda, ngan ku milih asupkeun mode "moro" langkung sering atanapi numutkeun aturan khusus. Versi anu dilaksanakeun di dieu ngan ukur asup kana mode "moro" nalika éta henteu tiasa langkung jauh ti 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 sareng Maéhan
Algoritma Hunt and Kill mangrupikeun metode anu sederhana tapi efektif pikeun ngahasilkeun mazes. Ieu rada sarupa jeung pilarian jero-heula (ie algoritma Recursive Backtracker), iwal ti lamun teu bisa balik leuwih jauh ti posisi ayeuna, éta sacara sistematis nyeken (atawa "hunts") ngaliwatan Maze pikeun manggihan sél anyar pikeun lumangsungna ti. Algoritma diwangun ku dua fase utama: leumpang sareng moro.
Kumaha Algoritma Hunt sareng Maéhan Gawé pikeun Generasi Maze
Lengkah 1: Mimitian dina sél acak
- Teangan sél acak dina grid jeung cirian salaku dilongok.
Lengkah 2: Fase Leumpang (Jalan Acak)
- Milih tatangga acak unvisited.
- Pindah ka tatangga éta, tandai salaku dilongok, sareng ukir jalur antara sél saméméhna sareng énggal.
- Malikan deui nepi ka euweuh tatangga nu teu didatangan.
Lengkah 3: Fase Moro (Backtracking via Scanning)
- Nyeken grid baris ku baris (atawa kolom ku kolom).
- Manggihan sél unvisited munggaran nu boga sahanteuna hiji dilongok tatangga.
- Sambungkeun sél éta ka tatangga anu didatangan pikeun neruskeun fase leumpang.
- Ngulang nepi ka sadaya sél geus dilongok.