> ## Content Index
> Fetch the complete content index at: https://arabroot.io/llms.txt
> Use this file to discover other available public pages before exploring further.

# كيف رسمت Doom عالماً ثلاثي الأبعاد بشجرة BSP؟
- URL: https://arabroot.io/articles/كيف-رسمت-doom-عالما-ثلاثي-الابعاد-بشجرة-bsp/
- Published: 2026-11-20T10:25:42.000Z
- Updated: 2026-11-20T11:25:23.000Z
- Description: نشرح كيف رتبت Doom جدرانها بشجرة BSP ورسمتها من القريب إلى البعيد، ونبني الشجرة والمرسم بـ Python ونعد ما يفحصه كل أسلوب على خرائط حتى 1,225 جداراً.
- Author: فريق عرب رووت
- Tags: الأدلة التقنية, تطوير الألعاب

من لعب Doom في التسعينات يتذكر غالباً اللحظة الأولى: ممرات بجدران مائلة، وغرف بارتفاعات مختلفة، وسلالم، وأضواء تخفت وتشتد، وكل ذلك يتحرك بسرعة على حاسوب مكتبي عادي بمعالج 386 أو 486، دون أي بطاقة رسوم ثلاثية الأبعاد 3D Graphics Card، لأن هذه الشرائح لم تكن قد وصلت إلى البيوت بعد. وإذا كنت مبرمجاً اليوم فالسؤال الطبيعي هو: كيف؟ فالمعالج CPU الذي كان يشغل اللعبة أبطأ بآلاف المرات من معالج هاتفك، وكان عليه أن يقرر في كل إطار Frame أي جدار يراه اللاعب وأيه مخفي خلف غيره، وأن يرسم كل بكسل على الشاشة بنفسه.

والإجابة ليست حيلة واحدة، وإنما مجموعة قرارات، أهمها شجرة تسمى BSP، اختصاراً لـ Binary Space Partitioning، أي التقسيم الثنائي للمساحة، يحسبها برنامج خاص مرة واحدة قبل اللعب في مرحلة المعالجة المسبقة Preprocessing، ثم تستخدمها اللعبة في كل إطار لتعرف ترتيب الجدران من القريب إلى البعيد دون أن تفرز شيئاً. وفي هذا المقال سوف نشرح الفكرة، ثم نبني نسختنا نحن: خريطة صغيرة من صنعنا، وباني شجرة Node Builder، وثلاث طرق لرسم الجدران، ونعد في كل واحدة كم جداراً فحصت وكم مرة كتبت كل عمود من الشاشة، على خرائط من 64 جداراً إلى 1,225.

وسوف نناقش في هذا المقال ما يلي:

- المشكلة التي حلتها Doom: من يخفي من، على معالج بلا شريحة رسوم.
- فكرة شجرة BSP، ومن أين جاءت، وكيف يقسم باني الشجرة الخريطة.
- الرسم من القريب إلى البعيد Front to Back مقابل خوارزمية الرسام Painter's Algorithm، ولماذا اختارت Doom الأول.
- مختبر بـ Python: خريطة وباني شجرة وثلاثة مرسمات Renderers، والتحقق من أنها ترسم الصورة نفسها.
- القياس على ثلاثة أحجام من الخرائط، وماذا يحدث إذا اختار الباني خطوط التقسيم بشكل سيئ، أو حذفنا فحص الصناديق Bounding Boxes، أو حركنا جداراً.
- ما لا تستطيعه هذه الطريقة: غرفة فوق غرفة، والأرض والسقف Visplanes، والأعداد بالنقطة الثابتة Fixed Point.

وهذا المقال جزء من مرحلة «حيل الألعاب الكلاسيكية»، وفيها نشرح كل حيلة ثم نعيد بناءها بكود يعمل:

[![](https://arabroot.io/content/images/2026/11/light-gun-how-it-works-cover-cover.webp)دليلكيف عرف المسدس الضوئي Light Gun أين أصبت البطة؟نشرح كيف عرف المسدس الضوئي هدفك على شاشة CRT بإطار أسود ومربع أبيض لكل هدف، ونعيد بناء الحيلة في المتصفح ونقيس لماذا تفشل على شاشات اليوم.](https://arabroot.io/articles/%D9%83%D9%8A%D9%81-%D8%B9%D8%B1%D9%81-%D8%A7%D9%84%D9%85%D8%B3%D8%AF%D8%B3-%D8%A7%D9%84%D8%B6%D9%88%D8%A6%D9%8A-light-gun-%D8%A7%D9%8A%D9%86-%D8%A7%D8%B5%D8%A8%D8%AA-%D8%A7%D9%84%D8%A8%D8%B7%D8%A9/)[![](https://arabroot.io/content/images/2026/11/racing-the-beam-cover-cover.webp)دليلAtari 2600: الرسم مع شعاع الشاشة Racing the Beamكيف رسمت ألعاب Atari 2600 صورها دون ذاكرة إطار: نكتب برنامج 6502 صغيراً ونعد دوراته في Stella لنرى ماذا يحدث حين يتأخر الكود عن الشعاع.](https://arabroot.io/articles/atari-2600-%D8%A7%D9%84%D8%B1%D8%B3%D9%85-%D9%85%D8%B9-%D8%B4%D8%B9%D8%A7%D8%B9-%D8%A7%D9%84%D8%B4%D8%A7%D8%B4%D8%A9-racing-the-beam/)[![](https://arabroot.io/content/images/2026/11/pacman-ghost-ai-cover-cover.webp)دليلكيف تفكر أشباح Pac-Man؟ ذكاء بقواعد بسيطةنشرح القواعد الأربع التي تختار بها أشباح Pac-Man أهدافها وجدول موجاتها وخطأ الفيض الشهير، ثم نبنيها على متاهتنا ونقيس أثر كل قاعدة في 392 لعبة.](https://arabroot.io/articles/%D9%83%D9%8A%D9%81-%D8%AA%D9%81%D9%83%D8%B1-%D8%A7%D8%B4%D8%A8%D8%A7%D8%AD-pac-man-%D8%B0%D9%83%D8%A7%D8%A1-%D8%A8%D9%82%D9%88%D8%A7%D8%B9%D8%AF-%D8%A8%D8%B3%D9%8A%D8%B7%D8%A9/)[![](https://arabroot.io/content/images/2026/11/sprite-flicker-limits-cover-cover.webp)دليللماذا كانت الشخصيات ترمش؟ حدود رسوميات NESنشرح لماذا لا يرسم جهاز NES أكثر من ثماني شخصيات في السطر، ونكتب ROM صغيراً يزدحم عمداً ونقيس في FCEUX أي طريقة رمش توزع الاختفاء بعدل.](https://arabroot.io/articles/%D9%84%D9%85%D8%A7%D8%B0%D8%A7-%D9%83%D8%A7%D9%86%D8%AA-%D8%A7%D9%84%D8%B4%D8%AE%D8%B5%D9%8A%D8%A7%D8%AA-%D8%AA%D8%B1%D9%85%D8%B4-%D8%AD%D8%AF%D9%88%D8%AF-%D8%B1%D8%B3%D9%88%D9%85%D9%8A%D8%A7%D8%AA-nes/)[![](https://arabroot.io/content/images/2026/11/fast-inverse-sqrt-cover-cover.webp)دليلالجذر التربيعي العكسي السريع في Quake IIIنفك حيلة 0x5f3759df في Quake III ونرى لماذا تعمل، ثم نقيس خطأها على كل عدد float موجب ونبحث عن أفضل ثابت ونقارن سرعتها بأمر rsqrtss.](https://arabroot.io/articles/%D8%A7%D9%84%D8%AC%D8%B0%D8%B1-%D8%A7%D9%84%D8%AA%D8%B1%D8%A8%D9%8A%D8%B9%D9%8A-%D8%A7%D9%84%D8%B9%D9%83%D8%B3%D9%8A-%D8%A7%D9%84%D8%B3%D8%B1%D9%8A%D8%B9-%D9%81%D9%8A-quake-iii-0x5f3759df/)

## المشكلة: من يخفي من؟

صدرت Doom من id Software في 10 ديسمبر 1993، وبنى محركها John Carmack، كما تذكر [صفحة اللعبة في Wikipedia](https://en.wikipedia.org/wiki/Doom%5F%281993%5Fvideo%5Fgame%29?ref=arabroot.io). وكانت قبلها لعبة الشركة [Wolfenstein 3D](https://en.wikipedia.org/wiki/Wolfenstein%5F3D?ref=arabroot.io)، وفيها كل الجدران على شبكة مربعات، بزوايا قائمة وارتفاع واحد، وهذا جعل المشكلة سهلة نسبياً: ترسل شعاعاً من عين اللاعب لكل عمود من الشاشة، وتمشي به على الشبكة مربعاً بمربع حتى يصطدم بجدار. أما Doom فجاءت بجدران بأي زاوية وأي طول، وبأرضيات وأسقف بارتفاعات مختلفة، فلم تعد الشبكة موجودة، وصار السؤال في كل إطار: من بين مئات الجدران في المستوى، أيها يظهر في كل عمود من الشاشة؟

![معالج Intel 80486DX2 مربع بلون رمادي فاتح عليه شعار Intel والرقم A80486DX2-66 وأرقام تعريف أخرى، وحوله إطار ذهبي](https://arabroot.io/content/images/2026/11/doom-bsp-i486-photo.webp)

معالج Intel 80486DX2، من فئة المعالجات التي شغلت Doom في بيوت التسعينات، دون أي شريحة رسوم ثلاثية الأبعاد. الصورة: Andrew Dunn، رخصة CC BY-SA 2.0، المصدر: [Wikimedia Commons](https://commons.wikimedia.org/wiki/File:Intel%5F80486DX2%5Ftop.jpg?ref=arabroot.io) (تم تصغيرها).

وإذا أردت أن تعرف هذه الحواسيب عن قرب، فقد خصص Fabien Sanglard جزءاً كبيراً من كتابه [Game Engine Black Book: DOOM](https://fabiensanglard.net/gebbdoom/?ref=arabroot.io) الذي نشره في الذكرى الخامسة والعشرين للعبة لوصفها: معالج 80486، وناقل VESA Local Bus الذي كانت تمر عبره الصورة إلى بطاقة العرض، والمترجم Watcom الذي بني به المحرك، وأجهزة NeXT التي طورت عليها اللعبة. والصورة التي يرسمها الكتاب هي صورة حاسوب يرسم كل بكسل بنفسه، فكل جدار لا يرسمه هو وقت يربحه.

والحلول البسيطة كلها مكلفة. الأول أن تفحص كل جدار لكل عمود، وتحتفظ لكل عمود بأقرب جدار رأيته حتى الآن، وهذا ما يسمى ذاكرة العمق Depth Buffer، وهي طريقة شرائح الرسوم اليوم، ولكنها على معالج 486 تعني أن العمل يكبر مع حجم المستوى كله لا مع ما يراه اللاعب. والثاني أن ترتب الجدران كلها من البعيد إلى القريب وترسمها بهذا الترتيب، فيغطي القريب البعيد، وهذه خوارزمية الرسام Painter's Algorithm، كما يرسم الرسام الجبال قبل الأشجار التي أمامها، ولكن الترتيب يتغير مع كل حركة للاعب، وفرز مئات الجدران في كل إطار مكلف، وفي بعض الحالات لا يوجد ترتيب صحيح أصلاً حين تتقاطع الجدران. وكل الطريقتين ترسم بكسلات سوف تمسح بعد لحظة، وهذا ما يسمى الرسم الزائد Overdraw، وهو هدر لا يحتمله معالج يرسم كل بكسل بنفسه.

## فكرة BSP: اقسم الخريطة مرة، واستفد منها كل إطار

الفكرة أقدم من Doom بسنوات. فقد نشر Henry Fuchs وZvi Kedem وBruce Naylor في مؤتمر SIGGRAPH عام 1980 بحثاً بعنوان «On Visible Surface Generation by A Priori Tree Structures» يبني الشجرة آلياً كمعالجة مسبقة، ثم وصف Chen وGordon عام 1991 كيف ترسم من القريب إلى البعيد باستخدامها، وتذكر [صفحة BSP في Wikipedia](https://en.wikipedia.org/wiki/Binary%5Fspace%5Fpartitioning?ref=arabroot.io) أن John Carmack استخدم هذه الطريقة في صناعة Doom. وفكرتها بسيطة جداً إذا نظرت إليها من الأعلى:

1. خذ جداراً من الخريطة، ومد خطه في الاتجاهين إلى ما لا نهاية. هذا الخط يقسم الخريطة إلى جهتين: أمامه Front وخلفه Back.
2. ضع كل جدار آخر في الجهة التي يقع فيها، وإذا قطعه الخط فاقسمه قطعتين، قطعة لكل جهة.
3. كرر الشيء نفسه داخل كل جهة على حدة، حتى تصل إلى مناطق صغيرة لا يخفي فيها أي جدار جداراً آخر، أي مناطق محدبة Convex. وتسمي Doom هذه المناطق النهائية Subsectors.

والنتيجة شجرة ثنائية: كل عقدة Node فيها خط تقسيم، ولها فرعان، وفي أطرافها الأوراق Leaves، وهي المناطق المحدبة بجدرانها. والشكل التالي يبين خريطة صغيرة وشجرتها:

![على اليمين خريطة مستطيلة فيها عمود مربع وجدار قصير، وثلاثة خطوط تقسيم متقطعة: الخط 1 أحمر رأسي، والخط 2 برتقالي أفقي على امتداد الجدار القصير، والخط 3 أزرق رأسي، والمناطق أ وب وج ود، والكاميرا في أ، وعلى اليسار الشجرة: العقدة 1 وتحتها العقدتان 2 و3، وتحتهما الأوراق أ وب وج ود، وتحتها أن الترتيب من القريب إلى البعيد أ ثم ب ثم ج ثم د](https://arabroot.io/content/images/2026/11/doom-bsp-01-idea.webp)

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

### لماذا نتوقف عند المنطقة المحدبة؟

قد يتساءل البعض: لماذا لا يستمر الباني في التقسيم حتى يبقى جدار واحد في كل ورقة؟ والإجابة أن المنطقة المحدبة لا تحتاج إلى أي ترتيب داخلها. فإذا كانت كل الجدران في الورقة أمام خطوط بعضها، فإن الكاميرا التي ترى وجه جدار منها لا يمكن أن يقف بينها وبين هذا الوجه جدار آخر من الورقة نفسها، وبالتالي يمكن رسم جدران الورقة بأي ترتيب دون أن يغطي أحدها الآخر. والتوقف هنا يوفر عقداً كثيرة في الشجرة، أي أسئلة أقل في كل إطار، وهذا بالضبط تعريف Subsector في Doom. وفي ملف الترويسة r\_defs.h من الكود المصدري تجد الهيكل node\_t فيه خط التقسيم بنقطة واتجاه، وصندوقان محيطان bbox، وفرعان children، أي ما في كلاسنا Node تقريباً، وتجد في p\_setup.c أن المستوى يحمل الشجرة جاهزة من ملف البيانات في ثلاثة أجزاء: العقد NODES، والمناطق SSECTORS، وقطع الجدران SEGS، أي أن اللعبة لا تبني شيئاً عند التحميل، وإنما تقرأ ما بناه الباني.

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

والثمن أن الشجرة تحسب قبل اللعب، فإذا تحرك جدار تغيرت الحقيقة التي بنيت عليها. ولذلك فإن الأبواب في Doom لا تدور ولا تنزلق جانباً، وإنما ترتفع وتنزل، لأن الحركة الرأسية تغير ارتفاع الأرض أو السقف في منطقة دون أن تغير خطوط الخريطة من الأعلى. وتذكر [صفحة محرك Doom](https://en.wikipedia.org/wiki/Doom%5Fengine?ref=arabroot.io) أن أداة منفصلة تبني بيانات الشجرة قبل اللعب، وأن ذلك قد يأخذ وقتاً طويلاً للمستويات الكبيرة، وسوف نقيس هذا الوقت بأنفسنا.

## من القريب إلى البعيد، لا العكس

الطريقة الأصلية في بحث 1980 كانت تستخدم الشجرة لترسم من البعيد إلى القريب، أي خوارزمية الرسام دون فرز. ولكن Doom تمشي بالعكس، من القريب إلى البعيد، والسبب أن الجدار الصلب الذي يرسم في عمود يغلق هذا العمود نهائياً، فلا يرسم فيه أي شيء بعده. وفي الكود المصدري لـ Doom الذي نشرته id Software تحت رخصة GPL على [GitHub](https://github.com/id-Software/DOOM?ref=arabroot.io)، تجد هذا في ملف [r\_bsp.c](https://github.com/id-Software/DOOM/blob/master/linuxdoom-1.10/r%5Fbsp.c?ref=arabroot.io): الدالة R\_RenderBSPNode تمر على الشجرة جهة الكاميرا أولاً، ولا تدخل الجهة البعيدة إلا إذا قالت الدالة R\_CheckBBox إن صندوقها المحيط Bounding Box ما زال يرى عموداً مفتوحاً واحداً على الأقل. والأعمدة المغلقة تحفظ في مصفوفة صغيرة اسمها solidsegs، ويحدد حجمها السطر `#define MAXSEGS 32`، أي أن Doom لا تحفظ حالة كل عمود على حدة، وإنما قائمة مدى Ranges من الأعمدة المغلقة.

ولكي ترى كيف تعمل هذه القائمة، لنفرض أن أول جدار مرسوم غطى الأعمدة من 100 إلى 180، فتصبح القائمة مدى واحداً \[100، 180\]. ثم جاء جدار يغطي من 150 إلى 220، فترسم Doom الجزء الجديد فقط من 181 إلى 220، وتدمج المديين في \[100، 220\]. ثم جاء جدار من 120 إلى 200، فلا ترسم منه شيئاً لأنه داخل مدى مغلق بالكامل، ولا تحتاج حتى أن تحسب ارتفاعه في أي عمود. وحين يصبح في القائمة مدى واحد يغطي من 0 إلى آخر عمود فالشاشة ممتلئة، وكل صندوق بعد ذلك سوف يرفض. والمدى الواحد يحفظ في 8 بايتات مهما كان طوله، ولذلك تكفي 32 خانة لأن الجدران المتجاورة تندمج بسرعة.

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

## المختبر: نبني BSP ومرسماً بأنفسنا

الآن سوف نبني نسخة مبسطة من الفكرة بـ Python، دون أي مكتبة خارجية، والكود كله من صنعنا ولا يأخذ شيئاً من كود Doom ولا من خرائطها. والتبسيط في ثلاثة أشياء: كل الجدران صلبة بارتفاع واحد، فلا نوافذ ولا درجات، ولا خامات Textures، وإنما لون لكل كتلة يغمق مع المسافة، والأرض والسقف لون ثابت. وهذا يكفي لنقيس السؤال الأهم: كم جداراً يجب أن نفحص، وكم مرة نكتب كل عمود، في كل طريقة.

والملفات ثلاثة: bsp.py فيه الخريطة والباني والمرسمات، وrun.py يشغل التجارب ويطبع الأرقام، وdraw.py يحفظ الصور بصيغة PNG بكاتب صغير مكتوب داخله. وشغلنا التجارب في Container من python:3.13-alpine:

```bash
cd lab
for c in tree one many builders move; do
  docker run --rm -v "$PWD:/lab" -w /lab python:3.13-alpine python3 run.py $c > out-$c.txt
done
docker run --rm -v "$PWD:/lab" -w /lab python:3.13-alpine python3 draw.py
```

### الكود: bsp.py

وفيما يلي الملف كاملاً، وهو مقسم إلى خمسة أجزاء مرقمة في التعليقات:

```python
# bsp.py: our own small map, our own BSP builder and three ways to draw the walls,
# written for the ArabRoot article on how Doom drew its world. Pure Python, no packages.
# Nothing here comes from Doom's code or data; the map is generated below.
import math, random, time

EPS = 1e-6

# ---------------------------------------------------------------------------
# 1. The map: solid blocks (convex polygons, clockwise), every edge is a one-sided wall
#    whose front faces outward (the walkable side is on the left of each edge).
# ---------------------------------------------------------------------------
def rect(x0, y0, x1, y1):
    return [(x0, y0), (x0, y1), (x1, y1), (x1, y0)]          # clockwise with y up

def ngon(cx, cy, r, n, rot=0.0):
    return [(cx + r * math.cos(rot - 2 * math.pi * k / n), cy + r * math.sin(rot - 2 * math.pi * k / n)) for k in range(n)]

def make_map(rows, cols, seed=7, S=512, T=16, DOOR=128):
    rnd = random.Random(seed)
    W, H = cols * S, rows * S
    blocks = [rect(-T, -T, W + T, 0), rect(-T, H, W + T, H + T),          # outer walls, bottom and top
              rect(-T, 0, 0, H), rect(W, 0, W + T, H)]                    # left and right
    for i in range(1, rows):                                               # walls between room rows
        y = i * S
        for j in range(cols):
            x0, x1 = j * S, (j + 1) * S
            blocks += [rect(x0, y - T / 2, x0 + S / 2 - DOOR / 2, y + T / 2),
                       rect(x0 + S / 2 + DOOR / 2, y - T / 2, x1, y + T / 2)]
    for j in range(1, cols):                                               # walls between room columns
        x = j * S
        for i in range(rows):
            y0 = 0 if i == 0 else i * S + T / 2
            y1 = H if i == rows - 1 else (i + 1) * S - T / 2
            blocks += [rect(x - T / 2, y0, x + T / 2, i * S + S / 2 - DOOR / 2),
                       rect(x - T / 2, i * S + S / 2 + DOOR / 2, x + T / 2, y1)]
    for i in range(rows):                                                  # one pillar per room
        for j in range(cols):
            cx, cy = j * S + rnd.uniform(170, 342), i * S + rnd.uniform(170, 342)
            kind = rnd.choice(["square", "octagon", "triangle", "slab"])
            if kind == "square":
                h = rnd.uniform(32, 64); blocks.append(rect(cx - h, cy - h, cx + h, cy + h))
            elif kind == "octagon":
                blocks.append(ngon(cx, cy, rnd.uniform(40, 70), 8, rnd.uniform(0, 1)))
            elif kind == "triangle":
                blocks.append(ngon(cx, cy, rnd.uniform(50, 80), 3, rnd.uniform(0, 6.28)))
            else:                                                          # a thin slanted wall
                a, L = rnd.uniform(0, math.pi), rnd.uniform(70, 120)
                ux, uy, nx, ny = math.cos(a), math.sin(a), -math.sin(a) * 8, math.cos(a) * 8
                p = [(cx - ux * L - nx, cy - uy * L - ny), (cx - ux * L + nx, cy - uy * L + ny),
                     (cx + ux * L + nx, cy + uy * L + ny), (cx + ux * L - nx, cy + uy * L - ny)]
                if area(p) > 0: p.reverse()
                blocks.append(p)
    segs = []
    for b, poly in enumerate(blocks):
        for k in range(len(poly)):
            (x1, y1), (x2, y2) = poly[k], poly[(k + 1) % len(poly)]
            segs.append((x1, y1, x2, y2, b))                               # b = block id, used for colour
    return blocks, segs, (W, H)

def area(poly):
    return sum(poly[k][0] * poly[(k + 1) % len(poly)][1] - poly[(k + 1) % len(poly)][0] * poly[k][1] for k in range(len(poly))) / 2

def side(px, py, line):
    """> 0: point on the front (left) of the line, < 0: back. line = (x, y, dx, dy)."""
    x, y, dx, dy = line
    return dx * (py - y) - dy * (px - x)

# ---------------------------------------------------------------------------
# 2. The node builder: pick a seg, use its line to split the rest into front and back, repeat
#    until every leaf is convex (no seg hides another), which Doom calls a subsector.
# ---------------------------------------------------------------------------
class Node:
    __slots__ = ("line", "front", "back", "bbox", "box")      # bbox = (front child box, back child box)
class Leaf:
    __slots__ = ("segs", "box")

def bbox(segs):
    xs = [s[0] for s in segs] + [s[2] for s in segs]; ys = [s[1] for s in segs] + [s[3] for s in segs]
    return (min(xs), min(ys), max(xs), max(ys))

def classify(seg, line):
    """returns ('front'|'back'|'split', pieces)"""
    a = side(seg[0], seg[1], line); b = side(seg[2], seg[3], line)
    L = math.hypot(line[2], line[3]); a /= L; b /= L                       # distances in map units
    if abs(a) < EPS and abs(b) < EPS:                                      # on the line: same direction = front
        return ("front" if (seg[2] - seg[0]) * line[2] + (seg[3] - seg[1]) * line[3] > 0 else "back"), None
    if a > -EPS and b > -EPS: return "front", None
    if a < EPS and b < EPS: return "back", None
    t = a / (a - b)
    mx, my = seg[0] + t * (seg[2] - seg[0]), seg[1] + t * (seg[3] - seg[1])
    p1, p2 = (seg[0], seg[1], mx, my, seg[4]), (mx, my, seg[2], seg[3], seg[4])
    return "split", (p1, p2) if a > 0 else (p2, p1)                        # (front piece, back piece)

def line_of(s):
    return (s[0], s[1], s[2] - s[0], s[3] - s[1])

def is_convex(segs):
    """a leaf is ready when no seg has another seg (even partly) behind its line."""
    for s in segs:
        ln = line_of(s)
        for t in segs:
            if t is not s and classify(t, ln)[0] != "front": return False
    return True

def score(c, segs, split_cost=8):
    ln = line_of(c); f = b = sp = 0
    for t in segs:
        k = classify(t, ln)[0]
        if k == "front": f += 1
        elif k == "back": b += 1
        else: sp += 1
    if b + sp == 0: return None                                            # splits nothing off: useless
    return sp * split_cost + abs(f - b)

def choose(segs, method, rnd, sample=40):
    if method in ("first", "random"):
        order = list(segs) if method == "first" else rnd.sample(segs, len(segs))
        return next(c for c in order if score(c, segs) is not None)
    cands = segs if len(segs) <= sample else segs[:: len(segs) // sample]
    best, best_cost = None, None
    for c in cands:                                                        # cost = splits*8 + imbalance
        cost = score(c, segs)
        if cost is not None and (best_cost is None or cost < best_cost): best, best_cost = c, cost
    return best or next(c for c in segs if score(c, segs) is not None)

def build(segs, method="best", rnd=None, depth=0, info=None):
    info = info if info is not None else {"nodes": 0, "leaves": 0, "segs": 0, "depth": 0, "splits": 0}
    info["depth"] = max(info["depth"], depth)
    if is_convex(segs):
        leaf = Leaf(); leaf.segs = segs; leaf.box = bbox(segs)
        info["leaves"] += 1; info["segs"] += len(segs)
        return leaf, info
    split = choose(segs, method, rnd)
    ln = line_of(split); front, back = [], []
    for t in segs:
        k, pieces = classify(t, ln)
        if k == "front": front.append(t)
        elif k == "back": back.append(t)
        else: front.append(pieces[0]); back.append(pieces[1]); info["splits"] += 1
    node = Node(); node.line = ln
    node.front, _ = build(front, method, rnd, depth + 1, info)
    node.back, _ = build(back, method, rnd, depth + 1, info)
    node.bbox = (node.front.box, node.back.box)
    f, b = node.bbox
    node.box = (min(f[0], b[0]), min(f[1], b[1]), max(f[2], b[2]), max(f[3], b[3]))
    info["nodes"] += 1
    return node, info

# ---------------------------------------------------------------------------
# 3. The camera and projection: 90 degree field of view, W columns.
# ---------------------------------------------------------------------------
W, NEAR = 320, 1.0

class Cam:
    def __init__(self, x, y, ang):
        self.x, self.y, self.ang = x, y, ang
        self.fx, self.fy = math.cos(ang), math.sin(ang)                    # forward
        self.rx, self.ry = math.sin(ang), -math.cos(ang)                   # right

    def to_cam(self, px, py):
        dx, dy = px - self.x, py - self.y
        return dx * self.rx + dy * self.ry, dx * self.fx + dy * self.fy   # (x right, z forward)

def project(cam, seg):
    """front-facing seg -> (first column, last column, x1, z1, x2, z2) in camera space, or None."""
    if side(cam.x, cam.y, line_of(seg)) <= 0: return None                  # we see its back: cull
    x1, z1 = cam.to_cam(seg[0], seg[1]); x2, z2 = cam.to_cam(seg[2], seg[3])
    if z1 < NEAR and z2 < NEAR: return None                                # behind the camera
    if z1 < NEAR:                                                          # clip at the near plane
        t = (NEAR - z1) / (z2 - z1); x1, z1 = x1 + t * (x2 - x1), NEAR
    elif z2 < NEAR:
        t = (NEAR - z2) / (z1 - z2); x2, z2 = x2 + t * (x1 - x2), NEAR
    s1, s2 = W / 2 + x1 / z1 * (W / 2), W / 2 + x2 / z2 * (W / 2)
    lo, hi = min(s1, s2), max(s1, s2)
    c0, c1 = max(0, math.ceil(lo - 0.5)), min(W - 1, math.ceil(hi - 0.5) - 1)
    if c0 > c1: return None                                                # outside the view
    return c0, c1, x1, z1, x2, z2

def depth_at(c, p):
    _, _, x1, z1, x2, z2 = p
    u = (c + 0.5 - W / 2) / (W / 2)
    den = (x2 - x1) - u * (z2 - z1)
    if abs(den) < 1e-12: return min(z1, z2)
    t = (u * z1 - x1) / den
    return z1 + t * (z2 - z1)

# ---------------------------------------------------------------------------
# 4. Three renderers. Each fills col_seg / col_z (what is drawn in every column) and counts its work.
# ---------------------------------------------------------------------------
def new_counters():
    return {"nodes": 0, "leaves": 0, "segs_tested": 0, "segs_projected": 0, "col_writes": 0, "depth_tests": 0, "bbox_rejects": 0}

def render_bruteforce(cam, segs):
    """No BSP: every seg, a depth buffer per column (what you would do with a Z-buffer)."""
    n = new_counters(); col_seg = [None] * W; col_z = [math.inf] * W
    for s in segs:
        n["segs_tested"] += 1
        p = project(cam, s)
        if not p: continue
        n["segs_projected"] += 1
        for c in range(p[0], p[1] + 1):
            z = depth_at(c, p); n["depth_tests"] += 1
            if z < col_z[c]: col_z[c] = z; col_seg[c] = s; n["col_writes"] += 1
    return col_seg, col_z, n

def render_painter(cam, tree):
    """BSP back to front: far side first, every visible seg overwrites what is behind it."""
    n = new_counters(); col_seg = [None] * W; col_z = [math.inf] * W
    def walk(node):
        if isinstance(node, Leaf):
            n["leaves"] += 1
            for s in node.segs:
                n["segs_tested"] += 1
                p = project(cam, s)
                if not p: continue
                n["segs_projected"] += 1
                for c in range(p[0], p[1] + 1):
                    col_z[c] = depth_at(c, p); col_seg[c] = s; n["col_writes"] += 1
            return
        n["nodes"] += 1
        near, far = (node.front, node.back) if side(cam.x, cam.y, node.line) >= 0 else (node.back, node.front)
        walk(far); walk(near)
    walk(tree)
    return col_seg, col_z, n

def bbox_open(cam, box, closed):
    """like Doom's R_CheckBBox: can any still-open column see this box?"""
    x0, y0, x1, y1 = box
    if x0 - 1 <= cam.x <= x1 + 1 and y0 - 1 <= cam.y <= y1 + 1: return True
    angs = []
    for px, py in ((x0, y0), (x0, y1), (x1, y0), (x1, y1)):
        cx, cz = cam.to_cam(px, py)
        angs.append(math.atan2(cx, cz))
    a0, a1 = min(angs), max(angs)
    if a1 < -math.pi / 4 or a0 > math.pi / 4: return False                # outside the 90 degree view
    a0, a1 = max(a0, -math.pi / 4), min(a1, math.pi / 4)
    c0 = max(0, int(W / 2 + math.tan(a0) * W / 2) - 1); c1 = min(W - 1, int(W / 2 + math.tan(a1) * W / 2) + 1)
    return any(not closed[c] for c in range(c0, c1 + 1))

def render_front_to_back(cam, tree, use_bbox=True):
    """Doom's order: near side first, a column is drawn once and then closed (solid walls)."""
    n = new_counters(); col_seg = [None] * W; col_z = [math.inf] * W
    closed = bytearray(W); state = {"open": W}
    def walk(node):
        if state["open"] == 0 and use_bbox: return
        if isinstance(node, Leaf):
            n["leaves"] += 1
            for s in node.segs:
                n["segs_tested"] += 1
                p = project(cam, s)
                if not p: continue
                n["segs_projected"] += 1
                for c in range(p[0], p[1] + 1):
                    if not closed[c]:
                        col_z[c] = depth_at(c, p); col_seg[c] = s; n["col_writes"] += 1
                        closed[c] = 1; state["open"] -= 1
            return
        n["nodes"] += 1
        front_side = side(cam.x, cam.y, node.line) >= 0
        near, far = (node.front, node.back) if front_side else (node.back, node.front)
        far_box = node.bbox[1] if front_side else node.bbox[0]
        walk(near)
        if not use_bbox or bbox_open(cam, far_box, closed): walk(far)
        else: n["bbox_rejects"] += 1
    walk(tree)
    return col_seg, col_z, n

# ---------------------------------------------------------------------------
# 5. Cameras: random points in the walkable area, at least 12 units from any wall.
# ---------------------------------------------------------------------------
def inside(poly, x, y):
    return all(side(x, y, (poly[k][0], poly[k][1], poly[(k + 1) % len(poly)][0] - poly[k][0], poly[(k + 1) % len(poly)][1] - poly[k][1])) < 0
               for k in range(len(poly)))

def dist_seg(x, y, s):
    dx, dy = s[2] - s[0], s[3] - s[1]
    t = max(0, min(1, ((x - s[0]) * dx + (y - s[1]) * dy) / (dx * dx + dy * dy)))
    return math.hypot(x - s[0] - t * dx, y - s[1] - t * dy)

def cameras(blocks, segs, size, count, seed=1):
    rnd = random.Random(seed); out = []
    while len(out) < count:
        x, y = rnd.uniform(0, size[0]), rnd.uniform(0, size[1])
        if any(inside(b, x, y) for b in blocks): continue
        if min(dist_seg(x, y, s) for s in segs) < 12: continue
        out.append(Cam(x, y, rnd.uniform(0, 2 * math.pi)))
    return out
```

في الكود أعلاه لاحظ التالي:

- **الخريطة make\_map:** شبكة من الغرف بحجم 512 وحدة، بينها جدران سمكها 16 وفي وسط كل جدار باب عرضه 128، وفي كل غرفة عمود Pillar مختلف الشكل يختاره مولد أرقام عشوائية بقيمة ابتدائية Seed ثابتة: مربع أو مثمن أو مثلث أو جدار رفيع مائل. وكل كتلة مضلع Polygon مرتب مع عقارب الساعة، فيكون الخارج على يسار كل ضلع، وهو الوجه الذي يرى منه الجدار.
- **الدالة side:** كل الهندسة في الملف تقوم عليها. فهي حاصل الضرب الاتجاهي Cross Product بين اتجاه الخط والمتجه إلى النقطة، فإذا كان موجباً فالنقطة أمام الخط، وإذا كان سالباً فهي خلفه. وقد شرحنا المتجهات Vectors في [مقال رياضيات الألعاب](https://arabroot.io/articles/%D8%B1%D9%8A%D8%A7%D8%B6%D9%8A%D8%A7%D8%AA-%D8%A7%D9%84%D8%A7%D9%84%D8%B9%D8%A7%D8%A8-%D8%A7%D9%84%D9%85%D8%AA%D8%AC%D9%87%D8%A7%D8%AA-vectors-%D9%88%D8%A7%D9%84%D8%AD%D8%B1%D9%83%D8%A9-%D9%88%D8%A7%D9%84%D8%AA%D8%B5%D8%A7%D8%AF%D9%85/)، وهذه العملية نفسها هي التي تقوم بها R\_PointOnSide في Doom.
- **الدالة classify:** تضع كل جدار أمام خط التقسيم أو خلفه، فإذا قطعه الخط قسمته قطعتين عند نقطة التقاطع. والجدار الواقع على الخط نفسه يذهب إلى الأمام إذا كان في الاتجاه نفسه، وإلى الخلف إذا كان معاكساً.
- **الباني build:** يتوقف حين تصبح المنطقة محدبة، أي حين لا يقع أي جدار خلف خط جدار آخر، وهذا ما تفحصه is\_convex. وإلا اختار خط تقسيم بالدالة choose: يجرب حتى 40 مرشحاً، ويعطي كل واحد تكلفة: عدد الجدران التي سوف يقسمها في 8، زائد الفرق بين عدد الجدران في الجهتين، ويختار الأقل. والضرب في 8 يعني أن التقسيم أغلى بكثير من عدم التوازن، لأن كل تقسيم يزيد عدد الجدران في الشجرة إلى الأبد.
- **الإسقاط project:** يحذف الجدار إذا كانت الكاميرا خلفه Back-face Culling، ثم يحوله إلى إحداثيات الكاميرا، ويقصه عند المستوى القريب Near Plane، ثم يحسب أول عمود وآخر عمود يغطيهما من 320 عموداً، بزاوية رؤية 90 درجة.
- **المرسمات الثلاثة:** render\_bruteforce يفحص كل الجدران ويحتفظ بأقرب واحد لكل عمود، كما تفعل ذاكرة العمق. وrender\_painter يمر على الشجرة من البعيد إلى القريب ويكتب كل عمود من كل جدار، فيغطي القريب البعيد. وrender\_front\_to\_back يمر من القريب إلى البعيد، ويكتب العمود مرة واحدة ثم يغلقه، ولا يدخل الجهة البعيدة إلا إذا قالت bbox\_open إن صندوقها يغطي عموداً مفتوحاً، وهي مقابل R\_CheckBBox.
- **العدادات:** كل مرسم يعد العقد التي زارها، والأوراق، والجدران التي فحصها، والجدران التي أسقطها فعلاً لأنها في مجال الرؤية، وكتابات الأعمدة، واختبارات العمق، والصناديق التي تخطاها.

### كيف يصبح الجدار عموداً على الشاشة؟

قبل التجارب يحسن أن نفهم ما تفعله الدالة project، لأنها نفس الحساب الذي يجريه أي محرك من هذا النوع. فالجدار في الخريطة قطعة بين نقطتين، والدالة تحول كل نقطة إلى إحداثيات الكاميرا: x إلى يمين الكاميرا، وz المسافة أمامها. ثم تقسم x على z، وهذا هو الإسقاط المنظوري Perspective Projection كله: الشيء الذي على بعد ضعف المسافة يظهر بنصف الحجم. وبزاوية رؤية 90 درجة يكون نصف عرض الشاشة، أي 160 عموداً، هو ما يقابل x مساوية لـ z، فيصبح رقم العمود 160 زائد 160 في x على z. والارتفاع على الشاشة بالقاعدة نفسها: جدار ارتفاعه 128 وحدة على بعد 200 وحدة يظهر بارتفاع 128 في 160 على 200، أي 102 بكسل، وعلى بعد 400 وحدة 51 بكسلاً. وهذا يفسر لماذا تكفي Doom بعمود رأسي لكل جدار في كل عمود من الشاشة: كل نقاط الجدار في العمود الواحد على المسافة نفسها من العين، فيكفي حساب z مرة واحدة للعمود كله.

وهناك حالتان تحتاجان عناية. الأولى أن يكون طرف من الجدار خلف الكاميرا، فتصبح z سالبة والقسمة عليها تعطي عموداً في الجهة المعاكسة من الشاشة، ولذلك تقص الدالة الجدار عند مستوى قريب Near Plane على بعد وحدة واحدة قبل القسمة. والثانية أن ترى الجدار من ظهره، وفي عالم من كتل صلبة لا ترى ظهر أي جدار إلا إذا كان مخفياً خلف وجه آخر، فتحذفه الدالة مبكراً بسؤال side نفسه، وهذا وحده يحذف قرابة نصف الجدران في كل إطار.

### ملف التجارب: run.py

```python
# run.py: builds the BSP for three map sizes and measures the three renderers on the same cameras.
#   python3 run.py tree      -> the tree for the 2x2 map
#   python3 run.py one       -> one camera, the three renderers side by side
#   python3 run.py many      -> 300 cameras on 2x2, 4x4 and 8x8 maps
#   python3 run.py builders  -> what if the node builder picks badly, or we drop the bbox check
#   python3 run.py move      -> what a moving wall costs: rebuilding the tree
import math, random, sys, time, platform
from bsp import (make_map, build, cameras, Cam, render_bruteforce, render_painter, render_front_to_back, W)

def tree_info(rows, cols, method="best", seed=3):
    blocks, segs, size = make_map(rows, cols)
    t = time.perf_counter()
    tree, info = build(segs, method, random.Random(seed))
    info["build_ms"] = (time.perf_counter() - t) * 1000
    return blocks, segs, size, tree, info

def same_picture(a, b):
    """columns where two renderers disagree on the block or the depth (more than 0.001 units)."""
    bad = 0
    for c in range(W):
        sa, sb = a[0][c], b[0][c]
        if (sa is None) != (sb is None) or (sa and (sa[4] != sb[4] or abs(a[1][c] - b[1][c]) > 1e-3)): bad += 1
    return bad

def measure(cams, segs, tree, modes):
    tot = {m: {} for m in modes}; ms = {m: 0.0 for m in modes}; bad = {m: 0 for m in modes}
    for cam in cams:
        ref = None
        for m in modes:
            t = time.perf_counter()
            if m == "brute": out = render_bruteforce(cam, segs)
            elif m == "painter": out = render_painter(cam, tree)
            elif m == "f2b": out = render_front_to_back(cam, tree)
            else: out = render_front_to_back(cam, tree, use_bbox=False)
            ms[m] += (time.perf_counter() - t) * 1000
            for k, v in out[2].items(): tot[m][k] = tot[m].get(k, 0) + v
            if ref is None: ref = out
            else: bad[m] += same_picture(ref, out)
    n = len(cams)
    return {m: ({k: v / n for k, v in tot[m].items()}, ms[m] / n, bad[m]) for m in modes}

def show(res):
    print(f"  {'renderer':10} {'ms/frame':>9} {'nodes':>7} {'leaves':>7} {'segs tested':>12} {'projected':>10} {'col writes':>11} {'overdraw':>9} {'depth tests':>12} {'bbox skip':>10} {'diff cols':>10}")
    for m, (c, ms, bad) in res.items():
        print(f"  {m:10} {ms:9.2f} {c['nodes']:7.1f} {c['leaves']:7.1f} {c['segs_tested']:12.1f} {c['segs_projected']:10.1f}"
              f" {c['col_writes']:11.1f} {c['col_writes'] / W:9.2f} {c['depth_tests']:12.1f} {c['bbox_rejects']:10.1f} {bad:10}")

cmd = sys.argv[1] if len(sys.argv) > 1 else "many"
print(f"# Python {platform.python_version()} on {platform.machine()}, W = {W} columns, FOV 90")

if cmd == "tree":
    blocks, segs, size, tree, info = tree_info(2, 2)
    print(f"map 2x2: {len(blocks)} solid blocks, {len(segs)} segs, {size[0]}x{size[1]} units")
    print(f"tree: {info['nodes']} nodes, {info['leaves']} leaves (subsectors), {info['splits']} splits,"
          f" {info['segs']} segs after splitting, depth {info['depth']}, built in {info['build_ms']:.1f} ms")

if cmd == "one":
    blocks, segs, size, tree, info = tree_info(2, 2)
    cam = Cam(90, 120, math.radians(45))
    for name, out in (("brute", render_bruteforce(cam, segs)), ("painter", render_painter(cam, tree)),
                      ("f2b", render_front_to_back(cam, tree))):
        print(f"{name:8}", " ".join(f"{k}={v}" for k, v in out[2].items()))
    f = render_front_to_back(cam, tree)
    order = []
    for s in f[0]:
        if s and s[4] not in order: order.append(s[4])
    print("blocks seen (block ids, sorted):", sorted(set(s[4] for s in f[0] if s)))
    print("columns that differ: painter vs brute", same_picture(render_bruteforce(cam, segs), render_painter(cam, tree)),
          "| f2b vs brute", same_picture(render_bruteforce(cam, segs), f))

if cmd == "many":
    for rows, cols in ((2, 2), (4, 4), (8, 8)):
        blocks, segs, size, tree, info = tree_info(rows, cols)
        cams = cameras(blocks, segs, size, 300)
        print(f"\nmap {rows}x{cols}: {len(segs)} segs -> {info['segs']} after {info['splits']} splits,"
              f" {info['nodes']} nodes, {info['leaves']} leaves, depth {info['depth']}, build {info['build_ms']:.0f} ms, 300 cameras")
        show(measure(cams, segs, tree, ["brute", "painter", "f2b"]))

if cmd == "builders":
    for rows, cols in ((4, 4),):
        for method in ("best", "first", "random"):
            blocks, segs, size, tree, info = tree_info(rows, cols, method)
            cams = cameras(blocks, segs, size, 300)
            print(f"\n{rows}x{cols} builder={method}: {info['splits']} splits, {info['segs']} segs, {info['nodes']} nodes,"
                  f" {info['leaves']} leaves, depth {info['depth']}, build {info['build_ms']:.0f} ms")
            show(measure(cams, segs, tree, ["brute", "f2b"] + (["f2b-nobbox"] if method == "best" else [])))

if cmd == "move":
    blocks, segs, size, tree, info = tree_info(8, 8)
    print(f"8x8 map, {len(segs)} segs: full build {info['build_ms']:.0f} ms")
    moved = [(s[0] + 4, s[1], s[2] + 4, s[3], s[4]) if s[4] == len(blocks) - 1 else s for s in segs]   # slide the last pillar 4 units
    t = time.perf_counter(); build(moved, "best", random.Random(3)); ms = (time.perf_counter() - t) * 1000
    print(f"one pillar moved 4 units: rebuild {ms:.0f} ms = {ms / 16.7:.0f} frames at 60 fps")
```

ولاحظ في الدالة measure أن كل كاميرا ترسم بالطرق الثلاث، ثم تقارن same\_picture كل عمود بالطريقة الأولى: هل رسم الكتلة نفسها وبالعمق نفسه حتى جزء من الألف؟ وهذه المقارنة هي ضماننا أن الأرقام التي سوف نقرؤها لثلاث طرق ترسم الصورة نفسها بالضبط، لا لطريقة سريعة ترسم شيئاً آخر.

## التجربة الأولى: كيف تبدو الشجرة؟

```bash
python3 run.py tree
```

والمخرج سوف يكون كما يلي:

```text
# Python 3.13.16 on x86_64, W = 320 columns, FOV 90
map 2x2: 16 solid blocks, 64 segs, 1024x1024 units
tree: 50 nodes, 51 leaves (subsectors), 34 splits, 98 segs after splitting, depth 9, built in 65.3 ms
```

في المخرج أعلاه لاحظ التالي:

- الخريطة 2×2 أي أربع غرف، فيها 16 كتلة صلبة و64 جداراً، على مساحة 1024 في 1024 وحدة.
- بنى الباني 50 عقدة و51 ورقة، والعدد دائماً هكذا في الشجرة الثنائية: الأوراق تزيد عن العقد بواحد.
- خطوط التقسيم قطعت 34 جداراً، فصار في الشجرة 98 قطعة بدل 64، أي أكثر بنسبة 53%. وهذا هو الثمن الأول للشجرة: الجدران تتكاثر.
- العمق 9، أي أن أي ورقة على بعد تسعة أسئلة على الأكثر من الجذر.
- البناء أخذ 65 مللي ثانية لخريطة من 64 جداراً، وسوف نرى كيف يكبر هذا الرقم.

والشكل التالي يبين الخريطة نفسها من الأعلى كما رسمها draw.py، مع خطوط التقسيم ملونة حسب عمقها في الشجرة، والكاميرا التي سوف نستخدمها في التجربة التالية، وبجانبها ما تراه الكاميرا كما رسمه مرسمنا:

![على اليمين خريطة من الأعلى: أربع غرف بجدران ملونة وفي كل غرفة عمود بشكل مختلف، وخطوط تقسيم ملونة، أحمر يقسم الخريطة أفقياً في الوسط، وبرتقالي وأصفر وأزرق ورمادي أدق، ونقطة سوداء للكاميرا في الغرفة السفلى اليسرى مع خطي زاوية الرؤية. وعلى اليسار المشهد من عين الكاميرا: عمود سماوي كبير في الوسط وجدران ملونة خلفه وأرض بنية وسقف رمادي](https://arabroot.io/content/images/2026/11/doom-bsp-02-map.webp)

الخريطة 2×2 مع خطوط التقسيم من شجرتنا، وما تراه الكاميرا عند (90، 120) باتجاه 45 درجة.

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

## التجربة الثانية: كاميرا واحدة بالطرق الثلاث

```bash
python3 run.py one
```

والمخرج سوف يكون كما يلي:

```text
# Python 3.13.16 on x86_64, W = 320 columns, FOV 90
brute    nodes=0 leaves=0 segs_tested=64 segs_projected=24 col_writes=734 depth_tests=881 bbox_rejects=0
painter  nodes=50 leaves=51 segs_tested=98 segs_projected=37 col_writes=881 depth_tests=0 bbox_rejects=0
f2b      nodes=29 leaves=16 segs_tested=35 segs_projected=15 col_writes=320 depth_tests=0 bbox_rejects=14
blocks seen (block ids, sorted): [1, 4, 5, 8, 11, 12, 13, 14]
columns that differ: painter vs brute 0 | f2b vs brute 0
```

في المخرج أعلاه لاحظ التالي:

- **الطريقة دون BSP** فحصت الجدران الـ 64 كلها، وأسقطت 24 منها لأنها في مجال الرؤية ووجهها نحو الكاميرا، وأجرت 881 اختبار عمق، وكتبت 734 مرة لأن كل جدار أقرب مما سبقه في عموده يكتب فوقه.
- **خوارزمية الرسام** زارت الشجرة كلها، 50 عقدة و51 ورقة، وفحصت القطع الـ 98، وكتبت 881 مرة على شاشة من 320 عموداً، أي أن كل عمود كتب 2.75 مرة في المتوسط. ولاحظ أن 881 هو نفسه عدد اختبارات العمق في الطريقة الأولى، وهذا منطقي لأن الاثنتين تمران على كل عمود من كل جدار مرئي، والفرق فقط هل تقارن قبل أن تكتب أم تكتب دائماً.
- **من القريب إلى البعيد** زارت 29 عقدة و16 ورقة فقط، وفحصت 35 قطعة، وأسقطت 15، وكتبت 320 مرة بالضبط، أي كل عمود مرة واحدة. وتخطت 14 صندوقاً لأن كل أعمدتها كانت مغلقة.
- والسطر الأخير هو الأهم: الأعمدة المختلفة بين الطرق صفر، أي أن الثلاث رسمت الكتلة نفسها بالعمق نفسه في كل عمود من الأعمدة الـ 320.

والشكل التالي يبين ماذا يعني ذلك على الشاشة. فقد حفظ draw.py الصورة بعد عدد من الجدران في كل ترتيب، والأسود هو الأعمدة التي لم ترسم بعد:

![صفان من أربع صور: في الأول من القريب إلى البعيد يظهر العمود السماوي القريب أولاً وحوله أسود، ثم تملأ الجدران الأعمدة السوداء حتى يبقى القليل بعد 7 جدران، وفي الثاني خوارزمية الرسام تبدأ بجدران بعيدة صغيرة ثم تغطيها جدران أقرب حتى الصورة النهائية بعد 881 كتابة، وتحتهما رسم بياني أحمر لعدد كتابات كل عمود يصل إلى 6 في الوسط](https://arabroot.io/content/images/2026/11/doom-bsp-03-order.webp)

من القريب إلى البعيد: العمود السماوي القريب أولاً، وكل عمود يرسم مرة. والرسام: البعيد أولاً ثم يغطى، وبعض الأعمدة كتب 6 مرات.

والصفان يحكيان القصة كاملة. في الأول يظهر العمود السماوي القريب من أول جدار، فيغلق 74 عموداً من 320، وبعد سبعة جدران مرئية صار 254 عموداً مغلقاً، والباقي يمتلئ تدريجياً، ولا يكتب أي عمود مرتين. وفي الثاني يرسم الرسام أولاً جدراناً بعيدة صغيرة سوف تختفي كلها تقريباً، فبعد 21 جداراً تكون الشاشة ممتلئة وقد كتب 475 مرة، ثم يكمل حتى 881 كتابة لأن كل جدار أقرب يمسح ما تحته. والرسم البياني في الأسفل يعد الكتابات لكل عمود: 22 عموداً فقط كتبت مرة واحدة، و123 مرتين، و109 ثلاث مرات، والأعمدة في الوسط خلف العمود السماوي كتبت حتى 6 مرات، كما في آخر سطر من مخرج draw.py:

```text
f2b: after 1 visible walls, 74 of 320 columns drawn, 74 column writes
f2b: after 3 visible walls, 171 of 320 columns drawn, 171 column writes
f2b: after 5 visible walls, 221 of 320 columns drawn, 221 column writes
f2b: after 7 visible walls, 254 of 320 columns drawn, 254 column writes
f2b: 37 walls drew, 320 column writes, max 1 on one column
painter: after 5 visible walls, 87 of 320 columns drawn, 88 column writes
painter: after 12 visible walls, 224 of 320 columns drawn, 256 column writes
painter: after 21 visible walls, 320 of 320 columns drawn, 475 column writes
painter: 37 walls drew, 881 column writes, max 6 on one column
overdraw per column: {1: 22, 2: 123, 3: 109, 4: 49, 5: 12, 6: 5}
```

ولاحظ في هذا المخرج أن سطر f2b يقول إن 37 جداراً رسمت، بينما قال المرسم في التجربة السابقة إنه أسقط 15 فقط. والفرق أن draw.py يمر على الشجرة كلها ليصنع الصور المتتالية، دون فحص الصناديق، أما المرسم الحقيقي فتوقف عن دخول الصناديق المخفية. والجدران الـ 22 الزائدة لم تكتب أي عمود لأن أعمدتها كانت مغلقة، أي أنها عمل بلا نتيجة، وهذا بالضبط ما يوفره فحص الصناديق كما سوف نقيس.

## التجربة الثالثة: 300 كاميرا على ثلاثة أحجام

كاميرا واحدة قد تكون حالة خاصة، ولذلك يضع run.py في كل خريطة 300 كاميرا عشوائية في الأماكن المفتوحة، على بعد 12 وحدة على الأقل من أي جدار وباتجاهات عشوائية، ويرسم من كل واحدة بالطرق الثلاث، على خرائط 2×2 و4×4 و8×8 غرف:

```bash
python3 run.py many
```

```text
# Python 3.13.16 on x86_64, W = 320 columns, FOV 90

map 2x2: 64 segs -> 98 after 34 splits, 50 nodes, 51 leaves, depth 9, build 75 ms, 300 cameras
  renderer    ms/frame   nodes  leaves  segs tested  projected  col writes  overdraw  depth tests  bbox skip  diff cols
  brute           3.58     0.0     0.0         64.0        8.0       512.7      1.60        552.0        0.0          0
  painter         3.55    50.0    51.0         98.0       14.8       552.0      1.73          0.0        0.0          0
  f2b             3.42    18.9     8.6         21.1        8.3       320.0      1.00          0.0       11.2          0

map 4x4: 275 segs -> 398 after 123 splits, 210 nodes, 211 leaves, depth 11, build 407 ms, 300 cameras
  renderer    ms/frame   nodes  leaves  segs tested  projected  col writes  overdraw  depth tests  bbox skip  diff cols
  brute           8.15     0.0     0.0        275.0       37.7       739.4      2.31       1006.8        0.0          0
  painter         9.91   210.0   211.0        398.0       56.3      1006.8      3.15          0.0        0.0          0
  f2b             4.30    36.7    16.3         34.4       13.3       320.0      1.00          0.0       21.3          0

map 8x8: 1225 segs -> 1674 after 449 splits, 850 nodes, 851 leaves, depth 15, build 2663 ms, 300 cameras
  renderer    ms/frame   nodes  leaves  segs tested  projected  col writes  overdraw  depth tests  bbox skip  diff cols
  brute          19.25     0.0     0.0       1225.0      153.1       987.8      3.09       1795.5        0.0          0
  painter        28.54   850.0   851.0       1674.0      198.4      1795.5      5.61          0.0        0.0          0
  f2b             6.12    59.1    25.5         55.1       19.9       320.0      1.00          0.0       34.6          0
```

في المخرج أعلاه لاحظ التالي:

- **الطريقة دون BSP** تفحص كل الجدران دائماً: 64 ثم 275 ثم 1,225، أي أن العمل يكبر مع الخريطة كلها، والزمن من 3.6 إلى 19.3 مللي ثانية للإطار.
- **خوارزمية الرسام** أسوأ من ذلك، لأنها تزور الشجرة كلها وفيها قطع أكثر من الجدران الأصلية: 1,674 قطعة في الخريطة الكبيرة، والرسم الزائد يرتفع من 1.73 إلى 5.61، أي أن كل عمود يكتب أكثر من خمس مرات في المتوسط، والزمن 28.5 مللي ثانية.
- **من القريب إلى البعيد** تفحص 21 ثم 34 ثم 55 قطعة فقط، رغم أن الخريطة كبرت 19 مرة، وتكتب 320 عموداً بالضبط في كل الحالات، والرسم الزائد 1.00 دائماً، والزمن 6.1 مللي ثانية في الخريطة الكبيرة، أي أسرع بثلاث مرات من الطريقة دون BSP وبأربع مرات ونصف من الرسام.
- عمود diff cols صفر في كل الصفوف، أي أن الطرق الثلاث رسمت الصورة نفسها في 900 إطار.

![ثلاثة رسوم بيانية بأعمدة رمادية وبرتقالية وزرقاء لثلاث خرائط: الجدران المفحوصة لكل إطار حيث يرتفع الرمادي إلى 1,225 والبرتقالي إلى 1,674 ويبقى الأزرق بين 21 و55، وكتابات الأعمدة حيث يبقى الأزرق 320 ويرتفع البرتقالي إلى 1,796، والزمن بالمللي ثانية حيث يصل البرتقالي إلى 28.5 والرمادي 19.3 والأزرق 6.1](https://arabroot.io/content/images/2026/11/doom-bsp-04-results.webp)

متوسط 300 كاميرا لكل خريطة: الرسم من القريب إلى البعيد يبقى قريباً من الثابت مهما كبرت الخريطة.

وقد يتساءل البعض: لماذا لم تكن من القريب إلى البعيد أسرع بكثير في الخريطة الصغيرة، 3.4 مقابل 3.6 مللي ثانية؟ والإجابة أن فحص الصناديق نفسه له تكلفة، ففي كل صندوق نحسب زوايا أربع زوايا ونمر على الأعمدة في مداها، وفي خريطة من 64 جداراً لا يوجد ما يكفي من العمل المخفي لتعوض هذه التكلفة. ولكن كلما كبرت الخريطة صار ما توفره الشجرة أكبر بكثير مما تكلفه، وهذه هي الحالة التي صممت لها Doom، فمستوياتها فيها مئات الجدران، واللاعب لا يرى إلا جزءاً صغيراً منها في أي لحظة.

📌

الأزمنة في هذا المقال من Python على جهاز مشترك، ورأينا أنها تتغير بين تشغيل وآخر بحسب ما يعمل على الجهاز، فقد أعطت الخريطة 4×4 في تشغيل آخر 5.4 مللي ثانية للطريقة دون BSP بدل 8.2\. أما العدادات، أي عدد الجدران والعقد والكتابات، فهي ثابتة تماماً بين التشغيلات لأن الكاميرات والخرائط مولدة بقيمة ابتدائية ثابتة. ولذلك اعتمد على العدادات لتقارن الطرق، وعلى الأزمنة لترى الاتجاه فقط.

## ماذا لو اختار الباني خطوط التقسيم بشكل سيئ؟

دالة التكلفة في الباني ليست تفصيلاً، وفي هذه التجربة نبني شجرة الخريطة 4×4 بثلاث طرق: بالتكلفة كما رأينا، وبأخذ أول جدار يصلح دائماً، وبجدار عشوائي:

```bash
python3 run.py builders
```

```text
# Python 3.13.16 on x86_64, W = 320 columns, FOV 90

4x4 builder=best: 123 splits, 398 segs, 210 nodes, 211 leaves, depth 11, build 409 ms
  renderer    ms/frame   nodes  leaves  segs tested  projected  col writes  overdraw  depth tests  bbox skip  diff cols
  brute           5.37     0.0     0.0        275.0       37.7       739.4      2.31       1006.8        0.0          0
  f2b             2.82    36.7    16.3         34.4       13.3       320.0      1.00          0.0       21.3          0
  f2b-nobbox      5.00   210.0   211.0        398.0       56.3       320.0      1.00          0.0        0.0          0

4x4 builder=first: 163 splits, 438 segs, 210 nodes, 211 leaves, depth 26, build 113 ms
  renderer    ms/frame   nodes  leaves  segs tested  projected  col writes  overdraw  depth tests  bbox skip  diff cols
  brute           7.78     0.0     0.0        275.0       37.7       739.4      2.31       1006.8        0.0          0
  f2b             6.17    46.3    17.0         39.2       14.8       320.0      1.00          0.0       30.3          0

4x4 builder=random: 185 splits, 460 segs, 226 nodes, 227 leaves, depth 15, build 99 ms
  renderer    ms/frame   nodes  leaves  segs tested  projected  col writes  overdraw  depth tests  bbox skip  diff cols
  brute           7.71     0.0     0.0        275.0       37.7       739.4      2.31       1006.8        0.0          0
  f2b             5.59    42.6    18.5         45.4       15.4       320.0      1.00          0.0       25.0          0
```

في المخرج أعلاه لاحظ التالي:

- **الباني بالتكلفة** قسم 123 جداراً وأعطى شجرة بعمق 11.
- **أول جدار** قسم 163 جداراً، أي 33% أكثر، والأسوأ أن العمق صار 26، أي أكثر من الضعف، لأن أول جدار في القائمة غالباً جدار خارجي على حافة الخريطة يقسم جزءاً صغيراً فقط منها. والمرسم من القريب إلى البعيد زار 46.3 عقدة بدل 36.7، وفحص 39.2 قطعة بدل 34.4.
- **الجدار العشوائي** قسم 185 جداراً، أي 50% أكثر، وعمقه 15، وفحص 45.4 قطعة.
- والصورة نفسها في كل الحالات، فالكتابات 320 وdiff cols صفر. أي أن الشجرة السيئة لا تعطي صورة خاطئة، وإنما تعطي عملاً أكثر في كل إطار، إلى الأبد، لأن الشجرة تبنى مرة وتستخدم ملايين المرات.

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

### وماذا لو حذفنا فحص الصناديق؟

في السطر f2b-nobbox من التجربة نفسها رسمنا من القريب إلى البعيد ولكن دون R\_CheckBBox، أي ندخل الجهة البعيدة دائماً، وكل ما نوفره هو إغلاق الأعمدة. والنتيجة: زار المرسم الشجرة كلها، 210 عقدة و211 ورقة، وفحص 398 قطعة، أي القطع كلها، رغم أنه كتب 320 عموداً فقط. وزمنه 5.0 مللي ثانية مقابل 2.8 مع الفحص. أي أن نصف الفائدة تقريباً يأتي من الترتيب وإغلاق الأعمدة، والنصف الآخر من القدرة على عدم زيارة ما لا يرى أصلاً، وكلاهما يحتاج الشجرة.

## ماذا لو تحرك جدار؟

```bash
python3 run.py move
```

```text
# Python 3.13.16 on x86_64, W = 320 columns, FOV 90
8x8 map, 1225 segs: full build 2390 ms
one pillar moved 4 units: rebuild 2371 ms = 142 frames at 60 fps
```

حركنا عموداً واحداً في الخريطة الكبيرة أربع وحدات فقط، فاحتاجت الشجرة إعادة بناء كاملة أخذت 2,371 مللي ثانية، أي ما يعادل 142 إطاراً بسرعة 60 إطاراً في الثانية. وباني Python أبطأ بكثير من أداة مكتوبة بلغة C، ولكن الفكرة لا تتغير: الشجرة لا تتحمل أن يتحرك شيء من الأعلى، ولهذا كانت كل الحركة في Doom رأسية: أبواب ترتفع، وأرضيات تنزل، ومصاعد، كلها تغير الارتفاع لا الخطوط. أما الأعداء والأشياء المتحركة فليست جدراناً أصلاً، وإنما صور مسطحة Sprites ترسم بعد الجدران، كما سوف نرى.

## ما تفعله Doom الحقيقية بعد الجدران

مرسمنا يتوقف عند الجدران الصلبة، أما Doom فتكمل في كل إطار بخطوتين أخريين، والشكل التالي يلخص الإطار كما تجده في الكود المصدري:

![ثلاثة صناديق متتالية: الجدران من القريب إلى البعيد مع أسماء R_RenderBSPNode وR_CheckBBox وsolidsegs، ثم الأرض والسقف Visplanes مع MAXVISPLANES = 128، ثم الشخصيات Sprites من البعيد إلى القريب، وتحتها شريط لعدد بالنقطة الثابتة 16 بتاً للجزء الصحيح و16 للكسر، وأن 1.5 يخزن كعدد صحيح 98,304](https://arabroot.io/content/images/2026/11/doom-bsp-05-doom.webp)

الإطار في Doom: الجدران أولاً من القريب إلى البعيد، ثم الأرض والسقف، ثم الشخصيات من البعيد إلى القريب، وكل الأرقام بالنقطة الثابتة.

### النوافذ والدرجات: جدران لا تغلق العمود

مرسمنا يفترض أن كل جدار صلب من الأرض إلى السقف، ولكن خرائط Doom مليئة بخطوط لها جهتان: حافة درجة، أو نافذة بين غرفتين، أو فتحة في سور منخفض، وهذه ترسم جزءاً من العمود فقط، الجزء العلوي أو السفلي، وترى من خلالها ما وراءها. ولذلك يوجد في r\_bsp.c بجانب R\_ClipSolidWallSegment دالة ثانية هي R\_ClipPassWallSegment، تكتب الجزء المرئي من هذه الخطوط دون أن تضيف أعمدتها إلى قائمة الأعمدة المغلقة، فيستمر المرور على الشجرة ليرسم ما خلفها. وتحفظ Doom لكل عمود حدين، أعلى وأدنى ما بقي مفتوحاً، وكل درجة أو نافذة تضيق هذين الحدين، فيرسم ما خلفها في الفتحة الباقية فقط. وهذا يعني أن المستوى المليء بالنوافذ والدرجات المفتوحة على مساحات واسعة يكلف أكثر بكثير من ممرات مغلقة، لأن الأعمدة تتأخر في الإغلاق، والصناديق البعيدة تبقى مرئية، وهذا ما يجعل الساحات المفتوحة في خرائط Doom أبطأ من الممرات على الأجهزة القديمة.

### الأرض والسقف: Visplanes

حين ترسم Doom جداراً في عمود، تعرف أين ينتهي من الأعلى ومن الأسفل، والفراغ فوقه وتحته هو سقف وأرض. فتسجل هذه الفراغات في هياكل تسمى Visplanes، كل واحدة منها سطح أفقي له ارتفاع وخامة ومستوى إضاءة واحد، ثم بعد انتهاء الجدران ترسم كل Visplane أفقياً سطراً بسطر، لأن الأرض المسطحة على مسافة ثابتة من العين في السطر الأفقي الواحد، وهذا يجعل رسمها رخيصاً. وفي ملف [r\_plane.c](https://github.com/id-Software/DOOM/blob/master/linuxdoom-1.10/r%5Fplane.c?ref=arabroot.io) تجد عددها محدوداً بالسطر `#define MAXVISPLANES 128`، وتذكر صفحة محرك Doom أن تجاوز هذا الحد في مستوى معقد كان يوقف اللعبة بخطأ «visplane overflow»، وهو خطأ تعرفه أجيال من صانعي الخرائط.

### الشخصيات والأشياء

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

### لماذا لا توجد غرفة فوق غرفة؟

الشجرة تقسم الخريطة من الأعلى، أي في بعدين فقط، وكل منطقة فيها لها أرض واحدة وسقف واحد. وبالتالي لا يمكن أن تكون غرفة فوق غرفة في المكان نفسه من الخريطة، لأن نقطة واحدة من الأعلى لا يمكن أن تكون في منطقتين. وتذكر صفحة محرك Doom أن ذلك غير ممكن لأن المستويات ثنائية الأبعاد في الحقيقة، ولذلك يسمى هذا الأسلوب 2.5D. ومن هنا جاء القيد الآخر: لا يمكن النظر للأعلى والأسفل بشكل صحيح، لأن الجدران ترسم دائماً كأعمدة رأسية، وهي تبقى رأسية فقط ما دامت الكاميرا أفقية. وما بدا للاعب عالماً ثلاثي الأبعاد كان في الحقيقة خريطة مسطحة مع ارتفاعات، وهذا القيد هو الذي جعل الرسم ممكناً على معالج 486.

### الأرقام بالنقطة الثابتة Fixed Point

بقيت حيلة أخيرة مخفية في كل سطر من المحرك: Doom لا تستخدم الأعداد العشرية Floating Point تقريباً. فكثير من معالجات 386 و486SX في البيوت لم يكن فيها وحدة للحساب العشري FPU، وحتى حين وجدت كانت أبطأ من الحساب بالأعداد الصحيحة. ولذلك عرف المحرك نوعاً اسمه fixed\_t في ملف [m\_fixed.c](https://github.com/id-Software/DOOM/blob/master/linuxdoom-1.10/m%5Ffixed.c?ref=arabroot.io) وملف الترويسة المرافق: عدد صحيح من 32 بتاً، أعلى 16 بتاً منه هي الجزء الصحيح، وأدنى 16 بتاً هي الكسر بوحدات 1 على 65,536\. فالعدد 1.5 يخزن كعدد صحيح 98,304، والجمع والطرح عمليات أعداد صحيحة عادية، والضرب ضرب عادي ثم إزاحة 16 بتاً إلى اليمين، وهذا ما تفعله الدالة FixedMul. وقد شرحنا في [مقال الأرقام العشرية Floating Point](https://arabroot.io/articles/%D8%A7%D9%84%D8%A3%D8%B1%D9%82%D8%A7%D9%85-%D8%A7%D9%84%D8%B9%D8%B4%D8%B1%D9%8A%D8%A9-floating-point-%D9%85%D9%86-%D8%A7%D9%84%D8%AF%D8%A7%D8%AE%D9%84/) كيف تخزن الأعداد العشرية، والنقطة الثابتة هي البديل الأبسط: دقة ثابتة في كل مكان، وسرعة الأعداد الصحيحة، والثمن مدى أصغر وخطر الفيض Overflow حين تضرب عددين كبيرين.

## الأخطاء التي تتكرر

- **اختيار خط التقسيم دون تكلفة:** رأينا أن أول جدار يعطي عمقاً 26 بدل 11، والعشوائي يقسم 50% جدراناً أكثر. قس الشجرة بعدد التقسيمات والعمق قبل أن تقيس سرعة الرسم.
- **حذف فحص الصناديق:** المرسم من القريب إلى البعيد دونه يرسم صورة صحيحة ولكنه يزور الشجرة كلها، فيضيع نصف الفائدة.
- **الخلط بين وجه الجدار وظهره:** إذا رتبت أضلاع الكتل بالاتجاه الخاطئ صارت كل الجدران تواجه الداخل، فيحذفها فحص الوجه الخلفي كلها وترى أرضاً وسقفاً فقط. اجعل ترتيب الأضلاع قاعدة واحدة في كل الخريطة، واختبرها بكاميرا واحدة قبل أي شيء.
- **الوثوق بالسرعة دون التحقق من الصورة:** المرسم السريع الذي يرسم صورة مختلفة ليس مرسماً أسرع، وإنما مرسم خاطئ. قارن كل طريقة جديدة بطريقة بسيطة مضمونة، عموداً بعمود، كما تفعل same\_picture.
- **قياس الأداء بالزمن وحده:** الأزمنة في Python على جهاز مشترك تغيرت بين التشغيلات، والعدادات لم تتغير. عد العمل أولاً، ثم قس الزمن.
- **تحريك الجدران في عالم مبني على BSP:** كل حركة من الأعلى تعني إعادة بناء، وفي خريطتنا الكبيرة أخذت 142 إطاراً. إذا احتجت جداراً يتحرك فاجعله شيئاً منفصلاً عن الشجرة.

## أي طريقة تناسب أي عالم؟ جدول قرار Decision Table

| الطريقة                              | ما قسناه في خريطة 1,225 جداراً | تحتاج                                   | تناسب                                                         |
| ------------------------------------ | ------------------------------ | --------------------------------------- | ------------------------------------------------------------- |
| كل الجدران مع عمق لكل عمود           | 1,225 جداراً و3.09 رسم زائد    | ذاكرة عمق، ولا معالجة مسبقة             | شرائح الرسوم الحديثة التي تفعل ذلك بالعتاد، والعوالم المتغيرة |
| BSP بخوارزمية الرسام                 | 1,674 قطعة و5.61 رسم زائد      | شجرة مبنية مسبقاً                       | الأشياء الشفافة القليلة، أو حين تحتاج الترتيب فقط             |
| BSP من القريب إلى البعيد مع الصناديق | 55 قطعة ورسم زائد 1.00         | شجرة مبنية مسبقاً، وعالم ثابت من الأعلى | الرسم البرمجي Software Rendering للعوالم الثابتة، كما في Doom |
| شبكة مربعات مع شعاع لكل عمود         | لم نقسه هنا                    | جدران على شبكة بزوايا قائمة             | عوالم بسيطة مثل Wolfenstein 3D                                |

## ماذا يبقى من BSP اليوم؟

شرائح الرسوم اليوم ترسم ملايين المثلثات مع ذاكرة عمق في العتاد، فلم يعد ترتيب الجدران مشكلة الرسم الأولى كما كان على معالج 486، وهذا ما رأيناه في [مقال أساسيات الألعاب ثلاثية الأبعاد](https://arabroot.io/articles/%D8%A7%D8%B3%D8%A7%D8%B3%D9%8A%D8%A7%D8%AA-3d-%D9%81%D9%8A-%D8%A7%D9%84%D8%A7%D9%84%D8%B9%D8%A7%D8%A8-%D8%A7%D9%84%D9%85%D8%AC%D8%B3%D9%85%D8%A7%D8%AA-meshes-%D9%88%D8%A7%D9%84%D8%AE%D8%A7%D9%85%D8%A7%D8%AA-%D9%88%D8%A7%D9%84%D8%A7%D8%B6%D8%A7%D8%A1%D8%A9/). ولكن الفكرة الأعمق في Doom ما زالت في كل محرك: لا ترسل إلى الرسم ما لا يراه اللاعب. فالمحركات تقسم العالم مسبقاً بأشجار مثل BVH وOctree، وتحذف ما خارج مجال الرؤية Frustum Culling، وما خلف غيره Occlusion Culling، وتحسب مسبقاً من يرى من في المستويات الثابتة. وكلها الفكرة نفسها: اعمل مرة قبل اللعب، ووفر في كل إطار.

والدرس الثاني الذي يتجاوز الألعاب أن أفضل تحسين كثيراً ما يكون نقل العمل من وقت التشغيل إلى وقت البناء. فالشجرة كلفت 2.4 ثانية في Python لخريطة كبيرة، ولكنها جعلت كل إطار يفحص 55 قطعة بدل 1,225، وهذا يشبه الفهرس Index في قواعد البيانات، الذي تدفع ثمنه عند الكتابة لتربح عند كل قراءة، وقد شرحنا الأشجار وفهارسها في [مقال هياكل البيانات](https://arabroot.io/articles/%D9%87%D9%8A%D8%A7%D9%83%D9%84-%D8%A7%D9%84%D8%A8%D9%8A%D8%A7%D9%86%D8%A7%D8%AA-%D9%84%D9%84%D9%85%D8%A8%D8%AA%D8%AF%D8%A6%D9%8A%D9%86/).

## تطبيق عملي

1. غير قيمة split\_cost في الدالة score من 8 إلى 1 ثم إلى 50، وأعد تجربة builders، وسجل عدد التقسيمات والعمق وعدد القطع المفحوصة في كل مرة. أين التوازن الأفضل لخريطتنا؟
2. أضف إلى render\_front\_to\_back توقفاً صريحاً حين تغلق كل الأعمدة الـ 320، وقارن عدد العقد المزورة مع فحص الصناديق ودونه.
3. بدل مصفوفة closed، احفظ الأعمدة المغلقة كقائمة مدى Ranges كما تفعل solidsegs في Doom، وقس كم مدى تحتاج في أسوأ كاميرا من الكاميرات الـ 300\. هل يكفي 32؟
4. اكتب دالة FixedMul بـ Python تضرب عددين بصيغة 16.16 وتعيد النتيجة بالصيغة نفسها، ثم جرب ضرب 300.0 في 300.0، ولاحظ ماذا يحدث لعدد صحيح من 32 بتاً.

## الخلاصة Summary

- شجرة BSP تقسم الخريطة بخطوط الجدران مرة واحدة قبل اللعب، وتعطي في كل إطار ترتيب الجدران من موقع الكاميرا وحده، بسؤال واحد عند كل عقدة: في أي جهة أنا؟
- Doom ترسم الجدران من القريب إلى البعيد، فكل عمود يرسم مرة ثم يغلق، والصناديق المخفية لا تزار: في خريطتنا الكبيرة فحص هذا المرسم 55 قطعة بدل 1,225، وكتب 320 عموداً بدل 1,796 عند الرسام، والصور متطابقة في 900 إطار.
- الشجرة لها ثمن: الجدران تتكاثر بالتقسيم، 64 صارت 98 و1,225 صارت 1,674، وجودة الباني تغير العمل في كل إطار، وأي حركة من الأعلى تعني إعادة البناء.
- القيود التي يتذكرها اللاعبون هي الوجه الآخر للحيلة: لا غرفة فوق غرفة، ولا نظر حقيقي للأعلى، وحد للـ Visplanes، والأبواب ترتفع ولا تدور.
- وتحت كل ذلك أعداد بالنقطة الثابتة 16.16 بدل الأعداد العشرية، لأن الحساب بالأعداد الصحيحة كان أسرع وأضمن على حواسيب تلك الفترة.

وفي المقال التالي من هذه المرحلة نصل إلى محرك جاء بعد Doom بست سنوات، وإلى حيلة صغيرة فيه صارت أشهر سطر في تاريخ برمجة الألعاب: الجذر التربيعي العكسي السريع في Quake III:

[![](https://arabroot.io/content/images/2026/11/fast-inverse-sqrt-cover-cover.webp)دليلالجذر التربيعي العكسي السريع في Quake IIIنفك حيلة 0x5f3759df في Quake III ونرى لماذا تعمل، ثم نقيس خطأها على كل عدد float موجب ونبحث عن أفضل ثابت ونقارن سرعتها بأمر rsqrtss.](https://arabroot.io/articles/%D8%A7%D9%84%D8%AC%D8%B0%D8%B1-%D8%A7%D9%84%D8%AA%D8%B1%D8%A8%D9%8A%D8%B9%D9%8A-%D8%A7%D9%84%D8%B9%D9%83%D8%B3%D9%8A-%D8%A7%D9%84%D8%B3%D8%B1%D9%8A%D8%B9-%D9%81%D9%8A-quake-iii-0x5f3759df/)[![](https://arabroot.io/content/images/2026/11/sprite-flicker-limits-cover-cover.webp)دليللماذا كانت الشخصيات ترمش؟ حدود رسوميات NESنشرح لماذا لا يرسم جهاز NES أكثر من ثماني شخصيات في السطر، ونكتب ROM صغيراً يزدحم عمداً ونقيس في FCEUX أي طريقة رمش توزع الاختفاء بعدل.](https://arabroot.io/articles/%D9%84%D9%85%D8%A7%D8%B0%D8%A7-%D9%83%D8%A7%D9%86%D8%AA-%D8%A7%D9%84%D8%B4%D8%AE%D8%B5%D9%8A%D8%A7%D8%AA-%D8%AA%D8%B1%D9%85%D8%B4-%D8%AD%D8%AF%D9%88%D8%AF-%D8%B1%D8%B3%D9%88%D9%85%D9%8A%D8%A7%D8%AA-nes/)[![](https://arabroot.io/content/images/2026/11/game-math-cover-cover.webp)دليلرياضيات الألعاب: المتجهات Vectors والحركة والتصادمالمتجهات والحركة وحاصل الضرب النقطي واختبارات التصادم والارتداد والنفق، بلعبة صغيرة ومختبر Python يصنع الأخطاء الشائعة ثم يصلحها.](https://arabroot.io/articles/%D8%B1%D9%8A%D8%A7%D8%B6%D9%8A%D8%A7%D8%AA-%D8%A7%D9%84%D8%A7%D9%84%D8%B9%D8%A7%D8%A8-%D8%A7%D9%84%D9%85%D8%AA%D8%AC%D9%87%D8%A7%D8%AA-vectors-%D9%88%D8%A7%D9%84%D8%AD%D8%B1%D9%83%D8%A9-%D9%88%D8%A7%D9%84%D8%AA%D8%B5%D8%A7%D8%AF%D9%85/)[![](https://arabroot.io/content/images/2026/11/game-performance-cover-cover.webp)دليلأداء اللعبة: قياس الإطارات Profiling وتحسينهانبني في Godot 4 بستاناً من 2,500 نخلة بطيئاً عن قصد، ثم نقيسه بأدوات المحرك ونصلحه في ست خطوات، ونعرف بالأرقام كم وفرت كل خطوة ومن أين، وما الثمن الذي دفعناه في رقم آخر.](https://arabroot.io/articles/%D8%A7%D8%AF%D8%A7%D8%A1-%D8%A7%D9%84%D9%84%D8%B9%D8%A8%D8%A9-%D9%82%D9%8A%D8%A7%D8%B3-%D8%A7%D9%84%D8%A7%D8%B7%D8%A7%D8%B1%D8%A7%D8%AA-profiling-%D9%88%D8%AA%D8%AD%D8%B3%D9%8A%D9%86%D9%87%D8%A7/)

## سجل التحديثات Changelog

- 20 نوفمبر 2026: كتابة المقال، وتشغيل المختبر على Python 3.13.16 داخل python:3.13-alpine: ثلاث خرائط و300 كاميرا لكل خريطة وثلاثة مرسمات وثلاثة بناة.