كشف التصادم

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

التسلسل الهرمي للأحجام المحيطة (BVH) هو بنية شجرية لمجموعة من الأحجام المحيطة . يتم تحديد التصادم من خلال اجتياز الشجرة بدءًا من الجذر. إذا لم يتقاطع حجم الجذر المحيط مع الكائن المراد دراسته، يمكن إيقاف الاجتياز. أما إذا حدث تقاطع، فيستمر الاجتياز ويفحص الفروع بحثًا عن أي تقاطع. يمكن استبعاد الفروع التي لا يوجد بها تقاطع مع الحجم المحيط من اختبارات التقاطع اللاحقة. وبالتالي، يمكن تحديد عدم تقاطع عدة كائنات في آن واحد. يمكن استخدام BVH مع الكائنات القابلة للتشوه مثل القماش أو الأجسام المرنة، ولكن يجب تعديل التسلسل الهرمي للأحجام مع تغير شكل الكائن. بالنسبة للكائنات القابلة للتشوه، يجب مراعاة التصادمات الذاتية أو التقاطعات الذاتية، ويمكن استخدام BVH لهذا الغرض أيضًا. يُحسب التصادم بين جسمين بحساب تقاطع الحجوم المحيطة بجذر الشجرة، وعند حدوث تصادم، نتعمق في الأشجار الفرعية المتقاطعة. أما التصادمات الدقيقة بين الجسمين أنفسهما، أو أجزائهما (غالباً مثلثات شبكة مثلثية )، فتُحسب فقط بين الأوراق المتقاطعة. ^{[ 7 ]} وينطبق النهج نفسه على التصادمات الثنائية والتصادمات الذاتية.

خلال المرحلة العامة، عندما تتحرك الأجسام في العالم أو تتشوه، يجب تحديث هياكل البيانات المستخدمة لإزالة التصادمات. في الحالات التي تكون فيها التغييرات بين إطارين أو خطوتين زمنيتين صغيرة، ويمكن تقريب الأجسام جيدًا باستخدام مربعات إحاطة محاذية للمحاور ، يمكن أن تكون خوارزمية المسح والتقليم ^{[ 5 ]} نهجًا مناسبًا.

تساهم عدة ملاحظات أساسية في كفاءة التنفيذ: يتقاطع مربعان محيطان إذا وفقط إذا كان هناك تداخل على طول المحاور الثلاثة؛ ويمكن تحديد التداخل، لكل محور على حدة، عن طريق فرز الفواصل الزمنية لجميع المربعات؛ وأخيرًا، تكون التحديثات بين إطارين صغيرة عادةً (مما يجعل خوارزميات الفرز المُحسَّنة للقوائم شبه المرتبة مناسبة لهذا التطبيق). تتتبع الخوارزمية المربعات المتقاطعة حاليًا، ومع تحرك الكائنات، تساعد إعادة فرز الفواصل الزمنية في تتبع الحالة. ^{[ 8 ]}

بمجرد اختيار زوج من الأجسام المادية لمزيد من الدراسة، يجب فحص التصادمات بعناية أكبر. مع ذلك، في العديد من التطبيقات، تُوصف الأجسام الفردية (إذا لم تكن قابلة للتشوه بشكل كبير) بمجموعة من الأشكال الهندسية الأولية الأصغر، وهي في الغالب مثلثات. لذا، توجد مجموعتان من المثلثات،${\displaystyle S={S_{1},S_{2},\dots ,S_{n}}}$و${\displaystyle T={T_{1},T_{2},\dots ,T_{n}}}$(لتبسيط الأمر، تحتوي كل مجموعة على نفس عدد المثلثات.)

الشيء البديهي الذي يجب فعله هو فحص جميع المثلثات${\displaystyle S_{j}}$ضد جميع المثلثات${\displaystyle T_{k}}$للتصادمات، لكن هذا ينطوي على${\displaystyle n^{2}}$تُعدّ المقارنات غير فعّالة للغاية. يُفضّل، إن أمكن، استخدام خوارزمية تقليم لتقليل عدد أزواج المثلثات التي يجب فحصها.

تُعرف عائلة الخوارزميات الأكثر استخدامًا باسم طريقة الحجوم المحيطة الهرمية . كخطوة تمهيدية، لكل كائن (على سبيل المثال،${\displaystyle S}$و${\displaystyle T}$) يحسب تسلسلًا هرميًا للأحجام المحيطة . ثم، في كل خطوة زمنية، عندما يلزم التحقق من التصادمات بين${\displaystyle S}$و${\displaystyle T}$تُستخدم الحجوم المحيطة الهرمية لتقليل عدد أزواج المثلثات قيد الدراسة. ولتبسيط الأمر، سنقدم مثالاً باستخدام الكرات المحيطة، مع العلم أن استخدام الكرات غير مرغوب فيه في كثير من الحالات.

لو${\displaystyle E}$هي مجموعة من المثلثات، ويتم حساب الكرة المحيطة مسبقًا.${\displaystyle B(E)}$هناك العديد من طرق الاختيار${\displaystyle B(E)}$، ${\displaystyle B(E)}$هي كرة تحتوي بالكامل${\displaystyle E}$ويكون صغيراً قدر الإمكان.

قبل الموعد المحدد،${\displaystyle B(S)}$و${\displaystyle B(T)}$يمكن حساب ذلك. من الواضح أنه إذا لم تتقاطع هاتان الكرتان (وهذا سهل الاختبار للغاية)، فلن تتقاطع أي منهما أيضًا.${\displaystyle S}$و${\displaystyle T}$لكن هذا ليس أفضل بكثير من خوارزمية تقليم الأجسام المتعددة .

لو${\displaystyle E={E_{1},E_{2},\dots ,E_{m}}}$إذا كانت مجموعة من المثلثات، فقم بتقسيمها إلى نصفين.${\displaystyle L(E):={E_{1},E_{2},\dots ,E_{m/2}}}$و${\displaystyle R(E):={E_{m/2+1},\dots ,E_{m-1},E_{m}}}$طبّق هذا على${\displaystyle S}$و${\displaystyle T}$وحساب الكرات المحيطة (مسبقًا)${\displaystyle B(L(S)),B(R(S))}$و${\displaystyle B(L(T)),B(R(T))}$والأمل هنا هو أن تكون هذه الكرات المحيطة أصغر بكثير من${\displaystyle B(S)}$و${\displaystyle B(T)}$وإذا، على سبيل المثال،${\displaystyle B(S)}$و${\displaystyle B(L(T))}$إذا لم تتقاطع المثلثات، فلا جدوى من فحص أي مثلث في${\displaystyle S}$ضد أي مثلث في${\displaystyle L(T)}$.

كعملية حسابية مسبقة ، خذ كل جسم مادي (مُمثل بمجموعة من المثلثات) وقم بتفكيكه بشكل متكرر إلى شجرة ثنائية ، حيث كل عقدة${\displaystyle N}$يمثل مجموعة من المثلثات، ويمثل طفلاها${\displaystyle L(N)}$و${\displaystyle R(N)}$. عند كل عقدة في الشجرة، احسب مسبقًا الكرة المحيطة${\displaystyle B(N)}$.

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

يتم الحصول على العديد من متغيرات الخوارزميات عن طريق اختيار شيء آخر غير الكرة لـ${\displaystyle B(T)}$إذا تم اختيار مربعات إحاطة محاذية للمحاور ، فسيتم الحصول على أشجار AABBTrees. أما أشجار مربعات الإحاطة الموجهة فتُسمى أشجار OBBTrees. بعض الأشجار أسهل في التحديث عند تغيير الكائن الأساسي. كما أن بعض الأشجار يمكنها استيعاب أشكال هندسية أولية ذات رتبة أعلى، مثل المنحنيات التكعيبية، بدلاً من المثلثات البسيطة.

بما أن التحقق من تقاطع جسمين قد يكون عملية مكلفة نسبيًا، فإن إحدى الطرق السريعة لتجنب هذه العملية الحسابية هي التحقق من تقاطع الحجوم المحيطة بالجسمين. تُستخدم الحجوم المحيطة عادةً في المرحلة المبكرة (التقليم) من عملية اكتشاف التصادم، بحيث لا تتم مقارنة سوى الأجسام ذات الحجوم المتداخلة بالتفصيل. ^{[ 9 ]} إذا لم تتداخل الحجوم، فلا داعي للتحقق من الأجسام الفعلية. يتطلب حساب التداخل أو التصادم بين الحجوم المحيطة عمليات حسابية إضافية، لذا لكي يُضيف اختبار الحجوم المحيطة قيمة، يجب: أ) أن تكون تكلفة تقاطع الحجوم المحيطة منخفضة، ب) أن تكون الحجوم المحيطة ضيقة بما يكفي لتقليل عدد حالات التقاطع "الإيجابية الكاذبة". في هذه الحالة، تعني حالة التقاطع الإيجابية الكاذبة أن الحجوم المحيطة تتقاطع ولكن الأجسام الفعلية لا تتقاطع. توفر أنواع الحجوم المحيطة المختلفة مزايا وعيوبًا مختلفة لهذه الخصائص.

تُعدّ الصناديق المحيطة المحاذية للمحاور (AABB) والمكعبات شائعة الاستخدام نظرًا لبساطتها وسرعة اختبارات التقاطع. ^{[ 10 ]} أما الحجوم المحيطة مثل الصناديق المحيطة الموجهة (OBB) و K-DOPs والأغلفة المحدبة، فتُقدّم تقريبًا أدقّ للشكل المغلق، ولكن على حساب اختبار تقاطع أكثر تعقيدًا .

يجب أن تخضع الكائنات التي لم تتمكن أساليب التقليم من استبعاد إمكانية حدوث تصادم لها لحساب دقيق للكشف عن التصادم.

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

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

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

على سبيل المثال، لنفترض مثلثين يتحركان مع مرور الوقت${\displaystyle {v_{1}(t),v_{2}(t),v_{3}(t)}}$و${\displaystyle {v_{4}(t),v_{5}(t),v_{6}(t)}}$في أي وقت، يمكن التحقق من تقاطع المثلثين باستخدام المستويات العشرين المذكورة سابقًا. إذا${\displaystyle P(u,v,w)}$هل تمر الطائرة عبر النقاط${\displaystyle u,v,w}$في${\displaystyle \mathbb {R} ^{3}}$ثم هناك عشرون طائرة${\displaystyle P(v_{i}(t),v_{j}(t),v_{k}(t))}$للتتبع. يجب تتبع كل مستوى مقابل ثلاثة رؤوس، مما ينتج عنه ستون قيمة للتتبع. باستخدام دالة البحث عن الجذور على هذه الدوال الستين، نحصل على أوقات التصادم الدقيقة للمثلثين المعطيين والمسارين المعطيين. إذا افترضنا أن مسارات الرؤوس عبارة عن كثيرات حدود خطية في${\displaystyle t}$عندئذٍ، تكون الدوال الستون الأخيرة في الواقع كثيرات حدود من الدرجة الثالثة، وفي هذه الحالة الاستثنائية، يُمكن تحديد وقت التصادم بدقة باستخدام صيغة جذور المعادلة التكعيبية. ويشير بعض المحللين العدديين إلى أن استخدام صيغة جذور المعادلة التكعيبية ليس مستقرًا عدديًا مثل استخدام أداة إيجاد جذور كثيرات الحدود.

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

متجه موضع مركز المثلث هو متوسط ​​متجهات موضع رؤوسه. لذا، إذا كانت إحداثيات رؤوسه ديكارتية${\displaystyle (x_{1},y_{1},z_{1})}$،${\displaystyle (x_{2},y_{2},z_{2})}$و${\displaystyle (x_{3},y_{3},z_{3})}$ثم يكون مركز الثقل${\displaystyle \left({\frac {(x_{1}+x_{2}+x_{3})}{3}},{\frac {(y_{1}+y_{2}+y_{3})}{3}},{\frac {(z_{1}+z_{2}+z_{3})}{3}}\right)}$.

هذه هي الدالة لحساب المسافة بين نقطتين ثلاثيتي الأبعاد باستخدام قطعة مستقيمة.${\displaystyle \mathrm {distance} ={\sqrt {(z_{2}-z_{1})^{2}+(x_{2}-x_{1})^{2}+(y_{2}-y_{1})^{2}}}}$

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

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

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

بعد التصادم غير المرن ، قد تحدث حالات خاصة من الانزلاق والسكون، ويستخدم محرك Open Dynamics Engine ، على سبيل المثال، القيود لمحاكاتها. تمنع القيود القصور الذاتي وبالتالي عدم الاستقرار. كما أن تطبيق حالة السكون باستخدام مخطط المشهد يمنع الانجراف.

بمعنى آخر، تعمل المحاكيات الفيزيائية عادةً بإحدى طريقتين: إما باكتشاف التصادم بعد وقوعه (بعد حدوثه) أو قبل وقوعه (قبل حدوثه). إضافةً إلى التمييز بين الاكتشاف بعد وقوع التصادم والاكتشاف قبل وقوعه ، تُقسّم جميع خوارزميات اكتشاف التصادم الحديثة تقريبًا إلى تسلسل هرمي من الخوارزميات. وغالبًا ما يُستخدم مصطلحا "منفصل" و"متصل" بدلًا من الاكتشاف بعد وقوع التصادم والاكتشاف قبل وقوعه .

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

لفترة طويلة، كانت ألعاب الفيديو تحتوي على عدد محدود جدًا من العناصر التي يجب معالجتها، لذا لم يكن فحص جميع الأزواج مشكلة. في الألعاب ثنائية الأبعاد، في بعض الحالات، كان الجهاز قادرًا على اكتشاف وحدات البكسل المتداخلة بين الصور المتحركة على الشاشة والإبلاغ عنها بكفاءة. ^{[ 13 ]} في حالات أخرى، يكفي تقسيم الشاشة إلى مربعات وربط كل صورة متحركة بالمربعات التي تتداخل معها لتوفير عملية تقليم كافية، وللفحوصات الزوجية، تُستخدم مستطيلات أو دوائر محيطة تُسمى مربعات الاصطدام، وتُعتبر دقيقة بما فيه الكفاية.

استخدمت الألعاب ثلاثية الأبعاد أساليب التقسيم المكاني لـ${\displaystyle n}$- تقليم الجسم، ولفترة طويلة تم استخدام كرة واحدة أو بضع كرات لكل كائن ثلاثي الأبعاد فعلي لإجراء عمليات التحقق الثنائية. عمليات التحقق الدقيقة نادرة جدًا، إلا في الألعاب التي تحاول محاكاة الواقع بدقة. وحتى في هذه الحالة، لا تُستخدم عمليات التحقق الدقيقة بالضرورة في جميع الحالات.

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

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

المحاكاة القوية هي التي تتفاعل مع أي مدخلات بطريقة منطقية. على سبيل المثال، تخيل لعبة فيديو لسباق سيارات عالية السرعة ، فمن المتوقع أن تقطع السيارات مسافة كبيرة على مضمار السباق من خطوة محاكاة إلى أخرى. إذا كان هناك عائق بسيط على المضمار (مثل جدار من الطوب)، فليس من المستبعد أن تقفز السيارة فوقه تمامًا، وهذا أمر غير مرغوب فيه على الإطلاق. في حالات أخرى، لا يتم تطبيق "التصحيح" الذي تتطلبه خوارزميات ما بعد التجربة بشكل صحيح، مما يؤدي إلى ظهور أخطاء قد تحاصر الشخصيات في الجدران أو تسمح لها بالمرور من خلالها والسقوط في فراغ لا نهاية له، حيث قد يكون هناك أو لا يكون هناك هاوية قاتلة لا قعر لها ، والتي يشار إليها أحيانًا باسم "الجحيم الأسود" أو "الجحيم الأزرق" أو "الجحيم الأخضر"، اعتمادًا على اللون السائد. هذه هي سمات نظام كشف التصادم والمحاكاة الفيزيائية الفاشل. لعبة Big Rigs: Over the Road Racing مثال سيئ السمعة على لعبة ذات نظام كشف تصادم فاشل أو ربما مفقود.

منطقة الإصابة

منطقة الاصطدام هي شكل غير مرئي يُستخدم عادةً في ألعاب الفيديو للكشف عن التصادمات في الوقت الفعلي؛ وهي نوع من أنواع الصناديق المحيطة. غالبًا ما تكون مستطيلة (في الألعاب ثنائية الأبعاد) أو متوازي مستطيلات (في الألعاب ثلاثية الأبعاد) متصلة بنقطة على جسم مرئي (مثل نموذج أو صورة متحركة) وتتبعها. كما أن الأشكال الدائرية أو الكروية شائعة أيضًا، على الرغم من أنها لا تزال تُسمى في الغالب "صناديق". من الشائع أن تحتوي الكائنات المتحركة على مناطق اصطدام متصلة بكل جزء متحرك لضمان الدقة أثناء الحركة. ^{[ 14 ]}

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

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