Slow A* Pathfinding Routine

[JP]

My 2 cents:

You can make it even faster by not using vector2d::getDistanceFrom but instead vector2d::getDistanceFromSQ which saves doing a square root operation (costly), which seems to be done 8 times for every time round the while loop.

You just use the distances as the cost so it doesn't matter if it's a squared distance or not as it will still be the same but on a larger scale.

[sudi]

I once wrote a a pathfinder and it was actually quite fast i think.

Download

[agamemnus]

A great container for such a thing is a heap. It will always make the cheapest node on top w/o the overhead of sorting the entire collection of nodes. This is already implemented for you if you use the stl priority_queue as your container.

A running list of maybe even 1000 active nodes re-sorted per node expansion (using quick-sort) would not really take too much time, I think. For my game, where I have a map of Europe (with nodes as cities and paths as roads, sea routes, and rivers), I only have at most 20 or so active nodes at a time. I suppose a search space where nodes are connected in a web (rather than a fractal-like tree), the running list will not be large.

you know one quick loop to insert the element at a desired position is much more faster than doing multiple searches on the whole array...
I guess to sort the open list so the 1st element is the one with the most cost and the last is the one with the least cost can also improve the calculation a bit more...

That is an optimization based on your search space, though. For me, opening the least-cost node will usually yield several extra nodes, so essentially, your method would become a bubble sort!

[Lonesome Ducky]

My 2 cents:

You can make it even faster by not using vector2d::getDistanceFrom but instead vector2d::getDistanceFromSQ which saves doing a square root operation (costly), which seems to be done 8 times for every time round the while loop.

You just use the distances as the cost so it doesn't matter if it's a squared distance or not as it will still be the same but on a larger scale.

Wouldn't it be better to estimate the distance only in the ways you can move? Say you're pathfinding with 8 directions. Wouldn't it be better to estimate the distance with those 8 directions, than in a direction you can't move?

[REDDemon]

Pathfinding doesn't require much time. The most difficult thing is to create "realistic path" and moving lots of units. if you need some suggestion on how to improve the algorithm just pm me.

[fabs]

It helps to have at least a few comments in the code so people can work out what the hell the variables are for.
e.g.

Code: Select all

bool findPath(u32 sx, u32 sy, u32 ex, u32 ey, array<Node *> &path);

what is sx, sy, ex, and ey?
How would anyone know?

I assume it's startX and endX for example.

Without looking at all the code, I can't imagine why that would slow it down rather than make it incorrect.

Without a decent heuristic it basically becomes Dijkstra's algorithm which pretty much uses brute force to find a path. The heuristic tells it which direction to prefer to test towards, so that it can find a result faster.