Raytracing (LOS) على خرائط البلاط ثلاثية الأبعاد تشبه Hex

Question

تحيات،

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

(لقد أبرزت بلاطًا تعسفيًا (أخضر) وبلاطه المجاور (الأصفر) للمساعدة في وصف كيف يفترض أن يعمل الأمر برمته ؛ لكن وظائف المجاورة ليس القضية ، تم حلها بالفعل.)

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

هذا سياق كاف ؛ سؤالي هو:
بالنظر إلى إحداثيات نقطتين A و B, ، كيف يمكنني إنشاء قائمة من البلاط (أو ، بالأحرى ، إحداثياتها) التي خط مستقيم بين A و B سوف الصليب؟

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

راجع للشغل ، قد يكون هذا مفيدًا: تستخدم الخرائط الخاصة بي (0،0،0) كموقف مرجعي. يمكن تعريف "الركض" للخريطة على أنه تعويض كل بلاط ((y+z) mod 2) * tileSize/2.0 إلى اليمين من الموضع الذي ستحصل عليه على نظام ديكارت "عاقل". بالنسبة للصفوف غير المقيدة ، فإن ذلك يعطي 0 ؛ للصفوف حيث (y+z) mod 2 هو 1 ، ينتج 0.5 بلاط.

أنا أعمل على C#4 لاستهداف .NET Framework 4.0 ؛ لكنني لست بحاجة حقًا إلى رمز معين ، فقط الخوارزمية لحل المشكلة الهندسية/الرياضية الغريبة. لقد كنت أحاول عدة أيام لحل هذا دون جدوى ؛ ومحاولة رسم كل شيء على الورق "لتصور" ، لم يساعد ذلك أيضًا :(.

شكرا مسبقا على أي إجابة

Answer 1

حتى يظهر أحد Soers Clever ، إليك الحل الغبي. سأشرح ذلك في 2D 'COS مما يجعل من الأسهل شرحه ، ولكنه سوف يتم التعميم على ثلاثية الأبعاد بسهولة كافية. أعتقد أن أي محاولة لمحاولة العمل بالكامل في مساحة مؤشر الخلية محكوم عليها بالفشل (على الرغم من أنني سأعترف بأن هذا ما أعتقده فقط وأتطلع إلى أن يكون خطأ).

لذلك تحتاج إلى تحديد وظيفة لتعيين من الإحداثيات الديكارتية إلى مؤشرات الخلايا. هذا واضح ومباشر ، إذا كان صعبة بعض الشيء. أولاً ، قرر ما إذا كان point(0,0) هو الركن الأيسر السفلي من cell(0,0) أو المركز ، أو نقطة أخرى. نظرًا لأنه يجعل التفسيرات أسهل ، سأذهب مع الزاوية السفلية اليسرى. لاحظ ذلك point(x,floor(y)==0) خرائط ل cell(floor(x),0). في الواقع ، أي point(x,even(floor(y))) خرائط ل cell(floor(x),floor(y)).

هنا ، أخترع وظيفة منطقية even الذي يعود صحيحًا إذا كانت حجتها عددًا صحيحًا. سأستخدم odd التالي: أي نقطة point(x,odd(floor(y)) خرائط ل cell(floor(x-0.5),floor(y)).

الآن لديك أساسيات الوصفة لتحديد خطوط الرؤية.

ستحتاج أيضًا إلى وظيفة لتعيينها cell(m,n) العودة إلى نقطة في الفضاء الديكارت. يجب أن يكون ذلك واضحًا بمجرد أن تقرر أين يكمن الأصل.

الآن ، ما لم أقم في غير محله بعض الأقواس ، أعتقد أنك في طريقك. ستحتاج إلى:

• قرر أين في cell(0,0) أنت وضع point(0,0); ؛ وضبط الوظيفة وفقًا لذلك ؛
• حدد أين تسقط النقاط على طول حدود الخلية ؛ و
• تعميم هذا في 3 أبعاد.

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

Answer 2

ربما يمكنك تجنب كل الرياضيات المعقدة إذا نظرت إلى مشكلتك بطريقة أخرى:

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