التقسيم المكاني

^title التقسيم المكاني ^section أنماط التحسين

النية

حدّد مواقع الكائنات بكفاءة عبر تخزينها في بنية بيانات منظّمة حسب مواضعها.

الدافع

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

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

وهذا يعني أن محرّك لعبتك يحتاج غالباً إلى الإجابة عن السؤال: «ما الكائنات القريبة من هذا الموقع؟» وإذا كان عليه الإجابة عن ذلك عدّة مرات في كل إطار، فقد يبدأ في أن يصبح عنق زجاجة للأداء.

وحدات في ميدان المعركة

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

^code pairwise

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

رسم خطوط المعركة

المشكلة التي نواجهها هي أن مصفوفة الوحدات لا تحمل أي ترتيب باطني. فللعثور على وحدة قريبة من موقع ما، علينا تمرير على المصفوفة كاملة. والآن، تخيّل أننا نبسّط لعبتنا قليلاً. فبدلاً من ميدان معركة ثنائي الأبعاد، تخيّل أنه خط معركة أحادي البعد.

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

الدرس واضح إلى حدٍّ كبير: إذا خزّنا كائناتنا في بنية بيانات منظّمة حسب مواقعها، فسنتمكّن من العثور عليها بسرعة أكبر بكثير. وهذا النمط يتعلق بتطبيق تلك الفكرة على مساحات لها أكثر من بُعد واحد.

النمط

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

متى تستخدمه

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

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

في بالك

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

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

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

شيفرة نموذجية

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

ورقة رسم بياني

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

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

شبكة من الوحدات المترابطة

حسناً، لنبدأ البرمجة. أولاً، بعض الأعمال التحضيرية. إليك صنف Unit الأساسي:

^code unit-simple

لكل وحدة موضع (في بُعدين) ومؤشر إلى Grid التي تعيش عليها. ونجعل Grid صنفاً friend، لأننا—as سنرى—حين يتغيّر موضع وحدة، عليها أن تؤدي رقصة معقّدة مع الشبكة للتأكّد من تحديث كل شيء بشكل صحيح.

وإليك رسماً للشبكة:

^code grid-simple

لاحظ أن كل خانة هي مجرّد مؤشر إلى وحدة. بعد ذلك، سنمدّ Unit بمؤشري next وprev:

^code unit-linked

يتيح لنا هذا تنظيم الوحدات في قائمة مترابطة ثنائية بدلاً من مصفوفة.

كل خانة في الشبكة تشير إلى أول وحدة في قائمة الوحدات الواقعة داخل تلك الخانة، ولكل وحدة مؤشرات إلى الوحدات التي قبلها وبعدها في القائمة. وسنرى السبب قريباً.

دخول ميدان المعركة

أول ما يلزم فعله هو التأكّد من أن الوحدات الجديدة تُوضع فعلاً في الشبكة عند إنشائها. وسنجعل Unit يتولّى ذلك في بانيه:

^code unit-ctor

وتُعرَّف دالة add() هذه على النحو التالي:

^code add

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

اشتباك السيوف

وحين تستقرّ جميع الوحدات في خلاياها، يمكننا أن نتركها تبدأ Hack-and-slash ببعضها. ومع هذه الشبكة الجديدة، تبدو الدالة الرئيسة للتعامل مع القتال كالتالي:

^code grid-melee

هي تمرّ على كل خانة ثم تستدعي handleCell() عليها. وكما ترى، فقد قسّمنا ميدان المعركة حقاً إلى اشتباكات صغيرة معزولة. ثم تتعامل كل خانة مع قتالها كالتالي:

^code handle-cell

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

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

الانطلاق إلى الأمام

لقد حللنا مشكلة الأداء، لكننا أنشأنا مشكلة جديدة مكانها. فالوحدات محبوسة الآن في خلاياها. فإذا حرّكنا وحدة عبر حدود الخانة التي تحتويها، فلن تراها وحدات تلك الخانة بعد ذلك، ولن يراها أحد غيرها. فميدان معركتنا مقسَّم إلى حدٍّ مفرط.

ولإصلاح ذلك، سنحتاج إلى بعض العمل في كل مرة تتحرّك فيها وحدة. فإذا عبرت خطوط حدود خانة، نحتاج إلى إزالتها من تلك الخانة وإضافتها إلى الخانة الجديدة. أولاً، سنمنح Unit دالة لتغيير موضعها:

^code unit-move

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

^code grid-move

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

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

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

على مسافة الذراع

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

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

^code handle-distance

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

هنا، تقع B ضمن نطاق هجوم A رغم أن مركزيهما في خلايا مختلفة. وللتعامل مع هذا، سنحتاج إلى مقارنة الوحدات ليس في الخانة نفسها فحسب، بل في الخلايا المجاورة أيضاً. ولتنفيذ ذلك، سنفصل أولاً الحلقة الداخلية من handleCell():

^code handle-unit

الآن لدينا دالة تأخذ وحدة واحدة وقائمة وحدات أخرى وترى ما إذا كانت هناك اصطدامات. ثم سنجعل handleCell() يستخدمها:

^code handle-cell-unit

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

^code handle-neighbor

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

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

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

1. حين نبحث عن اصطدامات لوحدة A، سننظر إلى جارها على اليمين ونجد B. فنسجّل هجوماً بين A وB.

2. ثم، حين نبحث عن اصطدامات لوحدة B، سننظر إلى جارها على اليسار ونجد A. فنسجّل هجوماً ثانياً بين A وB.

والنظر إلى نصف الخلايا المجاورة فقط يصحّح ذلك. ولا يهمّ أيّ نصف ننظر إليه إطلاقاً.

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

قرارات التصميم

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

هل التقسيم هرمي أم مسطّح؟

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

• إذا كان التقسيم مسطّحاً:

  • أبسط. فبنى البيانات المسطّحة أسهل في التفكير وأبسط في التنفيذ.

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

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

• إذا كان التقسيم هرمياً:

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

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

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

هل يعتمد التقسيم على مجموعة الكائنات؟

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

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

• إذا كان التقسيم مستقلاً عن الكائنات:

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

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

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

• إذا كان التقسيم يتكيّف مع مجموعة الكائنات:

  تقسّم التقسيمات المكانية مثل BSPs وأشجار k-d العالم بشكل تعاودياً بحيث يحتوي كل نصف على العدد نفسه تقريباً من الكائنات. وللقيام بذلك، عليك أن تعدّ عدد الكائنات في كل جانب عند اختيار المستويات التي نقسم على امتدادها. وسلّم تسلسل أحجام الحدود (bounding volume hierarchies) هو نوع آخر من تقسيمات المساحة يحسّن لأجل مجموعة الكائنات المحدّدة في العالم.

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

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

• إذا كان التقسيم مستقلاً عن الكائنات، لكن التسلسل الهرمي يعتمد على الكائنات:

  يستحق تقسيم مكاني واحد ذكراً خاصاً لأنه يجمع بعض أفضل خصائص التقسيمات الثابتة والمتكيفة معاً: الأشجار الرباعية (quadtrees).

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

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

  يمكنك رؤية التقسيم وهو يعمل إذا قرأت من اليسار إلى اليمين هنا:

  

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

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

  • يمكن نقل الكائنات بسرعة. وهذا يتبع ما سبق بطبيعة الحال. فـ«نقل» كائن هو مجرّد إضافة وإزالة، وكلاهما سريع إلى حدٍّ كبير مع الأشجار الرباعية.

  • التقسيمات متوازنة. فبما أن أي مربّع معطى سيكون فيه عدد أقل من حدّ أقصى ثابت من الكائنات، حتى حين تتجمّع الكائنات، فلن لديك تقسيمات منفردة فيها كومة هائلة من الكائنات.

هل تُخزَّن الكائنات في التقسيم وحده؟

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

• إذا كان المكان الوحيد الذي تُخزَّن فيه الكائنات:

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

• إذا كانت هناك مجموعة أخرى للكائنات:

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

    ومجموعة ثانية تخزّن الكائنات فحسب تمنحك طريقة للمرور عليها كلّها مباشرةً. فلك بنيتا بيانات، واحدة محسّنة لكل حالة استخدام.

انظر أيضاً

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

  • الشبكة
  • الشجرة الرباعية
  • تقسيم الفضاء الثنائي
  • شجرة k-d
  • التسلسل الهرمي لأحجام الحدود

• كل واحدة من بنى البيانات المكانية هذه تمتدّ أساساً ببنية بيانات معروفة جيداً من البُعد الواحد إلى أبعاد أكثر. ومعرفة أقاربها الخطّية ستساعدك على معرفة ما إذا كانت مناسبة لمشكلتك:

  • الشبكة هي فرز دلو دائم.
  • تقسيمات الفضاء الثنائي وأشجار k-d والتسلسلات الهرمية لأحجام الحدود هي أشجار بحث ثنائية.
  • الأشجار الرباعية والأشجار الثمانية هي المحاولات.