रिकर्सिव्ह बॅकट्रॅकर मेझ जनरेटर

रिकर्सिव्ह बॅकट्रॅकर अल्गोरिथम हा खरोखरच एक सामान्य उद्देश डेप्थ-फर्स्ट सर्च आहे. जेव्हा मेझ जनरेशनसाठी वापरला जातो तेव्हा तो यादृच्छिक मार्ग निवडण्यासाठी थोडासा बदल केला जातो, तर जर प्रत्यक्ष शोधासाठी वापरला जातो, तर सामान्यतः प्रत्येक लेव्हल फक्त रेषीय क्रमाने शोधला जातो. तो लांब, वळणदार कॉरिडॉर आणि खूप लांब, वळणावळणाच्या सोल्यूशनसह मेझ तयार करतो.

परिपूर्ण भूलभुलैया म्हणजे असा भूलभुलैया ज्यामध्ये भूलभुलैयामधील कोणत्याही बिंदूपासून दुसऱ्या बिंदूपर्यंत एकच मार्ग असतो. याचा अर्थ असा की तुम्ही वर्तुळात फिरू शकत नाही, परंतु तुम्हाला अनेकदा अडचणी येतील, ज्यामुळे तुम्हाला मागे वळून परत जावे लागेल.

येथे तयार केलेल्या भूलभुलैया नकाशांमध्ये कोणत्याही सुरुवातीच्या आणि शेवटच्या स्थानांशिवाय डीफॉल्ट आवृत्ती समाविष्ट आहे, म्हणून तुम्ही ते स्वतः ठरवू शकता: भूलभुलैयामधील कोणत्याही बिंदूपासून इतर कोणत्याही बिंदूपर्यंत एक उपाय असेल. जर तुम्हाला प्रेरणा हवी असेल, तर तुम्ही सुचविलेले प्रारंभ आणि शेवटचे स्थान सक्षम करू शकता - आणि दोघांमधील उपाय देखील पाहू शकता.

रिकर्सिव्ह बॅकट्रॅकर अल्गोरिथम ही परिपूर्ण भूलभुलैया (कोणत्याही लूपशिवाय आणि कोणत्याही दोन बिंदूंमधील एकच मार्ग नसलेली भूलभुलैया) निर्माण करण्यासाठी एक डेप्थ-फर्स्ट सर्च पद्धत आहे. हे सोपे, कार्यक्षम आहे आणि लांब, वळणदार कॉरिडॉरसह दृश्यमानपणे आकर्षक भूलभुलैया तयार करते.

त्याचे नाव असूनही, ते रिकर्सन वापरून अंमलात आणण्याची आवश्यकता नाही. ते बहुतेकदा LIFO क्यू (म्हणजेच स्टॅक) वापरून पुनरावृत्ती दृष्टिकोनात अंमलात आणले जाते. खूप मोठ्या भूलभुलैयासाठी, प्रोग्रामिंग भाषा आणि उपलब्ध मेमरीवर अवलंबून, रिकर्सन वापरल्याने कॉल स्टॅक ओव्हरफ्लो होण्याची शक्यता जास्त असते. LIFO क्यू मोठ्या प्रमाणात डेटा हाताळण्यासाठी अधिक सहजपणे अनुकूलित केली जाऊ शकते, जरी उपलब्ध मेमरी अपुरी असल्यास डिस्कवर किंवा डेटाबेसमध्ये क्यू ठेवली तरीही.

हे कसे कार्य करते

हे अल्गोरिथम स्टॅक-आधारित डेप्थ-फर्स्ट सर्च दृष्टिकोन वापरून चालते. येथे चरण-दर-चरण ब्रेकडाउन आहे:

1. सुरुवातीचा सेल निवडा आणि तो भेट दिलेला म्हणून चिन्हांकित करा.
2. भेट न दिलेले सेल असताना: शेजारच्या सेलकडे पहा जे अद्याप भेट दिलेले नाहीत. जर किमान एक भेट न दिलेला शेजारी असेल तर: भेट न दिलेल्या शेजाऱ्यांपैकी एक यादृच्छिकपणे निवडा. सध्याच्या सेल आणि निवडलेल्या शेजाऱ्यामधील भिंत काढा. निवडलेल्या शेजाऱ्याकडे जा आणि तो भेट दिला म्हणून चिन्हांकित करा. सध्याच्या सेलला स्टॅकवर ढकला. जर भेट न दिलेले शेजारी अस्तित्वात नसतील तर: स्टॅकमधील शेवटचा सेल पॉप करून मागे जा.
3. स्टॅक रिकामा होईपर्यंत ही प्रक्रिया सुरू ठेवा.

या अल्गोरिथमबद्दल एक मनोरंजक गोष्ट म्हणजे ते भूलभुलैया जनरेटर आणि भूलभुलैया सोडवणारे म्हणून काम करते. जर तुम्ही ते आधीच तयार झालेल्या भूलभुलैयावर चालवले आणि तुम्ही निश्चित केलेल्या शेवटच्या बिंदूवर पोहोचल्यावर थांबलात, तर स्टॅकमध्ये भूलभुलैयाचे समाधान असेल.

माझ्याकडे या साइटवर या अल्गोरिथमच्या दोन आवृत्त्या आहेत: या पृष्ठावर भूलभुलैया निर्माण करण्यासाठी LIFO क्यू आधारित आणि भूलभुलैया सोडवण्यासाठी पुनरावृत्ती आधारित, इतर अल्गोरिथमद्वारे देखील निर्माण केलेले भूलभुलैया (उपायांसह नकाशे अशा प्रकारे बनवले जातात). दोन भिन्न आवृत्त्या असणे फक्त खेळांसाठी आहे कारण मी एक मूर्ख आहे ज्याला ते मनोरंजक वाटते, दोन्हीपैकी एक दोन्हीसाठी काम करू शकले असते ;-)

पुढील वाचन

जर तुम्हाला ही पोस्ट आवडली असेल, तर तुम्हाला हे सूचना देखील आवडतील:

• एलरचा अल्गोरिदम भूलभुलैया जनरेटर
• वाढते वृक्ष अल्गोरिदम चक्रव्यूह जनरेटर
• विल्सन अल्गोरिदम मेझ जनरेटर