क्या 3 आयामी मैज बनाने के लिए एल्गोरिदम हैं? अनिवार्य रूप से 2 डी भूलभुलैया के समान ही है लेकिन ज़ेड गहराई अक्ष को पार किया जा सकता है? स्टार्ट टू एंड से प्राप्त करने के लिए विचार अभी भी वही है। बैकट्रैकिंग अभी भी इस्तेमाल किया जा सकता है?3 डी Mazes के लिए एल्गोरिदम
3 डी भूलभुलैया उत्पन्न करने के लिए मुझे किस एल्गोरिदम का उपयोग करना चाहिए?
here देखें। मेरा मतलब है कि आप भी घन में जा सकते हैं, न कि इसके चेहरों को फिर से शुरू करें।
मैंने क्रुस्काल के एल्गोरिदम here का उपयोग करके कुछ साल पहले 2 डी मैज बनाया था। आपके द्वारा वर्णित 3 डी मामले के साथ काम नहीं कर सका कोई कारण नहीं होना चाहिए। असल में आप एक सेल को एक घन मानते हैं, और इसमें एक बड़ी सरणी होती है जिसमें (प्रत्येक कोशिकाओं के लिए), +/- x, y, और z दिशाओं में 6 दीवारें होती हैं। एल्गोरिदम प्रारंभ में हर जगह सभी दीवारों से शुरू होता है और यादृच्छिक रूप से दीवारें गायब हो जाती हैं जब तक कि भूलभुलैया में हर कोशिका जुड़ा न हो।
+1 क्रस्कल के एल्गोरिदम के लिए। :) –
मुझे मूल विचार पसंद है, लेकिन शायद लक्ष्य केवल भूलभुलैया में हर सेल नहीं होना चाहिए, बल्कि इसके अलावा कनेक्शन लूप-मुक्त (ग्राफ सिद्धांत शब्दावली में "पेड़" होना चाहिए)। यह भूलभुलैया के समाधान को अद्वितीय होने के लिए मजबूर करेगा। इसके लिए यह आवश्यक है कि (अंतराल) दीवारों के गायब होने के लिए कुछ यादृच्छिक विकल्प अस्वीकार कर दिए जाएंगे, जब भी वे कनेक्शन में लूप पेश करेंगे। समतुल्य रूप से ये "खारिज" विकल्प वे हैं जो ग्राफ़ में जुड़े घटकों की संख्या को कम नहीं करते हैं। – hardmath
हार्डमाथ; कृष्काल का एल्गोरिदम इसका ख्याल रखता है। मैंने वास्तव में अपने oversimplified स्पष्टीकरण के साथ यह समझाया नहीं था। असल में, एक दीवार केवल तभी हटा दी जाएगी जब यह 2 नए क्षेत्रों से जुड़ा हो। यह जांच कर यह करता है कि दीवार के प्रत्येक किनारे पर दोनों कोशिकाएं एक अलग सेट से संबंधित हैं।यह एक विवाद-सेट डेटा संरचना के साथ वास्तव में कुशलता से किया जा सकता है। विकिपीडिया लिंक इसे बेहतर समझाता है। –
मेरे पास सभी चीजों में से 2 डी भूलभुलैया उत्पन्न करने के लिए कोड है, आरपीगल (कुछ सीखने के दौरान मैंने स्वयं अभ्यास के रूप में किया था)। जिस तरह से मैंने इसे लिखा है, सामान्य अलोग्रिथम के लिए आवश्यक केवल परिवर्तनों के बारे में ज़ेड आयाम को अतिरिक्त आयाम के रूप में जोड़ना होगा ...
पूरी बात 20 पेज लंबी है (हालांकि इसमें इनपुट/आउटपुट शामिल है) , तो यहां कुछ कोड है। आपको इसे जो भी भाषा चाहिए, उसमें अनुवाद करने में सक्षम होना चाहिए: मैंने इसे स्पेगेटी-कोड बेसिक से अनुवादित किया है (goto एस यहां बहुत अधिक उपयोग किए गए थे, हाँ। लेकिन यह एक मजेदार अभ्यास था)। दीवारों कि 'वर्ग', और चाहे या नहीं कि वर्ग दौरा किया गया है के लिए अन्य पर कब्जा के लिए एक:
//set out maximum maze size
maximumMazeSquareCounter = mazeHorizontalSize * mazeVerticalSize + 1;
// generate a starting horizontal positiongetRandomNumber(seed : randomNumber);
currentHorizontalPosition = %inth(randomNumber * (mazeHorizontalSize - 1)) + 1;
currentVerticalPosition = 1;
mazeSquareCounter = 1;
// generate the top row of the maze (with entrance)
mazeTopRow = generateEntrance(currentHorizontalPosition);
//write to the printer file
writeMazeDataLine(mazeTopRow);
mazeSquareCounter += 1;
//set the first position in the maze(the entry square
setPathPoint(currentHorizontalPosition : currentVerticalPosition);
//do until we've reached every square in the maze
dou mazeSquareCounter >= maximumMazeSquareCounter;
//get the next available random direction
mazeDirection = getNextRandomDirection(getNextAvailableDirection(currentHorizontalPosition : currentVerticalPosition));
//select what to do by the returned results
select;
//when FALSE is returned - when the maze is trapped
when mazeDirection = FALSE;
//if not at the horizontal end of the maze
if currentHorizontalPosition <> mazeHorizontalSize;
//add one to the position
currentHorizontalPosition += 1;
//else if not at the vertical end of the maze
elseif currentVerticalPosition <> mazeVerticalSize;
//reset the horizontal position
currentHorizontalPosition = 1;
//increment the vertical position
currentVerticalPosition += 1;
//otherwise
else;
//reset both positions
currentHorizontalPosition = 1;
currentVerticalPosition = 1;
endif;
//when 'N' is returned - going up (other directions removed)
when mazeDirection = GOING_NORTH;
//set the point above current as visited
setPathPoint(currentHorizontalPosition : currentVerticalPosition - 1);
//set the wall point to allow passage
setWallDirection(currentHorizontalPosition : currentVerticalPosition : GOING_NORTH);
//change the position variable to reflect change
currentVerticalPosition -= 1;
//increment square counter
mazeSquareCounter += 1;
endsl;
enddo;
//generate a random exit
// get a random number
getRandomNumber(seed : randomNumber);
// set to the horzontal position
currentHorizontalPosition = %inth(randomNumber * (mazeHorizontalSize - 1)) + 1;
//set the vertical position
currentVerticalPosition = mazeVerticalSize;
//set wall to allow for exit
setWallDirection(currentHorizontalPosition : currentVerticalPosition : GOING_SOUTH);
पूरे बात दो दो आयामी सरणी (अच्छी तरह से, आरपीजी समकक्ष) द्वारा समर्थित है। हर वर्ग का दौरा करने के बाद भूलभुलैया बनाई जाती है। केवल एकमात्र रास्ता, कीड़े-मोड़ भूलभुलैया।
यह त्रि-आयामी बनाने के लिए, इसे त्रि-आयामी सरणी का उपयोग करें, और आवश्यक आयाम अनुक्रमणिका जोड़ें।
मैं एक वर्ग ग्रिड पर 2 डी mazes के लिए कुछ समय पहले एक एल्गोरिथ्म के लिए बनाया गया है, वहाँ कोई कारण नहीं क्यों यह भी एक घन ग्रिड पर एक 3 डी भूलभुलैया के लिए नहीं काम करना चाहिए है।
एक 3 डी ग्रिड के साथ शुरू शुरू में पूरी तरह से दीवार कोशिकाओं के साथ आबादी।
...
प्रारंभ ग्रिड के एक छोर पर एक एजेंट, एजेंट एक्स में एक सीधी रेखा में गमन, वाई, जेड, -X, -Y या -Z दिशा समाशोधन दीवार के रूप में वह यात्रा करता है ।
एक्शन 'एन' में प्रत्येक चरण होने का एक छोटा सा मौका है।
एक्शन 'एम' तब होता है जब एजेंट सीधे एजेंट के सामने होता है और उसके सामने वाला सेल खाली होता है।
'एन' के एक यादृच्छिक पसंद है:
'एम' के एक यादृच्छिक विकल्प है और कुछ भी नहीं कर रहा है,
mazes के विशिष्ट हैं, और उनके चरित्र अत्यधिक 'एम' (मान्य जंक्शनों से कोई लेना देना) के लिए है और यह भी होने वाली 8 करने के लिए 1 के अवसरों को समायोजन करके ट्रिगर का समायोजन करके लचीला है। आप एक या दो क्रियाएं हटाना चाहते हैं, या अपने स्वयं के कार्यों को पेश करना चाहते हैं, उदाहरण के लिए एक छोटे से समाशोधन या एक कदम को दूर करने के लिए।
'एन' के लिए ट्रिगर भी एक और प्रकार की यादृच्छिकता हो सकता है, उदाहरण के लिए नीचे दिया गया उदाहरण काफी शाखाई मैज बनाने के लिए उपयोग किया जा सकता है, जो अभी भी कुछ लंबे सीधे हिस्से हैं।
float n = 1;
while (random_0_to_1 > 0.15)
{
n *= 1.2;
}
return (int)n;
कुछ छोटे समायोजन कार्रवाई 'एम' के लिए उदाहरण के ट्रिगर के लिए, मेरे सरल वर्णन से की आवश्यकता होगी कोशिकाओं यह रूप में अच्छी तरह जंक्शनों किस तरह कर रहे हैं पर निर्भर करता है की जाँच करता है करने के लिए आसन्न जाँच करने की आवश्यकता होगी वांछित।
भूलभुलैया के चक्र के लिए या तो 5 या 6 की आवश्यकता होती है और भूलभुलैया के लिए कम से कम एक विकल्प 'एम' कार्रवाई 5 और 6 की आवश्यकता होती है।
संभावनाओं/कार्यों और 'एम' ट्रिगर्स के कुछ विकल्प मैज बनाने वाले होते हैं जो काम नहीं करते हैं, उदाहरण के लिए अनावश्यक या खाली या दीवार कोशिकाओं से भरा है, लेकिन कई लगातार अच्छे परिणाम उत्पन्न करेंगे।
क्या आप चाहते हैं कि _solves_ एक भूलभुलैया, या _generates_ एक भूलभुलैया? –
@ एक्स-शून्य इसे उत्पन्न करता है। – jmasterx
आप एक ग्रिड पर 2 डी भूलभुलैया बना सकते हैं और इसे 3 डी बनाने के लिए प्रत्येक ग्रिड सेल "ऊंचाई" – danca