Pathfinding js library

Discussion and feedback on Construct 2

Post » Mon Sep 22, 2014 7:57 am

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

Best-First-Search and Trace appear to be the fastest methods and A* is kinda slow.
B
45
S
11
G
4
Posts: 515
Reputation: 7,389

Post » Mon Sep 22, 2014 9:05 am

Well this was neat! IDA* didn't seem to do very well :)
B
34
S
9
G
3
Posts: 517
Reputation: 5,206

Post » Mon Sep 22, 2014 10:37 am

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!
Scirra Founder
B
387
S
230
G
87
Posts: 24,249
Reputation: 192,250

Post » Mon Sep 22, 2014 7:52 pm

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.
B
11
S
2
Posts: 213
Reputation: 1,266


Return to Construct 2 General

Who is online

Users browsing this forum: No registered users and 8 guests