ما الطريق الذي سيكون الأكثر أمانًا ، وأين أكثر الأعداء وأين توجد مجموعة الإسعافات الأولية؟ كل هذه المشاكل التي كثيرا ما واجهتها في العلاقات المكانية يمكن حلها بشكل فعال باستخدام أقسام رياضية تسمى "مخططات فورونوي". من هذا المنشور سوف تتعلم كيفية تحليل بطاقات اللعبة وتلقي المعلومات التي تضمن واقعية ونجاح الذكاء الاصطناعي.
العلاقة المكانية
العلاقة المكانية هي أي معلومات تصف كيفية ارتباط كائن في الفضاء بكائن آخر. أمثلة: المسافة بينهما ، والمساحة التي يغطيها كل منهما ، وتقاطع هذه المناطق ، وعدد هذه الأشياء الموجودة في منطقة واحدة.
يتم استخدام هذه العلاقات باستمرار في ألعاب الفيديو ويمكن أن توفر معلومات مفيدة للغاية عن الذكاء الاصطناعي ، وكذلك للاعب نفسه.
فورونوي لديه إجابة
يصف
مخطط فورونوي العلاقة المكانية بين نقاط متباعدة عن كثب أو أقرب جيرانهم. هذه هي مجموعة من المضلعات المتصلة التي تم الحصول عليها من النقاط أو المواقع. يقع كل سطر من "منطقة" فورونوي في الوسط بين نقطتين.
لفهم ، ألق نظرة على الصورة:
كما ترون ، كل سطر يقع في الوسط بين نقطتين ، وكلها متصلة في الوسط. أضف المزيد من النقاط إلى المشهد وشاهد ما يحدث:
أصبحت الصورة أكثر إثارة للاهتمام! لدينا بالفعل مجالات حقيقية.
ماذا تخبرنا كل منطقة؟ نعلم أن التواجد في المنطقة مضمون ليكون أقرب إلى نقطة واحدة ، وهي أيضًا في المنطقة. هذا يخبرنا الكثير حول ما هو قريب ؛ هذه هي العلاقة المكانية الأساسية في مخططات فورونوي.
تحويل Voronoi الداخل الى الخارج: Delaunay التثليث
ويسمى النظام المقابل لمخطط فورونوي تثليث ديلوناي. يتكون هذا المخطط من خطوط من كل نقطة إلى أقرب جيرانها ، ويكون كل خط عموديًا على حافة فورونوي التي يتقاطع معها. إليك ما يبدو عليه:
الأبيض يمثل خط Delaunay. يتوافق كل سطر من خطوط Delaunay مع حافة Voronoi واحدة. في البداية يبدو أن بعضهم يعبر عدة حواف ، لكن بالنظر عن كثب ، ستدرك أن هذا ليس كذلك.
في الشكل ، يتوافق خط Delaunay الأخضر مع الضلع الوردي لفورونوي. فقط تخيل أن الضلع الوردي يمضي إلى أبعد من ذلك وترى أنه يتقاطع.
بفضل تثليث Delaunay ، نرى أنه بدلاً من المضلعات لدينا الآن العديد من المثلثات. هذا مفيد بشكل لا يصدق لأننا قسمنا المنطقة إلى مثلثات يمكن تقديمها. يمكن استخدام هذه التقنية في التغطية بالفسيفساء أو تثليث الأرقام. ! ممتاز
بالإضافة إلى ذلك ، هذه طريقة رائعة لإنشاء رسم بياني من نقاط متعددة في حال أردنا الانتقال من نقطة إلى أخرى. على سبيل المثال ، قد تشير النقاط إلى المدن.
بنية بيانات فورونوي
نحن نعرف بالفعل كيف يبدو مخطط فورونوي ؛ الآن دعونا نرى كيف سيبدو هيكل البيانات الخاص به. نحتاج أولاً إلى حفظ النقاط التي تشكل أساس مخطط فورونوي:
class VoronoiPoint { float x float y VoronoiRegion* region }
كل
VoronoiPoint لها موقع
(x, y) ورابط للمنطقة التي تقع فيها.
بعد ذلك نحتاج إلى وصف
VoronoiRegion :
class VoronoiRegion { VoronoiPoint* point Edge *edges[]
تخزن المنطقة رابطًا إلى
VoronoiPoint ، بالإضافة إلى قائمة بحواف
VoronoiEdges .
لنرى كيف يبدو
VoronoiEdges :
class VoronoiEdge { VoronoiPoint* pointA VoronoiPoint* pointB float distance
تعرف الحافة نقطتين تحددهما ، وكذلك المسافة بينهما. بالنسبة للعرض المرئي ، وكذلك لبناء شكل المنطقة المضلعة ، نحتاج إلى تخزين نقاط البداية والنهاية للحافة.
وهذا كل شيء. مع هذه المعلومات ، يمكننا بسهولة إنشاء مخطط فورونوي. أدناه سوف نتعلم كيف يتم إنشاء مخطط فورونوي. لكن الآن ، دعونا نلقي نظرة على بعض الأمثلة عن كيفية استخدام هذه البيانات.
ابحث عن أقرب خزانة دواء
مرة أخرى ، انظر إلى مخطط فورونوي للحصول على نقاط.
إذا كانت كل نقطة تدل على مجموعة للإسعافات الأولية ، فيمكننا تحديد المكان الأقرب منا بسرعة ، ولكن أولاً نحتاج إلى تحديد المنطقة التي نحن فيها. لا توفر مخططات فورونوي طريقة فعالة لتعريف المنطقة ، ومع ذلك ، لتسريع عملية البحث ، يمكننا تخزين رابط لكل منطقة في
شجرة الربع أو في
شجرة آر . وبعد أن تعلمنا المنطقة ، سنتمكن من التعرف على جيرانها وجيران جيرانها.
على سبيل المثال ، إذا لم يكن هناك المزيد من مجموعات الإسعافات الأولية في منطقتك ، فأنت بحاجة إلى العثور على مسار إلى آخر أقرب. من بنية البيانات والرمز الزائف الموضح أعلاه ، يمكننا أن نفهم أن معرفة المنطقة ، يمكننا التعرف على حوافها. وبمساعدة من هذه الأضلاع يمكننا الحصول على الجيران. سنأخذ أقرب جار ونرى ما إذا كانت هناك مجموعة الإسعافات الأولية.
يمكنك أيضًا تطبيق تثليث Delaunay هنا. يتكون من خطوط بين مجموعات الإسعافات الأولية. يمكنك بعد ذلك الالتفاف عليها باستخدام خوارزمية البحث عن مسار A * للعثور على أقرب مجموعة أدوات الإسعافات الأولية.
ابحث عن طريق آمن
استبدال جميع مجموعات الإسعافات الأولية مع أبراج مراقبة العدو. تحتاج إلى العثور على الطريق الأكثر أمانًا بينهما حتى لا يتم القبض عليك. تتمثل الطريقة القياسية لاجتياز الرسم البياني في ألعاب الفيديو في استخدام
خوارزمية A * . نظرًا لأن مخطط فورونوي هو رسم بياني ، فمن السهل جدًا إجراء البحث. نحتاج فقط إلى الخوارزمية A * ، التي تدعم هياكل الرسم البياني العامة ؛ تخطط للمستقبل وسوف تساعدك في المستقبل.
بعد إعداد الرسم البياني ، تحتاج إلى تعيين الوزن لكل حافة. بالنسبة لنا ، ستكون قيمة الوزن هي المسافة إلى أبراج المراقبة هذه ، ويمكنك الحصول عليها مباشرةً من بنية البيانات: كل
VoronoiEdge تعرف بالفعل المسافة بين نقطتين. عادةً ، كلما كانت القيمة على الحافة أصغر ، كانت القيمة أفضل ، ولكن في حالتنا ، زادت القيمة ، لأنها تشير إلى المسافة إلى البرج.
هذا ما يبدو عليه الرسم البياني الأولي إذا أردنا الانتقال من النقطة أ إلى النقطة ب:
بتطبيق الوزن على كل حافة ، سنرى الطريق الأفضل لاختيار:
الأضلاع الحمراء تشير إلى أقرب الاتصالات مع الأبراج. البرتقالي يدل على أطول منها ؛ الأصفر أكثر بعدا ، وأخيرا الأخضر - الأكثر أمانا. بعد تنفيذ A * باستخدام هذه الأوزان ، نحصل على المسار التالي:
باستخدام هذا المقاييس ، لن يتم اختيار الطريقة
الأسرع ، ولكن الطريقة
الأكثر أمانًا ، وهو ما نحتاج إليه. يجب أن تلتزم منظمة العفو الدولية بهذا المسار وألا تنحرف عنه!
يمكنك اتخاذ خطوة أخرى
لضمان مسار آمن: تخلص من جميع الحواف الأقرب من الحد الأدنى للمسافة الآمنة. على سبيل المثال ، إذا كان لكل برج مراقبة نصف قطر رؤية 30 وحدة ، عندئذٍ يمكن إزالة جميع الحواف ، وهي المسافة التي تكون فيها النقاط أقصر ، من الرسم البياني وليس تجاوزها.
يمكنك أيضًا استخدام هذه الطريقة للعثور على أوسع مسار للوحدات الكبيرة التي لا يمكنها المرور عبر الاختناقات. كل حافة لها مسافة بين نقطتين ، لذلك نحن نعرف ما إذا كان يمكن أن تمر في هذا الفضاء.
يمكنك أيضًا إجراء العملية المعاكسة - استخدم مخطط التثليث Delaunay ، واحصل على الخطوط القادمة من كل برج مراقبة. سيكون بمقدور الحراس لمنظمة العفو الدولية أن يحددوا بسرعة الأبراج الأخرى القريبة ، وإذا لزم الأمر ، فانتقل إلى مساعدتهم.
البحث عن مجموعة معبأة بإحكام من العناصر
لنفترض أننا بحاجة إلى إسقاط طرد من النعناع البري من طائرة لحفنة من الأختام التي تجلس على الأرض. أين هي أفضل طريقة لإسقاطه بحيث يمكن لأكبر عدد من القطط استخدامه؟ هذا يمكن أن يكون مكلفا للغاية. لكن لحسن الحظ ، يمكننا أن نفترض افتراضًا معقولًا باستخدام تثليث Delaunay.
تلميح: لا تنس أن تثليث Delaunay هو مجرد عكس الرسم البياني Voronoi. يتم تشكيلها عن طريق ربط كل نقطة Voronoi مع النقاط المجاورة التي تم الحصول عليها من قائمة الحواف.
مع هذه المجموعة من المثلثات ، يمكنك استكشاف المنطقة التي يغطيها كل مثلث. إذا وجدنا المثلث ذو المساحة الأصغر ، عندئذٍ لدينا ثلاث نقاط أو قطط. قد لا يكون متوسط الكثافة الكتلة على السطح ، ولكن سيكون افتراض جيد. إذا استطعنا التخلص من بعض الطرود بالنعناع ، فسوف نضع علامة على المثلثات التي تم اختيارها بالفعل والانتقال إلى الأشكال التالية بحجم متزايد.
وتسمى هذه المناطق أيضًا
الدوائر المقيدة لتثليث ديلوناي. كل دائرة هي أكبر دائرة يمكن وضعها في نقاط المثلث. فيما يلي صورة للدوائر المقيدة لمخطط فورونوي:
يمكنك استخدام المركز الدقيق للدوائر لتحديد مركز المنطقة التي يتم شحن النعناع البري. في الواقع ، فإن نصف قطر الدائرة هو وسيلة أكثر ملاءمة لتحديد أفضل مثلث يمكن طيه بدلاً من منطقة المثلث ، خاصة إذا كانت نقطتي المثلث قريبة جداً من بعضها البعض والثالث بعيد ؛ ثم نحصل على مثلث حاد للغاية ذي مساحة صغيرة ، لكن النقاط التي تحدده هي في الواقع متباعدة جدًا.
تنفيذ مخططات فورونوي
هناك عدة طرق لإنشاء مخططات Voronoi ، ويعتمد اختيار الطريقة المستخدمة على الوقت الذي نتلقى فيه البيانات.
خوارزمية فورتشن
أسرع طريقة تسمى
خوارزمية فورتشن . يتم تشغيله في
O(n log(n)) ويتطلب معرفة جميع النقاط المستخدمة لإنشاء الرسم البياني في الوقت الذي يبدأ فيه الجيل. إذا قمت بإضافة نقاط جديدة لاحقًا ، فسيتعين عليك تجديد الرسم البياني بأكمله. إذا كانت هناك نقاط قليلة ، فإن هذا قد لا يسبب مشاكل ، ولكن إذا كان لديك 100 ألف منهم ، فإن هذا قد يستغرق الكثير من الوقت!
تنفيذ هذه الخوارزمية غير بديهي. عبور مكافئ وحالات خاصة. ومع ذلك ، هذه هي أسرع طريقة. لحسن الحظ ، هناك العديد من تطبيقات خوارزمية المصدر المفتوح التي يمكنك استخدامها ، ولقد قدمت روابط إليها أدناه.
دعونا نرى كيف يعمل.
تتكون الخوارزمية في تحريك خط (عمودي أو أفقي) فوق منطقة بها نقاط. عندما يلتقي بنقطة ما ، يبدأ في سحب القطع المكشوفة منه ، والتي تستمر بخط كنس. هذه هي الرسوم المتحركة لهذه العملية:
تتقاطع القطع المكافئة المتقاطعة أضلاع فورونوي. ولكن لماذا مكافئ؟
لفهم ذلك ، تخيل أن كل نقطة تحتوي على منطاد قابل للنفخ يتضخم حتى تصطدم مع كرة أخرى. يمكنك نقل هذه الفكرة إلى دوائر تمدد على متن طائرة ثنائية الأبعاد. سنجعل كرة أخرى للأمام ونضع في كل نقطة مخروطًا مقلوبًا بزاوية ميل تبلغ 45 درجة ، مع زيادة إلى ما لا نهاية. ثم تخيل خطًا كاسحًا على شكل خط ، أيضًا عند 45 درجة ، والذي ينزلق على طوله حتى يصطدم بالأقماع. بما أن الطائرة والأقماع تقع في نفس الزاوية ، عندما تعبر ، فإنها تشكل قطعًا مكافئًا.
يكبر ، والأقماع عاجلا أو آجلا تتقاطع مع واحد أو أكثر من المخاريط الأخرى. إذا نظرنا إلى تقاطع المخاريط ، أو الدوائر ، فسنحصل على خطوط مستقيمة لحواف فورونوي. في الشكل ، يشير الخط الأحمر إلى تقاطع المخاريط. إذا نمت المخاريط أكثر (عموديًا إلى ما لا نهاية) ، فسيستمر الخط الأحمر في الامتداد.
عندما تنزلق الطائرة ويحدث أول اتصال مع المخروط ، سيكون الخط الناتج كما يلي:
مع مزيد من الحركة للطائرة على طول المخاريط ، سوف نرى كيف تشكل القطع المكافئة:
تواصل الطائرة التحرك في جميع أنحاء مكان الحادث. لكل نقطة يصادفها ، فإنه يفحص النقاط المجاورة على الخط الكاسح الذي يحتوي بالفعل على مكافئ ويبدأ مكافئًا جديدًا في تلك المرحلة. تستمر في النمو وتنمو إلى أن يبدأ هذا المكافئ الجديد في التداخل لا مع المتراكب السابق. ثم يغلق هذا المكافئ السابق. هذه هي النقطة التي تلتقي فيها خطوط فورونوي المكونة من ثلاث نقاط.
كما هو مذكور أعلاه ، من الصعب للغاية فهم هذا ، لذا توجد روابط لتطبيقات مفتوحة المصدر يمكنك استخدامها وتعلمها:
إدراج المثلث التزايدي
هناك طريقة أخرى تتمثل في إدراج نقطة واحدة بشكل تدريجي في كل مرة ، بدءًا من مثلث أساسي يتكون من ثلاث نقاط خارج المنطقة المحتملة لجميع النقاط الأخرى. تعمل هذه الطريقة مع
O(n^2) ولا تتطلب جميع النقاط في وقت التوليد.
عندما تقوم بإدراج نقطة جديدة ، فإنها تحدد المساحة الحالية التي تقع فيها. ثم يتم تقسيم هذه المنطقة ويتم إنشاء مناطق جديدة.
فيما يلي مثال مفتوح المصدر لاستخدامه وتعلمه:
استنتاج
الآن عليك أن تتخيل ما يمكن أن تقدمه مخططات فورونوي للعبة ولعبة الذكاء الاصطناعي. إذا كان لديك رسم بياني منظم للعقد والحواف ، فيمكنك طلب معلومات مهمة حتى يحصل كل شخص على مجموعات الإسعافات الأولية الخاصة به ، ويشار إلى أنه يتقدم عبر أبراج العدو.