السلام عليكم اخ وسام,

هل هناك طرق اخرى تستخدم فى ال Collision Detection غير طريقة ال
BSP Tree+Ray Tracing ؟!!!!
ولو فى طرق اخرى , هل بيختلف استخدامها باختلاف نوع اللعبة
FPS Shooter, RPG, Strategy, Car Racing Games
يعنى انا مش متخيل كيف يمكن استخدام ال BSP Tree+ Ray Tracing فى لعبة من نوع Car Racing ,
علما بانى كنت قد استخدمت هذه الطريقة فى مشروع RPG وكانت فعالة الى حد كبير جدا , الا انه كلما كبر حجم ال level كلما زاد الوقت اللازم لبناء ال BSP Tree اثناء تحميل اللعبة.



DirectX Developer

التعليق على مشاركة mahmoud yassin el taher في Oct 25, 2006 10:32 :

> هل هناك طرق اخرى تستخدم فى ال
> Collision Detection غير طريقة ال
> BSP Tree+Ray Tracing ؟!!!!

نعم... يوجد عدة طرق. هناك تقسيم OcTree وهو مشابه بالمبدأ للـ BSP Tree. هناك تقسيم الـ Portals وهو شائع جداً في ألعاب الـ FPS. لكن للذكر، الاستخدام العام لهذه الخوارزميات كلها ليس فقط للـ Collision Detection، وإنما لحد الحسابات إلى منطقة محدودة من العالم.. هذه الحسابات تشمل كشف الاصطدام، الرسم، والـ AI في بعض الحالات المحدودة.

> ولو فى طرق اخرى , هل بيختلف استخدامها باختلاف
> نوع اللعبة FPS Shooter, RPG, Strategy, Car Racing Games
> يعنى انا مش متخيل كيف يمكن استخدام ال BSP Tree+
> Ray Tracing فى لعبة من نوع Car Racing ,

بالنسبة لي فالوضع معكوس تماماً☺ ألعاب الـ RTS تمتلك خاصية مهمة تغنيك عن طرق التقسيم هذه كلها، وهي بنية الـ tiles. العالم يكون مصنوع من شبكة منتظمة من الخلايا المربعة أو السداسية.. لذا فإن تحديد محتويات منطقة ما عادة أمر غاية في البساطة وذو زمن تنفيذ ثابت...
أما بالنسبة للعبة سيارات أو FPS فإن الوضع صعب بدون طريقة تقسيم مثل تلك المذكورة أعلاه... لأن العالم مبني بشكل حر وليس مقسماً بطريقة منتظمة...


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

التعليق على مشاركة mahmoud yassin el taher في Oct 25, 2006 20:32 :

> علما بانى
> كنت قد استخدمت هذه الطريقة فى مشروع RPG وكانت فعالة
> الى حد كبير جدا , الا انه كلما كبر حجم ال level كلما
> زاد الوقت اللازم لبناء ال BSP Tree اثناء تحميل اللعبة.

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

شكراً

السلام عليكم,

الاخ وسام, عندما وجهت السؤال اليك لم يكن لشىء الا لانك مشرف قسم البرمجة وليس تقليلا من شان الاخرين, ويمكنك ان شئت ان تغير عنوان الموضوع بكل حرية, وانا اسف حقا, وارجو من الاخوة الاعضاء ان يسامحونى.

>نعم... يوجد عدة طرق. هناك تقسيم OcTree وهو مشابه بالمبدأ للـ BSP Tree.

نعم أعلم هذه الطريقة جيدا, ولا أعتقد انه يوجد اختلاف جوهرى بينها وبين ال BSP Tree حتى ان بعض الكتب يعتبرونهما طريقة واحدة, وهى تكون مفيدة اذا كانت ال Level فيها ارتفاعات, يعنى مثلا مبنى زو عدة طوابق وعلى ما أعتقد ان Quack1 من id soft هى اول من اسنخدم هذه الطريقة, بينما ال BSP Tree الاصلية استخدمت لاول مرة فى Doom1 .

اما طريقة ال Portals فليس لى علما وربما تتكرم وتقدم فكرة بسيطة عنها ولو امكن الحالات التى يفضل استخدامها فيها.

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

ألا تعتقد انها تندرج تحت ال Collisio Detection ?..... (:
وكنا قد استخدمنا طريقة جميلة وبسيطة لهذا الغرض, اختصرت فى زمن الCalculations بصورة كبيرة جدا, واطلقت عليها اسم ال Virtual Level .......(:

وشكرا جزيلا

DirectX Developer

أهلا بالأخ الكريم أحمد عبدالغنى

>هذا طبيعي. لكن ليس من المفروض أن تنفذ حسابات الـ bsp وقت تحميل المرحلة. وإنما يمكن تنفيذها بشكل مستقل وتحفظ الحسابات جانباً ضمن ملف يتم قراءته أثناء تحميل المرحلة. المشكلة أن البنية البرمجية تحوي الكثير من المؤشرات، وهذا يصعب عملية الحفظ.. لكنه ليس مستحيلاً

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

>المشكلة أن البنية البرمجية تحوي الكثير من المؤشرات، وهذا يصعب عملية الحفظ.. لكنه ليس مستحيلاً
لا أعتقد ان هذه مشكلة..........(: (:

لاكن اثناء ال Run Time وعند استخدام ال Tree فى تحديد الجزء الذى يجب ان يرسم مع ال Frustum تستغرق ايضا وقتا كبيرا لان ال Tree فى هذه الحالة تكون على مستوى عالى من التشعب.

ولاكن كنت قد خطر على بالى فكرة للتغلب على هذه المشكلة من وجهة نظر عامة,
وهى تقسيم ال Level الى عدد 3 أو 4 أجزاء لاكن لا يجب ان يزيد العدد كثيرا.
لو كنت قد شاهدت لعبة Prince Of Parsia لوجدت أن ال Level تكون على مستوى عالى من التفاصيل كما أنها طويلة نسبيا, هذا بخلاف ال Shaders , Special Effects, وغيرها من ال expensive viisual effects, لاكن لو تلاحظ أيضا ان كل مرحلة يتخللها عدد من مقاطع الفيديو أو Custom set of camera arrangment حيث ينقطع التفاعل مع اوامر اللاعب وتستمر لعدة ثوانى, ولكننى أعتقد -والله أعلم- انه فى هذه الاثناء يتم تحميل الجزء من المرحلة الذى سوف يكون مسرح الاحداث القادمة , ويكون هذا على ما أعتقد باستخدام Triggers أو شى مماثل ويكون التحميل فى ال Background أثناء عرض الفيديو أو ال Custom set of camera arrangment, والله أعلم.

فما رأيك فى هذه الطريقة؟!


DirectX Developer

التعليق على مشاركة mahmoud yassin el taher في Oct 25, 2006 14:52 :

> اما طريقة ال Portals فليس لى علما وربما
> تتكرم وتقدم فكرة بسيطة عنها ولو امكن الحالات التى يفضل استخدامها فيها.

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


> ألا تعتقد انها تندرج تحت ال Collisio Detection ?..... (:

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

> وكنا قد استخدمنا
> طريقة جميلة وبسيطة لهذا الغرض, اختصرت فى زمن الCalculations
> بصورة كبيرة جدا, واطلقت عليها اسم ال Virtual Level
> .......(:

يا حبذا لو تشرحها لنا...

التعليق على مشاركة mahmoud yassin el taher في Oct 26, 2006 01:25 :

> لاكن اثناء ال Run Time وعند
> استخدام ال Tree فى تحديد الجزء الذى يجب ان يرسم مع
> ال Frustum تستغرق ايضا وقتا كبيرا لان ال Tree فى هذه
> الحالة تكون على مستوى عالى من التشعب.

المفروض انك توقف عند حد معين وانت بتقسم المرحلة. يعني كفاية يصير معاك في وحدة البي إس بي حوالي 100 مثلث. مفيش داعي تنزل أكتر من كده. حرام عليك بقى أصلو عشان كمبيوتراتنا غلبانة قوي☺

السلام عليكم,
ألاخ وسام ساعرض فكرة ال Virtual Level ولكن أولا يجب ان أذكر الحاجة التى دفعتنى لاستخدام هذه الفكرة.
التصادم مع البيئة المحيطة أو (Collision Detection with the World), وهذا غير التصادم بين الشخصيات
استخدمنا الاسلوب المبنى على اساس ان ال Level عبارة عن Single Mesh , والاختبار يتم على مستوى ال Polygons التى
تكون هذه ال Mesh




ولكى تختبر مثلا ان شخصية ما تتصادم مع عائق
أمامها (حائط او صخرة مثلا), تقوم بارسال شعاع من مكان الشخصية الى المكان المفروض ان ينتقل اليه بعد الحركة, فلنقل
مسافة خطوة للامام, فإذا تقاطع هذا الشعاع مع أى Polygon من الـ Mesh التى تمثل ال Level فإنه فى هذه الحالة يكون قد حصل
التصادم , يعنى ممكن نعتبر ان ال Algorithm فى صورته المبسطة كالاتى :

========================================
// Assum that P1 is the current Location of the character
// P2 is the Point away from P1 by the required step length

Then to check for collision do
Cast a ray from P1 to P2
If the ray intersects any of the Level's Mesh Polygons
       Compare the Distance of the intersection point to the ray length     
If (Pintersection – P1 < P2 –P1 )      //this means there is one or more poly between P1,P2  	         
               Then there is a collision
        Else 
              No collision
=========================================

والحمد لله هنالك دالة تقوم بمهمة حساب التقاطع بين الشعاع من نقطة معينة فى الفضاء الى نقطة أخرى وبين Mesh Object ممثل
بواسطة D3DXBaseMesh,
والدالة هى D3DXIntersect()
وهذه الدالة تختبر ما اذا كان قد حدث تقاطع أم لا, وإذا حدث تقوم تقوم بحساب بعد نقطة التقاطع
من المكان الذى يمثل بداية الشعاع , (حاجة فظيعة طبعا).
الى الان انت ممكن ان تتصور ان مشكلة التصادم مع البيئة المحيطة قد انتهت,
لكن للاسف هذه الطريقة تكون فعالة فقط مع ال Levels صغيرة الحجم, فيمكنك ان تتصور مثلا Level حجمها 30,000 Polygon
اذا لكى تختبر التصادم معها عليك ان تستعمل الدالة (D3DXIntersect()) مع ال 30,000 Polygon وهذه بحد زاتها كارثة بمعنى الكلمة,
نعم كارثة لان الدالة D3DXIntersect() ليست بسيطة بل تحتوى على حسابات مكلفة الى حد ما.
اذا لا يمكن استخدام هذا الخوارزم فى صورته هذه, وكان على ايجاد طريقة ما لتقليل عدد ال polygons الذين يتم اختبارهم كل فرام , وهنا جاء دور ال Virtual Level.

وال Virtual Level ببساطه يمكن ان تعتبرها نسخة من ال Level الاصلية ولكن بعدد قليل جدا من ال polygons وهو الازم فقط لاجراء
اختبارت التصادم, دون ان يؤثر على الاداء العام للهدف المنشود.






وهذا النموذج المفلتر من ال Level تقوم بتصميمه كما تصمم ال Level نفسها فى أى 3D Package حيث تقوم بعملية تفصيل ال Virtual Level على ال Level الاصلية مع تصديرها للمحرك فى ملف منفصل, وتقوم اثناء تحميل المرحلة بتحميل ال Virtual فى Mesh Object مستقل بها
















مع ملاحظة ان جميع التحويلات التى تجريها على ال Original Mesh Object تجريها أيضا على ال Virtual,
وعند اجراء اختبار التصادم, نقوم بالاختبار بالنسبة لل Virtual Level وليس لل Original ,
الا اننا اثناء عملية ال Rendering , نرسم فقط ال Original Level Mesh, والتى غالبا ما تكون فى الـTree Structure الخاص بها.
أى ان ال Virtual Level تحمل ولا ترسم, وكل استخدامها هو لل Collision Detection.



بقى ان أقول انه عند تفصيل ال Virtual Level على الاصلية يجب ان تضبط الحيز العام الذه تشغله ليكون تقريبا نفس الحيز الذى تشغله الاصلية, والا فعند اجراء أى من ال Transformation على الاثنان معا قد يحدث اختلاف.

وارجو انى اكون عرفت ان اوصل الفكرة بشكلها البسيط

وأهلا باى استفسار او تعليق


---------------------------------------------
DirectX Developer

فكرة فعالة! بشكل عام هي الطريقة اليدوية لأسلوب كشف التصادم مع الـ Convex Hull.
هناك مقال في جاماسوترا يتحدث عن الموضوع:

http://www.gamasutra.com/features/20000330/bobic_pfv.htm

بشكل أمثل، يمكن جعل برنامج الـ 3D يقوم بتوليد الـ convex hull بنفسه ومن ثم معايرة النتائج بيد بشرية. مما يوفر وقت ويعطي النتائج المتوقعة...

بمناسبة الحديث عن البورتالز.. اللينك ده فيه شرح مفصل للعملية كليها:

http://www.flipcode.com/articles/portals_issue01.shtml

روح يا عم مين قدك...☺