Rekursif Backtracker Maze Generator

Algoritma backtracker rekursif pancen minangka telusuran sing paling jero. Yen digunakake kanggo nggawe mbingungake, rada diowahi kanggo milih dalan kanthi acak, dene yen digunakake kanggo tujuan telusuran sing nyata, biasane mung nggoleki saben level kanthi urutan linear. Cenderung ngasilake labirin kanthi koridor sing dawa lan gulung-gulung lan solusi sing dawa banget.

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 sing paling jero kanggo ngasilake labirin sing sampurna (maze tanpa puteran lan jalur siji ing antarane rong titik). Iku prasaja, efisien, lan mrodhuksi mazes visual narik kawigaten karo dawa, nduwurke tumpukan koridor.

Senadyan jenenge, ora kudu dileksanakake nggunakake rekursi. Asring dileksanakake ing pendekatan iteratif nggunakake antrian LIFO (IE tumpukan). Kanggo mbingungake sing gedhe banget, nggunakake rekursi luwih bisa nyebabake overflow tumpukan telpon, gumantung saka basa pamrograman lan memori sing kasedhiya. A antrian LIFO bisa luwih gampang dicocogake kanggo nangani akeh data, malah tetep antrian ing disk utawa ing database yen memori kasedhiya ora cukup.

Cara Kerjane

Algoritma kasebut ngoperasikake pendekatan telusuran sing paling jero adhedhasar tumpukan. Mangkene rincian langkah demi langkah:

1. Pilih sel wiwitan lan tandhani minangka dibukak.
2. Nalika ana sel sing ora dibukak:
   • Delengen sel-sel tetangga sing durung ditekani.
   • Yen paling ora ana pepadhamu sing ora dibukak:
     • Acak milih salah siji saka tanggi sing durung ditekani.
     • Copot tembok ing antarane sel saiki lan pepadhamu sing dipilih.
     • Pindhah menyang pepadhamu sing dipilih lan tandhani minangka dibukak.
     • Push sel saiki menyang tumpukan.
   • Yen ora ana tetanggan sing ora ditekani:
     • Backtrack dening pop sel pungkasan saka tumpukan.
3. Terusake proses iki nganti tumpukan kosong.

Kasunyatan sing menarik babagan algoritma iki yaiku bisa digunakake minangka generator mbingungake lan minangka pemecah mbingungake. Yen sampeyan mbukak ing mbingungake wis kui lan mung mandheg nalika sampeyan mencet titik pungkasan mutusaké, tumpukan bakal ngemot solusi kanggo mbingungake.

Aku bener duwe rong versi algoritma iki ing muter ing situs iki: antrian LIFO adhedhasar siji kanggo ngasilaken mazes ing kaca iki lan recursion adhedhasar kanggo mecahaken mazes, uga mazes kui dening algoritma liyane (iku carane peta karo solusi digawe). Duwe rong versi beda mung kanggo olahraga amarga aku nerd sing nemokake iku menarik, bisa uga bisa kanggo loro ;-)