Optimieren Sichtfeld Algorithmus in einem Raster mit Ziegeln gedeckt Karte

Question

Ich versuche, Field of View-Algorithmus in meinem Spiel zu implementieren, und ich folgte die große Tutorial hier: sight-and-light und hier ist das, was ich so weit gekommen:

Wie Sie sehen können, funktioniert es gut für mich :)

Und dann versuche ich, diesen Algorithmus in einer gekachelten Karte zu verwenden. Es funktioniert auch gut, aber nur ein bisschen langsam, so dass ich jetzt versuche, einen Weg zu finden, um den Algorithmus zu optimieren.

könnten einige Informationen zu optimieren:

• Das geflieste Karte Orthogonal ist
• Alle Kacheln haben die gleiche Größe 32 * 32 und sind quadratisch
• Fliesen markiert 0 bedeutet leer als 1 Mittel gekennzeichnet
  • Alle Hindernisse wurden mer: ein Hindernis
  • I Connected Component Labeling-Algorithmus für einen Vorprozess verwendet haben mehrere Regionen ged in
  • Ich weiß, dass alle Eckpunkte Position in jeder Regionen

Etwas wie folgt aus:

Sagen, ich habe 9 verbundenen Bereiche (9 Polygone) und 40 Ecken insgesamt.

Basierend auf dem Algorithmus, der in der oben genannten Verbindung wird es:

• Raycasting: 40 * 3 (3 Raycasting pro Vertices in Winkel + - 0,00001)
• Kanten 40
• Ränder * Raycasting Schnitttest: 40 * 40 * 3 == 4800

denke ich, es eine Möglichkeit sein sollte, die Strahl Gusszahl und die Kanten Zahl, die ich brauche zu tun, um die Schnittpunktberechnung zu reduzieren eine obige Situation, aber nur cou Ich würde keine gute Lösung finden.

Jeder Vorschlag geschätzt wird, Dank :)

Answer 1

Was Sie tun sehr viel optimiert werden kann. Zunächst ist es nicht sinnvoll, alle Scheitelpunkte zu verwenden und keine Schnitttests durchzuführen.

Nehmen Sie jedes Polygon. Finde für jeden Eckpunkt heraus, ob es ein Inversionspunkt ist. Nehmen Sie den Strahl vom Ursprung/Auge und prüfen Sie, ob der Nachbar auf derselben Seite ist. Finde heraus, welche Richtung zum Ursprung führt und folge ihm, bis du einen anderen Umkehrpunkt findest. Das Segment zwischen diesen Punkten sind diejenigen, die dem Ursprung/Auge gegenüberstehen. Wenn Sie eine konvexe Form haben, gibt es nur zwei davon, für komplexere kann es mehr geben.

Als nächstes konvertieren Sie den gesamten Inversionspunkt in Polarkoordinaten und sortieren Sie sie nach dem Winkel.Jetzt sollten Sie eine Reihe von möglicherweise überlappenden Intervallen haben (achten Sie auf den Warparound 360-> 0). Wenn die Szene einfach ist, sind die Intervalle nicht überlappend, so dass Sie nur Ihre Polygone mit dem Licht verfolgen müssen (keine Tests erforderlich). Wenn Sie eine Überlappung festgestellt haben, nehmen Sie den Umkehrpunkt und die aktuelle Kante aus dem vorhandenen Intervall und prüfen Sie, ob der Inversionspunkt auf derselben Seite wie der Ursprung/das Auge liegt. Wenn dies der Fall ist, können Sie den Strahl mit der aktuellen Kante zum Inversionspunkt schneiden, um den Fernpunkt zu erhalten und ihn mit dem Umkehrpunkt zu verbinden, der jetzt als aktuelle Kante ersetzt wird. Wenn es ein Intervall gibt, das zu keinem Polygon gehört, gehen die Strahlen in die Unendlichkeit (es gibt nichts zu sehen für alle Strahlen in diesem Polygon).

Dies funktioniert für alle nicht überlappenden Polygone.

Also in Ihrem Fall werden Sie nur 9 * 2 Inversionspunkte bekommen (Ihre Polygone sind einfach) und Sie müssen sehr wenige Rand- * Strahlkreuzungen machen, weil ihr Layout ziemlich spärlich ist und der Algorithmus schnell offensichtliche sich überschneidende Fälle.

Wenn dies für einige Echtzeitanwendungen ist, können Sie es weiter optimieren, indem Sie die Tatsache ausnutzen, dass die Inversionspunkte größtenteils gleich bleiben, und wenn sie sich ändern, bewegen sie sich entlang des Polygons normalerweise eine Kante (könnte mehr sein das Polygon ist klein, die Bewegungsentfernung ist groß).