पथ खोजने वाले एल्गोरिदम और ए * का एक सरल विवरण

भाग 1. सामान्य खोज एल्गोरिथ्म

परिचय

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

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

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

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

सरल सर्किट

यद्यपि आप इन अवधारणाओं को मनमाने ढंग से जटिल 3 डी वातावरण में लागू कर सकते हैं, चलो एक बहुत ही सरल योजना के साथ शुरू करते हैं: एक 5 x 5 वर्ग ग्रिड। सुविधा के लिए, मैंने प्रत्येक सेल को एक बड़े अक्षर के साथ चिह्नित किया।


सरल जाल।

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

प्रत्येक नोड एक "राज्य" का प्रतिनिधित्व करता है जिसमें चरित्र हो सकता है। हमारे मामले में, चरित्र की स्थिति उसकी स्थिति है, इसलिए हम प्रत्येक ग्रिड सेल के लिए एक नोड बनाते हैं:


ग्रिड कोशिकाओं का प्रतिनिधित्व करने वाले नोड्स।

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


आर्क ग्रिड कोशिकाओं के बीच अनुमेय आंदोलनों को दर्शाता है।

यदि हम A से B तक प्राप्त कर सकते हैं, तो हम कहते हैं कि B एक नोड का "पड़ोसी" है।

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

उदाहरण

मान लीजिए हम A से T पर जाना चाहते हैं । हम ए से शुरू करते हैं । आप ठीक दो कार्य कर सकते हैं: B पर जाएं या F पर जाएं ।

मान लीजिए हम बी में चले गए । अब हम दो काम कर सकते हैं: A पर लौटें या C पर जाएँ । हमें याद है कि हम पहले से ही ए में थे और वहां के विकल्पों पर विचार करते थे, इसलिए इसे फिर से करने का कोई मतलब नहीं है (अन्यथा हम पूरे दिन ए → बी → ए → बी ...) को स्थानांतरित करने में खर्च कर सकते हैं। इसलिए हम C पर जाएंगे ।

C में होने के कारण, हमें कहीं नहीं जाना है। B पर लौटना व्यर्थ है, अर्थात यह एक मृत अंत है। जब हम A में थे तब B को संक्रमण चुनना एक बुरा विचार था; शायद आपको इसके बजाय एफ की कोशिश करनी चाहिए?

हम इस प्रक्रिया को तब तक दोहराते रहेंगे जब तक हम टी में समाप्त नहीं हो जाते । इस समय, हम केवल ए से पथ को फिर से बनाते हैं, हमारे चरणों में लौटते हैं। हम टी में हैं ; हम वहां कैसे पहुंचे? ओ से ? अर्थात्, मार्ग के अंत में O → T है। हम ओ के पास कैसे पहुंचे ? और इसी तरह।

ध्यान रखें कि हम वास्तव में आगे नहीं बढ़ रहे हैं; यह सब सिर्फ एक सोचा प्रक्रिया थी। हम ए में खड़े रहना जारी रखते हैं, और जब तक हमें पूरा रास्ता नहीं मिल जाता है, तब तक हम इससे बाहर नहीं निकलेंगे। जब मैं कहता हूं कि " बी में चला गया", मेरा मतलब है "कल्पना करें कि हम बी में चले गए"।

सामान्य एल्गोरिथ्म

यह खंड पूरे लेख का सबसे महत्वपूर्ण हिस्सा है । रास्ते की खोज को महसूस करने में सक्षम होने के लिए आपको इसे बिल्कुल समझना चाहिए ; बाकी ( ए * सहित) केवल विवरण हैं। इस खंड में, आप तब तक समझेंगे जब तक आप इसका अर्थ नहीं समझते ।

इसके अलावा, यह खंड अविश्वसनीय रूप से सरल है।

आइए एक छद्म कोड में बदलकर, हमारे उदाहरण को औपचारिक रूप देने की कोशिश करें।

हमें उन नोड्स को ट्रैक करने की आवश्यकता है जिन्हें हम जानते हैं कि शुरुआती नोड से कैसे पहुंचें। शुरुआत में, यह केवल शुरुआती नोड है, लेकिन ग्रिड की "खोज" करने की प्रक्रिया में, हम सीखेंगे कि अन्य नोड्स को कैसे प्राप्त किया जाए। चलो नोड्स की इस सूची को पुनः प्राप्त करने के लिए कहते हैं:

 reachable = [start_node] 

हमें पहले से ही समीक्षा किए गए नोड्स को ट्रैक करने की आवश्यकता है ताकि उन्हें फिर से विचार न करें। explored उन्हें explored :

 explored = [] 

अगला, मैं एल्गोरिथ्म के मूल को रेखांकित करूंगा : खोज के प्रत्येक चरण में, हम उन नोड्स में से एक का चयन करते हैं, जिसे हम जानते हैं कि कैसे पहुंचें और देखें कि हम किस नए नोड से प्राप्त कर सकते हैं। यदि हम निर्धारित करते हैं कि अंतिम (लक्ष्य) नोड तक कैसे पहुंचें, तो समस्या हल हो गई है! अन्यथा, हम खोज जारी रखते हैं।

इतना सरल, क्या निराश भी करता है? और यह सच है। लेकिन यह पूरा एल्गोरिथ्म है। चलिए इसे छद्म कोड के साथ चरण दर चरण लिखते हैं।

हम तब तक खोज जारी रखते हैं जब तक हम या तो अंतिम नोड तक नहीं पहुँच जाते (इस मामले में, हम प्रारंभिक से अंतिम नोड तक का रास्ता खोजते हैं), या जब तक हम नोड्स से बाहर नहीं निकलते हैं जिसमें हम खोज कर सकते हैं (इस मामले में, आरंभ और समाप्ति नोड के बीच कोई रास्ता नहीं है) ।

 while reachable is not empty: 

हम उन नोड्स में से एक का चयन करते हैं, जिसे हम जानते हैं कि कैसे प्राप्त करना है, और जिसकी अभी तक जांच नहीं की गई है:

  node = choose_node(reachable) 

यदि हमने अभी सीखा कि अंतिम नोड को कैसे प्राप्त किया जाए, तो कार्य पूरा हो गया है! हमें बस previous लिंक को शुरुआती नोड पर वापस previous रास्ता बनाना होगा:

  if node == goal_node: path = [] while node != None: path.add(node) node = node.previous return path 

यह नोड को एक से अधिक बार जांचने का कोई मतलब नहीं है, इसलिए हम इसे ट्रैक करेंगे:

  reachable.remove(node) explored.add(node) 

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

  new_reachable = get_adjacent_nodes(node) - explored 

हम उनमें से प्रत्येक लेते हैं:

  for adjacent in new_reachable: 

यदि हम पहले से जानते हैं कि नोड तक कैसे पहुंचें, तो इसे अनदेखा करें। अन्यथा, इसे reachable सूची में जोड़ें, यह ट्रैक करने का तरीका कि यह इसमें कैसे मिला:

  if adjacent not in reachable: adjacent.previous = node # Remember how we got there. reachable.add(adjacent) 

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

 return None 

और ... यह बात है। यह संपूर्ण एल्गोरिथ्म है, और पथ निर्माण कोड एक अलग विधि में आवंटित किया गया है:

 function find_path (start_node, end_node): reachable = [start_node] explored = [] while reachable is not empty: # Choose some node we know how to reach. node = choose_node(reachable) # If we just got to the goal node, build and return the path. if node == goal_node: return build_path(goal_node) # Don't repeat ourselves. reachable.remove(node) explored.add(node) # Where can we get from here? new_reachable = get_adjacent_nodes(node) - explored for adjacent in new_reachable: if adjacent not in reachable adjacent.previous = node # Remember how we got there. reachable.add(adjacent) # If we get here, no path was found :( return None 

यहां फ़ंक्शन है जो पथ का निर्माण करता है, previous लिंक के बाद प्रारंभिक नोड पर:

 function build_path (to_node): path = [] while to_node != None: path.add(to_node) to_node = to_node.previous return path 

वह सब है। यह ए * सहित प्रत्येक पथ खोज एल्गोरिथ्म का छद्म कोड है।

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

इंटरएक्टिव डेमो

यहां एक डेमो और ऊपर दिखाए गए एल्गोरिदम के कार्यान्वयन का एक उदाहरण है (आप इसे मूल लेख के पृष्ठ पर चला सकते हैं)। choose_node बस एक यादृच्छिक नोड का चयन करता है। आप एल्गोरिथ्म को चरण दर चरण शुरू कर सकते हैं और reachable और explored की सूची को देख सकते explored , साथ ही जहां previous लिंक इंगित करते हैं।


ध्यान दें कि जैसे ही कोई रास्ता पता चलता है, खोज समाप्त हो जाती है; ऐसा हो सकता है कि कुछ नोड्स पर विचार भी नहीं किया जाता है।

निष्कर्ष

यहाँ प्रस्तुत एल्गोरिथ्म किसी भी पथ खोज एल्गोरिथ्म के लिए एक सामान्य एल्गोरिथ्म है।

लेकिन क्या प्रत्येक एल्गोरिथ्म को दूसरे से अलग करता है, क्यों ए * ए * है ?

यहां एक टिप है: यदि आप डेमो में खोज को कई बार चलाते हैं, तो आप देखेंगे कि एल्गोरिथ्म वास्तव में हमेशा एक ही रास्ता नहीं खोजता है। वह एक रास्ता ढूंढता है , और यह रास्ता जरूरी नहीं कि सबसे छोटा हो । क्यों?

भाग 2. खोज रणनीतियाँ

यदि आप पिछले अनुभाग में वर्णित एल्गोरिदम को पूरी तरह से नहीं समझते हैं, तो इसे वापस करें और इसे फिर से पढ़ें, क्योंकि आगे की जानकारी को समझने के लिए यह आवश्यक है। जब आप इसका पता लगाते हैं, तो A * आपको पूरी तरह से स्वाभाविक और तार्किक लगेगा।

गुप्त अवयव

पिछले भाग के अंत में, मैंने दो प्रश्नों को खुला छोड़ दिया: यदि प्रत्येक खोज एल्गोरिथ्म एक ही कोड का उपयोग करता है, तो A * A * की तरह व्यवहार क्यों करता है? और डेमो कभी-कभी अलग-अलग रास्ते क्यों खोजता है?

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

 node = choose_node(reachable) 

यह निर्दोष रूप से दिखने वाला स्ट्रिंग है जो सभी खोज एल्गोरिदम को एक दूसरे से अलग करता है। choose_node की कार्यान्वयन विधि पर निर्भर करता है।

तो डेमो विभिन्न रास्तों को क्यों खोजता है? क्योंकि इसकी choose_node पद्धति एक नोड को अनियमित रूप से चुनती है।

लंबाई मायने रखती है

choose_node फ़ंक्शन के व्यवहार में अंतर में choose_node , हमें ऊपर वर्णित एल्गोरिथ्म में एक छोटे से निरीक्षण को ठीक करने की आवश्यकता है।

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

 if adjacent not in reachable: adjacent.previous = node # Remember how we got there. reachable.add(adjacent) 

यह एक गलती है: क्या होगा यदि हमने इसे प्राप्त करने का सबसे अच्छा तरीका खोजा है? इस मामले में, इस छोटे पथ को प्रतिबिंबित करने के लिए previous नोड लिंक को बदलना आवश्यक है।

ऐसा करने के लिए, हमें शुरुआती नोड से किसी भी पहुंच योग्य नोड तक मार्ग की लंबाई जानने की आवश्यकता है। हम इसे मार्ग की लागत कहेंगे। अभी के लिए, हम मानते हैं कि एक नोड से पड़ोसी नोड्स में जाने पर 1 की निरंतर लागत होती है।

खोज शुरू करने से पहले, हम प्रत्येक नोड की cost मूल्य को infinity निर्दिष्ट करते हैं; इसके लिए धन्यवाद, कोई भी मार्ग इससे छोटा होगा। हम start_node नोड की cost को 0 भी सेट करेंगे।

फिर इस तरह कोड दिखेगा:

 if adjacent not in reachable: reachable.add(adjacent) # If this is a new path, or a shorter path than what we have, keep it. if node.cost + 1 < adjacent.cost: adjacent.previous = node adjacent.cost = node.cost + 1 

समान खोज लागत

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

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

यहाँ choose_node फ़ंक्शन का एक संभावित उदाहरण दिया choose_node है:

 function choose_node (reachable): best_node = None for node in reachable: if best_node == None or best_node.cost > node.cost: best_node = node return best_node 

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

निष्कर्ष

निम्नलिखित द्वारा विचार किए गए नोड को चुनने की विधि में एक साधारण बदलाव ने हमें एक अच्छा एल्गोरिथ्म प्राप्त करने की अनुमति दी: यह शुरू से अंत तक का सबसे छोटा रास्ता ढूंढता है।

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

क्या choose_node स्मार्ट बनाना संभव है? क्या हम इसे अग्रिम में सही रास्ता जानते हुए भी, अंत नोड की ओर खोज को निर्देशित कर सकते हैं?

यह पता चला है कि हम कर सकते हैं - अगले भाग में, हम अंत में choose_node को प्राप्त करते हैं, जो हमें सामान्य पथ खोज एल्गोरिदम को A * में बदलने की अनुमति देता है।

भाग 3. A से गोपनीयता का पर्दा हटाओ *

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

मैजिक एल्गोरिथ्म

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

 function choose_node (reachable): return magic(reachable, " ,     ") 

लुभावना लगता है, लेकिन जादू के चिप्स को अभी भी कुछ प्रकार के निम्न-स्तरीय कोड की आवश्यकता होती है। यहाँ एक अच्छा सन्निकटन है:

 function choose_node (reachable): min_cost = infinity best_node = None for node in reachable: cost_start_to_node = node.cost cost_node_to_goal = magic(node, "   ") total_cost = cost_start_to_node + cost_node_to_goal if min_cost > total_cost: min_cost = total_cost best_node = node return best_node 

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

हमने उपयोग किए जाने वाले जादू की मात्रा को भी कम कर दिया: हम जानते हैं कि शुरुआती नोड से प्रत्येक नोड (यह node.cost ) पर जाने की लागत क्या है, और हम नोड से अंतिम नोड तक जाने की लागत का अनुमान लगाने के लिए केवल जादू का उपयोग करते हैं।

जादुई नहीं, लेकिन बहुत भयानक ए *

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

 # Throws MuggleProcessorException cost_node_to_goal = magic(node, "   ") 

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

 cost_node_to_goal = distance(node, goal_node) 

ध्यान दें कि सबसे छोटा रास्ता और न्यूनतम दूरी अलग - अलग हैं: न्यूनतम दूरी का मतलब है कि वर्तमान और अंतिम नोड्स के बीच कोई बाधा नहीं है।

यह अनुमान प्राप्त करने के लिए काफी सरल है। हमारे ग्रिड उदाहरणों में, यह दो नोड्स (यानी abs(Ax - Bx) + abs(Ay - By) बीच शहर के ब्लॉक की दूरी है । यदि हम तिरछे तरीके से आगे बढ़ सकते हैं, तो मान sqrt( (Ax - Bx)^2 + (Ay - By)^2 ) बराबर होगा, और इसी तरह। सबसे महत्वपूर्ण बात यह है कि हम कभी भी मूल्य का बहुत अधिक अनुमान नहीं लगाते हैं।

तो यहाँ एक गैर choose_node संस्करण है choose_node :

 function choose_node (reachable): min_cost = infinity best_node = None for node in reachable: cost_start_to_node = node.cost cost_node_to_goal = estimate_distance(node, goal_node) total_cost = cost_start_to_node + cost_node_to_goal if min_cost > total_cost: min_cost = total_cost best_node = node return best_node 

एक फ़ंक्शन जो वर्तमान से अंतिम नोड तक की दूरी का अनुमान लगाता है, उसे एक अनुमानी कहा जाता है, और इस खोज एल्गोरिथ्म, देवियों और सज्जनों, को ... A * कहा जाता है।

इंटरएक्टिव डेमो

जब आप इस अहसास के कारण सदमे से उबर रहे होते हैं कि रहस्यमय A * वास्तव में इतना सरल है , तो आप डेमो को देख सकते हैं (या मूल लेख में इसे चला सकते हैं)। आप देखेंगे कि पिछले उदाहरण के विपरीत, खोज बहुत कम समय गलत दिशा में चलती है।

निष्कर्ष

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

यहाँ आपके संदर्भ के लिए मुख्य विधि का एक पूर्ण छद्म कोड है:

 function find_path (start_node, end_node): reachable = [start_node] explored = [] while reachable is not empty: # Choose some node we know how to reach. node = choose_node(reachable) # If we just got to the goal node, build and return the path. if node == goal_node: return build_path(goal_node) # Don't repeat ourselves. reachable.remove(node) explored.add(node) # Where can we get from here that we haven't explored before? new_reachable = get_adjacent_nodes(node) - explored for adjacent in new_reachable: # First time we see this node? if adjacent not in reachable: reachable.add(adjacent) # If this is a new path, or a shorter path than what we have, keep it. if node.cost + 1 < adjacent.cost: adjacent.previous = node adjacent.cost = node.cost + 1 # If we get here, no path was found :( return None 

build_path विधि:

 function build_path (to_node): path = [] while to_node != None: path.add(to_node) to_node = to_node.previous return path 

और यहाँ choose_node पद्धति है, जो इसे A * में बदल देती है:

 function choose_node (reachable): min_cost = infinity best_node = None for node in reachable: cost_start_to_node = node.cost cost_node_to_goal = estimate_distance(node, goal_node) total_cost = cost_start_to_node + cost_node_to_goal if min_cost > total_cost: min_cost = total_cost best_node = node return best_node 

वह सब है।

लेकिन हमें भाग 4 की आवश्यकता क्यों है?

अब जब आप समझते हैं कि A * कैसे काम करता है, तो मैं इसके अनुप्रयोग के कुछ अद्भुत क्षेत्रों के बारे में बात करना चाहता हूं, जो कोशिकाओं के एक ग्रिड में पथ खोजने तक सीमित होने से दूर हैं।

भाग 4. A * व्यवहार में

लेख के पहले तीन भाग पथ खोज एल्गोरिदम की बहुत नींव से शुरू होते हैं और ए * एल्गोरिथ्म के स्पष्ट विवरण के साथ समाप्त होते हैं। यह सब सिद्धांत में महान है, लेकिन यह समझना कि यह व्यवहार में कैसे लागू होता है, एक पूरी तरह से अलग विषय है।

उदाहरण के लिए, अगर हमारी दुनिया ग्रिड नहीं है तो क्या होगा?

क्या होगा अगर एक चरित्र तुरंत 90 डिग्री को घुमा नहीं सकता है?

अगर दुनिया अंतहीन है तो एक ग्राफ कैसे बनाया जाए?

क्या होगा अगर हम रास्ते की लंबाई के बारे में परवाह नहीं करते हैं, लेकिन हम सौर ऊर्जा पर निर्भर हैं और हमें जितना संभव हो उतना सूरज की रोशनी में होना चाहिए?

दो छोर नोड्स में से किसी के लिए सबसे छोटा रास्ता कैसे खोजें?

लागत समारोह

पहले उदाहरणों में, हमने शुरुआत और अंत नोड्स के बीच सबसे छोटे रास्ते की तलाश की। हालांकि, परिवर्तनीय लंबाई में आंशिक पथ लंबाई संग्रहीत करने के बजाय, हमने इसे cost कहा। क्यों?

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

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

मानदंड समारोह

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

भोले-भाले दृष्टिकोण को प्रत्येक ईंधन भरने के लिए सबसे छोटे मार्ग की गणना करना होगा और सबसे छोटे मार्ग का चयन करना होगा। यह काम करेगा, लेकिन यह काफी महंगी प्रक्रिया होगी।

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

स्थिति की बारीकियों के आधार पर, हम लक्ष्य को पूरी तरह से प्राप्त करने में सक्षम नहीं हो सकते हैं, या इसकी बहुत अधिक लागत आएगी (यदि हम चरित्र को आधे विशाल नक्शे के माध्यम से भेजते हैं, तो क्या अंतर एक इंच महत्वपूर्ण है?), इसलिए is_goal_node पद्धति true हो true जब हम वापस आ सकते हैं? हम "काफी करीब हैं।"

पूर्ण निश्चितता की आवश्यकता नहीं है।

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

लेकिन एक और अधिक गंभीर समस्या है: क्या होगा अगर दुनिया अंतहीन है? इस मामले में, भले ही हम इसे ग्रिड के रूप में प्रस्तुत कर सकते हैं, तो हम बस ग्रिड के अनुरूप ग्राफ का निर्माण नहीं कर पाएंगे, क्योंकि यह अनंत होना चाहिए।

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

यदि आप एल्गोरिथ्म को करीब से देखते हैं, तो आप देखेंगे कि हम ग्राफ के साथ कुछ भी नहीं कर रहे हैं; हम स्थानीय रूप से ग्राफ की जांच करते हैं, नोड्स प्राप्त करते हैं जो हम प्रश्न में नोड से पहुंच सकते हैं। जैसा कि डेमो ए * से देखा जा सकता है, ग्राफ के कुछ नोड्स की जांच बिल्कुल नहीं की जाती है।

तो हम अनुसंधान प्रक्रिया में सिर्फ ग्राफ क्यों नहीं बनाते?

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

तीन आयामों से परे

यहां तक ​​कि अगर आपकी दुनिया वास्तव में एक 2 डी मेष है, तो विचार करने के लिए अन्य पहलू भी हैं। उदाहरण के लिए, क्या होगा यदि कोई पात्र तुरंत 90 या 180 डिग्री को घुमा नहीं सकता, जैसा कि आमतौर पर होता है?

प्रत्येक खोज नोड द्वारा दर्शाया गया राज्य केवल एक स्थिति नहीं है ; इसके विपरीत, इसमें मूल्यों का एक मनमाना जटिल सेट शामिल हो सकता है। उदाहरण के लिए, यदि 90-डिग्री में एक सेल से दूसरे में संक्रमण में उतना ही समय लगता है, तो चरित्र की स्थिति को [position, heading] रूप में सेट किया जा सकता है। प्रत्येक नोड न केवल चरित्र की स्थिति का प्रतिनिधित्व कर सकता है, बल्कि उसकी टकटकी की दिशा भी; और ग्राफ़ के नए किनारे (स्पष्ट या अप्रत्यक्ष) इसे दर्शाते हैं।

यदि आप मूल 5x5 ग्रिड पर वापस जाते हैं, तो प्रारंभिक खोज स्थिति अब [A, East] । पड़ोसी नोड्स अब [B, East] और [A, South] - अगर हम एफ तक पहुंचना चाहते हैं, तो हमें सबसे पहले दिशा को समायोजित करने की आवश्यकता है, ताकि पथ फॉर्म [A, East] , [A, South] , [F, South] ।

पहला व्यक्ति शूटर? कम से कम चार आयाम: [X, Y, Z, Heading] । शायद यहां तक ​​कि [X, Y, Z, Heading, Health, Ammo] ।

ध्यान दें कि राज्य जितना अधिक जटिल होगा, उतना ही अधिक जटिल उत्तराधिकार कार्य होना चाहिए। ए * ही सरल है; कला अक्सर अच्छे उत्तराधिकारियों से उत्पन्न होती है।

निष्कर्ष

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

आगे पढ़ रहे हैं

अमित पटेल का एक उत्कृष्ट "परिचय ए * एल्गोरिथ्म" [हैबे पर अनुवाद ] है (और विभिन्न लेखों पर उनके अन्य लेख भी उत्कृष्ट हैं!)।