Is my A* implementation too slow?

Questions & Answers
1

Hi there,

For my bachelor thesis I need to compare A* to the Jump Point Search algorithm based on my own implementations in the Unity engine. I’m using 512x512 map files from to test them, for example AR0014SR.map.

Exported screens from after the algorithms have run: (top one is A*, bottom one JPS, red = expanded tiles, blue = best path)

[11644-jump+point+search.png|11644]

While JPS only takes ~190ms, standard A* is at over 5 secs - running on an i5-3450. Is this normal? Shouldn’t even A* accomplish this in a few ms on a grid of that size? (They find different paths, but both at a length of 229 tiles, so that seems correct.)

For the implementation, I’m using a priority queue (based on this) and the A* based on this article. I even tried a completely different A* implementation with a standard List that gets sorted everytime after I insert a node, but the time was also around 5 secs.

Thanks!

2

Benchmarks are always difficult, especially comparing two algorithms where the way that you implement have a great impact.

I didn’t know JPS, but A* take 5 seconds I think that is to mutch.

I recommend first to take some base values from already existent and optimized libraries. Search algorithms are part of “graph theory” and you will find good a* algorithms in graph libraries (c# - .NET graph library around? - Stack Overflow). Other alternative is take a look on excelent A* Pathfind project (A* Pathfinding Project), it is open source an there is a free version.