पहेली खेल में पैटर्न ढूंढना

Question

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

मुझे पता है कि कई कारकों पर निर्भर करता है, जैसे कि आप किस प्रकार के पैटर्न का पता लगाना चाहते हैं, या खेल के नियम ... लेकिन मैं जानना चाहता था कि इस तरह की समस्याओं में सबसे अधिक उपयोग किए जाने वाले एल्गोरिदम कौन से हैं ..

उदाहरण के लिए, कॉलम, बेजवेल्ड, यहां तक ​​कि टेट्रिस जैसे गेम।

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

इस तरह के खेलों में आमतौर पर कौन सी संरचनाएं उपयोग की जाती हैं?

Answer 1

यह हमेशा डोमेन-निर्भर है। लेकिन वहां दो स्थितियां भी हैं जहां आप इन प्रकार की खोज करेंगे। लोगों की स्थिति एक कदम के बाद है (खिलाड़ी द्वारा बनाए गए खेल के मैदान में बदलाव), और दूसरा होगा जब पूरा बोर्ड बदल गया हो।

टेट्रिस में, आपको टुकड़े गिरा दिए जाने के बाद पूरे बोर्ड को स्कैन करने की आवश्यकता नहीं होगी। आपको बस छूने वाली पंक्तियों को खोजना होगा।

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

एड्रियन कहते हैं, एक साधारण 2 डी सरणी पर्याप्त है। अक्सर, हालांकि, खोज-के-पैटर्न पहलू को सरल बनाने के लिए, आप इस सरणी के चारों ओर पिक्सल की "सीमा" जोड़ सकते हैं। सीमा के बिना, आपको किनारे वर्गों के साथ if बयान देना होगा जो कहता है "ठीक है, यदि आप शीर्ष पंक्ति में हैं, तो खोज न करें (और सरणी से बाहर निकलें)"।इसके आस-पास की सीमा के साथ, आप सुरक्षित रूप से केवल सब कुछ के माध्यम से खोज सकते हैं: अपने आप को if कथनों को सहेजना, स्वयं को शाखाबद्ध करना, स्वयं को पाइपलाइन समस्याओं को सहेजना, तेजी से खोजना।

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

Answer 2

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

संरचनाओं के बारे में: बोर्ड का प्रतिनिधित्व करने के लिए एक साधारण 2 डी-ऐरे पर्याप्त होना चाहिए।

Answer 3

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

यदि यह गेमप्ले रणनीतियों को अनुकरण करने जैसा कुछ है, तो एक एल्गोरिदम का उपयोग करें जो अधिक कुशल है।

एक और अधिक कुशल रणनीति में प्रत्येक बोर्ड को फिर से स्कैन करने की बजाए खेल बोर्ड में वृद्धिशील परिवर्तनों का ट्रैक रखने में शामिल हो सकता है।