વિલ્સન્સ એલ્ગોરિધમ મેઝ જનરેટર

વિલ્સનનું અલ્ગોરિધમ એક લૂપ-ઇરેઝ્ડ રેન્ડમ વોક પદ્ધતિ છે જે મેઝ બનાવવા માટે એકસમાન સ્પેનિંગ ટ્રી જનરેટ કરે છે. આનો અર્થ એ છે કે આપેલ કદના બધા શક્ય મેઝ જનરેટ થવાની શક્યતા સમાન છે, જે તેને એક નિષ્પક્ષ મેઝ જનરેશન ટેકનિક બનાવે છે. વિલ્સનના અલ્ગોરિધમને એલ્ડોસ-બ્રોડર અલ્ગોરિધમનું સુધારેલું સંસ્કરણ ગણી શકાય, કારણ કે તે સમાન લાક્ષણિકતાઓ સાથે મેઝ જનરેટ કરે છે, પરંતુ તે ખૂબ ઝડપથી ચાલે છે, તેથી મેં અહીં એલ્ડોસ-બ્રોડર અલ્ગોરિધમનો અમલ કરવાની તસ્દી લીધી નથી.

સંપૂર્ણ ભુલભુલામણી એ એક ભુલભુલામણી છે જેમાં ભુલભુલામણીના કોઈપણ બિંદુથી બીજા કોઈપણ બિંદુ સુધીનો એક જ રસ્તો હોય છે. તેનો અર્થ એ કે તમે વર્તુળોમાં ફરતા રહી શકતા નથી, પરંતુ તમને ઘણીવાર મૃત છેડાઓનો સામનો કરવો પડશે, જેના કારણે તમને પાછળ ફરીને પાછા ફરવું પડશે.

અહીં જનરેટ થયેલા મેઝ મેપ્સમાં કોઈ પણ શરૂઆત અને સમાપ્તિ સ્થિતિ વિના ડિફોલ્ટ સંસ્કરણ શામેલ છે, તેથી તમે તે જાતે નક્કી કરી શકો છો: મેઝના કોઈપણ બિંદુથી બીજા કોઈપણ બિંદુ સુધી ઉકેલ હશે. જો તમને પ્રેરણા જોઈતી હોય, તો તમે સૂચવેલ શરૂઆત અને સમાપ્તિ સ્થિતિને સક્ષમ કરી શકો છો - અને બંને વચ્ચેનો ઉકેલ પણ જોઈ શકો છો.

વિલ્સનના અલ્ગોરિધમ વિશે

લૂપ-ઇરેઝ્ડ રેન્ડમ વોલનો ઉપયોગ કરીને યુનિફોર્મ સ્પેનિંગ ટ્રીઝ બનાવવા માટે વિલ્સનનું અલ્ગોરિધમ ડેવિડ બ્રુસ વિલ્સન દ્વારા બનાવવામાં આવ્યું હતું.

વિલ્સને મૂળ રૂપે 1996 માં સંભાવના સિદ્ધાંતમાં રેન્ડમ સ્પેનિંગ ટ્રીઝ અને માર્કોવ ચેઇન પર સંશોધન કરતી વખતે આ અલ્ગોરિધમ રજૂ કર્યું હતું. તેમનું કાર્ય મુખ્યત્વે ગણિત અને આંકડાકીય ભૌતિકશાસ્ત્રમાં હોવા છતાં, સંપૂર્ણ રીતે સમાન મેઇઝ ઉત્પન્ન કરવાની ક્ષમતાને કારણે આ અલ્ગોરિધમને મેઇઝ જનરેશન માટે વ્યાપકપણે અપનાવવામાં આવ્યું છે.

મેઝ જનરેશન માટે વિલ્સનનું અલ્ગોરિધમ કેવી રીતે કામ કરે છે

વિલ્સનનું અલ્ગોરિધમ ખાતરી કરે છે કે રેન્ડમ વોકનો ઉપયોગ કરીને મુલાકાત ન લેવાયેલા કોષોમાંથી પુનરાવર્તિત રીતે રસ્તાઓ કોતરીને અંતિમ ભુલભુલામણી કોઈપણ લૂપ વિના સંપૂર્ણપણે જોડાયેલ છે.

પગલું 1: પ્રારંભ કરો

• દિવાલોથી ભરેલા ગ્રીડથી શરૂઆત કરો.
• બધા શક્ય પેસેજ કોષોની યાદી વ્યાખ્યાયિત કરો.

પગલું 2: રેન્ડમ શરૂઆતનો કોષ પસંદ કરો

• કોઈપણ રેન્ડમ કોષ પસંદ કરો અને તેને મુલાકાત લીધેલ તરીકે ચિહ્નિત કરો. આ પેઢી દરમિયાન ભુલભુલામણીના પ્રારંભિક બિંદુ તરીકે કાર્ય કરે છે.

પગલું 3: લૂપ-ઇરેઝિંગ સાથે રેન્ડમ વોક

• એક ન મુલાકાત લેવાયેલ કોષ પસંદ કરો અને રેન્ડમ ચાલ શરૂ કરો (રેન્ડમ દિશામાં આગળ વધો).
• જો ચાલ પહેલાથી જ મુલાકાત લીધેલા કોષ સુધી પહોંચે છે, તો પાથમાંના કોઈપણ લૂપ્સ ભૂંસી નાખો.
• એકવાર વોક મુલાકાત લીધેલા પ્રદેશ સાથે જોડાઈ જાય, પછી પાથના બધા કોષોને મુલાકાત લીધેલા તરીકે ચિહ્નિત કરો.

પગલું 4: બધા કોષોની મુલાકાત ન થાય ત્યાં સુધી પુનરાવર્તન કરો:

• જ્યાં સુધી દરેક કોષ ભુલભુલામણીનો ભાગ ન બને ત્યાં સુધી મુલાકાત ન લેવાયેલા કોષો પસંદ કરવાનું અને રેન્ડમ વોક કરવાનું ચાલુ રાખો.

વધુ વાંચન

જો તમને આ પોસ્ટ ગમી હોય, તો તમને આ સૂચનો પણ ગમશે:

• ટ્રી એલ્ગોરિધમનો મેઝ જનરેટર વધતો જાય છે
• ક્રુસ્કલનું અલ્ગોરિધમ મેઝ જનરેટર
• એલરનું અલ્ગોરિધમ મેઝ જનરેટર