Ich habe eine Sammlung von Punkten, die ein Gitter darstellen, ich suche nach einem Algorithmus, der mir die kürzeste Entfernung zwischen Punkt A und B bringt. Der Fang, der ein beliebiger Punkt (außer A und B) ist, kann ein Hindernis aufweisen, das den Weg behindert, und muss daher umgangen werden. Der Pfad darf sich nicht in Diagonalen bewegen.
Für alle anderen, die diese Art von Problemen lösen wollen, fand ich diese Referenzen sehr nützlich:
Dies ist ein ausgezeichneter Ort, um den A * Suchalgorithmus zu verwenden, einen heuristischen Suchalgorithmus, der optimale Pfade findet zwischen Punkten sehr schnell, auch wenn Hindernisse vorhanden sind. Die Idee besteht darin, das Gitter in ein Diagramm zu konvertieren, wobei jede Zelle im Gitter ein Knoten ist und in der Es gibt eine Kante zwischen zwei benachbarten Zellen, die nicht voneinander blockiert sind. Sobald Sie dieses Diagramm haben, ist die Antwort, die Sie suchen, der kürzeste Pfad im Diagramm vom Startknoten zum Zielknoten.
Um A * zu verwenden, benötigen Sie eine heuristische Funktion, die den Abstand von jedem Punkt des Rasters zum Zielquadrat "schätzt". Eine gute Heuristik dafür wäre, die Manhattan-Entfernung zwischen den beiden Punkten zu verwenden.
Wenn Sie nach einem einfacheren, aber dennoch äußerst effizienten Algorithmus suchen, um den kürzesten Pfad zu finden, sollten Sie sich den Dijkstra-Algorithmus
Hoffe, das hilft!
Dies ist ein einfaches Problem, das mit Breathth First Search gelöst werden kann
%Vor%