Tumuwuh Tangkal Algoritma Maze Generator

Algoritma Growing Tree téh pikaresepeun, sabab bisa niru paripolah sababaraha algoritma séjénna, gumantung kana kumaha sél salajengna dipilih nalika generasi. Implementasi dina kaca ieu ngagunakeun pendekatan breadth-first, kawas antrian.

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 Tangkal Numuwuh

Algoritma Growing Tree mangrupikeun metode anu fleksibel sareng kuat pikeun ngahasilkeun labirin anu sampurna. Algoritma ieu pikaresepeun sabab tiasa niru paripolah sababaraha algoritma generasi labirin anu sanés, sapertos algoritma Prim, backtracking rekursif, sareng divisi rekursif, gumantung kana kumaha anjeun milih sél salajengna pikeun diprosés.

Kumaha Algoritma Tangkal Tumuwuh Gawéna

Léngkah 1: Inisialisasi

• Mimitian ku grid sél anu teu acan didatangan.
• Pilih sél awal acak teras tambahkeun kana daptar.

Léngkah 2: Loop Generasi Labirin

• Salami daptar sél teu kosong: Pilih sél tina daptar dumasar kana strategi khusus (dijelaskeun di handap). Ukir bagian tina sél anu dipilih ka salah sahiji tatanggana anu teu acan didatangan (dipilih sacara acak). Tambahkeun tatangga kana daptar sabab ayeuna bagian tina labirin. Upami sél anu dipilih teu gaduh tatangga anu teu acan didatangan, hapus tina daptar.

Léngkah 3: Panghentian

• Algoritma réngsé nalika teu aya deui sél dina daptar, anu hartosna sakumna labirin parantos diukir.

Strategi Seleksi Sél (Fleksibilitas Algoritma)

Fitur anu ngabédakeun tina algoritma Growing Tree nyaéta kumaha anjeun milih sél mana anu bakal diprosés salajengna. Pilihan ieu mangaruhan pisan kana penampilan labirin:

Sél Panganyarna (Paripolah Kawas Tumpukan) – Backtracker Rekursif:

• Salawasna pilih sél anu panganyarna ditambahkeun.
• Ngahasilkeun koridor anu panjang sareng muter-muter kalayan seueur jalan buntu (sapertos labirin pamilarian anu mimitina jerona).
• Labirin condong gaduh bagian anu panjang sareng gampang direngsekeun.

Sél Acak (Algoritma Prim Acak):

• Pilih sél acak tina daptar unggal waktos.
• Nyiptakeun labirin anu langkung rata kalayan jalur anu rumit sareng kusut.
• Koridor anu panjangna langkung sakedik sareng langkung seueur cabang.

Sél Pangkolotna (Paripolah Sapertos Antrian):

• Salawasna pilih sél anu pangkolotna dina daptar.
• Ngahasilkeun labirin kalayan panyebaran anu langkung seragam, sapertos pola pamilarian breadth-first.
• Lorong pondok, rimbun, jeung sambunganana padet.
• (Ieu vérsi anu diimplementasikeun di dieu)

Pamarekan Hibrida:

Gabungkeun strategi pikeun rupa-rupa karakteristik labirin. Contona:

• 90% pang anyarna, 10% acak: Sigana mah lolobana siga labirin backtracker rekursif, tapi sakapeung aya dahan anu misahkeun koridor panjang.
• 50% pang anyarna, 50% pangkolotna: Nyimbangan koridor panjang ku rungkun anu tumuwuh.

Bacaan salajengna

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

• Kruskal urang Algoritma Maze generator
• Hunt jeung maéhan Maze generator
• Algoritma Maze generator Wilson urang