Welche Route ist die sicherste, wo sind die meisten Feinde und wo ist das nächste Erste-Hilfe-Set? All diese häufig auftretenden Probleme räumlicher Beziehungen können mithilfe mathematischer Partitionen, die als „Voronoi-Diagramme“ bezeichnet werden, effektiv gelöst werden. In diesem Beitrag erfahren Sie, wie Sie Spielkarten analysieren und Informationen erhalten, die den Realismus und Erfolg künstlicher Intelligenz sicherstellen.
Räumliche Beziehung
Eine räumliche Beziehung ist eine Information, die beschreibt, wie ein Objekt im Raum mit einem anderen in Beziehung steht. Beispiele: der Abstand zwischen ihnen, der von jedem Raum abgedeckte Bereich und der Schnittpunkt dieser Bereiche, die Anzahl solcher Objekte, die sich in einem Bereich befinden.
Solche Beziehungen werden ständig in Videospielen verwendet und können sehr nützliche KI-Informationen sowie den Spieler selbst liefern.
Voronoi hat eine Antwort
Das Voronoi-Diagramm beschreibt die räumliche Beziehung zwischen eng beieinander liegenden Punkten oder ihren nächsten Nachbarn. Dies ist eine Reihe verbundener Polygone, die aus Punkten oder Orten erhalten werden. Jede Linie von Voronois "Bereich" befindet sich in der Mitte zwischen zwei Punkten.
Schauen Sie sich zum Verständnis das Bild an:
Wie Sie sehen können, befindet sich jede Linie genau in der Mitte zwischen zwei Punkten, und alle sind in der Mitte verbunden. Fügen Sie der Szene noch ein paar Punkte hinzu und sehen Sie, was passiert:
Das Bild ist interessanter geworden! Wir haben bereits reale Bereiche.
Was sagt uns jeder der Bereiche? Wir wissen, dass es garantiert ist, dass Sie sich in der Nähe eines Punktes befinden, der sich ebenfalls in der Gegend befindet. Dies sagt uns viel darüber, was in der Nähe ist; Dies ist die grundlegende räumliche Beziehung in Voronoi-Diagrammen.
Drehen Sie Voronoi um: Delaunay-Triangulation
Das dem Voronoi-Diagramm entgegengesetzte System heißt Delaunay-Triangulation. Dieses Diagramm besteht aus Linien von jedem Punkt zu seinen nächsten Nachbarn, und jede Linie verläuft senkrecht zur Voronoi-Kante, die sie schneidet. So sieht es aus:
Weiß markiert die Delaunay-Linie. Jede Delaunay-Linie entspricht einer und nur einer Voronoi-Kante. Auf den ersten Blick scheinen einige von ihnen mehrere Kanten zu kreuzen, aber wenn Sie genau hinschauen, werden Sie feststellen, dass dies nicht der Fall ist.
In der Abbildung entspricht die grüne Delaunay-Linie der rosa Rippe von Voronoi. Stellen Sie sich vor, die rosa Rippe geht weiter und Sie sehen, dass sie sich schneiden.
Dank der Delaunay-Triangulation sehen wir, dass wir anstelle von Polygonen jetzt viele Dreiecke haben. Dies ist unglaublich nützlich, da wir den Bereich in Dreiecke unterteilt haben, die gerendert werden können. Diese Technik kann zur Tessellation oder Triangulation von Figuren verwendet werden. Großartig!
Darüber hinaus ist dies eine großartige Möglichkeit, ein Diagramm aus mehreren Punkten zu erstellen, falls wir von einem Punkt zum anderen wechseln möchten. Beispielsweise können Punkte Städte anzeigen.
Voronoi-Datenstruktur
Wir wissen bereits, wie das Voronoi-Diagramm aussieht. Nun wollen wir sehen, wie die Datenstruktur aussehen wird. Zuerst müssen wir die Punkte speichern, die die Grundlage des Voronoi-Diagramms bilden:
class VoronoiPoint { float x float y VoronoiRegion* region }
Jeder
VoronoiPoint hat einen Ort
(x, y) und einen Link zu dem Bereich, in dem er sich befindet.
Als nächstes müssen wir
VoronoiRegion beschreiben:
class VoronoiRegion { VoronoiPoint* point Edge *edges[]
Der Bereich speichert einen Link zu seinem
VoronoiPoint sowie eine Liste der
VoronoiEdges Kanten,
VoronoiEdges .
Mal sehen, wie
VoronoiEdges aussieht:
class VoronoiEdge { VoronoiPoint* pointA VoronoiPoint* pointB float distance
Die Kante kennt zwei Punkte, die sie definieren, sowie den Abstand zwischen ihnen. Für die visuelle Anzeige sowie für die Konstruktion der Form des polygonalen Bereichs müssen die Start- und Endpunkte der Kante gespeichert werden.
Und das ist alles. Mit diesen Informationen können wir leicht ein Voronoi-Diagramm erstellen. Im Folgenden erfahren Sie, wie das Voronoi-Diagramm erstellt wird. Schauen wir uns zunächst einige Beispiele an, wie diese Daten verwendet werden können.
Finden Sie Ihren nächsten Medizinschrank
Schauen Sie sich noch einmal das Voronoi-Diagramm für Punkte an.
Wenn jeder Punkt ein Erste-Hilfe-Set kennzeichnet, können wir schnell feststellen, wo wir am nächsten sind, aber zuerst müssen wir den Bereich bestimmen, in dem wir uns befinden. Voronoi-Diagramme bieten keine effektive Möglichkeit, eine Region zu definieren. Um die Suche zu beschleunigen, können wir jedoch einen Link zu jeder Region im
Quadrantenbaum oder im
R-Baum speichern. Und wenn wir die Region kennengelernt haben, können wir ihre Nachbarn und die Nachbarn ihrer Nachbarn erkennen.
Wenn es in Ihrer Region beispielsweise keine Erste-Hilfe-Sets mehr gibt, müssen Sie einen Weg zu einem anderen nächstgelegenen finden. Aus der oben gezeigten Datenstruktur und dem Pseudocode können wir verstehen, dass wir, wenn wir die Region kennen, ihre Kanten erkennen können. Und mit Hilfe dieser Rippen können wir Nachbarn bekommen. Wir werden den nächsten Nachbarn nehmen und sehen, ob ein Erste-Hilfe-Kasten darin ist.
Sie können hier auch die Delaunay-Triangulation anwenden. Es besteht aus Linien zwischen den Erste-Hilfe-Sets. Dann können Sie es mit dem A * -Pfad-Suchalgorithmus umgehen, um das nächste Erste-Hilfe-Set zu finden.
Suchen Sie nach einer sicheren Route
Ersetzen Sie alle Erste-Hilfe-Sets durch feindliche Wachtürme. Sie müssen den sichersten Weg zwischen ihnen finden, um nicht erwischt zu werden. Die Standardmethode zum Durchlaufen von Grafiken in Videospielen ist die Verwendung
des A * -Algorithmus . Da das Voronoi-Diagramm ein Diagramm ist, ist es sehr einfach, eine Suche durchzuführen. Wir brauchen nur den A * -Algorithmus, der allgemeine Graphstrukturen unterstützt; Planen Sie voraus und es wird Ihnen in Zukunft helfen.
Nachdem Sie das Diagramm vorbereitet haben, müssen Sie jeder Kante ein Gewicht zuweisen. Für uns ist der Gewichtswert der Abstand zu diesen Wachtürmen, und Sie können ihn direkt aus der Datenstruktur
VoronoiEdge : Jeder
VoronoiEdge kennt bereits seinen Abstand zwischen zwei Punkten. Normalerweise ist der Wert umso besser, je kleiner der Wert an der Kante A * ist. In unserem Fall ist der Wert jedoch umso größer, da er den Abstand zum Turm angibt.
So sieht das ursprüngliche Diagramm aus, wenn wir von Punkt A nach Punkt B wechseln möchten:
Wenn Sie auf jede Kante Gewicht auftragen, sehen wir, welche Route besser zu wählen ist:
Rote Rippen zeigen die nächsten Kontakte mit den Türmen an. Orange zeigt längere an; gelb noch weiter entfernt und schließlich grün - das sicherste. Nachdem wir A * mit diesen Gewichten ausgeführt haben, erhalten wir den folgenden Pfad:
Mit dieser Verwendung der Waage wird nicht
der schnellste , sondern
der sicherste Weg gewählt, was wir brauchen. KI sollte diesen Weg einhalten und nicht davon abweichen!
Sie können einen weiteren Schritt unternehmen,
um einen sicheren Weg zu
gewährleisten : Entfernen Sie alle Kanten, die näher als der minimale Sicherheitsabstand liegen. Wenn beispielsweise jeder Wachturm einen Sichtradius von 30 Einheiten hat, können alle Kanten, die Entfernung, bis zu der Punkte kürzer sind, aus dem Diagramm entfernt und nicht umgangen werden.
Sie können diese Methode auch verwenden, um die breiteste Route für große Einheiten zu finden, die Engpässe nicht überwinden können. Jede Kante hat einen Abstand zwischen zwei Punkten, sodass wir wissen, ob sie in diesem Raum passieren können.
Sie können auch die umgekehrte Operation ausführen - verwenden Sie das Delaunay-Triangulationsdiagramm und erhalten Sie die Linien, die von jedem Wachturm kommen. Die KI der Wachen kann schnell feststellen, welche anderen Türme sich in der Nähe befinden, und ihnen bei Bedarf helfen.
Suchen Sie nach dicht gepackten Artikeln
Angenommen, wir müssen ein Katzenminzenpaket aus einem Flugzeug fallen lassen, damit ein paar Robben auf dem Boden sitzen. Wo kann man es am besten fallen lassen, damit die meisten Katzen es benutzen können? Dies kann sehr kostspielig sein. Glücklicherweise können wir mit der Delaunay-Triangulation eine vernünftige Annahme treffen.
Hinweis: Vergessen Sie nicht, dass die Delaunay-Triangulation nur die Umkehrung des Voronoi-Diagramms ist. Es wird gebildet, indem jeder Voronoi-Punkt mit benachbarten Punkten verbunden wird, die aus der Liste der Kanten erhalten werden.
Mit dieser Sammlung von Dreiecken können Sie den Bereich erkunden, der von jedem der Dreiecke abgedeckt wird. Wenn wir das Dreieck mit der kleinsten Fläche finden, haben wir drei nächstgelegene Punkte oder Katzen. Es ist möglicherweise nicht der dichteste durchschnittliche Cluster auf der Oberfläche, aber es ist eine gute Annahme. Wenn wir ein paar Pakete mit Minze wegwerfen könnten, würden wir nur die bereits ausgewählten Dreiecke markieren und mit zunehmender Größe zu den nächsten übergehen.
Die Bezeichnung solcher Gebiete wird auch als
umschriebene Kreise der Delaunay-Triangulation bezeichnet. Jeder Kreis ist der größte Kreis, der an die Punkte des Dreiecks passen kann. Hier ist ein Bild der umschriebenen Kreise für das Voronoi-Diagramm:
Sie können die genaue Mitte der Kreise verwenden, um die Mitte des Bereichs zu bestimmen, in dem die Katzenminze versendet wird. Tatsächlich ist der Radius des Kreises eine geeignetere Methode, um das beste zu faltende Dreieck anstelle der Fläche des Dreiecks zu bestimmen, insbesondere wenn die beiden Punkte des Dreiecks sehr nahe beieinander liegen und der dritte weit entfernt ist. dann erhalten wir ein sehr scharfes Dreieck mit einer kleinen Fläche, aber die Punkte, die es definieren, sind tatsächlich sehr weit voneinander entfernt.
Implementierung von Voronoi-Diagrammen
Es gibt verschiedene Möglichkeiten, Voronoi-Diagramme zu erstellen, und die Wahl der verwendeten Methode hängt vom Zeitpunkt ab, zu dem wir die Daten erhalten.
Glücksalgorithmus
Der schnellste Weg heißt
Fortunes Algorithmus . Es läuft in
O(n log(n)) und erfordert, dass alle Punkte, die zum Generieren des Graphen verwendet werden, zum Zeitpunkt des Generierungsbeginns bekannt sind. Wenn Sie später neue Punkte hinzufügen, müssen Sie das gesamte Diagramm neu generieren. Wenn es nur wenige Punkte gibt, kann dies keine Probleme verursachen, aber wenn Sie 100.000 davon haben, kann dies viel Zeit in Anspruch nehmen!
Die Implementierung dieses Algorithmus ist nicht trivial. Kreuzparabeln und Sonderfälle. Dies ist jedoch die schnellste Methode. Glücklicherweise gibt es viele Implementierungen dieses Open-Source-Algorithmus, die Sie verwenden können, und ich habe unten Links dazu bereitgestellt.
Mal sehen, wie es funktioniert.
Der Algorithmus besteht darin, eine Linie (vertikal oder horizontal) über einen Bereich mit Punkten zu schieben. Wenn er einen Punkt erreicht, beginnt er, eine Parabel daraus zu ziehen, die mit einer geschwungenen Linie fortgesetzt wird. Hier ist die Animation dieses Prozesses:
Sich überschneidende Parabeln bilden die Voronoi-Rippen. Aber warum Parabeln?
Um dies zu verstehen, stellen Sie sich vor, dass jeder Punkt einen aufblasbaren Ballon enthält, der anschwillt, bis er mit einem anderen Ball kollidiert. Sie können diese Idee auf Kreise übertragen, die sich in einer 2D-Ebene erweitern. Wir werden einen weiteren Ball nach vorne machen und an jedem Punkt einen umgekehrten Kegel mit einem Neigungswinkel von 45 Grad platzieren, der bis ins Unendliche ansteigt. Stellen Sie sich dann eine geschwungene Linie in Form einer Linie vor, ebenfalls in einem Winkel von 45 Grad, die entlang gleitet, bis sie mit den Kegeln kollidiert. Da sich die Ebene und die Kegel im gleichen Winkel befinden, bilden sie beim Überqueren Parabeln.
Aufgewachsen schneiden sich die Zapfen früher oder später mit einem oder mehreren anderen Zapfen. Wenn wir den Schnittpunkt der Kegel oder Kreise betrachten, erhalten wir gerade Linien der Voronoi-Kanten. In der Abbildung zeigt die rote Linie den Schnittpunkt der Kegel an. Wenn die Zapfen noch weiter wachsen (vertikal bis unendlich), wird sich die rote Linie weiter dehnen.
Wenn die Ebene gleitet und der erste Kontakt mit dem Kegel auftritt, sieht die resultierende Linie folgendermaßen aus:
Bei weiterer Bewegung des Flugzeugs entlang der Kegel werden wir sehen, wie sich Parabeln bilden:
Das Flugzeug bewegt sich weiter in der Szene. Für jeden Punkt, auf den es trifft, untersucht es benachbarte Punkte auf der Kehrlinie, die bereits Parabeln haben, und startet an diesem Punkt eine neue Parabel. Sie bewegt sich weiter und wächst, bis sich diese neue Parabel nicht mehr mit der zuvor überlagerten überschneidet. Dann schließt diese vorherige Parabel. Dies ist der Punkt, an dem sich Voronois Dreipunktlinien treffen.
Wie oben erwähnt, ist dies ziemlich schwer zu verstehen. Hier finden Sie Links zu Open Source-Implementierungen, die Sie verwenden und lernen können:
Inkrementelle Dreieckeinfügung
Eine andere Methode besteht darin, schrittweise jeweils einen Punkt einzufügen, beginnend mit einem Basisdreieck von drei Punkten außerhalb des möglichen Bereichs aller anderen Punkte. Diese Methode wird mit
O(n^2) und erfordert zum Zeitpunkt der Generierung nicht alle Punkte.
Wenn Sie einen neuen Punkt einfügen, wird der vorhandene Bereich definiert, in den er fällt. Dieser Bereich wird dann unterteilt und neue Bereiche erstellt.
Hier ist ein Open Source-Beispiel zum Verwenden und Lernen:
Fazit
Jetzt müssen Sie sich vorstellen, welche Voronoi-Diagramme Ihrem Spiel und seiner KI geben können. Wenn Sie ein richtig strukturiertes Diagramm von Knoten und Kanten haben, können Sie wichtige Informationen anfordern, damit jeder seine Erste-Hilfe-Sets und Katzenminze erhält und an feindlichen Türmen vorbeikommt.