प्रिंटर के रूप में टेट्रिस

आकार के एक पूर्वनिर्धारित अनुक्रम को चालू करना, पुनर्व्यवस्थित करना और कम करना, टेट्रिस प्रिंटर एल्गोरिथ्म टेट्रिस यांत्रिकी का उपयोग करता है जो मनमाना बिटमैप उत्पन्न करता है।

एल्गोरिथम विवरण

एल्गोरिथ्म स्रोत छवि के पिक्सल को रेखा से टेट्रिस फील्ड लाइन के वर्गों में परिवर्तित करता है, नीचे से ऊपर की ओर बढ़ता है। एक एकल वर्ग उत्पन्न करने के लिए, एल्गोरिथ्म एक आयताकार क्षेत्र से मिलकर एक संरचना बनाता है जो इसके नीचे एक वर्ग द्वारा पूरी तरह से समर्थित है। आयताकार क्षेत्र की विधानसभा पूरी होने के बाद, इसकी रेखाएं साफ हो जाती हैं, इसके तहत एक वर्ग निकलता है। यहाँ इस व्यवहार के तीन उदाहरण हैं।




जैसा कि नीचे दिखाया गया है, एल्गोरिथ्म भी एक संरचना के साथ कई वर्ग उत्पन्न कर सकता है।


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


नीचे दिखाए गए 5 लाल वर्गों की पंक्ति 3 लाल वर्गों की पंक्ति के शीर्ष पर है। यह नीचे की रेखा के ऊपर एक सपाट मंच का निर्माण करके महसूस किया जाता है। मंच 5 लाल वर्ग उत्पन्न करने के लिए आवश्यक समर्थन प्रदान करता है। अंत में, अंतिम आकृति डालकर प्लेटफ़ॉर्म को हटा दिया जाता है, और नई लाइन जगह में आ जाती है। ध्यान दें कि यदि एल्गोरिदम को रिवर्स ऑर्डर (5 लाल वर्गों की एक पंक्ति के ऊपर 3 लाल वर्गों की एक पंक्ति) में लाइनें उत्पन्न करने की आवश्यकता है, तो प्लेटफ़ॉर्म की आवश्यकता नहीं होगी।

एक वर्ग पैटर्न

संदर्भ के लिए, मैं 7 टेट्रामिनो (खेल के टुकड़े) के नाम दूंगा।


लेख में प्रस्तुत टेट्रिस प्रिंटर एल्गोरिथ्म का संस्करण विशेष रूप से पुराने वीडियो गेम से स्प्राइट के प्रतिपादन के लिए बनाया गया है। ये गेम 8 × 8 टाइलों में ग्राफिक्स पैक करते हैं, और प्रत्येक पिक्सेल के लिए 2 बाइट आवंटित किए गए थे। इसलिए, स्प्राइट्स में आमतौर पर केवल 3 रंग और पारदर्शी क्षेत्र होते हैं और ज्यादातर का आकार 16 × 16 या 16 × 32 पिक्सेल होता है।

नीचे दिया गया एनीमेशन व्यक्तिगत वर्गों को बनाने के लिए उपयोग किए गए सभी पैटर्न दिखाता है। प्रत्येक पैटर्न विनिमेय टेट्रामिनो जे, टी और एल का उपयोग करता है, जो नीचे एक एकल वर्ग बनाता है। एल्गोरिथ्म इस टेट्रामिनो को स्प्राइट में मौजूद 3 रंगों में से एक को असाइन करता है। टेट्रामिनो के बाकी हिस्सों को मनमाना रंग सौंपा गया है। गेमप्ले के दौरान, सभी रंग स्थिर रहते हैं।


तीन टेट्रामिनो के आकार के कारण, पहले दो और अंतिम दो स्तंभों में सभी तीन रंगों से एक वर्ग बनाना असंभव है। इसलिए, 16 पिक्सेल की चौड़ाई के साथ स्प्राइट के प्रतिपादन के लिए खेल के मैदान की न्यूनतम चौड़ाई 2 + 16 + 2 = 20 वर्ग है। हालांकि, यह पता चला कि 20 बहुत कम है।

जैसा कि नीचे दिखाया गया है, एकल तल वर्ग से ऊपर का क्षेत्र केवल एक पंक्ति से मिलकर नहीं बन सकता है, क्योंकि केवल आंकड़े जो इसमें फिट हो सकते हैं (टेट्रामिनो I) का समर्थन नहीं है।


दो पंक्तियों के साथ, पूरे खेल के मैदान को फैलाने का एकमात्र तरीका है ताकि उसे समर्थन मिले ताकि टेट्रामिनो एस और जेड का उपयोग किया जा सके। लेकिन इस मामले में, शीर्ष पंक्ति में छेद बने रहेंगे।


नीचे वर्ग के ऊपर आवश्यक लाइनों की न्यूनतम संख्या 3 है, और जैसा कि ऊपर कई बार दिखाया गया है, ऐसे पैटर्न मौजूद हैं। 20 वर्गों में 16 पिक्सेल की चौड़ाई के साथ स्प्राइट रखने के लिए आवश्यक न्यूनतम चौड़ाई है। लेकिन 20 × 3 + 1 = 61, और यह संख्या 4 से विभाज्य नहीं है, जिसका अर्थ है कि इसे टेट्रामिनो से नहीं बनाया जा सकता है। हालांकि, 21 की चौड़ाई हमें 21 × 3 + 1 = 64 देती है, और इसे 16 टेट्रामिनो से बनाया जा सकता है। वास्तव में, यह चौड़ाई एल्गोरिदम को स्प्रैड को 17 पिक्सेल तक चौड़ा करने की अनुमति देती है।

मूल टेट्रिस के खेल के मैदान का आकार 10 × 20 वर्ग (1: 2 अनुपात) है। एल्गोरिथ्म के संस्करण में, यह अनुपात संरक्षित है - खेल के मैदान का आकार 21 × 42 वर्ग है।

चूंकि टेट्रामिनो जे, टी, और एल एक वर्ग बनाते समय विनिमेय हैं, और इन टेट्रामिनो के 3 वर्ग इसके ऊपर एक रेखा बनाने में शामिल हैं, एकल वर्ग बनाने के लिए 21 - 3 = 18 पैटर्न हैं। हालांकि, दर्पण समरूपता के कारण, वास्तव में केवल 9 हैं। इनमें से अधिकांश के लिए काम करने वाली 3 पंक्तियां हैं 9. हालांकि, एक संपूर्ण कंप्यूटर अध्ययन ने दिखाया कि दो पैटर्न की अधिक आवश्यकता थी। अगला संभावित विकल्प 7 लाइनें है, क्योंकि 21 × 7 + 1 = 148, जिसमें 37 टेट्रामिनो की आवश्यकता होती है। जैसा कि नीचे की छवियों में दिखाया गया है, ऐसे पैटर्न मौजूद हैं।

एकाधिक वर्ग पैटर्न

कई वर्ग बनाने के लिए पैटर्न एक ही वर्ग के पैटर्न द्वारा बनाए गए तीन रंगों तक सीमित हैं। परिणामी वर्ग टेट्रामिनो जे, टी और एल से निर्मित होते हैं, जिनमें से प्रत्येक निर्माण रेखा के ऊपर एक रेखा में 3 वर्गों पर कब्जा कर लेता है। एक एकल पैटर्न के साथ संभावित रूप से बनाए जा सकने वाले वर्गों की अधिकतम संख्या 21/3 = 7. है, हालांकि, 16 पिक्सेल की चौड़ाई के साथ स्प्राइट के लिए, सबसे सही टेट्रामिनो एक वर्ग नहीं बना सकता है। यहां तक ​​कि 17 पिक्सल की चौड़ाई के साथ स्प्राइट्स के मामले में, यह केवल एक रंग का एक वर्ग बना सकता है। इसलिए, 7 वर्गों से बनाने का पैटर्न शायद ही कभी उपयोग किया जाता है।


मनमाने ढंग से संयोजन के उपयोग से वर्गों की एक मनमानी संख्या बनाने के लिए पैटर्न की संख्या निर्धारित की जा सकती है। तीन वर्गों की एक पंक्ति के ऊपर एक पंक्ति का प्रतिनिधित्व करते हुए, नीचे दिए गए पैटर्न पर विचार करें। तीन आसन्न सफेद वर्गों के प्रत्येक ब्लॉक टेट्रामिनो का एक हिस्सा नामित करता है; निर्मित वर्ग नहीं दिखाए गए हैं।


तीन टेट्रामिनो 4 voids बनाते हैं। एक विशिष्ट पैटर्न बनाने के लिए 21 - 3 × 3 = 12 अंधेरे वर्ग हैं जिन्हें मनमाने ढंग से इन voids में डाला जा सकता है। इन अंधेरे वर्गों को वितरित करने के तरीकों की संख्या की गणना उन्हें एक लाइन पर रखकर किया जा सकता है जिसमें एकल सफेद वर्गों को डिवाइडर के रूप में माना जाता है।


तो, बहुपद के गुणांक के मूल्य की गणना करने के लिए कार्य कम कर दिया गया था। इन सफेद वर्गों को देखते हुए, आप समझ सकते हैं कि यह 15 में से 3 को चुनने के तरीकों की संख्या का सवाल है। = 455।

सामान्य मामले में, n के लिए यह बराबर है । लेकिन दर्पण समरूपता के कारण, वास्तव में, वे आधे से अधिक हैं; यदि मात्रा विषम है, तो दो से विभाजित करते हुए, हम निकटतम पूर्णांक में इसे पूरी तरह से सममित पैटर्न में शामिल करने के लिए गोल करते हैं जो इस सेट में मौजूद होना चाहिए, उदाहरण के लिए, 455 के साथ मामले के लिए नीचे दिखाया गया है।


इस सूत्र को 7 टेट्रामिनो में लागू करते हुए, हम स्पष्ट की पुष्टि करते हैं: 7 वर्ग बनाने के लिए केवल एक ही पैटर्न है।

6 वर्गों को बनाने का पैटर्न दो तरीकों से बनाया जा सकता है: दो भरी हुई लाइनें (2 × 21 + 6 = 48) और छह भरी हुई रेखाएं (6 × 21 + 6 = 132), जिसके लिए 12 और 33 टेट्रामिनो की आवश्यकता होती है। उपरोक्त सूत्र से पता चलता है कि 6 चौकों को बनाने के लिए 84 पैटर्न हैं, लेकिन उनमें से केवल 35 को 2 पूर्ण लाइनों से बनाया जा सकता है। 49 पैटर्न में 6 लाइनों की आवश्यकता होती है। नीचे दिखाए गए सममित पैटर्न के कारण संख्या विषम है।



यह भी ध्यान देने योग्य है कि यहां 2 लाइनें संभव हैं, क्योंकि एक वर्ग बनाने के पैटर्न के विपरीत जिसमें टेट्रामिनो एस और जेड की आवश्यकता होती है, इन पैटर्न में 6 आंकड़े का उपयोग किया जाता है।

नीचे दी गई तालिका में प्रत्येक प्रकार के पैटर्न द्वारा बनाए गए वर्गों की संख्या, पूर्ण रेखाओं की संख्या, उपयोग किए गए टेट्रामिनो की संख्या और पैटर्न की संख्या को दर्शाया गया है।


पैटर्न के उदाहरण।

मंच

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

नीचे दिए गए चित्रण में 10 मंच पैटर्न हैं। अंतिम उत्पन्न लाइन के वर्गों में से एक के ऊपर टेट्रामिनो टी को कम करके प्लेटफ़ॉर्म का निर्माण शुरू होता है। शेष टेट्रामिनो इस पहले टी पर भरोसा करते हैं। यही है, यदि पिछली उत्पन्न लाइन में कम से कम 1 वर्ग शामिल है, जैसे कि नीचे की छवि में लाल वर्ग, हम अगली पंक्ति उत्पन्न करने के लिए इसके ऊपर एक सपाट मंच बना सकते हैं।


प्लेटफॉर्म के निर्माण के बीच में, नीचे की रेखा पूरी हो जाती है और हटा दी जाती है, जिसके ऊपर तीन रेखाएँ होती हैं। अंतिम टेट्रामिनो जे या एल, जो इन लाइनों को हटा देगा, तब तक डाला नहीं जाता है जब तक कि निर्माण पैटर्न प्लेटफॉर्म के शीर्ष पर अगली स्प्राइट लाइन उत्पन्न नहीं करता है। यह अंतिम आंकड़ा पहले और अंतिम दो पंक्तियों में वर्गों के निर्माण को रोकता है। लेकिन, जैसा कि ऊपर उल्लेख किया गया है, इस प्रक्रिया में उपयोग किए गए टेट्रामिनो जे, टी और एल की ज्यामिति के कारण, वर्गों को बनाने के पैटर्न 17 आंतरिक स्तंभों तक सीमित हैं।

इसके अलावा, टेट्रामिनो टी के शीर्ष पर प्लेटफार्मों के निर्माण के 19 संभावित तरीकों में से केवल 10 को ऊपर दिखाया गया है।

पैक्ड मैटरिस

जैसा कि ऊपर कहा गया है, 6 वर्गों के निर्माण पैटर्न के एक सबसेट में केवल दो लाइनें समाविष्ट हैं। अन्य सभी पैटर्न में 6 लाइनों की आवश्यकता होती है। यह समझने के लिए कि यह मामला क्यों है, नीचे दिए गए पैटर्न पर विचार करें।


ये टेट्रामिनो टेट्रामिनो जे और एल के साथ विनिमेय हैं, और उनमें से प्रत्येक सामान्य पंक्ति में 3 आसन्न वर्ग जोड़ता है। पूर्ण होने वाली पंक्तियों को नीचे दिखाए गए मैट्रिक्स द्वारा दर्शाया गया है।


अब पूरी चीज टेट्रामिनो के साथ खाली जगह पैक कर रही है। बाईं ओर शुरू, एकमात्र विकल्प टेट्रामिनो I अनुक्रम का उपयोग करना है।


शेष स्थान को भरने का एकमात्र तरीका जे और ओ या आई और एल का उपयोग करना है। दोनों विकल्प नीचे दिखाए गए हैं।



दुर्भाग्य से, टेट्रामिनो ओ और एल ऊपर दिखाए गए मैट्रिसेस में समर्थित नहीं हैं। इस 6 वर्ग पैटर्न के लिए एक बड़ी मैट्रिक्स की आवश्यकता होती है।

एक वर्ग बनाने के दो पैटर्न में एक समान समस्या उत्पन्न होती है। नीचे मैट्रिक्स पर विचार करें:


दाएं पर नीचे की रेखा को भरने का एकमात्र तरीका अनुक्रम Z को श्रृंखलाबद्ध करना है।


इसी तरह, निचले बाएँ में 3 खाली वर्ग प्राप्त करने का एकमात्र तरीका टेट्रामिनो एस है।

मध्य रेखा में एस और जेड के बीच एक खाली वर्ग है और इसे भरने का एकमात्र तरीका टेट्रामिनो जे, टी या एल का उपयोग करना है, जैसा कि नीचे दिए गए आंकड़ों में दिखाया गया है।



इनमें से किसी भी आकार को सम्मिलित करना रिक्त स्थान को विभाजित करता है। बाईं ओर के खाली क्षेत्र में क्रमशः 5, 6 और 7 voids होते हैं। चूंकि इनमें से कोई भी मूल्य 4 से विभाज्य नहीं है, इसलिए इसे जारी रखना असंभव है। इस एकल वर्ग पैटर्न के लिए एक बड़ा मैट्रिक्स आवश्यक है।

नीचे दिए गए मैट्रिक्स में दिखाए गए एक वर्ग को बनाने के लिए दूसरे पैटर्न पर भी यही लागू होता है।


सबसे निचली रेखा को भरने के लिए टेट्रामिनो एस और जेड का उपयोग करने के बाद, बीच की रेखा में उनके बीच एक खाली जगह होती है।


जैसा कि नीचे की छवियों में दिखाया गया है, छेद डालने से रिक्त स्थान विभाजित होता है, और बाईं ओर के खाली क्षेत्र में क्रमशः 9, 10 या 11 वर्ग होते हैं; कोई भी संख्या 4 से विभाज्य नहीं है।



लेकिन एक वर्ग पैटर्न उत्पन्न करने के लिए मैट्रिक्‍स पैक करना एकमात्र तरीका नहीं है। उदाहरण के लिए, नीचे दिए गए 4 वर्गों के निर्माता पर एक नज़र डालें।


निम्नलिखित पैक्ड टेट्रामिनो के एक सेट के रूप में पैटर्न को प्रस्तुत करने का एक प्रयास है।


अंतिम एल को छोड़ दिया जाता है, क्योंकि इसके लिए स्थान तीसरी पंक्ति के पूरा होने और हटाने के बाद ही बनता है।

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

पैटर्न खोज

डेटा आउटपुट को सरल बनाने के लिए, टेट्रिस प्रिंटर एल्गोरिथ्म खेल के मैदान के शीर्ष केंद्र बिंदु पर टेट्रामिनो बनाने, इसे मोड़ने, क्षैतिज रूप से स्थानांतरित करने और इसे कम करने तक सीमित है। कुछ दूरी से गुजरने के बाद उसे कभी भी क्षैतिज रूप से स्थानांतरित नहीं करना पड़ता है। यह प्रतिबंध खोज स्थान को बहुत कम कर देता है, क्योंकि यह मैट्रिक्स में जोड़े गए आंकड़ों के तहत अंतराल के गठन की अनुमति नहीं देता है। एक उदाहरण के रूप में, आइए निम्नलिखित 3 वर्गों के मैट्रिक्स को देखें।


यदि हम जे को मैट्रिक्स के केंद्र में फेंकते हैं, जैसा कि ऊपर दिखाया गया है, तो हमें 2 खाली वर्गों का अंतर मिलता है, जिन्हें बाद के आंकड़ों से नहीं भरा जा सकता है। इसलिए, खोज इस पथ का अनुसरण नहीं करेगी।


चूंकि कवर किए गए अंतराल की अनुमति नहीं है, इसलिए मैट्रिक्स में प्रत्येक स्तंभ को भरे हुए वर्गों के ढेर के रूप में माना जा सकता है और इन ढेर की ऊंचाई पूरी मैट्रिक्स की सामग्री का पूरी तरह से वर्णन करती है। पंक्तियों की संख्या के बावजूद, 21-तत्वों के साथ एक-आयामी पूर्णांक सरणी दो-आयामी मैट्रिक्स का वर्णन करने के लिए पर्याप्त होगा।

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


छवि के ऊपरी बाएं कोने में टेट्रामिनो जे 3 कॉलमों पर रहता है। जब मैट्रिक्स पर कम होता है, तो 3 आसन्न ढेर की ऊंचाई क्रमशः 1, 1 और 2 वर्ग तक बढ़ जाती है। लेकिन इससे पहले कि आंकड़ा कम किया जा सकता है, आंकड़ा का निचला प्रोफ़ाइल संबंधित ढेर के ऊपरी प्रोफ़ाइल के अनुरूप होना चाहिए। यदि यह J खेल के मैदान के फर्श पर पड़ा हुआ है, तो इन स्तंभों में से प्रत्येक के नीचे 1, 1, और 0 खाली वर्गों के अंतराल होने चाहिए थे। चूंकि क्लीयरेंस की मनाही है, इसलिए 3 स्टैक की सापेक्ष ऊंचाइयों को पैटर्न से पूरी तरह से मेल खाना होगा।

अंतराल की कमी का एक और परिणाम यह था कि जब आंकड़े मैट्रिक्स में आते हैं, तो पंक्तियां नीचे से ऊपर तक भर जाती हैं। इससे पहले या इसके नीचे की सभी पंक्तियों को पूरा नहीं करने से पहले एक मैट्रिक्स के बीच में एक पंक्ति को भरना संभव नहीं है। मैट्रिक्स को भरने की प्रक्रिया में, इसकी निचली सीमा वास्तव में ऊपर जाती है। नतीजतन, एक मैट्रिक्स कॉलम स्टैक केवल तभी समर्थन प्रदान कर सकता है जब इसकी ऊंचाई शून्य से पूरी की गई पंक्तियों की संख्या 0. से अधिक हो। जब एक आकार मैट्रिक्स में जोड़ा जाता है, तो कम से कम एक कॉलम को समर्थन प्रदान करना होगा।

खोज एक दूसरे एक आयामी सरणी को संग्रहीत करता है जिसमें प्रत्येक पंक्ति में भरे हुए वर्गों की संख्या होती है। उपरोक्त J में संगत रेखाएँ 3 और 1 एक वर्ग हैं। जब आप इसे मैट्रिक्स में सम्मिलित करते हैं, तो ये मान सरणी के संबंधित तत्वों में जुड़ जाते हैं। पूर्ण लाइनों की संख्या 21 के मान के साथ तत्वों की संख्या है।

जैसा कि पिछले अनुभाग में कहा गया है, यदि जोड़ा गया आंकड़ा मैट्रिक्स को विभाजित करता है, तो परिणामी क्षेत्रों के आकार को 4 से विभाजित किया जाना चाहिए। उदाहरण के लिए, नीचे दी गई छवि में, मैं 2 क्षेत्रों को जोड़ता हूं, जिनमें से प्रत्येक में 46 खाली वर्ग हैं। चूंकि 46 4 से विभाज्य नहीं है, इसलिए शेष मैट्रिक्स में भरने का कोई तरीका नहीं है।


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

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

खोज करने से पहले, मैट्रिक्स में एक आंकड़ा जोड़ने के 371 तरीकों के यादृच्छिक क्रमांकन किए जाते हैं। खोज फ़ंक्शन का छद्म कोड नीचे दिखाया गया है।

private Result search(Matrix matrix, int remaining) { if (remaining == 0) { return SOLUTION } attempts := attempts + 1 if (attempts >= MAX_ATTEMPTS) { return TIMEOUT } if (     S  Z) {        S  Z if (  ) { Result result := search(matrix, remaining - 1) if (result == SOLUTION) { return SOLUTION }       if (result == TIMEOUT) { return TIMEOUT } } }          for(   ,    ) {      if (   ) { Result result := search(matrix, remaining - 1) if (result == SOLUTION) { return SOLUTION }       if (result == TIMEOUT) { return TIMEOUT } } } return NO_SOLUTION } 

खोज फ़ंक्शन के लिए दिया गया मूल मैट्रिक्स खाली है, नीचे पंक्ति के अलावा 3 आसन्न वर्गों के ब्लॉक हैं। इसे शेष आंकड़ों की संख्या के साथ प्रेषित किया जाता है जिन्हें जोड़ने की आवश्यकता होती है। यदि remaining 0 है, तो मैट्रिक्स में समाधान होता है और फ़ंक्शन वापस लौटता है। प्रत्येक पुनरावर्ती कॉल में प्रयासों की वैश्विक संख्या में वृद्धि होती है। यदि यह MAX_ATTEMPTS से अधिक है, जिसका मूल्य 1000 है, तो खोज फिर से शुरू होती है।

तीसरा if मैट्रिक्स के निचले हिस्से में टेट्रामिनो एस या जेड को जोड़ने की कोशिश करता है अगर स्पेस इसकी अनुमति देता है। इसका अर्थ नीचे दिखाए गए जैसे स्थितियों से बचने के लिए है, जब एल्गोरिथ्म मैट्रिक्स के भाग को भरने में समय बिताता है, समर्थन की कमी के कारण बाकी को भरने में सक्षम नहीं है।


if के लिए धन्यवाद if यह जल्दी से एक मंच बनाता है जिस पर निर्माण करना है:


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

छवि रूपांतरण

टेट्रिस प्रिंटर एल्गोरिथ्म बिटमैप की प्रत्येक पंक्ति को पास की श्रृंखला में परिवर्तित करता है। बाएं से दाएं की ओर बढ़ते हुए, "लालची" तरीके से प्रत्येक मार्ग टेट्रामिनो जे, टी और एल को सम्मिलित करता है जहां उन्हें रखा गया है। उदाहरण के लिए, नीचे दी गई छवि बिटमैप के 16 पिक्सेल की एक पंक्ति दिखाती है।


नीचे दी गई छवि इन 16 पिक्सेल को कवर करने के लिए आवश्यक 5 पास दिखाती है।






एल्गोरिथ्म सम्मिलित करने के लिए आकृतियों के अनुक्रम को पिक्सेल के रंगों द्वारा निर्धारित किया जाता है। ताकि आकार ओवरलैप न हो, बूलियन मानों का एक-आयामी सरणी उपयोग किया जाता है। आकृति डालने के लिए, सरणी में 3 शून्य तत्व मौजूद होने चाहिए। आकृति 3 के सफल सम्मिलन पर, संबंधित सरणी तत्व मान 1 लेते हैं।

एकाधिक पासों के बीच पूर्ण किए गए पिक्सेल को ट्रैक करने के लिए, बूलियन मानों के दूसरे एक आयामी सरणी का उपयोग किया जाता है। जब प्रत्येक आइटम 1 होता है, तो लाइन पूरी हो जाती है।

प्रत्येक पास के अंत में, छवि कनवर्टर एक या अधिक वर्ग बनाने के लिए सभी पैटर्न के लिए तालिका की खोज करता है। आउटपुट के लिए, यह नीचे दिए गए tetramino J, T और L के साथ संगत पैटर्न को पार करता है। उदाहरण के लिए, ऊपर दिखाया गया पहला पास 5 वर्गों को बनाने के लिए निम्न पैटर्न के रूप में प्रदर्शित होता है:

वास्तविक समय खोज

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


लेकिन छवि के निचले बाएं कोने में पिछले मार्ग में बनाया गया एक लाल वर्ग अतिरिक्त सहायता प्रदान करता है, जिससे भरी हुई रेखाओं की संख्या 3 हो जाती है।


इसके अलावा, एक वास्तविक समय की खोज टेट्रामिनो जे, टी या आई को फ्लिप करके एक ही रंग के 3 आसन्न पिक्सल को कवर कर सकती है।


वास्तव में, यह एक पास में बड़ी संख्या में पिक्सेल को कवर करते हुए, उल्टे और उल्टे टेट्रामिनो को मिला सकता है। उदाहरण के लिए, 16 पिक्सेल को कवर करने के लिए आवश्यक उपरोक्त 5 पास को नीचे दिखाए गए एकल पास में घटाया जा सकता है।


इस पैटर्न को प्राप्त करने के लिए, छवि कनवर्टर उत्सुकता से टेट्रामिनो जे, टी और एल को पैकिंग करके शुरू होता है।


फिर वह उत्सुक रूप से अप्रयुक्त संस्करणों को जोड़ने की कोशिश करता है, और इस मामले में वह एक और जे को जोड़ने का प्रबंधन करता है।


सिद्धांत रूप में, इस प्रक्रिया में एक पूर्व-गणना लुकअप तालिका का भी उपयोग किया जा सकता है, लेकिन ऐसी तालिका का सरासर आकार इसे व्यवहार में अनुपयुक्त बनाता है।

इस उदाहरण में, बनाई जाने वाली पंक्ति के ऊपर एक पंक्ति में 8 वर्ग खाली मैट्रिक्स की निचली पंक्ति में जोड़े जाते हैं। 21-चौड़े चौड़े खेल के मैदान पर n वर्गों के लिए, मैट्रिक्स h की ऊँचाई सबसे छोटी धनात्मक पूर्णांक है जैसे कि 21h - n 4. से विभाज्य है। इस स्थिति में, ऊँचाई 4 की एक मैट्रिक्स की आवश्यकता होती है।


वास्तविक समय की खोज ठीक उसी तरह से काम करती है जैसे कि ऊपर वर्णित खोज एल्गोरिदम, लेकिन इसमें मामूली सुधार है। पहले की तरह, मैट्रिक्स कॉलम स्टैक केवल तभी समर्थन प्रदान करता है जब स्तंभ की ऊंचाई शून्य से पूर्ण पंक्तियों की संख्या शून्य से अधिक हो। जब अंतर शून्य होता है, तो कॉलम स्टैक को समर्थन प्रदान नहीं करना चाहिए। हालांकि, इस संस्करण में, यदि यह शून्य के बराबर है, तो यह पिछले पास द्वारा उत्पन्न लाइन में वर्गों की जांच करता है। यही है, मैट्रिक्स की निचली पंक्ति के नीचे की पंक्ति में कोई भी वर्ग खाली कॉलम के लिए समर्थन प्रदान करता है।

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

प्रिंट

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

स्रोत कोड

जावा 7 प्रोजेक्ट के लिए सोर्स कोड यहां उपलब्ध है ।

पूर्व-तैयार तालिकाओं और वास्तविक-समय के लिए खोज एल्गोरिदम पैकेज में हैं। खोज और search.realtime । वास्तविक समय। वे search पैकेज में स्थित कुछ सामान्य कक्षाओं का उपयोग करते search । पूर्व-परिकलित खोज के परिणाम पाठ फ़ाइलों के अनुक्रम के रूप में patterns पैकेज में संग्रहीत किए जाते हैं। पाठ फाइलें ASCII वर्णों के रूप में पैक्ड मैट्रिसेस को A शुरू करती हैं A उदाहरण के लिए, emitters1.txt में पहले 3 मेट्रिसेस (एक वर्ग बनाने के लिए पैटर्न का सेट) इस तरह दिखते हैं:


जैसा कि लेख में बार-बार कहा गया है, उपरोक्त आसनों में 3 प्रतीक A प्रतीकों को tetramino J, T या L. Symbols B , C , D और इतने पर tetramino के अनुक्रम को दर्शाने के साथ प्रतिस्थापित किया जा सकता है जिसे आपको बनाने की आवश्यकता है।

imageconverter.ImageConverter वर्ग में main विधि है, जो एक एकल कमांड लाइन तर्क प्राप्त करती है: छवि स्प्राइट फ़ाइल का नाम। एक छवि 17 × 32 पिक्सेल से बड़ी नहीं हो सकती है और इसमें 3 से अधिक अपारदर्शी रंग नहीं हो सकते हैं। अन्य सभी पिक्सेल पारदर्शी होने चाहिए।

दिलचस्प बात यह है कि पुराने वीडियो गेम में, डेवलपर्स अक्सर अतिरिक्त रंग प्राप्त करने के लिए पृष्ठभूमि का उपयोग करते थे। उदाहरण के लिए, बबल बबल से विद्यार्थियों का मुंह और मुंह, गधे का गधा गधा काँग से गधा और मिस पाकमैन के मिस आइ से भौं। पीएसी-मैन वास्तव में पारदर्शी है। काली को एक ठोस पृष्ठभूमि से प्राप्त किया जाता है।


टेट्रिस खेल मैदान की पृष्ठभूमि का उपयोग एक समान तरीके से किया जा सकता है।

ImageConverter आउटपुट इस स्निपेट की तरह दिखता है:


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

printer.Printer वर्ग इस प्रारूप में एक पाठ फ़ाइल प्राप्त करता है और Tetris खेलकर एक छवि फ़ाइल उत्पन्न करता है।

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

पैटर्न फ़ाइलों को पुनर्जीवित करने के लिए, search.precomputed.PatternSearcher उपयोग करें। यह स्रोत कोड फ़ाइल की शुरुआत में स्थिरांक को बदलकर अनुकूलित किया जा सकता है।

 public static final int MATRIX_WIDTH = 21; public static final int MATRIX_HEIGHT = 4; public static final int EMITTED_SQUARES = 4; public static final int RANDOM_SETS = 100000; public static final int MAX_ATTEMPTS = 1000; 

RANDOM_SETS मैट्रिक्स में एक आकृति जोड़ने के लिए 371 तरीकों के यादृच्छिक क्रमपरिवर्तन की संख्या है। जब 100000 सेट किया जाता है, तो स्टार्टअप पर क्रमपरिवर्तन आरंभ करने में कई सेकंड लगते हैं। इसके अलावा, उनके भंडारण में एक गीगाबाइट से अधिक मेमोरी की आवश्यकता होती है।

MAX_ATTEMPTS खोज के निष्पादन समय को नियंत्रित करता है। 1000 का अपेक्षाकृत छोटा मूल्य खोज को यादृच्छिक शुरुआत को जल्दी से त्यागने की अनुमति देता है जो खुद को अच्छी तरह से दिखाने में विफल रहता है। हालांकि, यह साबित करने के लिए कि एक विशिष्ट मैट्रिक्स आकार और निर्मित चौकों की संख्या का कोई समाधान नहीं है, संपूर्ण खोज स्थान का पूरी तरह से पता लगाना आवश्यक है। ऐसा करने के लिए, आप MAX_ATTEMPTS को Integer.MAX_VALUE सेट कर सकते हैं।

इसी तरह के स्थिरांक search.realtime.RealtimeSearcher में पाए जाते हैं, जिसका उपयोग इमेज कन्वर्टर द्वारा किया जाता है। जैसा कि ऊपर उल्लेख किया गया है, एक बड़े RANDOM_SETS मूल्य को अधिकतम मेमोरी में वृद्धि की आवश्यकता होती है और एक लंबी शुरुआत की ओर जाता है। MAX_RETRIES प्रयासों की संख्या को नियंत्रित करता है, जिसके बाद वास्तविक समय खोज समर्पण करता है और पूर्व-गणना तालिका के साथ खोज पर वापस लौटता है।

ध्यान रखें कि दोनों खोज एल्गोरिदम 100% सीपीयू का उपयोग करते हैं, कई समानांतर धागे बनाते हैं जो उपलब्ध प्रोसेसर की संख्या के आकार के बराबर होते हैं।