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

في هذه المقالة سوف أشارك تطبيقي وأفكاري التي نشأت أثناء عملية تصميمها.

أولاً ، يجب أن أقول لماذا قررت تنفيذ شجرة رباعية.

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

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

هناك مناطق في لعبتي يُفيد فيها استخدام quadtree على الفور:

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

كما ترون ، أشجار رباعي تنوعا جدا. سيكون تجديد جيد في مجموعة الأدوات الخاصة بك.

يمكن العثور على جميع الكودات الموضحة في المقال على جيثب .

التحضير الأولي

قبل تفصيل كود quadtree ، نحتاج إلى فصول صغيرة Vector2 الهندسية: فئة Vector2 لتحديد النقاط وفئة Box لتحديد المستطيلات. على حد سواء سيكون boilerplate.

Vector2

فئة Vector2 أضيق الحدود. أنه يحتوي على صانعي فقط ، وكذلك + و / المشغلين. هذا كل ما نحتاجه:

 template<typename T> class Vector2 { public: T x; T y; constexpr Vector2<T>(TX = 0, TY = 0) noexcept : x(X), y(Y) { } constexpr Vector2<T>& operator+=(const Vector2<T>& other) noexcept { x += other.x; y += other.y; return *this; } constexpr Vector2<T>& operator/=(T t) noexcept { x /= t; y /= t; return *this; } }; template<typename T> constexpr Vector2<T> operator+(Vector2<T> lhs, const Vector2<T>& rhs) noexcept { lhs += rhs; return lhs; } template<typename T> constexpr Vector2<T> operator/(Vector2<T> vec, T t) noexcept { vec /= t; return vec; } 

صندوق

فئة Box ليست أكثر تعقيدًا:

 template<typename T> class Box { public: T left; T top; T width; // Must be positive T height; // Must be positive constexpr Box(T Left = 0, T Top = 0, T Width = 0, T Height = 0) noexcept : left(Left), top(Top), width(Width), height(Height) { } constexpr Box(const Vector2<T>& position, const Vector2<T>& size) noexcept : left(position.x), top(position.y), width(size.x), height(size.y) { } constexpr T getRight() const noexcept { return left + width; } constexpr T getBottom() const noexcept { return top + height; } constexpr Vector2<T> getTopLeft() const noexcept { return Vector2<T>(left, top); } constexpr Vector2<T> getCenter() const noexcept { return Vector2<T>(left + width / 2, top + height / 2); } constexpr Vector2<T> getSize() const noexcept { return Vector2<T>(width, height); } constexpr bool contains(const Box<T>& box) const noexcept { return left <= box.left && box.getRight() <= getRight() && top <= box.top && box.getBottom() <= getBottom(); } constexpr bool intersects(const Box<T>& box) const noexcept { return !(left >= box.getRight() || getRight() <= box.left || top >= box.getBottom() || getBottom() <= box.top); } }; 

أنه يحتوي على بعض الهدايا مفيدة.

ما هو أكثر إثارة للاهتمام هو أنه يحتوي على طريقة تحتوي على ، والتي تتحقق مما إذا كان المستطيل داخل آخر ، وطريقة intersects ، والذي يتحقق ما إذا كان المستطيل يتقاطع مع آخر.

سوف نستخدم contains عند الإدراج والحذف ، intersects عند التعرف على التقاطعات.

Quadtree

هنا هو Quadtree فئة Quadtree :

 template<typename T, typename GetBox, typename Equal = std::equal_to<T>, typename Float = float> class Quadtree { static_assert(std::is_convertible_v<std::invoke_result_t<GetBox, const T&>, Box<Float>>, "GetBox must be a callable of signature Box<Float>(const T&)"); static_assert(std::is_convertible_v<std::invoke_result_t<Equal, const T&, const T&>, bool>, "Equal must be a callable of signature bool(const T&, const T&)"); static_assert(std::is_arithmetic_v<Float>); public: Quadtree(const Box<Float>& box, const GetBox& getBox = GetBox(), const Equal& equal = Equal()) : mBox(box), mRoot(std::make_unique<Node>()), mGetBox(getBox), mEqual(equal) { } private: static constexpr auto Threshold = std::size_t(16); static constexpr auto MaxDepth = std::size_t(8); struct Node { std::array<std::unique_ptr<Node>, 4> children; std::vector<T> values; }; Box<Float> mBox; std::unique_ptr<Node> mRoot; GetBox mGetBox; Equal mEqual; bool isLeaf(const Node* node) const { return !static_cast<bool>(node->children[0]); } }; 

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

خيارات القالب:

• T : نوع القيم التي سيتم تضمينها في quadtree. يجب أن تكون فئة T سهلة ، لأنه سيتم تخزينها داخل رباعي. من الناحية المثالية ، يجب أن يكون هذا مؤشر أو بنية بيانات بسيطة صغيرة (POD).
• GetBox : نوع الكائن الذي تم استدعاؤه والذي سيتلقى القيمة عند الإدخال وإرجاع مستطيل.
• Equal : نوع الكائن الذي تم استدعاؤه للتحقق مما إذا كانت القيمتان متساويتان. بشكل افتراضي ، نستخدم عامل المساواة القياسي.
• Float : النوع الحسابي المستخدم في العمليات الحسابية. افتراضيا ، نستخدم float .

في بداية تعريف الفئة ، هناك ثلاثة تأكيدات ثابتة للتحقق من صحة معلمات القالب.

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

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

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

الآن يمكننا أن ننظر إلى Quadtree عضو Quadtree :

• mBox هو مربع mBox عالمي. يجب أن تكون جميع القيم المدرجة في quadtree ضمنها.
• mRoot هو أصل quadtree.
• mGetBox هو كائن يسمى ، والذي mGetBox للحصول على المستطيل من القيمة.
• mEqual هو الكائن الذي يسمى ، والذي mEqual للتحقق من المساواة بين القيمتين.

يقوم المنشئ ببساطة بتعيين mBox و mGetBox و mEqual ، كما ينشئ عقدة جذر.

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

نحن الآن على استعداد لبدء عمليات أكثر إثارة للاهتمام.

إدراج وحذف

قبل أن أعرض رمز الإدراج ، نحتاج إلى مناقشة العقد التي ستحتوي على القيم. هناك استراتيجيتان:

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

إذا كانت المستطيلات المحيطية صغيرة الحجم وبنفس الحجم تقريبًا ، فإن الإستراتيجية الأولى تكون أكثر فعالية عند البحث عن التقاطعات. ومع ذلك ، في حالة وجود مستطيلات كبيرة ، قد تحدث حالات متدهورة يكون الأداء فيها سيئًا للغاية. على سبيل المثال ، إذا قمنا بإدراج قيمة يكون مستطيلها في المربع المحيط العام ، فسيتم إضافتها إلى جميع الأوراق. وإذا قمنا بإدراج حد لهذه القيم ، فسيتم تقسيم كل العقد حتى MaxDepth الوصول إلى MaxDepth ولن تكون القيم في جميع الأوراق. لذلك ، سوف quadtree تحتوي $$$\ texttt {Threshold} \ times 4 ^ {\ texttt {MaxDepth}}$المعاني ، وهذا ... الكثير.

علاوة على ذلك ، مع الاستراتيجية الأولى ، سيكون الإدخال والحذف أبطأ قليلاً ، لأنه يتعين علينا إدراج (أو حذف) جميع العقد التي تتقاطع مع القيمة.

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

لمعرفة العقدة التي سنقوم بإدراجها أو حذفها ، سنستخدم وظيفتين مساعدتين.

الأول ، computeBox ، يحسب مستطيل العقدة التابعة بواسطة مستطيل العقدة الأصل وفهرس الربع الخاص به.

 Box<Float> computeBox(const Box<Float>& box, int i) const { auto origin = box.getTopLeft(); auto childSize = box.getSize() / static_cast<Float>(2); switch (i) { // North West case 0: return Box<Float>(origin, childSize); // Norst East case 1: return Box<Float>(Vector2<Float>(origin.x + childSize.x, origin.y), childSize); // South West case 2: return Box<Float>(Vector2<Float>(origin.x, origin.y + childSize.y), childSize); // South East case 3: return Box<Float>(origin + childSize, childSize); default: assert(false && "Invalid child index"); return Box<Float>(); } } 

الثاني ، getQuadrant ، بإرجاع الربع الذي توجد فيه القيمة:

 int getQuadrant(const Box<Float>& nodeBox, const Box<Float>& valueBox) const { auto center = nodeBox.getCenter(); // West if (valueBox.getRight() < center.x) { // North West if (valueBox.getBottom() < center.y) return 0; // South West else if (valueBox.top >= center.y) return 2; // Not contained in any quadrant else return -1; } // East else if (valueBox.left >= center.x) { // North East if (valueBox.getBottom() < center.y) return 1; // South East else if (valueBox.top >= center.y) return 3; // Not contained in any quadrant else return -1; } // Not contained in any quadrant else return -1; } 

تقوم بإرجاع -1 إذا لم يكن موجودًا في أي من الأرباع.

نحن الآن على استعداد للنظر في أساليب الإدراج والحذف.

إدراج

استدعاء الأسلوب ببساطة استدعاء أسلوب مساعد خاص:

 void add(const T& value) { add(mRoot.get(), 0, mBox, value); } 

هنا هو رمز طريقة المساعد:

 void add(Node* node, std::size_t depth, const Box<Float>& box, const T& value) { assert(node != nullptr); assert(box.contains(mGetBox(value))); if (isLeaf(node)) { // Insert the value in this node if possible if (depth >= MaxDepth || node->values.size() < Threshold) node->values.push_back(value); // Otherwise, we split and we try again else { split(node, box); add(node, depth, box, value); } } else { auto i = getQuadrant(box, mGetBox(value)); // Add the value in a child if the value is entirely contained in it if (i != -1) add(node->children[static_cast<std::size_t>(i)].get(), depth + 1, computeBox(box, i), value); // Otherwise, we add the value in the current node else node->values.push_back(value); } } 

في البداية ، يوجد افتراضان يتحققان من أننا لا نقوم بأي شيء غير منطقي ، على سبيل المثال ، نحن لا ندرج قيمة في عقدة لا تحتوي على المربع المحيط بها.

ثم ، إذا كانت العقدة عبارة عن ورقة ، ويمكننا إدراج قيمة جديدة فيها ، أي لم MaxDepth إلى MaxDepth أو Threshold ، قم بإجراء الإدراج. وإلا ، فإننا نشارك هذه العقدة ونعيد المحاولة.

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

هنا هو إجراء الفصل:

 void split(Node* node, const Box<Float>& box) { assert(node != nullptr); assert(isLeaf(node) && "Only leaves can be split"); // Create children for (auto& child : node->children) child = std::make_unique<Node>(); // Assign values to children auto newValues = std::vector<T>(); // New values for this node for (const auto& value : node->values) { auto i = getQuadrant(box, mGetBox(value)); if (i != -1) node->children[static_cast<std::size_t>(i)]->values.push_back(value); else newValues.push_back(value); } node->values = std::move(newValues); } 

ننشئ أربع عقد تابعة ، ومن ثم لكل قيمة للعقدة الأصل ، نقرر في أي عقدة (تابعة أو أصل) يجب تخزين القيمة.

إزالة

تقوم طريقة remove أيضًا باستدعاء طريقة المساعد:

 void remove(const T& value) { remove(mRoot.get(), nullptr, mBox, value); } 

فيما يلي رمز طريقة المساعد ، وهو مشابه جدًا لكود الإدراج:

 void remove(Node* node, Node* parent, const Box<Float>& box, const T& value) { assert(node != nullptr); assert(box.contains(mGetBox(value))); if (isLeaf(node)) { // Remove the value from node removeValue(node, value); // Try to merge the parent if (parent != nullptr) tryMerge(parent); } else { // Remove the value in a child if the value is entirely contained in it auto i = getQuadrant(box, mGetBox(value)); if (i != -1) remove(node->children[static_cast<std::size_t>(i)].get(), node, computeBox(box, i), value); // Otherwise, we remove the value from the current node else removeValue(node, value); } } 

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

نظرًا لأننا لا نهتم بترتيب القيم المخزنة في العقدة ، عندما أقوم بمسحها ، أستخدم تحسينًا بسيطًا: لقد قمت فقط بتغيير القيمة التي تم محوها باستخدام القيمة الأخيرة وحذفها:

 void removeValue(Node* node, const T& value) { // Find the value in node->values auto it = std::find_if(std::begin(node->values), std::end(node->values), [this, &value](const auto& rhs){ return mEqual(value, rhs); }); assert(it != std::end(node->values) && "Trying to remove a value that is not present in the node"); // Swap with the last element and pop back *it = std::move(node->values.back()); node->values.pop_back(); } 

نحتاج أيضًا إلى إلقاء نظرة على tryMerge :

 void tryMerge(Node* node) { assert(node != nullptr); assert(!isLeaf(node) && "Only interior nodes can be merged"); auto nbValues = node->values.size(); for (const auto& child : node->children) { if (!isLeaf(child.get())) return; nbValues += child->values.size(); } if (nbValues <= Threshold) { node->values.reserve(nbValues); // Merge the values of all the children for (const auto& child : node->children) { for (const auto& value : child->values) node->values.push_back(value); } // Remove the children for (auto& child : node->children) child.reset(); } } 

يتحقق tryMerge أن جميع العقد الفرعية هي أوراق وأن العدد الإجمالي لقيمها وقيم العقد الفرعية أقل من العتبة. إذا كان الأمر كذلك ، فنحن ننسخ جميع القيم من العقد الفرعية إلى العقدة الحالية ونحذف العقد الفرعية.

بحث تقاطع

تقاطع مع المستطيل

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

وسيتم query :

 std::vector<T> query(const Box<Float>& box) const { auto values = std::vector<T>(); query(mRoot.get(), mBox, box, values); return values; } 

في هذه الطريقة ، نختار ببساطة std::vector ، والتي ستحتوي على القيم التي تتقاطع مع المربع المحيط ، ونستدعي طريقة المساعد:

 void query(Node* node, const Box<Float>& box, const Box<Float>& queryBox, std::vector<T>& values) const { assert(node != nullptr); assert(queryBox.intersects(box)); for (const auto& value : node->values) { if (queryBox.intersects(mGetBox(value))) values.push_back(value); } if (!isLeaf(node)) { for (auto i = std::size_t(0); i < node->children.size(); ++i) { auto childBox = computeBox(box, static_cast<int>(i)); if (queryBox.intersects(childBox)) query(node->children[i].get(), childBox, queryBox, values); } } } 

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

جميع التقاطعات الزوجية

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

لتحقيق هذا ، نحن بحاجة إلى النظر في أن التقاطع يمكن أن يحدث فقط

• بين قيمتين المخزنة في عقدة واحدة

أو

• بين القيمة المخزنة في العقدة وقيمة أخرى مخزنة في سليل هذه العقدة.

نتيجة لهذا ، نحتاج إلى التحقق من التقاطع بين:

• القيمة والقيم التالية المخزنة في نفس العقدة

و

• القيمة والقيم المخزنة في السليل.

وبالتالي ، فإننا بالتأكيد لن نبلغ عن نفس التقاطع مرتين.

فيما يلي رمز findAllIntersections :

 std::vector<std::pair<T, T>> findAllIntersections() const { auto intersections = std::vector<std::pair<T, T>>(); findAllIntersections(mRoot.get(), intersections); return intersections; } 

مرة أخرى ، نحن ببساطة نخصص std::vector لتخزين التقاطعات واستدعاء وظيفة المساعد:

 void findAllIntersections(Node* node, std::vector<std::pair<T, T>>& intersections) const { // Find intersections between values stored in this node // Make sure to not report the same intersection twice for (auto i = std::size_t(0); i < node->values.size(); ++i) { for (auto j = std::size_t(0); j < i; ++j) { if (mGetBox(node->values[i]).intersects(mGetBox(node->values[j]))) intersections.emplace_back(node->values[i], node->values[j]); } } if (!isLeaf(node)) { // Values in this node can intersect values in descendants for (const auto& child : node->children) { for (const auto& value : node->values) findIntersectionsInDescendants(child.get(), value, intersections); } // Find intersections in children for (const auto& child : node->children) findAllIntersections(child.get(), intersections); } } 

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

findIntersectionsInDescendants بشكل متكرر findIntersectionsInDescendants التقاطعات بين القيمة المعطاة وجميع القيم المخزنة في الشجرة الفرعية:

 void findIntersectionsInDescendants(Node* node, const T& value, std::vector<std::pair<T, T>>& intersections) const { // Test against the values stored in this node for (const auto& other : node->values) { if (mGetBox(value).intersects(mGetBox(other))) intersections.emplace_back(value, other); } // Test against values stored into descendants of this node if (!isLeaf(node)) { for (const auto& child : node->children) findIntersectionsInDescendants(child.get(), value, intersections); } } 

هذا كل شئ! أكرر ، يتم نشر جميع التعليمات البرمجية على جيثب .

موارد مفيدة

إذا كنت ترغب في معرفة المزيد حول التعرف على التصادم وتقسيم هياكل البيانات ، فإنني أوصي بقراءة الكتاب بواسطة Christer Erickson Real-Time Collision Detection . يتم الكشف عن العديد من المواضيع بعمق وفي نفس الوقت يتم كتابة الكتاب بلغة مفهومة للغاية. علاوة على ذلك ، يمكن قراءة الفصول بشكل منفصل. هذا هو مصدر مرجعي كبير.

استنتاج

هذا يكمل العمل مع التعرف على الاصطدام. ومع ذلك ، هو فقط نصف المحرك المادي. النصف الثاني هو قرار الاصطدام .