Ich suche nach der besten Lösung für die Wegfindung in meinem Spiel. Die Karte ist letztendlich gitterbasiert, aber Objekte werden mithilfe von Floats positioniert und können sich in jede Richtung zu einem beliebigen Punkt auf der Karte bewegen. Der "Boden" in meinem Spiel hat einheitliche Bewegungskosten, aber natürlich kann es Hindernisse geben, die den Weg blockieren. Die meisten Hindernisse werden statisch sein, und obwohl es andere animierte Einheiten im Spiel geben wird, kann ich davonkommen, sie nicht zu berücksichtigen - es ist ein Strategiespiel im Stil eines isometrischen Themenkrankenhauses , also keine Kämpfe.
Die meisten Artikel zur Wegfindung, die ich gesehen habe, behandeln 3D- oder gitterbasierte 2D-Bewegungen. Irgendwelche Vorschläge für etwas, das meinen Anwendungsfall abdecken könnte? Danke vielmals.
quelle
Antworten:
Dies wird als "Problem der Pfadfindung in jedem Winkel" bezeichnet. Sie haben grundsätzlich zwei Möglichkeiten:
Generieren Sie ein Navigationsnetz für Ihre Karte und durchsuchen Sie dieses mit A *
Durchsuchen Sie ein Raster mit einem Algorithmus, der speziell für die Pfadfindung in beliebigen Winkeln vorgesehen ist. Traditionell war die A * + -Pfadglättung (lineare Interpolation usw.) der Weg , aber heutzutage ist Theta * eine beliebtere Alternative , die einfacher zu implementieren ist, schneller läuft und bessere Ergebnisse liefert als die Pfadglättung.
Alle oben genannten Methoden führen zu nahezu optimalen Ergebnissen. Wenn Sie aus irgendeinem Grund optimale Ergebnisse benötigen , wurde dieses Papier vor einigen Wochen veröffentlicht. Ich hatte jedoch noch keine Gelegenheit, es zu lesen, daher weiß ich nicht, wie effizient es ist oder wie schwierig es zu implementieren ist.
quelle