यादृच्छिक टाइल लेआउट

Question

मुझे कार्बनिक और यादृच्छिक दिखने वाले तरीके से एक केंद्रीय बिंदु से विकिरण वाली एक बड़ी ग्रिड पर टाइल लगाने की आवश्यकता है। नए टाइल्स को कम से कम 1 अन्य टाइल को छूने वाले ग्रिड पर खुली जगह खोजने की आवश्यकता होगी।

क्या कोई मुझे इस दिशा में मदद करने के लिए दिशा के अधिकार में इंगित कर सकता है? या कुछ बुनियादी अवधारणाओं को मैं इस नस में पढ़ सकता हूं?

उदाहरण के लिए, इस तस्वीर में, पहले से ही बनाया गया आकार (पीला) है और मुझे एक नया टाइल मिल रहा है, जो 1x1, 2x2, या 3x3 हो सकता है। यह पता लगाने का एक अच्छा तरीका खोजने का प्रयास कर रहा हूं कि मैं नया टाइल कहां रख सकता हूं ताकि यह मौजूदा टाइल्स की अधिकतम मात्रा को छू सके।

चित्र: alt text http://osomer.com/grid.JPG

Answer 1

वैकल्पिक रूप से, आप इस समस्या के दृष्टिकोण के रूप में पीले रंग की टाइल्स दूर नीले/पृष्ठभूमि पर "को नष्ट कर रहा" सकता है। ऐसा करने के लिए, प्रत्येक चरण में, एक पीले रंग की टाइल को "क्षरण राशि" ई में एक निश्चित संख्या को एक कार्डिनल दिशा में पड़ोसी पृष्ठभूमि पृष्ठभूमि के साथ एक निश्चित संख्या जोड़ें (और संभवत: उसमें से एक अंश पृष्ठभूमि पृष्ठभूमि टाइल पर पड़ सकता है यह तिरछे)।

फिर, जब कोई नया टाइल लगाने का समय आता है, तो आप प्रत्येक पृष्ठभूमि टाइल के लिए 0 से ई से यादृच्छिक संख्या चुन सकते हैं; सबसे बड़ा एक "eroded" दूर है। वैकल्पिक रूप से, आप ई उनके वजन होने के साथ, एक साधारण भारित यादृच्छिक विकल्प कर सकते हैं।

2x2 या 3x3 टाइल्स के लिए, आप केवल उन टाइलों से चुन सकते हैं जो उपयुक्त रूप से 2x2 या 3x3 वर्ग "फिट" (यानी, 2x2 या 3x3 इसके किनारे पर क्षीणित टाइल "फिट करते हैं, जिससे कि इसका कारण न हो पहले से स्थापित टाइल्स के साथ ओवरलैप)। लेकिन वास्तव में, आप कभी भी प्राकृतिक रूप से एक-एक-एक क्षरण/टाइल प्लेसमेंट के रूप में कुछ नहीं ढूंढ पाएंगे।

आप प्रत्येक पुनरावृत्ति के साथ बने रहने के दौरान क्षरण रकम को फिर से गणना कर सकते हैं, केवल तभी जब आप एक नया टाइल जोड़ते हैं, इसके चारों ओर के क्षरण के योग (एक सरल +=)। इस बिंदु पर, यह एक अन्य परिप्रेक्ष्य/दर्शन के बावजूद अनिवार्य रूप से एक और उत्तर के समान है।

कटाव का एक नमूना ग्रिड ई का योग करता है, प्रत्यक्ष कार्डिनल पड़ोसियों जा रहा है 4 के साथ, और विकर्ण पड़ोसियों जा रहा +1:

Erosion Sums http://img199.imageshack.us/img199/4766/erosion.png

एक उच्च ई साथ लोगों

लिए सबसे अधिक संभावना कर रहे हैं दूर "eroded" हो; उदाहरण के लिए, इस में, पश्चिम और दक्षिण चेहरे पर दो छोटे इनलेट्स पीले रंग से दूर हो जाने की संभावना है, इसके बाद उत्तर और पूर्वी चेहरे पर छोटे बे होते हैं। सबसे कम संभावना है कि वे एक कोने से पीले रंग को छूते हैं। आप तय कर सकते हैं कि प्रत्येक टाइल के लिए 0 से ई से यादृच्छिक संख्या असाइन करके और उच्चतम यादृच्छिक संख्या वाले किसी को मिटाना या एक साधारण भारित यादृच्छिक चयन करना या अपनी पसंद के किसी भी निर्णय विधि से तय करना है।

Answer 2

विशुद्ध रूप से यादृच्छिक के लिए, आप एक खाली ग्रिड और एक "उम्मीदवार" सूची (भी खाली) के साथ शुरू करते हैं।

ग्रिड के केंद्र में पहला टाइल रखें, फिर प्रत्येक आसन्न टाइल को उसमें जोड़ें जिसे आपने अभी "उम्मीदवार" सूची में रखा है। फिर, प्रत्येक मोड़, "उम्मीदवार" सूची में एक यादृच्छिक प्रविष्टि चुनें और वहां एक टाइल रखें। जहां आपने अभी टाइल लगाई है, उसके बगल में प्रत्येक आसन्न ग्रिड स्थान देखें, और प्रत्येक व्यक्ति जो खाली भी है, उसे अगली बार "उम्मीदवार" सूची में रखें (यदि पहले से नहीं है)।

अपने टाइल ग्रिड में छेद बनाने से बचने के लिए, पहले से भरे आसन्न टाइल की संख्या के आधार पर ग्रिड स्थान चुनने की संभावना में वृद्धि करें (इसलिए यदि केवल एक आसन्न टाइल पहले ही भर चुकी है, तो शायद यह कम हो। सब भर चुके हैं, इसकी बहुत अधिक संभावना होगी)।

छद्म कोड में:

grid = new array[width,height]; 
candidates = new list(); 

function place_tile(x,y) { 
    // place the tile at the given location 
    grid[x,y] = 1; 

    // loop through all the adjacent grid locations around the one 
    // we just placed 
    for(y1 = y - 1; y1 < y + 1; y1++) { 
     for(x1 = x - 1; x1 < x + 1; x1++) { 
      // if this location doesn't have a tile and isn't already in 
      // the candidate list, add it 
      if (grid[x,y] != 1 && !candidates.contains(x1,y1)) { 
       candidates.add(x1,y1); 
      } 
     } 
    } 
} 

// place the first tile in the centre 
place_tile(width/2, height/2); 

while (!finished) { 
    // choose a random tile from the candidate list 
    int index = rand(0, candidates.length - 1); 

    // place a tile at that location (remove the entry from 
    // the candidate list) 
    x, y = candidates[index]; 
    candidates.remove(index); 
    place_tile(x, y); 
} 

Answer 3

आपके प्रश्न के साथ समस्या यह है कि 'कार्बनिक और यादृच्छिक' कई अलग-अलग चीजें हो सकती हैं। मुझे दो लिंक

• random fractal terrain (अनुभाग में 'बादल आसमान' देखो और कल्पना करें कि आप यह ख के लिए/डब्ल्यू, या अपने मामले पीला/पृष्ठभूमि में बारी) पैदा दिखा।
• erosion अनुकरण

दो ऊपर नमूने मेरे लिए 'जैविक और यादृच्छिक' कर रहे हैं ('को खत्म' के तहत छवि को देखो), लेकिन आप उन से संतुष्ट नहीं हो सकता है। इसलिए, मुझे लगता है कि आपको 'जैविक और यादृच्छिक' क्या परिभाषित करना होगा।

अभी के लिए, मैं नई टाइल्स को जोड़ने के लिए मार्गदर्शक नियम की अपनी परिभाषा ले लेंगे (लेकिन नहीं लगता कि यह जरूरी एक ही समस्या है) है, जो मैंने पढ़ा है के रूप में:

दो आकृतियों को देखते हुए (यह मानते हुए कि बिटमैप्स)

मैं भी

समझेंगे आकार इस तरह की सापेक्ष स्थिति है कि छू पक्षों की संख्या अधिकतम है
• ओवरलैप अनुमति नहीं है
• आप जिसके परिणामस्वरूप के अंदर छेद छोड़ सकते हैं, आकार में विलय कर दिया
• आप नहीं आकार घुमा सकते हैं

इस तरह की स्थितियों के तहत आप कम तो x y समाधान और में परीक्षण की आवश्यकता प्रत्येक को आपको की आवश्यकता है - अगर ओवरलैप होता है तो इसे छोड़ दें - अगर वे को स्पर्श नहीं करते हैं तो इसे छोड़ दें - यदि वे स्पर्श करते हैं तो सामान्य सामान्य किनारों की संख्या की गणना करें, उपरोक्त सभी तीन परीक्षण निरंतर समय में किए जा सकते हैं। वाई सभी पीले रंग की टाइल स्कैनिंग (जिसमें से संख्या x * y)

तो, उपर्युक्त ओ (एन^4) में आसानी से किया जा सकता है, क्या यह आपके लिए पर्याप्त है?

Answer 4

दोहरी ग्राफ के लिए एक यादृच्छिक स्पैनिंग पेड़ की गणना करें, यानी, वह ग्रिड जिसका चरम आपकी कोशिकाओं के केंद्र हैं। इसके लिए, ग्रिड के केंद्र में शुरू करें और यादृच्छिक गहराई-पहली खोज करें। फिर केंद्र से वृक्ष दूरी बढ़ने के लिए कोशिकाओं की साजिश।