Wie man die Sichtbarkeit in 2D bestimmt

Question

Ich entwickle eine KI-Sandbox und würde gerne berechnen, was jedes Lebewesen sehen kann.

Die Regel besagt, dass das, was sich hinter den Rändern der Formen befindet, aus der Sicht der Entität einfach ausgeblendet wird. Das Bild verdeutlicht alles:

Alt-Text http://img231.imageshack.us/img231/2972/shadows.png

Ich brauche sie entweder als Eingabe für die künstliche Intelligenz oder grafisch, um sie für eine bestimmte Entität anzuzeigen, während sie sich bewegt

Irgendwelche coolen Ideen?

Answer 1

Dies ist nicht der schnellste Algorithmus, aber er erzeugt ein Polygon, das für die weitere Analyse durch Ihre KI nützlich sein könnte:

1. Berechnen Sie für jedes Liniensegment den Winkel zwischen dem Objekt und den beiden Endpunkten.
2. Sortieren Sie die Punkte nach Winkel.
3. "Sweep" um 360°, wobei Sie verfolgen, welche Liniensegmente sich mit der Sweep-Linie schneiden. Wenn Sie den Punkt am Anfang des Segments kreuzen, fügen Sie dieses Segment der Menge hinzu; wenn Sie den Punkt am Ende des Segments kreuzen, entfernen Sie dieses Segment aus der Menge.
4. Die nächstgelegenen Liniensegmente bilden ein Polygon des Sichtbaren. Das Polygon ist die Vereinigung von Dreieckssplittern.

Mir ist klar, dass diese Erklärung nicht besonders gut ist, aber ich habe eine Online-Demo hier mit denen Sie spielen können, um ein Gefühl dafür zu bekommen, wie es funktioniert. Die Erweiterung auf Kreise ist wahrscheinlich gar nicht so schlecht (berühmte letzte Worte).

Answer 2

Wenn Sie einfache Formen verwenden, um die Sicht der Entität zu blockieren, gibt es eine einfache Möglichkeit, dies zu tun, die ich implementiert habe:

Erstellen einer VisionWave Objekt, das sich entweder horizontal oder vertikal bewegen kann. Sie können ein VisionWave unter Verwendung einer Ausgangskoordinate, zweier Linien, die diesen Punkt schneiden, und einer Entfernung vom Ausgangspunkt.

Sie sollten 4 Wellen haben: eine nach oben, eine nach unten, eine nach links und eine nach rechts, und die Linien, die sie definieren, sollten eine Steigung von 1 und -1 haben (d.h. ein X). Meine grobe Zeichnung unten zeigt eine Welle (nach rechts), dargestellt durch die > Charakter.

  \     /
   \   />
    \ / >
     @  >
    / \ >
   /   \>
  /     \

Erstellen Sie eine Schleife, die jede Welle pixelweise ausbreitet. Wenn Sie die Welle ausbreiten, möchten Sie Folgendes tun:

1. Markieren Sie jedes Pixel, das von der Welle berührt wird, als sichtbar.
2. Wenn eines der Pixel, die von der Welle berührt werden, das Licht blockiert, muss die Welle in zwei Teile geteilt werden, die sich dann rekursiv ausbreiten.

Ich habe ein solches System in meinem Roguelike implementiert und es ist sehr schnell. Stellen Sie sicher, dass Sie Ihren Code auf Engpässe untersuchen.

Wenn Sie sehr clever sind, könnten Sie es mit kreisförmigen Wellen anstelle von geraden Linien versuchen, aber ich weiß nicht, ob das wegen der trigonometrischen Berechnungen schneller ginge.

Answer 3

Bestimmen Sie, welche Scheitelpunkte für Ihren Augenpunkt sichtbar sind, und projizieren Sie dann diese Scheitelpunkte auf einer geraden Linie vom Augenpunkt weg, um neue Scheitelpunkte zu erstellen. Schließen Sie die Form und Sie haben ein Polygon erstellt, das den unsichtbaren Bereich darstellt.

Voir Schattenvolumina für das 3D-Äquivalent.