Generator Labirin Algoritma Eller

Algoritma Eller iku algoritma generasi labirin sing kanthi efisien ngasilake labirin sing sampurna (labirin tanpa puteran lan jalur tunggal antarane rong titik) nggunakake pendekatan baris demi baris. Iki ngasilake labirin sing padha karo algoritma Kruskal, nanging ditindakake kanthi ngasilake mung siji baris saben wektu, tanpa perlu nyimpen kabeh labirin ing memori. Iki ndadekake migunani kanggo ngasilake labirin sing gedhe banget ing sistem sing winates banget lan kanggo generasi konten prosedural.

Labirin sing sampurna yaiku labirin sing ana persis siji dalan saka sembarang titik ing mbingungake menyang titik liyane. Iku tegese sampeyan ora bisa mungkasi munggah ing bunderan, nanging sampeyan bakal kerep nemoni bund ends, meksa sampeyan kanggo nguripake lan bali.

Peta mbingungake sing digawe ing kene kalebu versi standar tanpa posisi wiwitan lan pungkasan, supaya sampeyan bisa mutusake dhewe: bakal ana solusi saka sembarang titik ing mbingungake menyang titik liyane. Yen sampeyan pengin inspirasi, sampeyan bisa ngaktifake posisi wiwitan lan pungkasan sing disaranake - lan malah ndeleng solusi ing antarane loro kasebut.

Babagan Algoritma Eller

Algoritma Eller dikenalake dening David Eller.

Algoritma iki misuwur amarga pendekatan baris demi baris sing efisien kanggo nggawe labirin, saengga cocog kanggo labirin tanpa wates utawa labirin sing digawe kanthi wektu nyata. Algoritma iki umume dikutip ing literatur babagan nggawe konten prosedural lan nggawe labirin, nanging aku durung bisa nemokake sumber utama sing njlentrehake publikasi asline.

Cara Kerja Algoritma Eller kanggo Generasi Labirin

Algoritma Eller ngolah siji baris saben wektu, njaga lan ngowahi set sel sing nyambung. Iki njamin konektivitas nalika ngindhari puteran, lan kanthi efisien ngluwihi labirin mudhun.

Sacara téoritis, iki bisa digunakaké kanggo ngasilaké labirin tanpa wates, nanging kanggo mesthekake yèn labirin sing diasilaké pancèn bisa dirampungaké, perlu ngalih menyang logika "baris pungkasan" ing sawijining wektu kanggo ngrampungaké labirin kasebut.

Langkah 1: Inisialisasi Baris Pertama

• Menehi saben sel ing baris ID set unik.

Langkah 2: Gabungake Sawetara Sel sing Jejer kanthi Horizontal

• Gabungake sel-sel sing jejer kanthi acak kanthi nyetel menyang ID sing padha. Iki njamin ana bagean horisontal.

Langkah 3: Nggawe Sambungan Vertikal menyang Baris Sabanjure

• Kanggo saben set sing katon ing baris, paling ora siji sel kudu nyambung mudhun (kanggo njamin konektivitas).
• Pilih siji utawa luwih sel kanthi acak saka saben set kanggo nyambung menyang baris sabanjure.

Langkah 4: Pindhah menyang Baris Sabanjure

• Terusake sambungan vertikal kanthi menehi ID set sing padha menyang sel sing cocog ing ngisor iki.
• Menehi ID set anyar menyang sel sing durung ditugasake.

Langkah 5: Baleni Langkah 2–4 Nganti Baris Pungkasan Tekan

• Terusake proses baris demi baris.

Langkah 6: Proses Baris Pungkasan

• Priksa manawa kabeh sel ing baris pungkasan kalebu ing set sing padha kanthi nggabungake set kapisah sing isih ana.

Wacan Salajengipun

Yen sampeyan seneng karo kiriman iki, sampeyan bisa uga seneng saran iki:

• Generator Labirin Perburuan lan Pembunuhan
• Rekursif Backtracker Maze Generator
• Generator Labirin Wit Sing Tumbuh