Ich mache Wegfindung auf einem 2D-Gitter.
Ich muss die Entfernung als eine meiner Heuristiken berechnen.
Außerdem muss ich den nächsten Punkt zurückgeben, wenn der vollständige Pfad nicht gefunden wird.
Das Berechnen der genauen Entfernung mit doppelter Genauigkeit scheint unnötiger Aufwand zu sein. Gibt es eine schnelle Annäherung, die ich verwenden kann, die immer noch genau genug ist, um meine Bedürfnisse zu erfüllen? (innerhalb der Rundungsgenauigkeit von 1)
Übrigens sind Pfadlängen typischerweise nur etwa 5-30 Knoten, also wäre es am Ende nicht sinnvoll, eine genauere Funktion zu verwenden.
Ich muss den nächsten Punkt zurückgeben, wenn der vollständige Pfad nicht gefunden wird.
In diesem Fall könnten Sie die Quadratwurzeloperation in der Abstandsberechnung überspringen, d. h. quadrierte Abstände mit nur dy * dy + dx * dx vergleichen.
Dies funktioniert seit a 2 & lt; b 2 wenn und nur wenn a & lt; b für zwei beliebige Entfernungen a und b .
In einem 2D-Gitter würde dies rein mit ganzen Zahlen implementiert werden.
Wenn Sie nicht-ganzzahlige Werte benötigen, würde ich wahrscheinlich mit double s gehen, bis sich das als Engpass erweist.
Wenn es sich um ein 2D-Raster handelt, können Sie die Entfernung Manhattan in Betracht ziehen. Dadurch können Sie ständig in Rastereinheiten arbeiten und die Quadratwurzel vermeiden. Wie aiobe vorschlägt, ist dies wahrscheinlich eine Mikrooptimierung.
Etwas besser als Manhattan Entfernung und fast so schnell wäre:
%Vor%Es ist genau, wenn entweder dx oder dy Null sind. Der Fehler auf der Diagonale beträgt etwa 6% und der maximale Fehler beträgt etwa 12%.
Und das kann verbessert werden, indem ein anderer Begriff hinzugefügt wird:
%Vor%Dies hat einen maximalen Fehler von weniger als 7% und der Fehler entlang der Diagonalen beträgt weniger als 3%.
Tags und Links algorithm performance distance