Betrachten Sie die A * -Suche auf einer kachelbasierten Karte. Ein einfacher Code wäre: Wenn sich in dieser Zelle eine Einheit befindet, die nicht erreichbar ist, ist dies in Ordnung.
Es gibt jedoch ein Problem mit der Kartenauflösung. Wenn ich mir Warcraft 3 anschaue, haben Monster und Strukturen einen unterschiedlichen Radius, und Sie können sehr nah gehen, was eher vektorbasiert ist. Wie wurde dies implementiert?
Was ist die Standardlösung, um die Kollisionserkennung für sich bewegende Hindernisse in einen Pfadfindungsalgorithmus wie Warcraft 3 zu integrieren?
Antworten:
Ich kann nicht sicher sagen, welche Art von Ansatz von WC3-Entwicklern verwendet wurde, aber es sieht ziemlich nach Hierarchical Annotated A * aus. Der im WC3Editor definierte Einheitenradius wurde unverändert für die 3D-Modellskalierung verwendet, aber die tatsächliche Einheitengröße für die Pfadfindung war diskret, möglicherweise so etwas wie unitSize = (int) (unitRadius / 10). Es war nicht vektorbasiert, das ist sicher.
Angenommen, es gibt viele Pfadknoten, die ein hochauflösendes Knotenraster erstellen. Eine einfache Einheit wie ein Ghul hat eine Größe von 2. Um sie irgendwo in einem Gitter zu platzieren, benötigen wir 4 freie Pfadknoten nebeneinander. Ein Todesritterheld ist mit einer Größe von 3 etwas größer und nimmt insgesamt 9 Pfadknoten ein. Jetzt setzen wir 2 Zikkurate zusammen und lassen einen 2 Knoten breiten Raum dazwischen und schicken einen Ghul und einen Todesritter auf die andere Seite. Ghul wird in der Lage sein, zwischen zwei Zikkuraten zu wechseln, während der Todesritter sich bewegen muss. Wie kann es bestimmt werden?
Um zu sehen, ob ein Knoten eine Einheit bestimmter Größe aufnehmen kann, weisen wir jedem Knoten einen speziellen Freigabewert zu, der eine maximal zulässige Einheitsgröße definiert. Grundsätzlich bedeutet dies, dass für einen Knoten mehrere Begrenzungsprüfungen durchgeführt wurden und die größtmöglichen Grenzen als Freigabe des Knotens gespeichert wurden. Wenn wir also einen Todesritter auf einen Knoten setzen wollen, ist es so einfach, die Freigabe des Knotens mit der Größe des Todesritters zu vergleichen. Natürlich werden die Dinge viel komplexer, wenn mehrere Einheiten um Knoten konkurrieren, aber das ist eine andere Geschichte.
Weitere Informationen finden Sie in diesem Artikel:
http://harablog.wordpress.com/2009/01/29/clearance-based-pathfinding/
quelle
Es würde Tessellation verwenden, um Pfadregionen AKA-Navigationsnetze zu erstellen. Dieser Artikel erklärt das Konzept mit vollständigen Diagrammen.
Sie können weiterhin A * als Pfadfindungsansatz beibehalten. Ihr Netzwerk ist jedoch kein Raster (4-verbundener Graph) mehr, sondern ein Graph, der die willkürliche Konnektivität zwischen Ihren polygonalen Regionen darstellt. Sie müssen also Ihren Algorithmus anpassen.
quelle