Rekursif Backtracker Maze Generator

Algoritma backtracker rekursif sejatine minangka panelusuran depth-first tujuan umum. Nalika digunakake kanggo nggawe labirin, rada diowahi kanggo milih jalur kanthi acak, dene yen digunakake kanggo tujuan panelusuran sing nyata, biasane mung nggoleki saben level kanthi urutan linier. Iki cenderung ngasilake labirin kanthi koridor sing dawa lan muter-muter lan solusi sing dawa banget lan muter-muter.

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.

Algoritma backtracker rekursif minangka metode telusuran jero-pisan kanggo ngasilake labirin sing sampurna (labirin tanpa puteran lan jalur tunggal antarane rong titik). Iki prasaja, efisien, lan ngasilake labirin sing narik kawigaten sacara visual kanthi koridor sing dawa lan muter-muter.

Senajan jenenge kaya ngono, ora mesthi kudu diimplementasikake nggunakake rekursi. Asring diimplementasikake kanthi pendekatan iteratif nggunakake antrian LIFO (yaiku tumpukan). Kanggo labirin sing gedhe banget, nggunakake rekursi luwih cenderung nyebabake limpahan tumpukan panggilan, gumantung saka basa pamrograman lan memori sing kasedhiya. Antrian LIFO bisa luwih gampang diadaptasi kanggo nangani data sing akeh, sanajan njaga antrian ing disk utawa ing database yen memori sing kasedhiya ora cukup.

Cara Kerjane

Algoritma iki beroperasi nggunakake pendekatan telusuran depth-first berbasis stack. Iki rincian langkah demi langkah:

1. Pilih sel wiwitan lan tandhani minangka wis dibukak.
2. Nalika ana sel sing durung dibukak: Deloken sel-sel tangga teparo sing durung dibukak. Yen paling ora ana siji tangga teparo sing durung dibukak: Pilih salah siji tangga teparo sing durung dibukak kanthi acak. Copot tembok antarane sel saiki lan tangga teparo sing dipilih. Pindhah menyang tangga teparo sing dipilih lan tandhani minangka sing wis dibukak. Dorong sel saiki menyang tumpukan. Yen ora ana tangga teparo sing durung dibukak: Mundur kanthi ngetokake sel pungkasan saka tumpukan.
3. Terusake proses iki nganti tumpukan kosong.

Kasunyatan sing menarik babagan algoritma iki yaiku bisa digunakake minangka generator labirin lan uga minangka pemecah labirin. Yen sampeyan mbukak ing labirin sing wis digawe lan mandheg nalika tekan titik pungkasan sing wis ditemtokake, tumpukan kasebut bakal ngemot solusi kanggo labirin kasebut.

Aku sejatine duwe rong versi algoritma iki sing digunakake ing situs iki: sing adhedhasar antrian LIFO kanggo ngasilake labirin ing kaca iki lan sing adhedhasar rekursi kanggo ngrampungake labirin, uga labirin sing digawe dening algoritma liyane (kaya ngono carane peta nganggo solusi digawe). Duwe rong versi sing beda mung kanggo olahraga amarga aku wong sing seneng banget lan nganggep menarik, salah siji bisa uga bisa digunakake kanggo loro-lorone ;-)

Wacan Salajengipun

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

• Generator labirin Algoritma Kruskal
• Generator Labirin Wit Sing Tumbuh
• Generator Labirin Algoritma Eller