🕴🏻 👐🏼 👨🏻‍⚖️ ब्रेडबोर्ड पर खेल "साँप" डालना। भाग 1: राज्य मशीनें 🚱 📶 👐🏼

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

गेम स्नेक (वह एक साँप, अजगर, बोआ कंस्ट्रिक्टर, आदि) सभी के लिए व्यापक रूप से जाना जाता है। वह 70 के दशक से आती है, लेकिन मैं उसकी कहानी नहीं दोहराऊंगी, जिसे आप विकिपीडिया या कई लेखों पर पढ़ सकते हैं । गेम में काफी सरल नियम हैं और एक ही समय में नशे की लत गेमप्ले)) इसके लिए धन्यवाद, इसे अक्सर ट्यूटोरियल या कोड नमूनों के लिए उपयोग किया जाता है । उच्च-स्तरीय प्रोग्रामिंग भाषाओं में, ऐसा गेम बनाना काफी आसान है। लेकिन अधिक सीमित परिस्थितियों में, सबसे दिलचस्प शुरू होता है, उदाहरण के लिए, LabVIEW पर एक कार्यान्वयन । FPGA पर भी कई विकल्प हैं: लिंक 1 , लिंक 2 , लिंक 3 , लिंक 4 । लेकिन मानक श्रृंखला के अलग-अलग टीटीएल-चिप्स पर एक भी विकल्प नहीं आया है। ताकि हम क्या करें।

ऐसा लगता है कि FPGA समाधान हमारे लिए निकटतम हैं, और आप वहां से बहुत अधिक उधार ले सकते हैं? लेकिन सभी विकल्पों में जो मैंने देखा, वे आसानी से बाएं और दाएं रजिस्टरों में बिखरे हुए हैं। उदाहरण के लिए, बहुत बार प्रत्येक क्षेत्र सेल के लिए एक अलग बिट या संख्या आवंटित की जाती है। हम इसे ढीले पाउडर के साथ नहीं कर सकते हैं, क्योंकि प्रत्येक नया रजिस्टर एक अलग माइक्रोक्रिसिट है जिसे कहीं और रखा जाना चाहिए, और फिर जुड़ा होना चाहिए। इसलिए, हम अन्य डेवलपर्स द्वारा संचित सभी अनुभव को पार करते हैं और खरोंच से सब कुछ करेंगे। एक बोनस के रूप में, हम ROM के अपवाद के साथ k555 / kr1533 श्रृंखला के घरेलू (और बेहतर - सोवियत) चिप्स पर सब कुछ एकत्र करेंगे, जिसे नए सिरे से लेना होगा।

समस्या का निरूपण

हमारे पास इस तरह के प्रतिबंध होंगे: आकार 8 × 8 कोशिकाओं (चीनी एलईडी मैट्रिक्स ) का एक क्षेत्र, 8 कोशिकाओं की पूंछ की लंबाई। एक साँप दीवारों से गुजर सकता है, लेकिन हम पहले से पूंछ के साथ चौराहे पर प्रक्रिया नहीं करेंगे (डिजाइन को जटिल नहीं करने के लिए, आप इसे बाद में जोड़ सकते हैं)। खेल के पूरे राज्य का वर्णन करने के लिए हमें चाहिए:

सिर की स्थिति (X = 0..7, Y = 0..7, 6 बिट्स)
आंदोलन की दिशा (↑ ↓ of →, 2 बिट्स)
Apple स्थिति (X, Y, 6 बिट)
पूंछ की लंबाई (0..7, 3 बिट्स)
पूंछ कोशिकाओं की स्थिति (प्रत्येक 6 बिट के 0 से 7 टुकड़े तक)

कुल मिलाकर, 65 बिट्स प्राप्त किए जाते हैं, भले ही हम प्रत्येक के 8 बिट्स के रजिस्टरों को लेते हैं, केवल 8 ऐसे माइक्रोक्रिस्केट्स (और एक और ट्रिगर) को राज्य को संग्रहीत करने की आवश्यकता होती है, यह काफी है।

लेकिन पूँछ जहाँ चाहे वहाँ स्थित नहीं हो सकती, यह सिर से "बढ़ता" है। इसलिए, हम पूंछ के प्रत्येक खंड के पूर्ण निर्देशांक को संग्रहीत नहीं कर सकते हैं, लेकिन केवल उस दिशा में पिछले सेल (या सिर) से किस दिशा में इसे खींचने की आवश्यकता है। फिर, 6 × 8 = 48 बिट्स के बजाय, हमें 4 × 8 = 16 बिट्स की आवश्यकता है, और यह चार रजिस्टर मामलों में से कई की बचत है!

स्वचालित मशीनें

आइए मूर या मीलों के समान मशीनों पर सब कुछ करने की कोशिश करें। इस तरह के ऑटोमेटन को लागू करने के लिए, उनके बीच स्विच करने के लिए राज्य मेमोरी (रजिस्टर) और कॉम्बिनेशन लॉजिक का थोड़ा सा होना पर्याप्त है। विकिपीडिया

चित्र

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

आप अधिक जानकारी और सुंदर चित्र पा सकते हैं, उदाहरण के लिए, इस लेख में हैबे पर

छोटा विषयांतर

, , . , ROM , ROM. ( , ).

, , .

, « » .

विभिन्न राज्यों के एक साँप (यदि आप सेब की स्थिति को ध्यान में नहीं रखते हैं) में 2 ^ 8 + 2 ^ 10 + ... + 2 ^ 24 states 32 मिलियन हो सकते हैं। उन्हें तालिका में लिखना संभव नहीं है, और इससे भी अधिक एक संक्रमण ग्राफ खींचना है। लेकिन अधिकांश संक्रमण काफी समान होते हैं (सिर केवल एक आसन्न कोशिका को स्थानांतरित करता है, और पूंछ प्रति मोड़ एक खंड चलती है)। इस मामले में, हम प्रत्येक व्यक्ति की स्थिति का वर्णन नहीं कर सकते हैं, लेकिन पिछले एक के कार्य के रूप में एक नया राज्य तैयार कर सकते हैं। इसके अलावा, हम पूरे गेम को कई समानांतर ऑटोमेटा में विभाजित कर सकते हैं: 1) दिशा की एक स्वचालित मशीन, 2) सिर की स्थिति की एक स्वचालित मशीन, 3) पूंछ के लिए एक स्वचालित मशीन। और उनमें से प्रत्येक को निर्धारित करना क्योंकि यह अधिक सुविधाजनक होगा:

1) ,  │  
  ────────────────────┼───────────────────
   ←        ←/↓/↑     │ ←
   ←          →       │ →
   ↑        ↑/←/→     │ ↑
   ↑          ↓       │ ↓
   ......          │

2) ,  │  
  ─────────────────────┼──────────────
   ←             (x,y) │ (x-1, y)
   →             (x,y) │ (x+1, y)
   ↑             (x,y) │ (x, y-1)
   ↓             (x,y) │ (x, y+1)

3) ,                       │  
  ─────────────────────────────────────────┼──────────────────────────
   ←            (t1,t2,t3,t4,t5,t6,t7,t8)  │ (←,t1,t2,t3,t4,t5,t6,t7)
   ......                               │

दिशा

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

सिर

एक हेड पोजीशन मशीन के लिए, इस तरह की तालिका लिखना अधिक कठिन होगा। लेकिन इसमें अनिवार्य रूप से केवल 2 ऑपरेशन शामिल हैं: +1 और -1। उन्हें 4-बिट योजक K155IM6 पर लागू किया जा सकता है। +1 के लिए, हम b'0001 के साथ अपना समन्वय जोड़ेंगे, और -1 के लिए b'1111 के साथ (जो वास्तव में अतिरिक्त सेवा में -1 है )। हमें दो योजक (x और y के लिए), थोड़े से तर्क की आवश्यकता होगी, और हम राज्य को 8-बिट रजिस्टर IR27 में संग्रहीत करेंगे (हमें अभी भी उनकी बहुत आवश्यकता है):

चलो इसे बोर्ड पर इकट्ठा करते हैं, और सत्यापन के लिए हम तुरंत एलईडी मैट्रिक्स को दो डिकोडर से जोड़ देंगे। व्युत्क्रम आउटपुट वाला डिकोडर ID7 है, और प्रत्यक्ष के लिए यह K561ID1 (CD4028) लेना संभव होगा, लेकिन मेरे पास यह नहीं था। एक और विकल्प 8 ट्रांजिस्टर को चाबियाँ के रूप में लेना है, लेकिन मैं ऐसा नहीं करना चाहता था, इसलिए मुझे बेवकूफी से एक और EEPROM (केवल 8 कोशिकाओं को लिखना) खर्च करना पड़ा। शीर्ष पर एक अलग बोर्ड पर नए सिर की स्थिति का तर्क एक और विषयांतर

चलो एक छोटा ब्रेक लेते हैं और ब्रेडबोर्ड (और कुछ चिप मामलों) को बचाते हैं। हम फिर से इस तथ्य का लाभ उठाएंगे कि किसी भी संयोजन सर्किट को टेबल को रोम में लिखकर एक LUT द्वारा प्रतिस्थापित किया जा सकता है। लेकिन इतनी बड़ी मेज के लिए यह कैसे करना है? हम एक और चाल का उपयोग करेंगे - हम इसके विपरीत करेंगे: EEPROM को हमारे तर्क सर्किट से बदलें और इसे प्रोग्रामर में डाल दें। _{अप्रयुक्त पैर प्रतिरोधों के माध्यम से जमीन से जुड़े होते हैं।}_{(यदि आप प्रोग्रामर की सेटिंग में नहीं जाते हैं तो यह नहीं किया जा सकता है)} अब हम अपने तर्क आरेख को ROM के रूप में पढ़ेंगे और एक टेबल प्राप्त करेंगे। हम इसे उसी प्रोग्रामर के साथ एक वास्तविक EEPROM में लिखते हैं, जिसे हम अलग-अलग तत्वों के सर्किट के बजाय रखते हैं।

पूंछ

पूंछ में 2 से 8 कोशिकाओं की लंबाई (हमारी सीमाओं में) है। इस लंबाई को संग्रहीत करने के लिए, आप एक पारंपरिक रिज़ॉल्यूशन का उपयोग खाता रिज़ॉल्यूशन इनपुट के साथ कर सकते हैं। वास्तव में, यह वही परिमित राज्य मशीन होगी, जिसमें नया राज्य S 'S + 1 या जस्ट S (यदि खाता निषिद्ध है) के बराबर होगा। पूंछ खुद (या बल्कि, वह दिशा जहां यह बढ़ता है) हम 8 बिट्स के दो रजिस्टरों में संग्रहीत करेंगे। सैद्धांतिक रूप से, कोई भी तैयार शिफ्ट रजिस्टर (उदाहरण के लिए, आईआर 8) ले सकता था, लेकिन वे हाथ में नहीं थे, इसलिए बहुत ही आईआर 27 का उपयोग किया गया था। प्रत्येक चरण में, वर्तमान हेड मूवमेंट दिशा को रजिस्टर के पहले बिट में लिखा जाता है, और दूसरे और अगले में पिछले एक का मान। इससे पूंछ की वृद्धि की दिशा प्राप्त करने के लिए, हमें सिर्फ एक बिट पलटना होगा। आप रिकॉर्डिंग करते समय इसे तुरंत कर सकते हैं, लेकिन मैंने फैसला किया कि शेष सर्किट के लिए व्युत्क्रम को छोड़ना बेहतर था।

योजना

कुल मिलाकर, हमारी अगली चाल की मशीन इस फॉर्म को लेती है: यह चित्र (हर किसी की तरह) क्लिक करने योग्य है। यह योजना का एक "शुद्ध" (सैद्धांतिक दृष्टिकोण से) हिस्सा है। उत्पादन कोडित मूर मशीन के लिए लगभग सही उदाहरण । U1 नई दिशा के लिए जिम्मेदार है, सिर की स्थिति के लिए U2, जो U5 में संग्रहीत हैं। U3 और U4 का उपयोग पूंछ के लिए किया जाता है, और इसकी लंबाई U6 में संग्रहीत (और बढ़ जाती है) होती है। अगला, हमें स्क्रीन पर हमारे पास मौजूद हर चीज का प्रदर्शन करने की आवश्यकता होगी, और एक अंतरिक्ष यान भी होगा, केवल अधिक गंदे रूप में। साथ ही एक आदिम यादृच्छिक संख्या जनरेटर, एक अलग घड़ी संकेत और अन्य हैक के साथ सर्किट के बीच एक संक्रमण।

उप-योग

मुझे उम्मीद है कि इस लेख में आपकी रुचि है और मैं दूसरे भाग को जल्दी से समाप्त करने की कोशिश करूंगा।

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

खैर, जैसा कि यह होना चाहिए: जैसे, शेयर, रीट्वीट, साइन अप, घंटी दबाएं, आदि ...)) और आज के लिए सब कुछ, आपका ध्यान के लिए धन्यवाद! जारी रहती है…

ROM फर्मवेयर और सामान्य

UPD स्कीम के साथ पुरालेख : दूसरा भाग यहां उपलब्ध है ।

ब्रेडबोर्ड पर खेल "साँप" डालना। भाग 1: राज्य मशीनें