Wie kann man in einem 2D-Spiel mit Kacheln die Sichtfläche schnell berechnen?

24

Ich habe eine Matrix aus Kacheln, auf einigen dieser Kacheln befinden sich Objekte. Ich möchte berechnen, welche Kacheln für den Spieler sichtbar sind und welche nicht, und ich muss es sehr effizient ausführen (damit es schnell genug berechnet werden kann, selbst wenn ich große Matrizen (100x100) und viele Objekte habe).

Ich habe versucht, es mit Bresenhams Linienalgorithmus zu machen , aber es war langsam. Außerdem gab es mir einige Fehler:

----XXX-        ----X**-     ----XXX-
-@------        -@------     -@------
----XXX-        ----X**-     ----XXX-
(raw version)   (Besenham)   (correct, since tunnel walls are 
                              still visible at distance)

(@ is the player, X is obstacle, * is invisible, - is visible)

Ich bin mir sicher, dass dies möglich ist - schließlich haben wir NetHack, Zangband und alle haben sich irgendwie mit diesem Problem befasst :)

Welchen Algorithmus können Sie dafür empfehlen?


Für meine Bedürfnisse definiere ich sichtbar wie folgt: Plättchen ist sichtbar, wenn mindestens ein Teil (z. B. eine Ecke) des Plättchens mit einer geraden Linie, die kein Hindernis schneidet, mit der Mitte des Spielerplättchens verbunden werden kann.

Rogach
quelle
1
Hoppla, mein Fehler, NetHack hat nicht mit der Sichtlinie
rumgespielt
Einige ältere Ideen finden Sie unter fadden.com/tech/fast-los.html . Dies geht jedoch auf die Zeit zurück, als CPUs relativ langsam waren und Gleitkommaberechnungen am besten vermieden wurden.
verblasst

Antworten:

10

Ihre Definition von Sichtbar lautet wie folgt:

Ein Plättchen ist sichtbar, wenn mindestens ein Teil (z. B. eine Ecke) des Plättchens mit einer geraden Linie, die kein Hindernis schneidet, mit der Mitte des Spielerplättchens verbunden werden kann

Sie können dieses Konzept buchstäblich umsetzen, indem Sie die Strahlen von Ihrem Spielerplättchen verfolgen und sie mit Ihrer Szene schneiden. Sie brechen jede Iteration ab, sobald der Strahl auf ein Hindernis trifft (oder eine bestimmte Entfernungsschwelle überschreitet), da Sie nur an den Feldern interessiert sind, die der Spieler direkt sehen kann. Ich werde den Prozess für Sie abbrechen:

  1. Geben Sie an, wie genau der Algorithmus sein soll. Dies ist die Anzahl der Strahlen, die Sie verfolgen werden.
  2. Teilen Sie den vollen 360-Grad-Kreis durch die gewählte Genauigkeit, um zu wissen, wie viele Grad zwischen den einzelnen Strahlen gedreht werden sollen.
  3. Beginnen Sie bei 0 Grad und erhöhen Sie den Wert um den in Schritt 2 festgelegten Wert. Erstellen Sie einen Strahl mit dem Ursprung in der Mitte des Spielerplättchens und der Richtung, die durch den aktuellen Winkel bestimmt wird.
  4. Gehen Sie für jeden Strahl, beginnend mit dem Spielerplättchen, entlang der Richtung des Strahls, bis Sie auf ein Hindernisplättchen stoßen. Fügen Sie diese Kachel zur Liste der sichtbaren Kacheln hinzu und fahren Sie mit dem nächsten Strahl fort. Möglicherweise möchten Sie auch eine maximale Distanz hinzufügen, um "aufzugeben", falls keine Kollision gefunden wird.

Hier ist ein Bild mit 3 Beispielstrahlen. Die dunkleren Kacheln sind das "Ergebnis" jedes Strahls, dh wo die Kollision stattgefunden hat. Sie müssen dies jedoch im gesamten Kreis wiederholen:

Bildbeschreibung hier eingeben

Stellen Sie den maximalen Abstand und die Anzahl der Strahlen für die Leistung ein. Zu wenig und Sie werden Fliesen verpassen, zu viel und Ihre Leistung wird leiden. Je weiter die Strahlen wandern müssen, desto größer wird der "Fehler" und desto präziser wird es.

Bearbeiten

Überprüfen Sie das folgende Tutorial zum Raycasting, insbesondere Schritt 3 und Schritt 4, um das Schnittbit des Algorithmus zu implementieren:

http://www.permadi.com/tutorial/raycast/rayc7.html

David Gouveia
quelle
Sollte ich nur einen festen Abstand (z. B. 0,3 Punkte) zu jedem Strahl "gehen" oder muss ich für jeden Strahl so etwas wie den Besenham-Algorithmus ausführen?
Rogach
Wenn Sie nur um eine feste Distanz vorrücken, bekommen Sie Probleme mit fehlenden Kacheln. Überprüfen Sie dieses Tutorial auf Raycasting . Ich werde diese Ressource auch in meine Antwort aufnehmen. Grundsätzlich wird getrennt nach horizontalen und vertikalen Kollisionen gesucht.
David Gouveia
1
Der Algorithmus ist gut, aber es werden sehr viele Strahlen benötigt, um mit langen Tunneln mit einer Breite von 1 Kachel richtig zu arbeiten.
HolyBlackCat
@HolyBlackCat - das ist nur der Fall, wenn Sie Strahlen in gleichmäßigen Winkeln in alle Richtungen aussenden. Sie können jedoch vermeiden, die meisten dieser Strahlen zu senden, und sie nur an den Zeilenenden in Ihrer Szene werfen. Hier ist eine gute Erklärung: redblobgames.com/articles/visibility
Rogach
8

Ich würde lieber Schattenstrahlen als Sichtlinienstrahlen werfen.

Angenommen, dies ist Ihr Ansichtsbereich (der potenziell sichtbare Bereich).

######################
#####.............####
###................###
##..................##
#....................#
#....................#
#..........@.........#
#....................#
#....................#
##..................##
###................###
#####.............####
######################

Die # Blöcke sind nicht sichtbar, während die. sind sichtbar

Lassen Sie uns ein Hindernis setzen X:

######################
#####.............####
###................###
##.....X.....XXX....##
#......X.......X.....#
#...X.XX.............#
#...X......@.........#
#...X..........X.....#
#...XXXXXX...........#
##..................##
###....X...........###
#####.............####
######################

Sie haben eine Liste der X, die sich im Ansichtsbereich befinden. Dann markieren Sie jedes Feld, das sich hinter jedem dieser Hindernisse befindet, als ausgeblendet. Wenn ein Hindernis als ausgeblendet markiert ist, entfernen Sie es aus der Liste.

######################
#####.............####
###................###
##.....X.....XXX....##
#......X.......X.....#
#...X.XX.............#
#...X......@.........#
#...X..........X.....#
#...XXXXX*...........#
##......##..........##
###....*#..........###
#####.###.........####
######################

Im obigen Beispiel können Sie sehen, wie der Schatten ganz rechts von der Bodenwand geworfen wird und wie dieser Schatten das verborgene Hindernis aus der Liste des zu prüfenden Hindernisses löscht (X muss prüfen; * markiert).

Wenn Sie die Liste mit einer Binär-Partition sortieren, so dass zuerst das cosest X geprüft wird, können Sie Ihre Prüfung etwas beschleunigen.

Sie können eine Art "Naval Battles" -Algorithmus verwenden, um einen Block von Xs auf einmal zu überprüfen (im Grunde suchen Sie nach einem benachbarten X in einer Richtung, die den Schattenkegel breiter machen kann).

[BEARBEITEN]

Es werden zwei Strahlen benötigt, um einen Schatten korrekt zu werfen. Da eine Kachel rechteckig ist, können viele Annahmen unter Verwendung der verfügbaren Symmetrien getroffen werden.

Die Strahlkoordinaten können mithilfe einer einfachen Raumaufteilung um das Hindernisplättchen berechnet werden:

Beispiel für eine Raumaufteilung

Jeder rechteckige Bereich bestimmt, welche Ecke der Kachel als Schattenkegelkante verwendet werden soll.

Diese Überlegung kann weiter vorangetrieben werden, um mehrere benachbarte Kacheln zu verbinden und sie wie folgt einen einzelnen, breiteren Kegel werfen zu lassen.

Der erste Schritt besteht darin, sicherzustellen, dass sich keine Hindernisse in Richtung des Betrachters befinden. In diesem Fall wird stattdessen das nächste Hindernis berücksichtigt:

wähle das nächste Hindernis

Wenn das gelbe Plättchen ein Hindernis ist, wird dieses Plättchen zum neuen roten Plättchen.

Betrachten wir nun die obere Kegelkante:

Kandidatenplättchen

Die blauen Kacheln sind alle mögliche Kandidaten, um den Schattenkegel breiter werden zu lassen: Wenn mindestens eine von ihnen ein Hindernis ist, kann der Strahl unter Verwendung der Raumteilung um diese Kacheln wie zuvor gesehen bewegt werden.

Die grüne Kachel ist nur dann ein Kandidat, wenn sich der Beobachter über der folgenden orangefarbenen Linie befindet:

erweiterte Prüfung

Gleiches gilt für den anderen Strahl und für die anderen Positionen des Betrachters zum roten Hindernis.

Die Grundidee besteht darin, für jeden Kegelwurf so viel Fläche wie möglich abzudecken und die Liste der zu überprüfenden Hindernisse so schnell wie möglich zu verkürzen.

FxIII
quelle
Interessanter Ansatz und wahrscheinlich eine bessere Idee wegen seiner subtraktiven Natur. Nachdem ich das gelesen habe, würde ich es wahrscheinlich auch so umsetzen.
David Gouveia
Ich kann Probleme in Situationen wie voraussehen diese . Spieler in Gelb, Hindernisse in Blau und Lila. Der Spieler sollte das violette Hindernis sehen können (wie der grüne Strahl zeigt). Aber der rote Schattenstrahl, der durch das blaue Hindernis geht, weist die lila Kachel zurück. Aber ich denke, die Version mit Blickrichtung hat das Potenzial, größere Probleme als diese zu haben.
David Gouveia
Dieses Problem ergibt sich aus der Definition von "versteckt": Wenn ein Strahl eine Kachel schneidet, deckt er diese (fast) nie vollständig ab. Das gleiche Problem wird mit Aliasing beim Rendern von Liniensegmenten behoben. Persönlich denke ich, dass ein Plättchen versteckt ist, wenn der größte Teil davon bedeckt ist. Man kann definieren, dass es vollständig bedeckt ist. Sie können feststellen, ob es eine Seite freilegt, die möglicherweise den Schattenkegel breiter macht. Wie auch immer Löschen Sie nur die Blöcke, die vollständig abgedeckt sind.
FxIII
@DavidGouveia - welche größeren Probleme?
Rogach
@DavidGouveia - Ich habe es bereits mit Schattenkegeln versucht und es war sehr ineffizient. Bezüglich der Präzision der Sichtbarkeitsstrahlen - ~ 5500 Strahlen reichen aus, um die Wand 20 Kacheln in jede Richtung zu sehen, wenn Sie direkt daneben stehen, und da der Abstand, in dem nur eine einzige Kachel sichtbar ist, viel größer ist. Und was das Fehlen einiger Kacheln in größerer Entfernung angeht - nun, nicht jeder hat ein perfektes Sehvermögen, oder?
Rogach
8

Das Problem, das Sie zu lösen versuchen, wird manchmal als Sichtfeld, kurz FOV, bezeichnet. Wie Sie als Beispiel Roguelikes erwähnt haben, sollten Sie sich ansehen, was das RogueBasin-Wiki zu diesem Thema zu sagen hat (es gibt sogar Links zu Implementierungen): http://www.roguebasin.com/index.php?title=Field_of_Vision

Es gibt einige verschiedene Algorithmen mit unterschiedlichen Vor- und Nachteilen - ein sehr praktischer Vergleich ist auch bei RogueBasin verfügbar: http://www.roguebasin.com/index.php?title=Comparative_study_of_field_of_view_algorithms_for_2D_grid_based_worlds

Tapio
quelle
Wirklich gute und vollständige Zusammenfassung!
Rogach
Diese Website ist eine großartige Ressource, danke, dass Sie diesen Link geteilt haben. Es enthält auch eine erstaunlich verständliche Beschreibung, wie A *
-Pfadfindung
Der Link in der Antwort geht jetzt zur Homepage der Site - roguebasin.com/index.php?title=Category:FOV scheint eine sinnvolle Übereinstimmung zu sein.
Fadden