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

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

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

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

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

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

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

ભુલભુલામણી પેઢી માટે વિલ્સનનું અલ્ગોરિધમ કેવી રીતે કાર્ય કરે છે

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

પગલું ૧ઃ પ્રારંભ કરો

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

સ્ટેપ 2: રેન્ડમ સ્ટાર્ટિંગ સેલ પસંદ કરો

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

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

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

પગલું ૪ઃ જ્યાં સુધી તમામ સેલની મુલાકાત ન લેવાય ત્યાં સુધી તેનું પુનરાવર્તન કરોઃ

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