العثور على كائنات داخل دائرة نصف قطرها

Question

تبحث عن طريقة خفيفة الوزن للعثور على الأشياء داخل دائرة نصف قطرها.

حتى الآن ، فإن الإجابة الواضحة بالنسبة لي هي الذهاب من خلال كل كائن ، ومقارنة موضع X و Y مع مركز نصف القطر.

مثال:

Turret - البحث عن أهداف في دائرة نصف قطرها.

TargetArray - مجموعة من الأهداف المحتملة.

WithinRangeArray - صفيف ندفع الأهداف المعمول بها

Distance^2 = (TargetArray[n].x - Turret.x)^2  +  (TargetArray[n].y - Turret.y)^2

if( Distance^2 < maxRadius^2 ){
WithinRangeArray.push(TargetArray[n])
}

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

الطول المثالي لـ Targetarray: أقل من 500 هدف في وقت واحد.

Answer 1

قبل حساب المسافة الشعاعية ، تحقق أولاً لمعرفة ما إذا كان الكائن داخل المربع يتركز على موقع البرج. إذا كان الهدف _x <turret_x-range ، فهو خارج النطاق ولا حاجة للتحقق من المسافة ، وكذلك تحقق من نطاق turret_x+، نطاق turret_y ، turret_y+. وهذا يتطلب 4 مقارنات كحد أقصى و 4 إضافات/طرح OPS لتحديد ما إذا كان الهدف موجود في المربع.

Answer 2

في 2D ، يمكنك تنفيذ Quadtree ، وفي 3D ، يمكنك تنفيذ Octree مما يعني أنك ستتمكن من تجميع كائنات وتجاهل مجموعات كبيرة منها بشكل أكثر كفاءة قبل التحقق بالفعل من مسافاتها الدقيقة. يجب عليك Google لهم إذا كنت تريد معرفة المزيد. إنها هياكل بيانات مفيدة للغاية لعالم الأشياء.

قد لا يوفر التنفيذ النهائي مساحة بنفس القدر ، لكنه سيكون سريعًا بشكل لا يصدق لأنه يمكنك تجاهل عدد كبير من الكائنات بسرعة كبيرة.

Answer 3

يمكنك تخزين الأهداف المحتملة في Multiset Keyed على ساحة الشبكة التي يشغلونها. ثم تحتاج فقط إلى التكرار على الأهداف الموجودة في مربعات الشبكة بالقرب من مربع شبكة البرج التي قد تكون أهدافًا.

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