4 ms·

Look into RRT, it works way too well for how simple it is, and it's great for reducing search complexity for pathfinding.

• HelloNurse 10y ago
  There's pathfinding and pathfinding. This thread is about exact algorithms for rectangular grids, not approximate algorithms for a continuous space.
  • derefr 10y ago
    There's pathfinding and pathfinding, and then there's pathfinding. Social network analysis also requires route-planning for degree-of-separation computation, but since in those cases you just have a digraph, not a [continuous or discrete] metric space, all you get to use there is Dijkstra. (Anyone who knows better, I'd be delighted to find out I'm wrong—for the sake of my own search runtimes.)
  • triclops200 10y ago
    They're already using a heuristic, I gave them another one to try. It's easy to discretize random samples to a grid.
    • HelloNurse 10y ago
      No, A* heuristics (including extreme ones like jump point search) do not prejudice optimality of the found shortest path, the same that would be found by Dijkstra's algorithm without heuristics. They are only "heuristic" with respect to the subordinate purpose of finding the optimal path cheaply (ignoring as many graph nodes as possible), while the RRT heuristic produces a suboptimal result (not the absolute shortest path, but the shortest path that goes through arbitrarily chosen nodes)