Pathfinding js library

  • http://qiao.github.io/PathFinding.js/visual/

    Best-First-Search and Trace appear to be the fastest methods and A* is kinda slow.

  • Try Construct 3

    Develop games in your browser. Powerful, performant & highly capable.

    Try Now Construct 3 users don't see these ads
  • Well this was neat! IDA* didn't seem to do very well

  • I don't think any pathfinding algorithm is best in all circumstances. In two tries I was able to draw a map that A* performed best on (714 operations, vs. 767 best-first, 803 trace). A* is pretty smart at trying likely routes. It seems if you draw a map where there is a long likely route that's actually blocked off at the end, and have a fairly indirect route to the target, then A* is sometimes fastest at working out the first path is a dead-end and then quickly identifying a route down the second path, whereas other algorithms sometimes revert to a slow iteration working backwards. Basically given arbitrary circumstances I think A* manages to never be terrible.

    Wikipedia says A* "considers fewer nodes than any other admissible search algorithm with the same heuristic". The cost of running the search is also amortized by running it in a web worker, so it runs in parallel to the game and therefore shouldn't ever impact the framerate. So I think it's not a problem as it is.

    Still, it's a very cool demo and great visualisation of how the algorithms work!

  • I draw a more or less complicated map, first time A* needed 24ms, second time only 3ms...

    I think A* is very good in general. IDA* by the way was not able to find the path in my map.

Jump to:
Active Users
There are 1 visitors browsing this topic (0 users and 1 guests)