شرح بسيط لخوارزميات العثور على المسار و A *

الجزء 1. خوارزمية البحث العامة

مقدمة

يعد العثور على المسار أحد الموضوعات التي عادة ما تكون الأكثر صعوبة لمطوري الألعاب. الفقراء على وجه الخصوص يفهمون خوارزمية A * ، ويعتقد الكثيرون أن هذا نوع من السحر غير المفهوم.

الغرض من هذه المقالة هو شرح البحث عن المسار بشكل عام و A * بشكل خاص بطريقة مفهومة للغاية ويمكن الوصول إليها ، وبالتالي وضع حد للاعتقاد الخاطئ السائد بأن هذا الموضوع معقد. مع التفسير الصحيح ، كل شيء بسيط للغاية.

يرجى ملاحظة أننا سننظر في المقال في البحث عن وسيلة للألعاب ؛ بخلاف المزيد من المقالات الأكاديمية ، فإننا نتجاهل خوارزميات البحث مثل Depth-First أو Breadth-First. بدلاً من ذلك ، سنحاول الانتقال من الصفر إلى A * في أسرع وقت ممكن.

في الجزء الأول ، سنشرح أبسط مفاهيم العثور على المسار. من خلال فهم هذه المفاهيم الأساسية ، ستدرك أن A * واضحة بشكل مدهش.

دائرة بسيطة

على الرغم من أنه يمكنك تطبيق هذه المفاهيم على بيئات 3D المعقدة التعسفية ، دعنا نبدأ بمخطط بسيط للغاية: شبكة بحجم 5 × 5. للراحة ، قمت بتمييز كل خلية بحرف كبير.


شبكة بسيطة.

أول شيء سنفعله هو تخيل هذه البيئة على أنها رسم بياني. لن أشرح بالتفصيل ماهية الرسم البياني ؛ ببساطة ، هذه مجموعة من الدوائر متصلة بالسهام. تسمى الدوائر "عقدة" ، وتسمى الأسهم "الحواف" .

تمثل كل عقدة "حالة" قد تكون فيها الشخصية. في حالتنا ، حالة الشخصية هي موضعه ، لذلك نقوم بإنشاء عقدة واحدة لكل خلية شبكة:


العقد التي تمثل خلايا الشبكة.

الآن إضافة الأضلاع. وهي تشير إلى الحالات التي يمكن "الوصول إليها" من كل ولاية معينة ؛ في حالتنا ، يمكننا الانتقال من أي خلية إلى الخلية التالية ، باستثناء الخلايا المحظورة:


تشير الأقواس إلى الحركات المسموح بها بين خلايا الشبكة.

إذا استطعنا الانتقال من A إلى B ، فإننا نقول أن B هي "جار" للعقدة A.

تجدر الإشارة إلى أن الأضلاع لها اتجاه ؛ نحتاج إلى حواف من A إلى B ومن B إلى A. قد يبدو هذا غير ضروري ، ولكن ليس عندما تنشأ "شروط" أكثر تعقيدًا. على سبيل المثال ، قد تسقط الشخصية من السقف إلى الأرض ، ولكنها غير قادرة على القفز من الأرض إلى السقف. يمكنك الانتقال من حالة "الأحياء" إلى حالة "الموتى" ، ولكن ليس العكس. و هكذا.

مثال

لنفترض أننا نريد الانتقال من A إلى T. نبدأ بـ A. يمكنك القيام بعملين بالضبط: اذهب إلى B أو اذهب إلى F.

دعنا نقول انتقلنا إلى B. الآن يمكننا أن نفعل شيئين: العودة إلى A أو الذهاب إلى C. نتذكر أننا كنا بالفعل في A ونظرنا في الخيارات هناك ، لذلك ليس من المنطقي أن نفعل ذلك مرة أخرى (وإلا فبإمكاننا قضاء يوم كامل في نقل A → B → A → B ...). لذلك سوف نذهب إلى C.

يجري في C ، ليس لدينا مكان للتحرك. إن العودة إلى " ب" لا معنى لها ، أي أنها طريق مسدود. كان اختيار الانتقال إلى B عندما كنا في A فكرة سيئة ؛ ربما يجب أن تجرب F بدلاً من ذلك؟

نستمر في تكرار هذه العملية حتى ننتهي في T. في هذه اللحظة ، نقوم ببساطة بإعادة إنشاء المسار من A ، والعودة في خطواتنا. نحن في تي . كيف وصلنا إلى هناك؟ من س ؟ أي أن نهاية المسار لها شكل O → T. كيف وصلنا إلى يا ؟ و هكذا.

ضع في اعتبارك أننا لا نتحرك حقًا ؛ كل هذا كان مجرد عملية فكرية. نستمر في الوقوف في A ، ولن نخرج منه حتى نعثر على المسار بالكامل. عندما أقول "انتقل إلى B " ، أعني "تخيل أننا انتقلنا إلى B ".

الخوارزمية العامة

هذا القسم هو الجزء الأكثر أهمية في المقال بأكمله . يجب أن تفهمها تمامًا حتى تتمكن من تحقيق البحث عن الطريق ؛ الباقي (بما في ذلك A * ) هي مجرد تفاصيل. في هذا القسم ، سوف تفهم حتى تفهم المعنى .

بالإضافة إلى ذلك ، هذا القسم بسيط للغاية.

دعونا نحاول إضفاء الطابع الرسمي على مثالنا ، وتحويله إلى رمز زائف.

نحن بحاجة إلى تتبع العقد التي نعرف كيفية الوصول إليها من عقدة البداية. في البداية ، هذه ليست سوى عقدة البداية ، ولكن في عملية "استكشاف" الشبكة ، سوف نتعلم كيفية الوصول إلى العقد الأخرى. دعنا ندعو إلى قائمة العقد هذه reachable :

 reachable = [start_node] 

نحتاج أيضًا إلى تتبع العقد التي تم استعراضها بالفعل حتى لا نراها مرة أخرى. explored ندعو لهم explored :

 explored = [] 

بعد ذلك ، سأحدد جوهر الخوارزمية : في كل خطوة من خطوات البحث ، نختار إحدى العقد التي نعرف كيفية الوصول إلى العقد الجديدة التي يمكننا الحصول عليها وإلقاء نظرة عليها. إذا حددنا كيفية الوصول إلى العقدة النهائية (الهدف) ، فسيتم حل المشكلة! خلاف ذلك ، نواصل البحث.

في غاية البساطة ، ما حتى الإحباط؟ وهذا صحيح. ولكن هذه هي الخوارزمية بأكملها. دعنا نكتبها خطوة بخطوة باستخدام الكود الزائف.

نستمر في البحث حتى نصل إلى العقدة النهائية (في هذه الحالة ، نجد المسار من العقدة الأولى إلى العقدة الأخيرة) ، أو حتى نفد العقد التي يمكنك البحث فيها (في هذه الحالة ، لا توجد وسيلة بين العقد البداية والنهاية) .

 while reachable is not empty: 

نختار إحدى العقد التي نعرف كيف نحصل عليها ، والتي لم يتم التحقيق فيها بعد:

  node = choose_node(reachable) 

إذا تعلمنا للتو كيفية الوصول إلى العقدة النهائية ، فإن المهمة تكون كاملة! نحتاج فقط إلى بناء المسار باتباع الروابط 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 

هذا كل شيء. هذا هو الكود الكاذب لكل خوارزمية البحث عن المسار ، بما في ذلك A * .

أعد قراءة هذا القسم حتى تفهم كيف يعمل كل شيء ، والأهم من ذلك ، لماذا يعمل كل شيء. سيكون من المثالي رسم مثال باليد على الورق ، ولكن يمكنك أيضًا مشاهدة عرض توضيحي تفاعلي:

عرض تفاعلي

فيما يلي عرض توضيحي ومثال على تنفيذ الخوارزمية الموضحة أعلاه (يمكنك تشغيله على صفحة المقالة الأصلية ). choose_node فقط يختار عقدة عشوائية. يمكنك بدء الخوارزمية خطوة بخطوة وإلقاء نظرة على قائمة explored reachable explored ، وكذلك المكان الذي تشير إليه الروابط previous .


لاحظ أن البحث ينتهي بمجرد اكتشاف المسار ؛ قد يحدث أن بعض العقد لا تعتبر حتى.

استنتاج

الخوارزمية المقدمة هنا هي خوارزمية عامة لأي خوارزمية البحث عن مسار.

ولكن ما الذي يميز كل خوارزمية عن أخرى ، لماذا A * هي A * ؟

إليك نصيحة: إذا قمت بإجراء البحث في العرض التوضيحي عدة مرات ، فسترى أن الخوارزمية لا تجد دائمًا نفس المسار دائمًا. يجد طريقًا ، وهذا المسار ليس بالضرورة الأقصر . لماذا؟

الجزء 2. استراتيجيات البحث

إذا لم تفهم الخوارزمية الموضحة في القسم السابق تمامًا ، فارجع إليها وقراءتها مرة أخرى ، لأنه ضروري لفهم مزيد من المعلومات. عندما تكتشف ذلك ، ستظهر A * بشكل طبيعي ومنطقي تمامًا.

العنصر السري

في نهاية الجزء السابق ، تركت سؤالين مفتوحين: إذا كانت كل خوارزمية بحث تستخدم نفس الكود ، فلماذا تتصرف A * مثل A * ؟ ولماذا تجد التجريبي في بعض الأحيان مسارات مختلفة؟

ترتبط الإجابات على كلا السؤالين ببعضهما البعض. على الرغم من أن الخوارزمية محددة جيدًا ، إلا أنني تركت جانبًا واحدًا دون حل ، وكما اتضح ، فهو المفتاح لشرح سلوك خوارزميات البحث:

 node = choose_node(reachable) 

هذه السلسلة ذات المظهر البريء هي التي تميز كل خوارزميات البحث عن بعضها البعض. choose_node يعتمد على طريقة تنفيذ 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 . بفضل هذا ، فإن أي مسار سيكون أقصر من هذا. سنقوم أيضًا بتعيين cost عقدة start_node على 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 :

 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 

بشكل حدسي ، يتوسع البحث عن هذه الخوارزمية "شعاعيًا" من عقدة البدء حتى تصل إلى عقدة النهاية. إليك عرض توضيحي تفاعلي لهذا السلوك:

استنتاج

سمح لنا تغيير بسيط في طريقة اختيار العقدة التي تم النظر فيها فيما يلي بالحصول على خوارزمية جيدة إلى حد ما: حيث تجد أقصر مسار من البداية إلى النهاية.

ولكن هذه الخوارزمية ، إلى حد ما ، لا تزال "غبية". يواصل البحث في كل مكان حتى يتعثر على عقدة طرفية. على سبيل المثال ، ما هي النقطة في المثال الموضح أعلاه للبحث في الاتجاه A ، إذا كان من الواضح أننا نتحرك بعيدًا عن عقدة النهاية؟

هل من الممكن جعل choose_node أكثر ذكاءً؟ هل يمكننا أن نجعله يوجه البحث باتجاه العقدة النهائية ، حتى دون معرفة المسار الصحيح مقدمًا؟

اتضح أننا نستطيع - في الجزء التالي ، أن نصل في النهاية إلى choose_node ، مما يسمح لنا بتحويل خوارزمية البحث عن المسار العام إلى A * .

الجزء 3. إزالة حجاب السرية من A *

الخوارزمية التي تم الحصول عليها في الجزء السابق جيدة جدًا: حيث تجد أقصر مسار من عقدة البداية إلى النهاية الأخيرة. ومع ذلك ، فهو يهدر طاقته: فهو يفكر في الطرق التي يصفها الشخص بوضوح بأنها خاطئة - وعادة ما يتحرك بعيدًا عن الهدف. كيف يمكن تجنب ذلك؟

خوارزمية السحر

تخيل أننا نقوم بتشغيل خوارزمية بحث على جهاز كمبيوتر خاص مع شريحة يمكن أن تفعل السحر . بفضل هذه الشريحة المذهلة ، يمكننا التعبير عن 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 أيضًا مقدار السحر المستخدم: نحن نعرف بالضبط تكلفة الانتقال من عقدة البداية إلى كل عقدة (هذا هو node.cost ) ، ونحن نستخدم السحر فقط للتنبؤ بتكلفة الانتقال من العقدة إلى العقدة النهائية.

ليست سحرية ، ولكن رهيبة جدا A *

لسوء الحظ ، فإن الرقائق السحرية جديدة ، ونحن بحاجة إلى دعم من المعدات القديمة. معظم الكود يناسبنا ، باستثناء هذا السطر:

 # 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 طريقة 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 درجة؟

كيفية بناء الرسم البياني إذا كان العالم لا نهاية لها؟

ماذا لو كنا لا نهتم بطول المسار ، لكننا نعتمد على الطاقة الشمسية وعلينا أن نكون تحت أشعة الشمس قدر الإمكان؟

كيفية العثور على أقصر طريق إلى أي من العقدتين النهاية؟

وظيفة التكلفة

في الأمثلة الأولى ، بحثنا عن أقصر الطرق بين العقد البداية والنهاية. ومع ذلك ، بدلاً من تخزين أطوال المسار الجزئي في length المتغير ، أطلقنا عليه cost . لماذا؟

يمكننا أن نجعل A * لا تبحث فقط عن أقصر ، ولكن أيضًا عن أفضل مسار ، ويمكن اختيار تعريف "best" استنادًا إلى أهدافنا. عندما نحتاج إلى أقصر مسار ، تكون التكلفة هي طول المسار ، ولكن إذا كنا نريد تقليل ، على سبيل المثال ، استهلاك الوقود ، فإننا نحتاج إلى استخدامه كتكلفة. إذا كنا نريد زيادة "الوقت الذي تقضيه تحت أشعة الشمس" ، فإن التكلفة هي الوقت الذي تقضيه بدون الشمس. و هكذا.

في الحالة العامة ، هذا يعني أن التكاليف المقابلة ترتبط بكل حافة من الرسم البياني. في الأمثلة الموضحة أعلاه ، تم تعيين القيمة ضمنيًا وكانت تعتبر دائمًا تساوي 1 ، لأننا عدنا الخطوات على طول الطريق. لكن يمكننا تغيير تكلفة الضلع وفقًا لما نريد تقليله.

وظيفة المعيار

دعنا نقول أن هدفنا هو سيارة ، وهو بحاجة للوصول إلى محطة الوقود. أي التزود بالوقود سوف تناسبنا. يستغرق أقصر طريق إلى أقرب محطة وقود.

سيكون النهج الساذج هو حساب أقصر طريق لكل عملية تزود بالوقود بدوره وتحديد أقصرها. هذا سوف ينجح ، لكنها ستكون عملية مكلفة للغاية.

ماذا لو استطعنا استبدال أحد goal_node بأسلوب ، على عقدة معينة ، يمكنه معرفة ما إذا كانت محدودة أم لا. بفضل هذا ، يمكننا البحث عن عدة أهداف في نفس الوقت. نحتاج أيضًا إلى تعديل الاستدلال بحيث تعيد التكلفة المقدرة الدنيا لجميع العقد النهائية الممكنة.

اعتمادًا على تفاصيل الموقف ، قد لا نتمكن من تحقيق الهدف بشكل مثالي ، أو is_goal_node الكثير (إذا أرسلنا الحرف من خلال نصف خريطة ضخمة ، فهل الفرق بوصة واحدة مهمة؟) ، لذلك يمكن أن تعود طريقة is_goal_node إلى is_goal_node عندما نتمكن من نحن "قريبون بما فيه الكفاية".

اليقين الكامل غير مطلوب.

قد لا يكون تمثيل العالم كشبكة منفصلة كافياً للعديد من الألعاب. خذ على سبيل المثال مطلق النار أو لعبة السباق من الشخص الأول. العالم منفصل ، لكن لا يمكن تمثيله كشبكة.

ولكن هناك مشكلة أكثر خطورة: ماذا لو كان العالم لا نهاية له؟ في هذه الحالة ، حتى لو تمكنا من تقديمها في شكل شبكة ، فلن نتمكن ببساطة من بناء رسم بياني يتوافق مع الشبكة ، لأنه يجب أن يكون غير محدود.

ومع ذلك ، لا تضيع كل شيء. بالطبع ، بالنسبة لخوارزمية البحث عن الرسم البياني ، نحتاج بالتأكيد إلى رسم بياني. لكن لا أحد قال إن الرسم البياني يجب أن يكون شاملاً !

إذا نظرت عن كثب إلى الخوارزمية ، ستلاحظ أننا لا نفعل أي شيء مع الرسم البياني ككل ؛ نحن نفحص الرسم البياني محليًا ، ونحصل على العقد التي يمكننا الوصول إليها من العقدة المعنية. كما يتضح من العرض التوضيحي A * ، فإن بعض العقد من الرسم البياني لا يتم التحقيق فيها على الإطلاق.

فلماذا لا نبني الرسم البياني في عملية البحث؟

نجعل الموضع الحالي للشخصية هو نقطة الانطلاق. عند استدعاء get_adjacent_nodes يمكنه تحديد الطرق الممكنة التي يمكن للشخصية من خلالها الانتقال من عقدة معينة ، وإنشاء العقد المجاورة على الطاير.

وراء ثلاثة أبعاد

حتى لو كان عالمك عبارة عن شبكة ثنائية الأبعاد ، فهناك جوانب أخرى يجب مراعاتها. على سبيل المثال ، ماذا لو لم تتمكن الشخصية من تدوير 90 أو 180 درجة على الفور ، كما هو الحال عادة؟

لا يجب أن تكون الحالة الممثلة بكل عقدة بحث مجرد موقع ؛ على العكس من ذلك ، قد يتضمن مجموعة من القيم المعقدة بشكل تعسفي. على سبيل المثال ، إذا كانت المنعطفات بزاوية 90 درجة تستغرق وقتًا من الوقت الذي تستغرقه عملية الانتقال من خلية إلى أخرى ، فيمكن تعيين حالة الشخصية كـ [position, heading] . لا يمكن أن تمثل كل عقدة موقف الشخصية فحسب ، بل يمكن أن تمثل أيضًا اتجاه نظرته ؛ والحواف الجديدة للرسم البياني (صريحة أو غير مباشرة) تعكس هذا.

إذا عدت إلى شبكة 5 × 5 الأصلية ، يمكن الآن أن يكون موقع البحث الأولي هو [A, East] . العقد المجاورة الآن هي [B, East] و [A, South] - إذا أردنا الوصول إلى F ، نحتاج أولاً إلى ضبط الاتجاه بحيث يأخذ المسار الشكل [A, East] ، [A, South] ، [F, South] .

أول شخص مطلق النار؟ أربعة أبعاد على الأقل: [X, Y, Z, Heading] . ربما حتى [X, Y, Z, Heading, Health, Ammo] .

لاحظ أنه كلما كانت الحالة أكثر تعقيدًا ، كلما كانت الوظيفة الاستدلالية أكثر تعقيدًا. * نفسه بسيط ؛ الفن غالبا ما ينشأ من الاستدلال الجيد.

استنتاج

الغرض من هذه المقالة هو تبديد الأسطورة مرة واحدة وإلى الأبد أن A * هي خوارزمية صوفية لا يمكن فك تشفيرها. على العكس من ذلك ، لقد أظهرت أنه لا يوجد شيء غامض فيه ، وفي الواقع يمكن استنتاجه ببساطة من خلال البدء من نقطة الصفر.

مزيد من القراءة

يمتلك أميت باتيل "مقدمة لخوارزمية A * ممتازة " [ الترجمة على Habré] (ومقالاته الأخرى حول مواضيع مختلفة هي أيضًا ممتازة!).