डार्ट पर सेलुलर ऑटोमेटा

क्लासिक सेलुलर ऑटोमोबोन का कार्यान्वयन - कॉन्यूवियन "लाइफ" - एक नौसिखिया प्रोग्रामर के लिए एक ही कार्य है क्योंकि यह एक साधारण रेडियो रिसीवर को मिलाप करने के लिए एक रेडियो तकनीशियन के लिए है। उन लोगों के लिए जो "जीवन" नहीं जानते हैं, इस लेख को पढ़ें: विकिपीडिया: जीवन (खेल) ।

मुझे आपको नियमों को याद दिलाना है: कार्रवाई सेल फ़ील्ड पर होती है। प्रत्येक कोशिका में 8 पड़ोसी होते हैं - पक्ष या कोनों द्वारा इसके निकट स्थित कोशिकाएं। खेल की शुरुआत में, कुछ कोशिकाओं को भरा जाता है, प्रारंभिक जीव का गठन होता है, बाकी खाली होते हैं। विकास निम्नानुसार होता है: अगली पीढ़ी में, 2 से कम या 3 से अधिक पड़ोसियों वाली सभी भरी हुई कोशिकाओं को साफ किया जाता है और ठीक 3 पड़ोसियों के साथ खाली कोशिकाओं को भरा जाता है।

दिलचस्प विन्यास के साथ खेलने के बाद, यह थोड़ा उबाऊ हो जाता है। वास्तव में, 40 वर्षों से, वर्णित सभी चीजों को विभिन्न लेखों और पुस्तकों के सैकड़ों पन्नों पर चबाया गया है। कुछ नया और दिलचस्प खोजना मुश्किल है। फिर नियमों को बदलने की इच्छा है - क्या होगा अगर नए जीव पूरी तरह से अलग तरीके से व्यवहार करते हैं?


यहां आप तुरंत डेमो देख सकते हैं।

शुरुआत के लिए, आप उन कोशिकाओं की संख्या को बदल सकते हैं, जिन पर पुरानी मृत्यु और नए दिखाई देते हैं। केवल 2 ⁸ विकल्प (एन = 1..8 पड़ोसियों पर एक सेल दिखाई देता है?) कोशिकाओं के जन्म के लिए और मृत्यु के लिए 2 ⁹ , कुल मिलाकर हमारे पास 2 ¹⁷ , एक अच्छी राशि है। हालांकि, इनमें से अधिकांश विन्यास रुचि के नहीं हैं (वे जल्दी से मर जाते हैं या अनिश्चित काल तक फैल जाते हैं)। जॉन कॉनवे ने खुद लिखा कि उन्होंने नियमों का प्रयोग किया, मूल्यों का चयन किया ताकि विकास दिलचस्प हो: खराब अनुमानित, अपेक्षाकृत लंबा, विभिन्न पृथक विन्यासों को पीछे छोड़ते हुए, और इसलिए भी कि सरल रूप से बढ़ते विन्यास नहीं थे। और अंत में मैं एक ही आया कि अब सबसे बड़ी लोकप्रियता है।

अब नियमों को सामान्य बनाने की कोशिश करते हैं। हमारे पास एक सेल है जिसे भरा या खाली किया जा सकता है, साथ ही साथ कोशिकाओं का एक समूह - पड़ोसी। कुल 2 समूह - एक सेल से और 8 सेल से।

हमें निर्देशांक के वेतन वृद्धि की एक सूची की आवश्यकता है जो संसाधित एक के सापेक्ष समूह की कोशिकाओं की स्थिति निर्धारित करती है। पहले समूह (केंद्रीय सेल) के लिए यह एकमात्र जोड़ी (+0, +0) होगी। दूसरी (पड़ोसी कोशिकाओं) के लिए - आठ जोड़े (-1, -1), (-1, +0), ..., (+1, +0), (+1, +1)।

नियमों को निर्धारित करने के लिए, हम बूलियन प्रकार के द्वि-आयामी सरणी का उपयोग करते हैं। आयाम समूहों के संभावित राज्यों की संख्या द्वारा निर्धारित किया जाता है: पहले के लिए - दो (केंद्र में सेल खाली या भरा हुआ है), दूसरे के लिए - नौ (0 पड़ोसियों से अधिकतम संख्या - 8)।

ऐरे एलिमेंट इंडेक्स प्रत्येक समूह में भरे हुए सेल की संख्या को निर्धारित करता है, और एलिमेंट (गलत) या भरा (सही): प्रोसेसिंग के बाद एलिमेंट वैल्यू सेल की स्थिति को निर्धारित करता है। इस प्रकार, यह पता लगाने के लिए कि 4 पड़ोसियों के साथ एक भरे हुए सेल के साथ क्या करना है, हमें इंडेक्स (1, 4) के साथ तत्व को चालू करने की आवश्यकता है। यदि मान गलत है, तो हम सेल को साफ़ करते हैं; यदि सही है, तो हम इसे अपरिवर्तित छोड़ देते हैं। और सरणी की सामग्री इस तरह होगी: सूचकांक (0, 3), (1, 2) और (1, 3) वाले तत्व सत्य हैं, बाकी झूठे हैं।

एन समूहों के लिए नियमों को संक्षेप में प्रस्तुत करने के लिए: समन्वय सरणी में पूर्णांक मानों के जोड़े की एन सूची होगी, और नियमों के सेट को एक एन-आयामी सरणी द्वारा दर्शाया जाएगा, जिनमें से nth आयाम nth समूह के लिए झुकाव जोड़े की सूची की संख्या 1 + होगी।

नियमों की इस संरचना के साथ, विकल्पों की संख्या केवल कल्पना द्वारा सीमित है, हालांकि अभी भी नियमों के विस्तार की संभावना है। अब कार्यान्वयन की बारीकियों के बारे में।

मेरे द्वारा जानी जाने वाली सभी भाषाओं में प्रोग्राम संख्या के साथ कोई सरणी कार्यान्वयन नहीं है, इसलिए आपको अपना स्वयं का लिखना होगा। हम निम्नानुसार एक-आयामी सरणी के माध्यम से करते हैं: चलो n-वें आयाम के लिए _n [आयामी ₁ , Q ₂ , ..., Q _n ] को सूचकांकों की श्रेणी [0 ... Q _n - 1] के साथ _n- आयामी सरणी बनाएँ। हम आयाम Q ₁ * Q ₂ * ... * Q _{n के} साथ एक आयामी सरणी e 'बनाते हैं और प्रत्येक तत्व e [i ₁ , i ₂ , ..., i _n ] तत्व e' [i ₁ * k ₁ + i ₂ * k ₂ + को असाइन करते हैं। ... + i _n * k _n ], जहां k _m = 1 * Q ₁ * Q ₂ * ... * Q _{m - 1} । यही है, k ₁ = 1, k ₂ = Q ₁ , k ₃ = Q ₁ * Q ₂ , आदि। यह एक-से-एक पत्राचार है, दूसरे शब्दों में, सरणी ई के विभिन्न तत्व सरणी के विभिन्न तत्वों के अनुरूप होंगे '।

गति और सरलता के लिए, मैं एक सीमित लूप वाले क्षेत्र को लागू करूंगा। पूर्णांक X के लिए लूप एल्गोरिथ्म रेंज में समन्वय करता है [0 ... K - 1] निम्नानुसार है: यदि, जब समन्वय बदलता है, तो यह इस सीमा को छोड़ देता है, तो हम K इकाइयों द्वारा इसे बढ़ा या घटा देंगे (यह निर्भर करता है कि यह हमारी सीमा के बाईं या दाईं ओर है) जब तक समन्वय निर्धारित सीमा तक नहीं लौटता। फिर, जब सीमा के दाईं ओर "पत्तियों" का समन्वय होता है, तो यह बाईं सीमा के माध्यम से "प्रवेश" करेगा और इसके विपरीत।

एल्गोरिथ्म को सूत्र X = X - मंजिल (X / K) * K द्वारा लागू किया जाता है, लेकिन यदि K दो की शक्ति है, तो तेज और सरल सूत्र X = X & K का उपयोग करना बेहतर है।

क्षेत्र, इसलिए, एन एक्स एन कोशिकाओं का एक दो आयामी सरणी होगा, जिसे परिचित पत्राचार ई (एक्स, वाई) => ई '(एक्स + वाई * एन) का उपयोग करके एक आयामी के रूप में दर्शाया जा सकता है।

अब अनुकूलन के बारे में थोड़ा:

आपको विकास के हर चरण में पूरे क्षेत्र को फिर से नहीं बनाना चाहिए। बेशक, शुरुआत में आपको प्रारंभिक कॉन्फ़िगरेशन के सभी कक्षों को खींचना होगा, लेकिन फिर प्रत्येक पीढ़ी के लिए यह केवल परिवर्तित कोशिकाओं को फिर से तैयार करने के लिए पर्याप्त है।

प्रत्येक सेल के लिए पड़ोसियों की संख्या की जांच करने के साथ सभी भरे हुए कोशिकाओं और पड़ोसी अपूर्ण कोशिकाओं को संसाधित करने के बजाय, यह केवल सेल अधिभोग में परिवर्तन की प्रक्रिया करना बेहतर होता है, प्रत्येक सेल में अपने पड़ोसियों की संख्या को संग्रहीत करता है: जब सेल भरा होता है, तो यह कोशिकाओं पर "स्कैटर" इकाइयां होती है, जिनमें से यह एक पड़ोसी है। , इन कोशिकाओं के लिए पड़ोसियों की संख्या के मूल्य में वृद्धि। और इसके विपरीत, जब सेल शुद्ध होता है, तो यह इन इकाइयों को "लेता है"।

चूंकि हमारे पास कई समूह हैं, इसलिए यह पता चलता है कि प्रत्येक सेल के लिए हमें प्रत्येक समूह के लिए पड़ोसियों की संख्या की एक सूची रखनी चाहिए। लेकिन इस सूची के बजाय एक पूर्णांक के बजाय इसका उपयोग करने के लिए तेजी से होगा यह पत्राचार सिद्धांत के अनुसार एक बहुआयामी सरणी से एक आयामी एक में संक्रमण के दौरान अनुवाद के समान है, जिसे हमने पहले जांच की थी: [के ₁ , के ₂ , ... के _n ] => [के ₁ + क्यू ₁ * के ₂ + क्यू ₁ * क्यू ₂ * के ₃ + ... + क्यू ₁ * ... * क्यू _{एन -1} * के _एन ]।

इस प्रकार, पीढ़ी चक्र इस तरह दिखेगा:

• पहले चक्र से पहले, प्रारंभिक कॉन्फ़िगरेशन के सभी सेल संसाधित होते हैं। वे और वे कोशिकाएं जिनके पड़ोसी हैं, उन्हें संसाधित कोशिकाओं की सूची में दर्ज किया गया है।
• कोशिकाओं से सभी कोशिकाओं को परिवर्तन के लिए जांचा जाता है (यदि उनके राज्य और राज्य इस समय उनके पड़ोसियों की संख्या के अनुरूप नियमों के कोड से समान नहीं हैं)। यदि, नियमों के अनुसार, राज्य को बदलना चाहिए, तो इस सेल को परिवर्तित togglingCells कोशिकाओं की सूची में दर्ज किया गया है।
• कोशिकाओं की सूची साफ हो गई है।
• TogglingCells से सभी कोशिकाएं अपने राज्य को "बिखरने" या "पड़ोस" लेने से बदल देती हैं, जिससे वे पड़ोसी हैं। पड़ोसियों की एक परिवर्तित संख्या वाली सभी कोशिकाओं को कोशिकाओं में प्रवेश किया जाता है।
• TogglingCells कोशिकाओं को खींचा जाता है।
• togglingCells साफ हो गया है।

मैंने कार्यक्रम को Google डार्ट भाषा में लिखा है, आप इसे यहाँ देख सकते हैं। आप यहां जावास्क्रिप्ट में संकलित कार्यक्रम चला सकते हैं ।



अब नियमों के दिलचस्प सेटों के बारे में जिन्हें मैंने पाया:

क्षैतिज-ऊर्ध्वाधर-विकर्ण टूटना

सैंडी जीवी (SandyLifeHV)

• उत्तरजीविता
  
  • 1 या 2 तिरछे + 1 या 2 लंबवत / क्षैतिज रूप से
• जन्म
  
  • 2 तिरछे + 0 लंबवत / क्षैतिज रूप से
  • 0 तिरछे + 2 लंबवत / क्षैतिज रूप से
  • 1 तिरछे + 2 लंबवत / क्षैतिज रूप से

नियमों का यह संस्करण क्विकसैंड के समान एक विकास द्वारा विशेषता है। एक बेतरतीब भरा मैदान कई सौ पीढ़ियों के बाद स्थिर हो जाता है। इस स्थिति में, कई स्थिर कॉन्फ़िगरेशन बनते हैं, जैसे कि ब्लॉक और विकर्ण धारियां, और 2 पीढ़ियों की अवधि के साथ सबसे सरल स्पंदित विन्यास - 2 कोशिकाओं की एक विकर्ण पंक्ति और 3 कोशिकाओं का एक ऊर्ध्वाधर। 3 पीढ़ियों की अवधि के साथ एक स्पंदित क्रॉस भी अक्सर पाया जाता है। "शॉकर" भी हैं - कई स्पंदनशील कोशिकाओं के साथ स्थिर विन्यास, साथ ही साथ "तितलियां" - कीट फड़फड़ाते पंखों के समान, लंबी अवधि के साथ स्पंदनात्मक विन्यास। मैंने विन्यास नहीं देखा है।

SandyD (SandyLifeD)

नियम पिछले वाले के समान हैं, केवल जन्म के बजाय 1 पड़ोसी तिरछे और 2 लंबवत / क्षैतिज रूप से, जन्म नियम का उपयोग 2 पड़ोसियों के साथ तिरछे और 1 खड़ी / क्षैतिज रूप से किया जाता है।

इसके अलावा quicksand, लेकिन वे तेजी से स्थिर होते हैं - 100-200 पीढ़ियों के बाद, और अन्य कॉन्फ़िगरेशन उत्पन्न होते हैं। लगभग कोई स्थिर कॉन्फ़िगरेशन (मुख्य रूप से 2x2 ब्लॉक) नहीं हैं, लेकिन लोगों को स्पंदित करते हैं - एक संपूर्ण चिड़ियाघर। आप लोकप्रिय कॉन्फ़िगरेशन "ब्रैकेट", चमकता हुआ किनारों के साथ वर्ग, पिछले नियमों से एक क्रॉस, "कैंडी", स्पंदित कचरा और एक बड़ा जटिल और बड़े "बल्ले" के रूप में नोट कर सकते हैं। कभी-कभी एक कॉन्फ़िगरेशन ऊर्ध्वाधर / क्षैतिज लड़ाकू जेट का उत्पादन करता है।

अमीबा (अमीबालाइफ)

• उत्तरजीविता
  
  • 2 तिरछे + 0-2 लंबवत / क्षैतिज रूप से
  • 0-2 तिरछे + 2 लंबवत / क्षैतिज रूप से
• जन्म
  • 2 तिरछे + 0-2 लंबवत / क्षैतिज रूप से

इन नियमों के तहत यादृच्छिक विन्यास जल्दी से हीरे जैसी आकृति ग्रहण कर लेता है। वह कई स्पंदित क्षेत्रों में विभाजित होने के लिए इच्छुक नहीं है और बाईं स्थिर और स्पंदित ब्लॉकों को चुनना पसंद करती है। अत्यधिक अनिच्छा से बढ़ता है और सिकुड़ता है, लेकिन छोटे आकार के साथ यह अक्सर गायब हो जाता है, एक छोटे से स्थिर या स्पंदित विन्यास को पीछे छोड़ देता है।

इलेक्ट्रॉनिक्स (इलेक्ट्रॉनिकलाइफ)

• उत्तरजीविता
  
  • 2-3 तिरछे + 2 लंबवत / क्षैतिज रूप से
  • 0-1 तिरछे + 2-3 लंबवत / क्षैतिज रूप से
• जन्म
  • 1-2 तिरछे + 1-2 लंबवत / क्षैतिज रूप से

ये नियम इस तथ्य को जन्म देते हैं कि कॉन्फ़िगरेशन मुद्रित सर्किट बोर्ड की पटरियों के समान आयताकार-विकर्ण आकार के होते हैं। लगभग एक हजार पीढ़ियों के बाद, आयताकार विन्यास को स्पंदित करना आमतौर पर क्षेत्र में बना रहता है।

पफ टूट जाना

तरल (लिक्विडलाइफ)

• कोशिका का उद्भव / उत्तरजीविता
  • 0-1 ऊपरी + 1-3 केंद्रीय + 2-3 कम
  • 1-2 ऊपरी + 2-3 केंद्रीय + 0-1 कम
  • 2-3 ऊपरी + 1-3 केंद्रीय + 1-2 कम

विन्यास जल्दी से त्रिकोणीय "चश्मे" में "उबलते पानी के साथ भाप" का रूप ले लेता है। यह आमतौर पर कई हजार पीढ़ियों के बाद "शांत" होता है, जिसके बाद इन में "पानी" स्पंदित करने के साथ इन "चश्मे" की एक प्रणाली बनी हुई है।

अर्माडा (आर्मडालाइफ)

• कोशिका का उद्भव / उत्तरजीविता
  
  • 0-1 ऊपरी + 1-2 केंद्रीय + 2-3 कम
  • 1-3 ऊपरी + 1-2 केंद्रीय + 1-3 कम
  • 2-3 ऊपरी + 1-2 केंद्रीय + 0-1 कम

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

साइड ब्रेकडाउन

तार (वायरलाइफ)

• उत्तरजीविता
  • 1-3 क्षैतिज + 1-2 ऊर्ध्वाधर
• जन्म
  • 2 क्षैतिज + 2-3 ऊर्ध्वाधर

यह कॉन्फ़िगरेशन झटके में फिर से गिराने और हमला करने के लिए जाता है, धीरे-धीरे अंत में विस्तार करता है और सही कोणों पर तिरछे "तार" टुकड़ों को छोड़ता है। इसके अलावा अक्सर एक "महत्वपूर्ण" पत्थर और एक मधुमक्खी, एक घूर्णन "बृहदान्त्र" होता है। स्पंदित विन्यास के बीच, एक "चार बिंदुओं", दो पत्थरों के एक "crumpler", और एक "स्माइल" को एक लंबे स्पंदन अवधि के साथ भेद कर सकता है। अक्सर, एक छोटे से अलग कॉन्फ़िगरेशन के विकास के परिणामस्वरूप, एक स्थिर "रोम्बस" बनता है।

कर्ल (TwirlLife)

• उत्तरजीविता
  • 1-3 क्षैतिज + 1-3 ऊर्ध्वाधर
• जन्म
  • 2 क्षैतिज + 2 ऊर्ध्वाधर

यहां, "तार" के टुकड़ों के बजाय, "पत्थरों" के स्थिर ढेर और विभिन्न जटिलता के "कर्ल" बनते हैं। वहाँ एक आम तिरछे चलते "स्थान" विन्यास है।

ब्रैकेट ब्रेकडाउन

सांप (सांप)

• उत्तरजीविता
  • एक कोष्ठक में 2-3 कोशिकाएँ, दूसरे में 0
• जन्म
  • प्रत्येक स्टेपल में 1-2 कोशिकाएं

इन नियमों के साथ, यहां तक ​​कि सबसे छोटे विन्यास अक्सर जटिल "भाप इंजन" में बदल जाते हैं। हम एक ऊर्ध्वाधर "सांप" को बाइसेल्युलर "मर" की एक संभावित पीढ़ी के साथ अलग कर सकते हैं, एक बढ़ती धारीदार त्रिकोण, एक बढ़ती विकर्ण पंक्ति, स्पंदनशील कचरा पैदा करते हैं। इसके अलावा, कुछ विन्यास परिणामी विकर्ण पंक्ति के साथ एककोशिकीय "संकेतों" को प्रसारित कर सकते हैं, जिसे अन्य विन्यासों द्वारा दबाया जा सकता है। एक सरल लंबवत चलती कॉन्फ़िगरेशन है - एक "ट्रॉली", जो लुप्त होने वाले "धुएं" को पीछे छोड़ सकती है, साथ ही एक स्पंदित "मकड़ी", जो अक्सर विकर्ण पंक्ति का एक स्टेबलाइज़र है।

कार्यक्रम में आपको नियमों के कोड भी मिलेंगे, जिनमें से प्रत्येक में एक दिलचस्प विशेषता है।