طرق الكشف عن الاصطدام على نطاق واسع؟
https://stackoverflow.com/questions/1616448
-
06-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russianسؤال
أنا أقوم ببناء محرك فيزيائي ثنائي الأبعاد وأريد إضافة اكتشاف تصادم واسع الطور، على الرغم من أنني أعرف فقط نوعين أو ثلاثة أنواع:
- تحقق من كل شيء مقابل كل شيء آخر (تعقيد O(n^2))
- الاجتياح والتقليم (الفرز والاجتياح)
- شيء عن قسم الفضاء الثنائي (لست متأكدًا من كيفية القيام بذلك)
ولكن بالتأكيد هناك المزيد من الخيارات أليس كذلك؟ما هم؟وهل يمكن تقديم وصف أساسي لكل منها أو روابط للأوصاف؟
رأيت هذا ولكني أطلب قائمة بالخوارزميات المتاحة، وليست الأفضل بالنسبة لاحتياجاتي.
في هذه الحالة، "اكتشاف الاصطدام واسع الطور" هو طريقة تستخدمها المحركات الفيزيائية لتحديد الأجسام الموجودة في محاكاتها والتي تكون قريبة بما يكفي لتبرير المزيد من التحقيق وربما حل الاصطدام.
المحلول
تعتمد أفضل طريقة على الاستخدام المحدد ، ولكن خلاصة القول هي أنك تريد تقسيم مساحة العالم الخاصة بك بحيث (أ) كل جسم في قسم فرعي واحد تمامًا ، (ب) كل قسم فرعي كبير بما يكفي لا يمكن أن تصطدم إلا مع الأجسام في نفس التقسيم الفرعي أو التقسيم الفرعي المجاور ، و (ج) عدد الأجسام في قسم فرعي معين صغير قدر الإمكان.
تعتمد كيف تفعل ذلك على عدد الأجسام التي لديك ، وكيف تتحرك ، وما هي متطلبات أدائك ، وكم الوقت الذي تريد قضاءه على محركك. إذا كنت تتحدث عن الأجسام التي تتحرك في مساحة مفتوحة إلى حد كبير ، فإن أبسط تقنية هي تقسيم العالم إلى شبكة حيث تكون كل خلية أكبر من كائنك الأكبر ، وتتبع قائمة الكائنات في كل خلية. إذا كنت تقوم ببناء شيء على نطاق لعبة الممرات الكلاسيكية ، فقد يكون هذا الحل يكفي.
إذا كنت تتعامل مع الأجسام تتحرك في عالم مفتوح أكبر ، فستصبح شبكة بسيطة ساحقة بسرعة كبيرة ، وربما تريد نوعًا من البنية القائمة على الأشجار مثل Quadtrees ، كما يقترح Arriu.
إذا كنت تتحدث عن تحريك الأجسام داخل المساحات المحددة بدلاً من المساحات المفتوحة ، فقد تفكر في شجرة BSP; ؛ أقسام الأشجار في العالم إلى "مساحة يمكنك السير فيها" و "الجدران" ، وتحدد قصتها في الشجرة ما إذا كان في وضع قانوني. اعتمادًا على هندسة العالم ، يمكنك أيضًا استخدام BSP لاكتشاف المرحلة العريضة للتصادم بين الهيئات في العالم.
خيار آخر للهيئات التي تتحرك في مساحة محدودة سيكون محرك بوابة ؛ إذا كان بإمكان عالمك أن يتكون من مناطق مضلعة محدبة حيث يكون كل جانب من جانب المضلع إما جدارًا صلبًا أو "بوابة" إلى مساحة مقعرة أخرى ، فيمكنك بسهولة تحديد ما إذا كان الجسم داخل منطقة مع اختبار نقطة في البوليجون و تبسيط اكتشاف التصادم من خلال النظر فقط إلى الهيئات في نفس المنطقة أو المناطق المتصلة.
نصائح أخرى
بديل عن Quadtrees أو BSPTrees كروي (circletrees في 2D ، سيكون التنفيذ أكثر أو أقل كما هو). الميزة التي تتمتع بها كرات كروية هي أنها تتعامل مع الكثير من الكائنات الديناميكية بشكل جيد للغاية. إذا كنت تتحرك كائنات باستمرار ، فإن BSPTrees و Quadtrees أبطأ بكثير في تحديثاتها من شجرة الكرة/الدائرة.
إذا كان لديك مزيج جيد من الثابت و الكائنات الديناميكية ، وهو الحل الجيد بشكل معقول هو استخدام Quadtree/BSPTREE للإحصائيات وشجرة الكرة/cicle للكائنات الديناميكية. فقط تذكر أنه بالنسبة لأي كائن معين ، ستحتاج إلى التحقق من ذلك على حد سواء الأشجار.
انصح Quadtree التقسيم. الأمر بسيط للغاية ويعمل بشكل جيد. هنا فلاش العرض التوضيحي من الكشف عن تصادم القوة الغاشمة مقابل الكشف عن الاصطدام Quadtree. (يمكنك إخباره بإظهار بنية Quadtree.) هل لاحظت كيف أن اكتشاف تصادم Quadtree هو 3 ٪ فقط من القوة الغاشمة في هذا العرض التوضيحي؟
أيضًا ، إذا كنت جادًا في محركك ، فإنني أوصي بشدة بالتقاطها الكشف عن التصادم في الوقت الحقيقي. إنه ليس مكلفًا وهو كتاب رائع حقًا يغطي كل ما تريد معرفته. (بما في ذلك اكتشاف التصادم القائم على وحدة معالجة الرسومات.)
تعتمد جميع خوارزميات التسارع على استخدام اختبار غير مكلف لاستبعاد الكائنات (أو مجموعات من الكائنات) وبالتالي تقليص عدد الاختبارات باهظة الثمن التي يتعين عليك القيام بها. أرى الخوارزميات في الفئات ، كل منها لديه العديد من الاختلافات.
التقسيم المكاني. نحت المساحة واستبعاد المرشحين الذين هم في مناطق مختلفة. على سبيل المثال ، BSP ، الشبكات ، octrees ، إلخ.
تقسيم الكائن. على غرار #1 ، لكن التجميع يركز على الكائنات نفسها أكثر من المساحة التي يقيمون فيها. على سبيل المثال ، تسلسلات هرمية للحجم.
أساليب الفرز والكتابة. ضع الأشياء بالترتيب مكانيًا واستبعاد التصادم بين تلك غير المجاورة.
1 و 2 غالبًا ما يكونان هرميين ، ويتكرران في كل قسم حسب الحاجة. مع 3 ، يمكنك التكرار اختياريا على طول أبعاد مختلفة.
تعتمد المقايضات كثيرًا على هندسة المشهد. هل تتجمع الكائنات أم أنها موزعة بالتساوي أو قليلة؟ هل هم كل شيء بنفس الحجم أم أن هناك اختلافات كبيرة في الحجم؟ هل المشهد ديناميكي؟ هل يمكنك تحمل الكثير من وقت المعالجة المسبقة؟
الاختبارات "غير المكلفة" هي في الواقع على طول مجموعة من الرمي حقًا إلى نوع من التوسعة. إن اختيار أفضل خوارزمية يعني تقليل نسبة تكلفة الاختبار غير المكلف إلى تخفيض عدد الاختبارات باهظة الثمن. إلى جانب المخاوف الخوارزمية ، تدخل في ضبط ، مثل القلق بشأن موقع ذاكرة التخزين المؤقت.
البديل هو شبكات عادية ، على سبيل المثال 20x20 أو 100x100 (يعتمد على عالمك وحجم ذاكرتك). التنفيذ أبسط من بنية عودية مثل أشجار الربع/BSP (أو أشجار المجال لهذه المسألة).
الكائنات عبور حدود الخلية هي أبسط قليلاً في هذه الحالة ، ولا تتدهور بقدر التنفيذ الساذج لـ BSP/Quad/Oct-Tree.
باستخدام ذلك (أو غيرها من التقنيات) ، يجب أن تكون قادرًا على إعدام العديد من الأزواج والحصول على مجموعة من الاصطدامات المحتملة التي تحتاج إلى مزيد من التحقيق.
لقد توصلت للتو إلى حل لا يعتمد على حجم الشبكة وربما يكون O (nlogn) (وهذا هو الأمثل عندما لا توجد تصادمات) على الرغم من الأسوأ في O (n (nنlogn) (عندما يصطدم كل شيء).
لقد قمت أيضًا بتطبيقه واختبرته ، وهنا رابط إلى مصدر. لكنني لم أقارنها بحل القوة الغاشمة.
وصف لكيفية عمله: (أنا أبحث عن تصادمات مستطيلات)
على محور X ، أحفر المستطيلات وفقًا للحافة اليمنى (O (Nlogn))
لكل مستقيم في القائمة المصنفة ، أخذت الحافة اليسرى وأجر بحثًا ثنائيًا حتى أجد الحافة اليمنى على يسار الحافة اليسرى وأدخل هذه المستطيلات بين هذه المؤشرات في مجموعة ممكن البحث الثنائي ، n إدراج int المجموعة عند o (log n) لكل إدراج)
على المحور y أفعل الشيء نفسه
في كل مجموعة من المجموعات ، لدي الآن تصادمات محتملة على x (في مجموعة واحدة) وعلى y (int الآخر) ، أتقاطع مع هذه المجموعات والآن لدي تصادمات على كل من المحور x ومحور y (وهذا يعني أنني آخذ العناصر الشائعة) (O (n))
آسف على الوصف السيئ ، أتمنى أن تفهم بشكل أفضل من المصدر ، مثالًا موضحًا هنا: صورة
إذا كانت المساحة التي تتحرك فيها كائناتك محدودة ، فيمكنك استخدام شبكة لتقسيم الكائنات الخاصة بك. ضع كل كائن في كل خلية شبكة يغطيها الكائن (بالكامل أو جزئيًا). للتحقق مما إذا كان الكائن يصطدم مع أي كائن آخر ، حدد كائن خلايا الشبكة A ، ثم احصل على قائمة الكائنات الفريدة في تلك الخلايا ، وأخيراً اختبار كائن A مقابل كل كائن فريد. يعمل هذا النهج بشكل أفضل إذا كانت معظم الكائنات موجودة عادة في خلية شبكة واحدة.
إذا لم تكن مساحتك محدودة ، فستحتاج إلى تنفيذ نوع من الشبكة الديناميكية التي يمكن أن تنمو عند الطلب في كل من الاتجاهات الأربعة (في 2D).
تتمثل ميزة هذا النهج على خوارزف أكثر تكيفًا (أي BSP ، Quadtree ، circletree) في أنه يمكن الوصول إلى الخلايا في الوقت (1) الوقت (أي وقت ثابت) بدلاً من الوقت (log n) الوقت (أي الوقت اللوغاريتمي). ومع ذلك ، فإن هذه الخوارزميات الأخيرة قادرة على التكيف مع التباين الكبير في كثافة الكائنات. يعمل نهج الشبكة بشكل أفضل عندما تكون كثافة الكائن ثابتة إلى حد ما عبر الفضاء.
أود أن أوصي بالإشارة التمهيدية إلى فيزياء اللعبة من إيان ميلينجتون ، تطوير محرك فيزياء اللعبة. لديها قسم رائع حول اكتشاف تصادم الطور الواسع مع رمز العينة.
لقد استخدمت شجرة رباعية في مشروع أكبر، وهو أمر جيد لكائنات اللعبة التي لا تتحرك كثيرًا (عمليات إزالة وإعادة إدراج أقل).وينطبق نفس المبدأ على الثمانيات.
الفكرة الأساسية هي إنشاء بنية شجرة متكررة، والتي تخزن 4 (للرباعي)، أو 8 (oct) كائنات فرعية من نفس نوع جذر الشجرة.تمثل كل عقدة في الشجرة قسمًا من الفضاء الديكارتي، على سبيل المثال، -100 -> +100 على كل محور قابل للتطبيق.يمثل كل طفل نفس المساحة، ولكن مقسمة إلى النصف (الطفل المباشر للمثال سيمثل، على سبيل المثال، -100->0 على المحور X، و-100->0 على المحور Y).
تخيل مربعًا، أو مستوى، بمجموعة معينة من الأبعاد.الآن ارسم خطًا عبر المركز على كل محور، وقسم هذا المستوى إلى 4 مستويات أصغر.الآن خذ واحدة منها وقم بذلك مرارًا وتكرارًا، حتى تصل إلى نقطة يكون فيها حجم مقطع المستوى تقريبًا بحجم كائن اللعبة.الآن لديك شجرتك.فقط الأجسام التي تشغل نفس المستوى هي التي يمكن أن تتصادم.عندما تحدد الكائنات يستطيع تتصادم، يمكنك إنشاء أزواج من الاصطدامات المحتملة منها.في هذه المرحلة، اكتمل الطور العريض، ويمكنك الانتقال إلى اكتشاف تصادم الطور الضيق، وهو المكان الذي توجد فيه حساباتك الأكثر دقة والأكثر تكلفة.
الغرض من Broadphase هو استخدام حسابات غير مكلفة لتوليد تصادمات محتملة وإزالة الاتصالات التي تحدث لا تستطيع مما يؤدي إلى تقليل العمل الذي يتعين على خوارزمية المرحلة الضيقة الخاصة بك القيام به، مما يجعل خوارزمية اكتشاف الاصطدام بأكملها أكثر كفاءة.
لذا، قبل المضي قدمًا ومحاولة تنفيذ مثل هذه الخوارزمية، مثلك:
كم عدد الأشياء الموجودة في لعبتي؟إذا كان هناك الكثير، فربما أحتاج إلى مرحلة واسعة.إذا لم يكن الأمر كذلك، فإن الطور الضيق سيكون كافيا.أيضًا، هل أتعامل مع العديد من الأجسام المتحركة؟
يتم إبطاء هياكل الأشجار عمومًا عن طريق تحريك الأجسام، حيث يمكنها تغيير موضعها في الشجرة بمرور الوقت، وذلك ببساطة عن طريق الحركة.يتطلب ذلك إزالة الكائنات وإعادة إدراجها في كل إطار (محتملًا)، وهو أقل من المثالي.
إذا كان الأمر كذلك، فستكون أفضل حالًا باستخدام Sweep and Prune، الذي يحافظ على الحد الأدنى/الحد الأقصى لأكوام نطاقات الأشكال في عالمك.لا يلزم إعادة إدراج الكائنات، ولكن يجب اللجوء إلى الأكوام في كل إطار، ويعتقد أن هذا أسرع بشكل عام من عرض الشجرة، مع اجتياز عمليات الإزالة وإعادة الإدراج.
اعتمادًا على خبرتك في البرمجة، قد يكون تشفير أحدهما أكثر تعقيدًا من الآخر.لقد وجدت شخصيًا أن الأشجار أكثر سهولة في البرمجة، ولكنها أقل كفاءة وأكثر عرضة للخطأ، لأنها تثير مشكلات أخرى، مثل ما يجب فعله إذا كان لديك كائن يقع مباشرة فوق المحور أو المركز من العقدة الجذرية.يمكن حل هذه المشكلة باستخدام الأشجار السائبة، التي لها بعض التداخل المكاني، بحيث يتم دائمًا إعطاء الأولوية لعقدة فرعية واحدة على العقد الأخرى عند حدوث مثل هذه الحالة.
