Generator Labirin Algoritma Eller

Algoritma Eller nyaéta algoritma generasi labirin anu sacara efisien ngahasilkeun labirin anu sampurna (labirin tanpa puteran sareng hiji jalur antara dua titik) nganggo pendekatan baris-demi-baris. Éta ngahasilkeun labirin anu sami sareng algoritma Kruskal, tapi ku cara ngahasilkeun ngan hiji baris dina hiji waktos, tanpa kedah nyimpen sakumna labirin dina mémori. Éta ngajantenkeun éta mangpaat pikeun ngahasilkeun labirin anu ageung pisan dina sistem anu terbatas pisan sareng pikeun generasi eusi prosedural.

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 Eller

Algoritma Eller diwanohkeun ku David Eller.

Algoritma ieu kasohor ku pendekatan baris demi baris anu efisien pikeun ngahasilkeun labirin, janten idéal pikeun labirin anu teu terbatas atanapi labirin anu dihasilkeun sacara real-time. Ieu umumna disebatkeun dina literatur generasi eusi prosedural sareng generasi labirin, tapi kuring teu acan tiasa mendakan sumber primér anu ngajelaskeun publikasi aslina.

Kumaha Algoritma Eller Gawéna pikeun Generasi Labirin

Algoritma Eller ngolah hiji baris dina hiji waktu, ngajaga sareng ngarobih sét sél anu nyambung. Éta mastikeun konéktivitas bari nyingkahan puteran, sareng sacara efisien manjangkeun labirin ka handap.

Sacara téoritis ieu tiasa dianggo pikeun ngahasilkeun labirin anu teu aya tungtungna, nanging pikeun mastikeun yén labirin anu dihasilkeun sabenerna tiasa direngsekeun, perlu pikeun ngalih ka logika "baris terakhir" dina hiji waktos pikeun ngarengsekeun labirin éta.

Léngkah 1: Ngamimitian Baris Kahiji

• Beri unggal sél dina jajar ID set unik.

Léngkah 2: Gabungkeun Sababaraha Sél Padeukeut sacara Horizontal

• Gabungkeun sél anu padeukeut sacara acak ku cara nyetel kana ID set anu sami. Ieu mastikeun aya bagian horizontal.

Léngkah 3: Jieun Sambungan Vertikal ka Baris Salajengna

• Pikeun unggal sét anu muncul dina jajar, sahenteuna hiji sél kedah nyambung ka handap (pikeun mastikeun konéktivitas).
• Pilih hiji atawa leuwih sél sacara acak tina unggal sét pikeun nyambung ka jajar salajengna.

Léngkah 4: Pindah ka Baris Salajengna

• Teruskeun sambungan vertikal ku cara masihan ID set anu sami ka sél anu saluyu di handap.
• Tetapkeun ID set anyar ka sél anu teu acan ditugaskeun.

Léngkah 5: Balikan Léngkah 2–4 Nepi ka Baris Pamungkas Kahontal

• Teruskeun ngolah jajar demi jajar.

Léngkah 6: Ngolah Baris Pamungkas

• Pastikeun sadaya sél dina jajar terakhir kagolong kana set anu sami ku cara ngahijikeun set anu misah anu sésana.

Bacaan salajengna

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

• Hunt jeung maéhan Maze generator
• Algoritma Maze generator Wilson urang
• Rekursif Backtracker Maze generator