Raytracing (LoS) auf 3D-hex-wie Fliesen Karten

Question

Grüße,

Ich arbeite an einem Projekt, das Spiel eine 3D-Variante von hexagonalen Fliese Karten verwendet. Fliesen sind eigentlich Würfel, nicht Hexfelder, sind aber wie Flüche angelegt (weil ein Quadrat zu einem Würfel zu extrapolieren von 2D auf 3D gedreht werden kann, aber es gibt keine 3D-Version eines hex). Anstatt eine ausführliche Beschreibung, hier geht ein Beispiel einer 4x4x4 Karte:

(Ich habe einen beliebigen Kachel (grün) und seine benachbarten Fliesen (gelb), um Hilfe hervorgehoben wird beschrieben, wie das Ganze funktionieren soll, aber die adjacency Funktionen sind nicht die Frage , das ist schon gelöst.)

Ich habe einen Strukturtyp Fliesen zu repräsentieren, und Karten werden als 3D-Array von Kacheln dargestellt (eingewickelt in einer Map Klasse einiger Utility-Methoden hinzufügen, aber das ist nicht sehr relevant). Jede Fliese sollte repräsentiert einen perfekt kubischen Raum, und sie sind alle genau die gleiche Größe. Außerdem wird der Versatz zwischen benachbarten „Reihen“ genau der Hälfte der Größe einer Kachel.

Das ist, genug Kontext; meine Frage ist:
In Anbetracht der Koordinaten von zwei Punkten A und B, wie kann ich eine Liste der Fliesen erzeugen (oder vielmehr ihre Koordinaten), dass eine gerade Linie zwischen A und B würde überqueren?

Das würde später für eine Vielzahl von Zwecken verwendet werden, wie zum Beispiel der Bestimmung Line-of-sight, Ladepfad Legalität, und so weiter.

BTW kann dies nützlich sein: meine Karten verwenden, um die (0,0,0) als Referenzposition. Der ‚jagging‘ der Karte kann als Ausgleich jede Kachel ((y+z) mod 2) * tileSize/2.0 nach rechts von der Position definiert werden, es auf einem „vernünftigen“ kartesisch System haben würde. Für die nicht-gezackten Reihen, daß die Ausbeuten 0; für Zeilen, in denen (y+z) mod 2 1 ist, ergibt es 0,5 Fliesen.

Ich arbeite an C # 4 das .Net Framework 4.0 ausgerichtet ist; aber ich weiß nicht wirklich spezifischen Code benötigen, nur den Algorithmus das seltsame geometrische / mathematische Problem zu lösen. Ich habe mehrere Tage versucht, dies zu keinem Erfolg zu lösen; und zu versuchen, das Ganze auf Papier zeichnen zu „visualisieren“ es hilft nicht entweder :(.

Vielen Dank im Voraus für jede Antwort

Answer 1

Bis einer der klugen SOers auftaucht, hier ist meine dumme Lösung. Ich werde es in 2D ‚cos erklären, dass macht es einfacher zu erklären, aber es wird in 3D verallgemeinern leicht genug. Ich denke, dass jeder Versuch, um zu versuchen, diesen Raum vollständig in Zellindex zu arbeiten, ist zum Scheitern verurteilt (obwohl ich gebe zu, es ist genau das, was ich denke, und ich freue mich auf sein erwies sich als falsch).

Sie müssen also eine Funktion definieren von kartesischen Koordinaten zu Zellindizes abzubilden. Dies ist einfach, wenn auch ein wenig schwierig. Zuerst entscheiden, ob point(0,0) die untere linke Ecke des cell(0,0) ist oder der Mitte oder einem anderen Punkt. Da es die Erklärungen leichter macht, werde ich mit linken unteren Ecke gehen. Beachten Sie, dass jede point(x,floor(y)==0) zu cell(floor(x),0) abbildet. Tatsächlich kann jeder point(x,even(floor(y))) Karten zu cell(floor(x),floor(y)).

Hier erfinden ich die Boolesche Funktion even die True zurückgibt, wenn sein Argument eine gerade ganze Zahl ist. Ich werde odd verwenden nächsten. Jeder Punkt point(x,odd(floor(y)) zu cell(floor(x-0.5),floor(y)) Karten

Jetzt haben Sie die Grundlagen des Rezepts für Linien-of-sight zu bestimmen.

Sie haben auch eine Funktion benötigen von cell(m,n) zurück zu einem Punkt in kartesischer Raum abzubilden. Das sollte einfach sein, wenn Sie, wo die Herkunft Lügen haben.

Nun, wenn ich ein paar Klammern verloren habe, ich glaube, Sie auf Ihrem Weg sind. Sie müssen an:

• entscheiden, wo in cell(0,0) Sie Position point(0,0); und stellen Sie die Funktion entsprechend;
• entscheiden, wo Punkte entlang der Zellgrenzen fallen; und
• verallgemeinert dies in 3 Dimensionen.

Je nach Größe des Spielfeldes, um die kartesischen Koordinaten der Zellgrenzen in einer Lookup-Tabelle (oder eine andere Datenstruktur) gespeichert werden könnte, was würde wahrscheinlich die Dinge beschleunigen.

Answer 2

Vielleicht können Sie alle komplexe Mathematik vermeiden, wenn Sie an Ihrem Problem auf andere Weise aussehen:

Ich sehe, dass Sie nur Ihre Blöcke verschieben (abwechselnd) entlang der ersten Achse um die Hälfte der Blockgröße. Wenn Sie Ihre Blöcke aufgeteilt entlang diesem das obige Beispiel Achse (mit Schichten) werden wird ein (9x4x4) einfache kartesisches System mit regelmäßigen gestapelten Blöcken koordinieren. Jetzt das Raytracing tun wird viel einfacher und weniger fehleranfällig.