🐋 ☝🏻 🛬 एअर इंडिया को नियंत्रित करने के लिए वोरोनोई आरेख का उपयोग कैसे करें 🧘🏽 💚 🤷🏼

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

स्थानिक संबंध

एक स्थानिक संबंध कोई भी जानकारी है जो बताती है कि अंतरिक्ष में कोई वस्तु दूसरे से कैसे संबंधित है। उदाहरण: उनके बीच की दूरी, उनमें से प्रत्येक क्षेत्र द्वारा कवर किया गया क्षेत्र और इन क्षेत्रों का अंतरक्षेत्र, एक क्षेत्र में स्थित ऐसी वस्तुओं की संख्या।

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

वोरोनोई का जवाब है

वोरोनोई आरेख निकटवर्ती बिंदुओं या उनके निकटतम पड़ोसियों के बीच स्थानिक संबंध का वर्णन करता है। यह अंक या स्थानों से प्राप्त जुड़े बहुभुजों का एक समूह है। वोरोनोई के "क्षेत्र" की प्रत्येक पंक्ति दो बिंदुओं के बीच में स्थित है।

समझने के लिए, चित्र पर एक नज़र डालें:

जैसा कि आप देख सकते हैं, प्रत्येक रेखा बिल्कुल दो बिंदुओं के बीच में है, और वे सभी केंद्र में जुड़े हुए हैं। दृश्य में कुछ और बिंदु जोड़ें और देखें कि क्या होता है:

तस्वीर और दिलचस्प हो गई है! हमारे पास पहले से ही वास्तविक क्षेत्र हैं।

प्रत्येक क्षेत्र हमें क्या बताता है? हम जानते हैं कि क्षेत्र में होने की गारंटी एक बिंदु के सबसे करीब होने की गारंटी है, जो क्षेत्र में भी है। यह हमें बताता है कि पास में क्या है; वोरोनोई आरेखों में ऐसा मौलिक स्थानिक संबंध है।

वोरोनोई को अंदर बाहर करें: डिलायने त्रिकोणासन

वोरोनोई आरेख के विपरीत प्रणाली को डेलौनाय त्रिकोण कहा जाता है। इस आरेख में प्रत्येक बिंदु से उसके निकटतम पड़ोसियों तक की रेखाएँ होती हैं, और प्रत्येक पंक्ति वोरोनोई किनारे के लिए लंबवत होती है, जो इसे प्रतिच्छेद करती है। यहाँ यह कैसा दिखता है:

श्वेत रंग डेलौनाय रेखा को दर्शाता है। प्रत्येक Delaunay लाइन एक और केवल एक वोरोनोई किनारे से मेल खाती है। पहले तो ऐसा लगता है कि उनमें से कुछ ने कई किनारों को पार किया है, लेकिन निकट से देखने पर आपको महसूस होगा कि ऐसा नहीं है।

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

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

इसके अलावा, यह कई बिंदुओं से एक ग्राफ बनाने का एक शानदार तरीका है जब हम एक बिंदु से दूसरे बिंदु पर जाना चाहते हैं। उदाहरण के लिए, डॉट्स शहरों को इंगित कर सकते हैं।

वोरोनोई डेटा संरचना

हम पहले से ही जानते हैं कि वोरोनोई आरेख क्या दिखता है; अब देखते हैं कि इसका डेटा स्ट्रक्चर कैसा दिखेगा। पहले हमें उन बिंदुओं को सहेजना होगा जो वोरोनोई आरेख के आधार हैं:

class VoronoiPoint { float x float y VoronoiRegion* region }

प्रत्येक VoronoiPoint में एक स्थान (x, y) और उस क्षेत्र का लिंक होता है जिसमें वह स्थित है।

आगे हमें VoronoiRegion का वर्णन करने की आवश्यकता है:

 class VoronoiRegion { VoronoiPoint* point Edge *edges[] // our list of edges }

यह क्षेत्र अपने VoronoiPoint लिए एक लिंक संग्रहीत करता है, साथ ही साथ VoronoiEdges किनारों की एक सूची भी VoronoiEdges ।

आइए देखें कि VoronoiEdges कैसा दिखता VoronoiEdges :

 class VoronoiEdge { VoronoiPoint* pointA VoronoiPoint* pointB float distance // distance between point A and point B float x1, z1, x2, z2 // to visualize start & end of the edge }

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

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

अपने नजदीकी दवा कैबिनेट का पता लगाएं

फिर से, बिंदुओं के लिए वोरोनोई आरेख देखें।

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

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

आप यहां डेलौनाय त्रिभुज भी लगा सकते हैं। इसमें प्राथमिक चिकित्सा किट के बीच की रेखाएँ होती हैं। फिर आप निकटतम प्राथमिक चिकित्सा किट को खोजने के लिए ए * पथ खोज एल्गोरिथ्म का उपयोग करके इसके चारों ओर प्राप्त कर सकते हैं।

सुरक्षित मार्ग की तलाश करें

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

ग्राफ तैयार करने के बाद, आपको प्रत्येक किनारे पर वजन निर्दिष्ट करना होगा। हमारे लिए, वेट वैल्यू इन वॉच टावरों की दूरी होगी, और आप इसे सीधे डेटा संरचना से प्राप्त कर सकते हैं: प्रत्येक VoronoiEdge पहले से ही दो बिंदुओं के बीच की दूरी जानता है। आमतौर पर, किनारे A * पर मूल्य जितना छोटा होता है, उतना बेहतर, लेकिन हमारे मामले में, मूल्य जितना अधिक होगा, क्योंकि यह टॉवर की दूरी को इंगित करता है।

यदि हम बिंदु A से बिंदु B पर जाना चाहते हैं तो यह प्रारंभिक ग्राफ़ जैसा दिखता है:

प्रत्येक किनारे पर वजन लागू करना, हम देखेंगे कि कौन सा मार्ग चुनना बेहतर है:

लाल पसलियों को टावरों के साथ निकटतम संपर्कों का संकेत मिलता है। नारंगी लंबे लोगों को इंगित करता है; पीला और भी दूर, और अंत में, हरा - सबसे सुरक्षित। इन भारों के साथ A * निष्पादित करने के बाद, हमें निम्नलिखित पथ मिलते हैं:

तराजू के इस उपयोग के साथ, सबसे तेज़ नहीं, बल्कि सबसे सुरक्षित तरीका चुना जाएगा, जो कि हमें चाहिए। एआई को इस मार्ग का पालन करना चाहिए और इससे विचलित नहीं होना चाहिए!

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

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

आप विपरीत ऑपरेशन भी कर सकते हैं - Delaunay त्रिभुज आरेख का उपयोग करें, और प्रत्येक प्रहरीदुर्ग से आने वाली लाइनें प्राप्त करें। गार्ड का एआई जल्दी से यह निर्धारित करने में सक्षम होगा कि कौन से टॉवर पास हैं और यदि आवश्यक हो, तो उनकी सहायता के लिए जाएं।

एक कसकर भरे हुए सामान की तलाश करें

मान लीजिए हमें जमीन पर बैठे जवानों के झुंड के लिए एक हवाई जहाज से एक कटनीप पार्सल छोड़ने की जरूरत है। इसे गिराने का सबसे अच्छा तरीका कहां है ताकि बिल्लियों की सबसे बड़ी संख्या इसका उपयोग कर सके? यह बेहद महंगा हो सकता है। लेकिन, सौभाग्य से, हम Delaunay triangulation का उपयोग करके एक उचित धारणा बना सकते हैं।

संकेत: यह मत भूलो कि Delaunay त्रिकोण केवल वोरोनोई आरेख का विलोम है। यह प्रत्येक वोरोनोई बिंदु को किनारों की सूची से प्राप्त पड़ोसी बिंदुओं के साथ जोड़कर बनाया गया है।

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

ऐसे क्षेत्रों के पदनाम को डेलौनाय त्रिभुज के परिमित मंडल भी कहा जाता है। प्रत्येक सर्कल सबसे बड़ा सर्कल है जो त्रिकोण के बिंदुओं पर फिट हो सकता है। यहाँ वोरोनोई आरेख के लिए परिमित हलकों की एक छवि है:

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

वोरोनोई आरेखों का कार्यान्वयन

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

फॉर्च्यून एल्गोरिथम

सबसे तेज़ तरीके को फॉर्च्यून के एल्गोरिथ्म कहा जाता है । यह O(n log(n)) में चलता है और आवश्यकता है कि ग्राफ़ उत्पन्न करने के लिए उपयोग किए जाने वाले सभी बिंदुओं को पीढ़ी शुरू होने के समय पर जाना जाए। यदि आप बाद में नए अंक जोड़ते हैं, तो आपको पूरे ग्राफ़ को फिर से बनाना होगा। यदि कुछ बिंदु हैं, तो यह समस्या का कारण नहीं हो सकता है, लेकिन अगर आपके पास उनमें से 100 हजार हैं, तो इसमें बहुत समय लग सकता है!

इस एल्गोरिथ्म का कार्यान्वयन nontrivial है। पारबोलों और विशेष मामलों को पार करें। हालाँकि, यह सबसे तेज़ विधि है। सौभाग्य से, इस खुले स्रोत एल्गोरिदम के कई कार्यान्वयन हैं जो आप उपयोग कर सकते हैं, और मैंने उन्हें नीचे लिंक प्रदान किए हैं।

आइए देखें कि यह कैसे काम करता है।

एल्गोरिथ्म में डॉट्स के साथ एक क्षेत्र पर एक पंक्ति (ऊर्ध्वाधर या क्षैतिज) को स्लाइड करना शामिल है। जब वह एक बिंदु से मिलता है, तो वह उसमें से एक परवलय खींचना शुरू कर देता है, जो एक व्यापक रेखा के साथ जारी रहता है। यहाँ इस प्रक्रिया का एनीमेशन है:

पेराबोलस का सेवन करने से वोरोनोई पसलियों का निर्माण होता है। लेकिन परवल क्यों?

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

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

जब प्लेन स्लाइड होता है और शंकु के साथ पहला संपर्क होता है, तो परिणामी लाइन इस तरह होगी:

शंकु के साथ विमान की आगे की गति के साथ, हम देखेंगे कि परवलय कैसे बनता है:

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

जैसा कि ऊपर कहा गया है, यह समझना काफी मुश्किल है, इसलिए यहां खुले स्रोत कार्यान्वयन के लिंक दिए गए हैं जिनका आप उपयोग कर सकते हैं और सीख सकते हैं:

GitHub पर जावा। लेखक: बेनी कजूर नीलसन और एलन ओडगार्ड https://github.com/sorbits/visual-fortune-algorithm/tree/master
गीथ पर पायथन: https://github.com/MikkoJo/Voronoi द्वारा पोस्ट किया गया: मिक्को जोहानसन
फॉर्च्यून के एल्गोरिथ्म का एक विस्तृत कार्यान्वयन: http://blog.ivank.net/fortunes-algorithm-and-implementation.html

वृद्धिशील त्रिभुज सम्मिलन

एक अन्य विधि एक समय में एक बिंदु को सम्मिलित करना है, जो अन्य सभी बिंदुओं के संभावित क्षेत्र के बाहर तीन बिंदुओं के आधार त्रिकोण से शुरू होता है। यह विधि O(n^2) साथ चलती है और पीढ़ी के समय सभी बिंदुओं की आवश्यकता नहीं होती है।

जब आप एक नया बिंदु सम्मिलित करते हैं, तो यह मौजूदा क्षेत्र को परिभाषित करता है जिसमें यह गिरता है। यह क्षेत्र तब विभाजित है और नए क्षेत्र बनाए गए हैं।

उपयोग और सीखने के लिए एक खुला स्रोत उदाहरण है:

जावा स्रोत। द्वारा पोस्ट किया गया: पॉल चबाना । मुफ्त उपयोग के लिए। ज़िप फ़ाइल डाउनलोड करें । स्रोत: http://www.cs.cornell.edu/home/chew/Delaunay.html

निष्कर्ष

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

एअर इंडिया को नियंत्रित करने के लिए वोरोनोई आरेख का उपयोग कैसे करें