Share
Was ist der sicherste Weg, wo befinden sich die meisten Gegner und wo befindet sich das nächste Gesundheitspaket? Diese häufigen räumlichen Beziehungsfragen können alle mit einer mathematischen Routine namens Voronoi effizient gelöst werden. Am Ende dieses Tutorials haben Sie die Werkzeuge und das Wissen, um Ihre Karten zu analysieren und Informationen zu erzeugen, die für den Realismus und den Erfolg der KI von entscheidender Bedeutung sind.
zusammenhängende PostsWenn Sie mehr über die KI (künstliche Intelligenz) erfahren möchten, lesen Sie folgende Informationen:
Eine räumliche Beziehung ist alles, was beschreibt, wie ein Objekt in einem Raum mit einem anderen Objekt zusammenhängt. Zum Beispiel: ihre Entfernung voneinander, wie viel Fläche jeder Bereich bedeckt und ob sich diese Bereiche überlappen oder wie viele dieser Objekte sich in einem Bereich befinden.
Diese Beziehungen tauchen immer wieder in Videospielen auf und können der KI oder dem Spieler sehr nützliche Informationen liefern.
EIN Voronoi-Diagramm beschreibt die räumliche Beziehung zwischen nahegelegenen Punkten oder ihren nächsten Nachbarn. Es ist eine Menge von Verbindungspunkten, die von Punkten oder Orten abgeleitet werden. Jede Linie einer Voronoi-Region liegt auf halbem Weg zwischen zwei Punkten.
Schauen wir uns ein Bild an, um ein Gefühl dafür zu bekommen:
Hier können Sie sehen, dass sich jede Linie genau in der Mitte zwischen zwei Punkten befindet und dass sie sich alle in der Mitte treffen. Lassen Sie uns noch einige weitere Punkte hinzufügen und sehen, was passiert:
Das wird jetzt interessanter! Wir fangen an, tatsächliche Regionen zu bekommen.
Also, was sagt uns jede Region? Wir wissen, dass wir uns innerhalb einer Region mit Sicherheit am nächsten Punkt befinden, der sich auch innerhalb der Region befindet. Dies sagt uns viel über das, was uns nahe ist, und ist die grundlegende räumliche Beziehung in Voronoi-Diagrammen.
Die Umkehrung eines Voronoi-Diagramms wird als Delaunay-Triangulation bezeichnet. Dieses Diagramm besteht aus Linien von jedem Punkt zu seinen nächsten Nachbarn, und jede Linie ist senkrecht zu der Voronoi-Kante, die sie kreuzt. So sieht es aus:
Die weißen Linien sind die Delaunay-Linien. Jede Delaunay-Zeile entspricht einer und nur einer Voronoi-Kante. Obwohl es auf den ersten Blick wie einige überlappende Kanten aussieht, schauen wir uns das genauer an.
Hier bezieht sich die grüne Delaunay-Linie auf die rosa Voronoi-Kante. Man muss sich nur vorstellen, dass sich der rosa Rand weiter erstreckt, und dann sieht man, dass sie sich kreuzen.
Mit Delaunay können Sie sehen, dass wir jetzt anstelle von Vielpunkt-Polygonen eine Reihe von Dreiecken haben. Dies ist unglaublich nützlich, da wir gerade einen Bereich in rendbare Dreiecke unterteilt haben. Diese Technik kann zur Tessellierung oder Triangulation von Formen verwendet werden. Super cool!
Es ist auch eine großartige Möglichkeit, die Menge von Punkten als Diagramm aufzubauen, falls Sie sich von einem Punkt zum anderen wagen möchten. Stellen Sie sich vor, die Punkte sind Städte.
In Ordnung, wir wissen, wie Voronoi aussieht; Lassen Sie uns nun einen Blick auf die Datenstruktur eines Voronoi-Diagramms werfen. Zuerst müssen wir die Punkte speichern, die dem Voronoi-Diagramm zugrunde liegen:
Klasse VoronoiPoint float x float y VoronoiRegion * region
Jeder VoronoiPoint hat einen Standort (x, y), und ein Verweis auf die Region, in der es sich befindet.
Als nächstes müssen wir das beschreiben VoronoiRegion:
class VoronoiRegion VoronoiPoint * Punkt Kante * Kanten [] // Unsere Liste der Kanten
Die Region speichert eine Referenz auf ihre VoronoiPoint, sowie eine Liste der VoronoiEdges das hat es gebunden.
Nun schauen wir uns das an VoronoiEdges:
class VoronoiEdge voronoiPoint * pointA VoronoiPoint * pointB float distance // Entfernung zwischen Punkt A und Punkt B float x1, z1, x2, z2 // um Anfang und Ende der Kante zu visualisieren
Eine Kante kennt die zwei Punkte, die sie definieren, sowie den Abstand zwischen ihnen. Zur visuellen Darstellung oder zum Erstellen der tatsächlichen Form des Polygonbereichs sollten Sie die Start- und Endpunkte der Kante speichern.
Und da haben wir es. Mit diesen Informationen können wir das Voronoi-Diagramm problemlos verwenden. Weiter unten wird gezeigt, wie das Voronoi-Diagramm tatsächlich erstellt wird. Im Moment wollen wir uns jedoch einige Beispiele ansehen, wie wir die Daten verwenden können.
Schauen wir uns noch einmal das Voronoi-Diagramm der Punkte an.
Wenn jeder Punkt ein Gesundheitspaket darstellt, können Sie schnell herausfinden, wo der nächstgelegene war - aber zuerst müssen Sie die Region ermitteln, in der Sie sich befinden. Voronoi bietet keine effiziente Möglichkeit, dies direkt aus der Box herauszufinden. Sie können jedoch einen Verweis auf jede Region in einem Quadtree oder einem R-Tree speichern, sodass die Suche schnell erfolgen kann. Und sobald Sie Ihre Region haben, können Sie ihre Nachbarn und ihre Nachbarn finden.
Wenn zum Beispiel das Gesundheitspaket in Ihrer Region nicht mehr vorhanden ist, benötigen Sie einen Weg, um das nächstgelegene zu finden. Wenn wir auf unsere Datenstruktur und den Pseudocode oben verweisen, sehen wir, dass wir aus einer Region ihre Kanten herausfinden können. Und mit diesen Kanten können wir dann die Nachbarn bekommen. Schnappen Sie sich den nächsten Nachbarn und dann können wir sehen, ob er ein Gesundheitspaket hat.
Die Delaunay-Triangulation kann auch hier verwendet werden. Es besteht aus Linien zwischen den einzelnen Gesundheitspaketen. Dies kann dann mit A * Pathfinding durchlaufen werden, um die nächstgelegene Packung zu finden, falls jemand die Packungen in Ihrer Nähe erfasst hat.
Lassen Sie uns statt Gesundheitspaketen jeden Punkt als gegnerischen Wachturm vorstellen. Sie müssen den sichersten Weg durch sie finden, ohne dabei erwischt zu werden. Eine übliche Methode zum Durchqueren eines Diagramms in Videospielen ist die Verwendung des A * -Algorithmus (http://en.wikipedia.org/wiki/A*_search_algorithm). Da das Voronoi-Diagramm ein Diagramm ist, ist dieses einfach einzurichten. Sie benötigen lediglich einen A * -Algorithmus, der generische Diagrammstrukturen unterstützt. ein wenig vorausplanung kann sich hier auszahlen.
Wenn der Graph eingerichtet ist, müssen wir jede Kante wiegen. Der Gewichtswert, um den es uns geht, ist der Abstand von diesen Schutztürmen, und wir können diesen Wert direkt aus unserer Datenstruktur ziehen: jeweils VoronoiEdge kennt den Abstand zwischen den beiden Punkten bereits. Normalerweise ist ein niedrigerer Wert an einer A * -Kante besser, in diesem Fall möchten wir jedoch, dass der größere Wert idealer ist, da er die Entfernung zum Turm darstellt.
So sieht der Startgraph aus, wenn wir uns von Punkt A nach Punkt B bewegen wollen:
Wenn wir das Gewicht auf jede Kante anwenden, sehen wir, welche Route sich am besten eignet:
Die roten Kanten repräsentieren die nächsten Begegnungen mit den Türmen. Die Orange weniger so; weniger gelb als das; und schließlich ist grün das sicherste. Wenn Sie A * mit diesen Gewichten ausführen, sollte der folgende Pfad erzeugt werden:
Wenn Sie die Gewichte auf diese Weise verwenden, ist das nicht gewährleistet am schnellsten Weg, aber die am sichersten, was du willst. Es wäre auch ratsam, wenn die KI in der Nähe dieses Weges bleibt und Streunungen vermeidet!
Ein weiterer Schritt, den Sie unternehmen können Garantie Sicherer Durchgang ist das Entfernen von Kanten, die unter einen Mindestabstand fallen. Wenn zum Beispiel jeder Wachturm einen Sichtbereich von 30 Einheiten hatte, dann könnten alle Kanten, deren Abstand zu ihren Punkten geringer ist als diese, aus der Grafik entfernt und überhaupt nicht durchquert werden.
Eine andere Anwendung ist es, die breiteste Route für Einheiten zu finden, die groß sind und nicht durch enge Räume passen. Da jede Kante einen Abstand zwischen ihren beiden Punkten hat, wissen wir, ob sie durch diesen Raum passen kann.
Wenn wir stattdessen eine Delaunay-Triangulierung des Diagramms verwenden, würden wir von jedem Wachturm aus Linien erhalten. Eine an einem Turm stationierte Wächter-KI könnte schnell herausfinden, was die anderen Türme in der Nähe sind, und möglicherweise zu einem übergehen, um ihn bei Bedarf zu unterstützen.
Angenommen, Sie möchten ein Paket Katzenminze für ein paar niedliche Kätzchen auf einem Feld abwerfen. Was ist der beste Ort, um es fallen zu lassen, damit die meisten Kätzchen es genießen können? Dies könnte eine sehr, sehr teure Rechnung sein. Aber zum Glück können wir mit unserer Delaunay-Triangulation eine fundierte Vermutung treffen.
Spitze: Denken Sie daran, dass die Delaunay-Triangulation nur das Inverse des Voronoi-Diagramms ist. Es wird einfach gebildet, indem jeder Voronoi-Punkt mit seinen Nachbarpunkten aus seiner Kantenliste verbunden wird.
Mit dieser Sammlung von Dreiecken können wir die Fläche untersuchen, die jedes Dreieck abdeckt. Wenn wir das Dreieck mit der kleinsten Fläche finden, haben wir die drei nächstgelegenen Punkte oder Kätzchen. Es ist zwar nicht das dichteste durchschnittliche Rudel Kätzchen im Feld, aber es ist eine gute Vermutung. Wenn wir mehrere Catnip-Pakete ablegen können, können wir einfach markieren, auf welche Dreiecke wir uns bereits bezogen haben, und das nächstkleinere bekommen.
Die Darstellung dieser Bereiche wird auch als bezeichnet Kreisen der Delaunay-Triangulation. Jeder Kreis ist der größte Kreis, der in die Punkte der Dreiecke passen kann. Hier ist ein Bild der Kreiskreise für ein Voronoi-Diagramm:
Sie können den genauen Mittelpunkt der Kreise verwenden, um die Mitte des Bereichs zu bestimmen, in dem das Catnip-Paket abgelegt werden soll. Der Radius des Kreises ist tatsächlich eine bessere Methode, um das beste Dreieck anstelle des Dreieckbereichs zu bestimmen - insbesondere, wenn zwei Punkte eines Dreiecks sehr nahe beieinander liegen und einer weit entfernt ist, wodurch ein sehr scharfes Dreieck mit wenig Fläche entsteht, das jedoch nur eine Darstellung darstellt Punkte, die eigentlich ziemlich weit auseinander liegen.
Es gibt verschiedene Möglichkeiten, Voronoi-Diagramme zu erstellen. Der Zeitpunkt, zu dem Sie die Daten haben, kann dabei helfen, die zu verwendende Technik zu bestimmen.
Die schnellste Methode wird als Fortune-Algorithmus bezeichnet. Es ist O (n log (n)) und erfordert, dass alle Punkte, die zum Erzeugen des Graphen verwendet werden, zum Zeitpunkt der Erstellung vorhanden sind. Wenn Sie später neue Punkte hinzufügen, müssen Sie das gesamte Diagramm neu generieren. Dies ist vielleicht keine große Sache mit wenigen Punkten, aber wenn Sie etwa 100.000 haben, kann es eine Weile dauern!
Die Implementierung dieses Algorithmus ist nicht trivial. Sie müssen Parabeln schneiden und einige Sonderfälle behandeln. Es ist jedoch die schnellste Technik. Glücklicherweise gibt es bereits viele Open Source-Implementierungen, die Sie verwenden können, und wir haben sie hier verlinkt.
Schauen wir uns kurz an, wie es funktioniert.
Der Algorithmus besteht darin, eine Linie (entweder vertikal oder horizontal) über die Fläche von Punkten zu streichen. Wenn es auf einen Punkt trifft, beginnt es, eine Parabel zu zeichnen, die mit der geschwungenen Linie fortfährt. Hier ist eine Animation des Prozesses:
(Mit freundlicher Genehmigung von Mnbayazit, freigegeben für die Public Domain.) Die sich kreuzenden Parabeln erzeugen die Voronoi-Kanten. Warum aber Parabeln??
Um dies zu verstehen, stellen Sie sich jeden Punkt mit einem sich erweiternden Ballon vor, bis er mit einem anderen Ballon in Kontakt kommt. Sie können diese Idee in Kreise extrahieren, die sich auf einer 2D-Ebene erstrecken. Wir gehen noch einen Schritt weiter und platzieren an jedem Punkt einen umgedrehten Kegel, einen Kegel mit einer Neigung von 45 Grad, der ins Unendliche geht. Dann stellen wir uns die Sweep-Linie als eine Ebene vor, die sich ebenfalls um 45 Grad bewegt, bis sie mit den Zapfen in Kontakt kommt. Da die Ebene und die Kegel im gleichen Winkel liegen, erzeugen sie beim Überschneiden Parabeln.
Wenn die Kegel vertikal wachsen, schneiden sie sich mit einem oder mehreren Kegeln. Wenn wir uns anschauen, wo sich die Kegel oder Kreise schneiden, erhalten wir die geraden Linien der Voronoi-Kanten. Hier sehen Sie die rote Linie, an der sich die Kegel schneiden. Wenn sich die Kegel weiter ausdehnten (vertikal bis unendlich), würde sich die rote Linie weiter ausdehnen.
Wenn das Flugzeug über einen Kegel streicht und einen ersten Kontakt mit ihm herstellt, wird eine Linie so erzeugt:
Während sich die Ebene durch die Kegel bewegt, können Sie die Parabeln sehen, die sich bilden:
Das Flugzeug geht weiter durch die Szene. Für jeden Punkt, auf den es trifft, werden die Nachbarpunkte auf der Sweep-Linie untersucht, die bereits Parabeln enthalten, und eine neue Parabel für diesen Punkt wird gestartet. Es bewegt sich weiter und wächst, bis sich diese neue Parabel mit einer anderen überschneidet als zuvor. Diese vorherige Parabel ist dann abgesperrt. Hier treffen sich die Voronoi-Linien von drei Punkten.
Wie bereits erwähnt, ist es ein bisschen kompliziert. Hier sind einige Open Source-Implementierungen, die Sie verwenden und untersuchen können:
Eine andere Methode ist das schrittweise Einfügen eines Punkts, wobei mit einem Basisdreieck von drei Punkten außerhalb des möglichen Bereichs aller anderen Punkte begonnen wird. Diese Technik ist O (n ^ 2) und erfordert nicht, dass zum Zeitpunkt der Generierung alle Punkte vorhanden sind.
Wenn ein neuer Punkt eingefügt wird, sucht er nach einer vorhandenen Region, in die er passt. Diese Region wird dann unterteilt und neue Regionen werden erstellt.
Hier ist ein Open Source-Beispiel, das Sie verwenden und untersuchen können:
Inzwischen sollten Sie ein Gefühl dafür haben, was Voronoi-Diagramme für Ihr Spiel und seine KI bieten können. Mit einem gut strukturierten Graphen von Knoten und Kanten können Sie wichtige Informationen abfragen, um sicherzustellen, dass die Jungtiere die benötigte Katzenminze erhalten und dass Sie den sichersten Weg wählen, um sie zu erreichen. Und für den Fall, Sie können auch herausfinden, wo sich das nächste med Kit befindet.
Accentsconagua