إيجاد طريق بين العقبات المستديرة

غابات الملاحة

A * Path Finder Algorithm هي أداة قوية لتوليد مسارات مثالية بسرعة. عادةً ما تظهر A * عند التنقل في الخرائط من الشبكات ، ولكن يمكن استخدامها ليس فقط للشبكات! يمكن أن تعمل مع أي الرسوم البيانية. يمكنك استخدام A * لتجد طريقك في عالم العقبات المستديرة.


في المقال الأصلي ، كل الصور تفاعلية.

كيف تحل خوارزمية واحدة هاتين المشكلتين؟ لنبدأ بوصف موجز لكيفية عمل A *.

الخوارزمية A *

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

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

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

الايرل لقب انكليزي

A * يعمل مع رسم بياني : مجموعة من العقد متصلة بواسطة الحواف . في عالم قائم على الشبكة ، تشير كل عقدة إلى خلية شبكة منفصلة ، وكل حافة عبارة عن اتصال بالخلايا المجاورة إلى الشمال أو الجنوب أو الشرق أو الغرب.

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

المسار عبر رسم بياني عبارة عن سلسلة من العقد متصلة بواسطة الحواف:


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

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

الانتقال الحافة الجيل

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

الظلال الداخلية إلى نقطتين

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


كما اتضح ، للدوائر مع المراكز $$$دولا$ و $$$B$ ونصف القطر $$$r_A$ و $$$r_B$ المراكز التي هي على مسافة $$$د$ :

$$

$$\ theta = \ arccos {{r_A + r_B} \ over {d}}$$

تحديد $$$\ theta$ يمكننا بسهولة العثور على النقاط $$$C$ . $$$D$ . $$$E$ و $$$F$ .

الظلال الخارجية إلى نقطتين

عند بناء الظلال الخارجية (هذه هي مهمة البكرات ) ، يتم استخدام تقنية مماثلة.


لالظلال الخارجية يمكن أن نجد $$$\ theta$ على النحو التالي:

$$

$$\ theta = \ arccos {{\ lvert r_A - r_B \ rvert} \ over d}$$

لا يهم أي من الدوائر أكبر ، A أو B ، ولكن كما ترون من الصورة ، $$$\ theta$ وضعت على الجانب الأقرب إلى B ، ولكن على الجانب B الأبعد من A.

خط البصر

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


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

لحساب المسافة من نقطة $$$C$ إلى شريحة خط مستقيم $$$\ overline {AB}$ سوف نستخدم الطريقة التالية :

أولا ، نحسب $$$u$ - جزء من المسافة على طول الجزء $$$\ overline {AB}$ حيث يتقاطع العمودي هذه النقطة $$$C$ :

$$

$$u = {(C - A) \ cdot (B-A) \ over (B-A) \ cdot (B-A)}$$

ثم نحسب الموقف $$$E$ في $$$\ overline {AB}$ :

$$

$$E = A + \ mathrm {clamp} (u، 0، 1) * (B - A)$$

بعد $$$د$ من $$$C$ لخفض $$$\ overline {AB}$ هي المسافة من $$$C$ إلى $$$E$ :

$$

$$d = \ | E - C \ |$$

ل $$$d <r$ تتداخل الدائرة مع خط البصر $$$دولا$ في $$$B$ ، ويجب تجاهل الحافة. إذا $$$d \ ge r$ ثم خط الأفق $$$دولا$ في $$$B$ موجود ويجب أن تترك الضلع.

جيل مغلف الحافة

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


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

وضع كل ذلك معا

بعد إنشاء حواف النقل ، ومغلفات الحواف والعقد ، ثم التخلص من جميع حواف الانتقال المتداخلة ، يمكننا إنشاء رسم بياني وبدء البحث عن المسار باستخدام خوارزمية A *.

تحسينات

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

العقبات التي تهم بعضنا البعض

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

اثنين من نقطة الظل

تذكر أنه يمكن العثور على المظلمات إلى نقطتين باستخدام هذه الصيغة للظلال الداخلية:

$$

$$\ theta = \ arccos {{r_A + r_B} \ over {d}}$$

والصيغ لالظلال الخارجية:

$$

$$\ theta = \ arccos {{\ lvert r_A - r_B \ rvert} \ over d}$$

عندما تلمس دائرتان بعضهما البعض أو تتقاطع ، فلا توجد بينهما ظلال داخلية. في هذه الحالة $$${r_A + r_B} \ over d$ اكثر من واحد لأن قيمة قوس قزح خارج مجال التعريف $$$[- 1، 1]$ غير محدد ، من المهم التحقق من تقاطع الدوائر قبل العثور على أركوسين.

وبالمثل ، إذا كانت إحدى الدوائر موجودة تمامًا في دائرة أخرى ، فلن يكون هناك ظلال خارجية بينهما. في هذه الحالة $$${r_A - r_B} \ over d$ خارج النطاق $$$[- 1، 1]$ ، وهذا هو ، فإنه لا يحتوي على أركوسين.

خط الانتقال حافة الرؤية

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

أذكر الحساب $$$u$ - جزء من المسافة على طول حافة الانتقال حيث يمس العمودي على النقطة الحافة. إذا كان لمس الدوائر غير مسموح به ، فعندئذ تكون القيمة $$$u$ خارج النطاق $$$[0،1]$ وهذا يعني أن الدائرة لا يمكن أن تمس الحافة ، لأنه سيتعين عليها أن تلمس إحدى نقاط نهاية الحافة. هذا غير ممكن لأن نقاط النهاية الخاصة بالحافة متشابكة بالفعل مع دوائر أخرى.

ومع ذلك ، إذا سمحنا بإمكانية تداخل الدوائر ، فعندئذٍ القيم $$$u$ خارج النطاق $$$[0،1]$ يمكن أن تتداخل مع خط البصر على طول الحافة. يتوافق هذا مع الحالات التي توجد فيها الدائرة خارج نهاية حافة النقل ، ولكن تتداخل أو تلامس نقطة النهاية. لتتبع مثل هذه الحالات رياضيا ، فإننا سوف تحد $$$u$ الفاصلة $$$[0،1]$ :

$$

$$E = A + clamp (u، 0، 1) * (B - A)$$

مغلف خط البصر

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


لتحديد ما إذا كان مظروف الحافة قد تم حظره بواسطة عائق آخر ، نستخدم الطريقة التالية لتحديد النقاط التي تتقاطع بها دائرتان. إذا الدوائر لديها مراكز في نقاط $$$دولا$ و $$$B$ ونصف القطر $$$r_A$ و $$$r_B$ حيث $$$د$ - المسافة بين $$$دولا$ و $$$B$ بالنسبة للمبتدئين ، نحن بحاجة إلى التحقق من العديد من الحالات. إذا لم تلمس الدوائر بعضها البعض (أي $$$d> r_A + r_B$ )
هي واحدة داخل الآخر ( $$$d <| r_A - r_B |$ ) أو تطابق ( $$$د = 0 دولا$ و $$$r_A = r_B$ ) ، ثم الدوائر لا يمكن أن تؤثر على مغلفات بعضهم البعض.

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

$$

$$a = {r_A ^ 2 - r_B ^ 2 + d ^ 2 \ over 2d}$$

نتائج $$$دولا$ يمكننا أن نجد الزاوية $$$\ theta$ :

$$

$$\ theta = \ arccos {a \ over r_A}$$

إذا $$$\ theta$ هو الصفر ، ثم تلمس الدوائر في $$$C$ . خلاف ذلك ، هناك نقطتين تقاطع المقابلة الإيجابية والسلبية $$$\ theta$ .


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

بعد إجراء تغييرات على حساب الظل إلى نقطتين وخط البصر لحواف الانتقال ومظاريف الحواف ، كل شيء يعمل بشكل صحيح.

متغير دائرة نصف قطرها الممثل و Minkowski التمديد

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

مؤجل الحافة الجيل

بشكل عام ، رسم بياني لغابة من $$$ن$ العقبات تحتوي $$$O (n ^ 2)$ حواف الانتقال ، ولكن لأن كل واحد منهم يحتاج إلى التحقق من خط الرؤية مع $$$ن$ العقبات ، ثم إجمالي الوقت توليد الرسم البياني هو $$$O (n ^ 3)$ . بالإضافة إلى ذلك ، يمكن أن تؤدي أزواج من حواف الانتقال إلى إنشاء حواف مظروف ، ويجب فحص كل واحدة منها مع كل عقبة لخط الرؤية. ومع ذلك ، نظرًا للكفاءة العالية لخوارزمية A * ، عادة ما ينظر إلى جزء فقط من هذا الرسم البياني الكبير لإنشاء المسار الأمثل.

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

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

الحالة التالية هي عندما وصلت A * إلى هذه النقطة $$$ع$ على حافة عقبة $$$C$ على طول حافة النقل: يجب على neighbors() إرجاع مظاريف الحواف المؤدية من $$$ع$ . للقيام بذلك ، نحدد حواف الانتقال الخارجة من العقبة عن طريق حساب الظلات إلى نقطتين بينهما $$$C$ وجميع العقبات الأخرى ، والتخلص من كل تلك التي ليست في خط البصر. ثم نجد جميع مظاريف الحواف متصلة $$$ع$ مع هذه الحواف الانتقالية ، وإسقاط تلك التي يتم حظرها من قبل العقبات الأخرى. نرجع كل مظاريف الحواف هذه ، مع توفير حواف الانتقال للعودة في مكالمة لاحقة neighbors() .

الحالة الأخيرة هي عندما توغلت A * حول حافة الظرف على طول العقبة $$$C$ ويحتاج إلى المغادرة $$$C$ على طول حافة الانتقال. نظرًا لأن الخطوة السابقة تم حسابها وحفظها جميع حواف النقل ، يمكنك ببساطة العثور على المجموعة الصحيحة من الحواف وإعادتها.

قطعنا الأظرف المدببة للأضلاع

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

يتكون المسار الأمثل عبر مجموعة العقبات دائمًا من حواف الانتقال بالتناوب ومظاريف الحواف. لنفترض أننا ندخل العقدة $$$دولا$ وتقرر كيفية الخروج منه:


تسجيل الدخول من خلال $$$دولا$ يعني أننا نتحرك في اتجاه عقارب الساعة ( $$$\ circlearrowright$ ). يجب علينا الخروج من العقدة ، مما يسمح لنا بمواصلة التحرك في اتجاه عقارب الساعة ( $$$\ circlearrowright$ ) ، وهذا هو ، لا يمكننا الخروج إلا من خلال العقدة $$$B$ أو $$$D$ . إذا كنت الخروج من خلال $$$C$ ثم انعطاف ( $$$\ curlywedge$ ) الطرق التي لن تكون الأمثل. نحن بحاجة إلى تصفية هذه الحواف المدببة.

أولاً ، لاحظ أن A * يعالج كل حافة غير موجهة على أي حال. $$$P \ longleftrightarrow Q$ مثل اثنين من الحواف الموجهة $$$P \ longrightarrow Q$ و $$$Q \ longrightarrow P$ . يمكننا الاستفادة من هذا عن طريق تحديد الحواف والعقد مع الاتجاه.

1. عقدة $$$P$ تصبح العقد مع الاتجاه - في اتجاه عقارب الساعة ( $$$P \ circlearrowright$ ) أو عكس اتجاه عقارب الساعة ( $$$P \ circlearrowleft$ ) السهام.
2. حواف الانتقال غير الموجهة $$$P \ longleftrightarrow Q$ تصبح حواف المنحى $$$P ، p \ longrightarrow Q ، \ hat {q}$ و $$$Q ، q \ longrightarrow P ، \ hat {p}$ حيث $$$ع$ و $$$ف دولا$ هي التوجهات ، و $$$\ hat {x}$ يعني الاتجاه المعاكس $$$x$ .
3. مغلفات الضلع غير الموجهة $$$P \ longleftrightarrow Q$ تصبح حواف المنحى $$$P \ circlearrowright \ longrightarrow Q \ circlearrowright$ و $$$P \ circlearrowleft \ longrightarrow Q \ circlearrowleft$ . هذا هو المكان الذي يحدث التصفية: لا يمكننا تمكين $$$P \ circlearrowright \ longrightarrow Q \ circlearrowleft$ و $$$P \ circlearrowleft \ longrightarrow Q \ circlearrowright$ ، لأن التغيير في الاتجاه يخلق مكامن الخلل ( $$$\ curlywedge$ ).

في دائرتنا ، العقدة $$$دولا$ سوف تتحول إلى عقدتين ، $$$A \ circlearrowright$ و $$$A \ circlearrowleft$ لديها حافة انتقال واردة $$$\ longrightarrow A \ circlearrowright$ والحافة الانتقالية المنتهية ولايته $$$A \ circlearrowleft \ longrightarrow$ . إذا ضربنا الطريق $$$A \ circlearrowright$ ثم يجب الخروج من خلال العقدة $$$\ circlearrowright$ والتي ستكون إما حافة الانتقال $$$B \ circlearrowright \ longrightarrow$ (من خلال حافة المغلف $$$A \ circlearrowright \ longrightarrow B \ circlearrowright$ ) ، أو الحافة الانتقالية $$$D \ circlearrowright \ longrightarrow$ (من خلال حافة المغلف $$$A \ circlearrowright \ longrightarrow D \ circlearrowright$ ). لا يمكننا الخروج من خلال $$$C \ circlearrowleft \ longrightarrow$ ، لأن اتجاه الدوران سوف يتغير بهذه الطريقة ، وقمنا بتصفية مغلف الحافة $$$A \ circlearrowright \ longrightarrow C \ circlearrowleft$ .

بتصفية هذه الأظرف المدببة للحواف من الرسم البياني ، قمنا بزيادة كفاءة الخوارزمية.

قطع حواف متقاطعة

يمكن قطع المسارات الجزئية ، حيث تتقاطع الحواف الأخيرة لعملية النقل مع الحافة قبل الأخيرة من الانتقال.

العقبات المضلعة

راجع Game Programming Gems 2 ، الفصل 3.10 ، تحسين مسار نقاط الرؤية ، كتبه Thomas Young. يناقش هذا الفصل عقد القطع ، ولكن ليس للدوائر ، ولكن للمضلعات.

المواد المرجعية

• مهمة الأحزمة
• مهمة البكرة
• المسافة بين النقطة والخط
• تقاطع دائرتين