الشبكة العربية لمطوري الألعاب

موهوب  16mofed84 مشاركة 1

في الألعاب كيف تحدد اللعبة مكان اطلاق الرصاص ؟اذا استخمنا محرك. الفيزياء و اعتبرنا الرصاصة كتله لن ينجح لان سرعتها كبيره و حجمها صغير و سرعه الupdate حوالي ١٦ ميلي ثانيهو الطريقه الرياضي بطيئة الطريقتين بطيئين جداً  حتى على مدى طلقه وحده 
طبعا أنا أتكلم عن عدد ١٠٠ الف مثلث

مبتدئ  فراس أسعد مشاركة 2

الطريقة الرياضية ليست بطيئة و هي ما تستعمله معظم الألعاب (تسمى أحيانا Hitscan). ببساطة استعمل تتبع أو بعث الأشعة raytracing/raycasting و قم بحل معادلة قطع الشعاع لصندوق التصادم hit box للاعداء (في حالة قطع الشعاع لجسم كروي مثلا تحصل على معادلة من الدرجة الثانية تُحل باستعمال المميز). يمكن استعمال الطريقة الفيزيائة للاجسام الكبيرة و الابطأ مثل الصواريخ. تتبع الاشعة قد يكون بطيء اذا كان لديك العديد من الاشعة التي تنعكس عن الاجسام عدة مرات أو اذا كانت الاجسام معقدة، و لكن معظم الالعاب لا تحاول ان تكون واقعية 100% لأن التبسيط اسرع و يعطي نتائج جيدة. استعمال خوارزمية تقسيم فراغي spatial partitioning جيدة يقلل من عدد الاجسام التي تتعامل معها هذه الطريقة.

بعض الوصلات التي قد تساعدك:
http://en.wikipedia.org/wiki/Hitscan
http://gamedev.stackexchange.com/questions/13650/how-are-bullets-simulated-in-video-games
http://wiki.teamfortress.com/wiki/Mechanics#Hit_detection

مبتدئ  Ali Amin مشاركة 3

مثل ما قال الاخ فراس

الطريقة بطيئة جدا لو كنت ستقوم بالتحقق من تصادم الray مع كل الpolygons

الطريقة الصحيحة هو ان تقوم بعمل box او sphere حول مجسمات الاعداء و تقوم بالتحقق من التصادم ما بين الray و هذا الbox او الsphere و لو تحقق التصادم تقوم بعمل تحقق من التصادم ما بين الray و كل الpolygons في هذا المجسم لكي تعطي نتائج اكثر تفصيلا

خبير مدير وسام البهنسي مشاركة 4

بتاريخ 01/ربيع الأول/1433 05:56 م، قطب Ali Amin حاجبيه بشدة وهو يقول:

مثل ما قال الاخ فراس

الطريقة بطيئة جدا لو كنت ستقوم بالتحقق من تصادم الray مع كل الpolygons

الطريقة الصحيحة هو ان تقوم بعمل box او sphere حول مجسمات الاعداء و تقوم بالتحقق من التصادم ما بين الray و هذا الbox او الsphere و لو تحقق التصادم تقوم بعمل تحقق من التصادم ما بين الray و كل الpolygons في هذا المجسم لكي تعطي نتائج اكثر تفصيلا

تماماً، كما أنك قد تجد أن الكشف ضد كافة المضلعات في المجسم أيضاً مكلف، خصوصاً مع كثرة الكشوفات (مثلاً في حالة إطلاق رصاص بندقية أو مدفع رشاش أو أسلحة لعدد كبير من الجنود).
 
لتسريع الكشف عن المضلعات المتقاطعة يمكن استخدام خوارزميات تسريع تعتمد على تحليل المجسم في وقت آنف واستخراج بعض المعلومات التي تساعد في تقليل عدد المضلعات المطلوب كشف التقاطع معها. من هذه الخوارزميات خوارزمية k-DOP Tree وخوارزميات التقسيم الفراغي كالـ BSP والـ Octree والـ kD Tree.
 
المرجع الأفضل لهذه الأمور هو كتاب Real-time Collision Detection للكاتب كريستوفر إريكسون، وهو أحد مبرمجي شركة سوني العتيدين.
 

وسام البهنسي
مبرمج في إنفيديا وإنفريمز

موهوب  16mofed84 مشاركة 5

انا قمت بالاتي :
في كل موديل تحقق من Ray intersect -sphere  طبعا الكره جاهزه من اول
في كل mesh تحقق من Ray intersect -sphere 
و بعديها على كل مثلث Sphere ..
و الاخر Ray - Triangle
و الكود هو :
http://dzindzinovic.blogspot.com/2010/05/xna-ray-intersect-triangle.html
 
http://dzindzinovic.blogspot.com/2010/05/xna-pick-model-triangle-with-ray.html

في فكره ..لتقليل الحسابات
اذا كنا ننقل كل مثلث بضربه بمصفوفه transform..
فلماذا لا نضرب الشعاع لمره واحده بعكس المصفوفه و لكن هل ()matrix.invert هو المطلوب ؟

خبير مدير وسام البهنسي مشاركة 6

الاختبارين الأولين ضروريين، لكن الثالث: مثلث ضد كرة... لماذا؟
 
الكود المذكور في تلك المدونة يقوم فقط باختبار المثلثات في المجسم ولا يقوم باختبار الشعاع ضد الكرة. يجب أن تقوم بذلك بنفسك قبل نداء الإجراء PickedTriangle.


في 02/ربيع الأول/1433 05:03 ص، قال 16mofed84 بهدوء وتؤدة:

في فكره ..لتقليل الحسابات
اذا كنا ننقل كل مثلث بضربه بمصفوفه transform..
فلماذا لا نضرب الشعاع لمره واحده بعكس المصفوفه و لكن هل ()matrix.invert هو المطلوب ؟

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

WorldToModel = ModelToWorld.Inverse();

وسام البهنسي
مبرمج في إنفيديا وإنفريمز

موهوب  16mofed84 مشاركة 7

الكود يعمل ١٠٠٪ شغال لكنه يأخذ ٥ ميلي ثانيه و الحد الأقصى هو ١/٦٠ = ١٦.٦ ميلي ثانيه لا اعلم ما المشكله بالتحديد يقال ان CPU تستطيع حل ملايين معادلات في اجزاء من الثانيه الا انها خيبت ظني نوع الجهاز intel core 2 quad لا اعلم ما المشكله ؟!؟!

مبتدئ  Ali Amin مشاركة 8

ربما لو عرضت جزء من الكود يمكننا مساعدتك و مزيد من المعلومات مثل عدد المثلثات في الاعداء و عدد الاعداء  الخ...

هناك تكنيك اخر يستعمل و هو عمل مجسم اخر من الاعداء يكون very low boly لا يتم رسمه على الاطلاق و إنما يتم فقط حسابات التصادم على اساسه

لو كنت تستعمل xna و تستعمل دالة للكشف عن التصادم مثل في هذا الكود : 

http://dzindzinovic.blogspot.com/2010/05/xna-ray-intersect-triangle.html

 و تحول لهذه الدالة paramater من نوع vector3 فوضع كلمة ref سيسرع الأمر كثيرا لأن النوع vector3 من نوع struct و ليس class و هذا معناه انه في كل مرة تقوم بنداء الدالة يتم نسخ هذا المتغير مرة اخرى , فلو كان لديك 5 الاف مثلث فسيتم نسخ المتغير 5 الاف مرة و تدميره في نهاية الدالة

موهوب  16mofed84 مشاركة 9

اعتذر عن التأخر ..
الكود بعد استخدام ref و الinverse matrix لل شعاع الى ان مشكله جديده ظهرت في matrix الشعاع لا يظهر نتيجته الا ضمن مكان محدود ...و اعتقد ان مصفوفه التحويل هي matrix.identity لان العكس ايضا هو matrix.identity
ذكرت كلمه الاعداء في النص .. ايضا انا استخدمه لايجاد مكان اصطدام مع الحائط ..
مشكورين جميعا
        public bool RayCastTestFast(Vector3 pos, Vector3 target, float dist, out Vector3 v, out Vector3 normal, bool fl)
        {
            v = Vector3.Zero;
            float min = 9999999f;
            Triangle Tmin = null;
            Ray r = new Ray(pos, -Vector3.Normalize(target - pos));

            Matrix TriangleTransfrom = new Matrix();
            if (fl) r.Direction = -r.Direction;
            BoundingSphere RSp = new BoundingSphere(pos, 4f);
            foreach (CCMEntity ent in CCMEntities)
            {
                if (!ent.Rigid.BoundingBox.RayIntersect(eHelper.ToJVector(pos), eHelper.ToJVector(r.Direction))) continue;
                Matrix trans = eHelper.ToXnaMatrix(ent.Rigid.Orientation);
                trans.Translation = eHelper.ToXnaVector(ent.Rigid.Position);
                Ray rr = new Ray(Vector3.Transform(r.Position, Matrix.Invert(trans)), 
                                 Vector3.Transform(r.Direction, Matrix.Invert(trans)));
                for (int meshCount = 0; meshCount < ent.Meshes.Length; meshCount++)
                {
                    float? rtest = r.Intersects(ent.Meshes[meshCount].Sphere);
                    if (rtest.HasValue)
                    {
                        for (int triCount = 0; triCount < ent.Meshes[meshCount].Triangles.Length; triCount++)
                        {
                            if(ent.Meshes[meshCount].Triangles[triCount].Sphere.Intersects(rr).HasValue)
                            {
                                Vector3 intersect = Vector3.Zero;
                                if (eHelper.RayToTriangle(ref r, out intersect,
                                    ref ent.Meshes[meshCount].Triangles[triCount]))
                                {
                                    if (Vector3.Distance(intersect, rr.Position) < min)
                                    {
                                        TriangleTransfrom = trans;
                                        Tmin = ent.Meshes[meshCount].Triangles[triCount];
                                        min = Vector3.Distance(intersect, rr.Position);
                                        v = intersect;
                                    }
                                }
                            }
                        }
                    }
                }

            }
            if (Tmin != null)
            {
                Triangle ttt = new Triangle();
                ttt.P1 = Tmin.P1;
                ttt.P2 = Tmin.P2;
                ttt.P3 = Tmin.P3;
                ttt.Transform(TriangleTransfrom);
                normal = (ttt.P1.Normal + ttt.P2.Normal + ttt.P3.Normal) / 3f;
                return true;
            }
            else
            {
                v = Vector3.Zero;
                normal = Vector3.Zero;
                return false;
            }
        }
////////////////////////////////////////////////////////////////// ehelper class
    public static bool RayToTriangle(ref Ray cursorRay, out Vector3 intersection,ref GameA1.Triangle t)
    {
        System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch();
        sw.Start();

        float pickDist = 0.0f; // distance from ray origin to intersection
        float pickU = 0.0f; // barycentric coordinate of intersection
        float pickV = 0.0f; // barycentric coordinate of intersection

        if (RayIntersectTriangle(ref cursorRay.Position,
            ref cursorRay.Direction,ref t.P3.Position,
            ref t.P2.Position,ref t.P1.Position, ref pickDist, 
            ref pickU, ref pickV))
        {
            if (pickDist > 0.0f)
            {
                intersection = pickU * t.P2.Position + 
                               pickV * t.P1.Position + 
                               (1 - pickU - pickV) * t.P3.Position;
                return true;
            }
        }

        intersection = Vector3.Zero;
        return false;
    }


    private static bool RayIntersectTriangle(ref Vector3 rayPosition,
                                            ref Vector3 rayDirection,
                                            ref Vector3 tri0,
                                            ref Vector3 tri1,
                                            ref Vector3 tri2, 
                                            ref float pickDistance,
                                            ref float barycentricU, 
                                            ref float barycentricV)
    {
        // Find vectors for two edges sharing vert0
        Vector3 edge1 = tri1 - tri0;
        Vector3 edge2 = tri2 - tri0;

        // Begin calculating determinant - also used to calculate barycentricU parameter
        Vector3 pvec = Vector3.Cross(rayDirection, edge2);

        // If determinant is near zero, ray lies in plane of triangle
        float det = Vector3.Dot(edge1, pvec);
        if (det < 0.0001f)
            return false;

        // Calculate distance from vert0 to ray origin
        Vector3 tvec = rayPosition - tri0;

        // Calculate barycentricU parameter and test bounds
        barycentricU = Vector3.Dot(tvec, pvec);
        if (barycentricU < 0.0f || barycentricU > det)
            return false;

        // Prepare to test barycentricV parameter
        Vector3 qvec = Vector3.Cross(tvec, edge1);

        // Calculate barycentricV parameter and test bounds
        barycentricV = Vector3.Dot(rayDirection, qvec);
        if (barycentricV < 0.0f || barycentricU + barycentricV > det)
            return false;

        // Calculate pickDistance, scale parameters, ray intersects triangle
        pickDistance = Vector3.Dot(edge2, qvec);
        float fInvDet = 1.0f / det;
        pickDistance *= fInvDet;
        barycentricU *= fInvDet;
        barycentricV *= fInvDet;

        return true;
    }

مبتدئ  Ali Amin مشاركة 10

الشيء السيء في هذا الكود انه عندما يجد intersection انت مجبر ان تكمل التحقق من الاصطدام لكي تعرف اقرب نقطة تصادمت مع الشعاع

او ربما يكون عدد المجسمات او المثلثلات الذي يتم التحقق من الاصطدام معها عدد كبير تحتاج لتقليله