A* Path finding.

Hi,

I implemented the A* Algorithm and now I am trying to optimize it...

The problem is usual, I have to go from A to B, calculating the *shortest* path. I am using as Euristic the Euclidienne distance from each evaluated point to the final destination.

Now, I have a limited movement points, therefore, to optimize the calculation time, I don't want to use as destination B, but I would like to use a point C. C being on (AB) at a distance cost a bit over the allowed movement. The idea behind that being to restrict the area of calculation.

Can anyone help me to find the lower cost solution to find C coordinates?

Thanks =)

I would "virtually walk" the path (AB) and add up the costs per step. if costs > allowed { return C(x,y) }.

I don´t know much theory, the "Euclidienne distance", is that sqrt(deltax+deltay)? This would be the first optimization, getting rid of the square root.

Hirsch,

if I "virtually walk" the path (AB), then I have to calculate the moving cost from A to B which is the heavy part of A*.

In my specific case, the working area is 50*50. A* can have to evaluate 2500 cost. My max movement being around 6. The idea is to calculate a partial destinal to reduce the cost calculation to a 7*7 square, and to reproduce that for each turn antil b is reached.

As for the "Euclidienne distance", it is what you described. Thanks for the tips, was already implemented this way =)

From my understanding of the algorithm this is impossible. You need the full run to get the shortest path.

What kind of program is this? A Game? Maybe you can precalculate all possible paths when the map file is being compiled or something...

You could also use another less precise distance model like this:
1 step vertical or horizontal = 10 units
1 step diagonal = (ca.) 14 units
And thus you can easily sum up the costs in steps without knowing the "real" distance. "add" is a good operation for optimization too

The program is in fact a "battle engine" for a web game (http://www.holy-war.com). People are planning the way their troops act/react. In the actual version of it, troops can walk on the same "square" as other troops. I want to avoid that, therefore, I have to generate some path finding.

I cannot precalculate the path because my obstacles (other troops) are moving.

I know that if I am cutting the global path in several parts, it will no more be the shortest path, but I think that it will still be quite efficient.

I got an idea:
You could calculate the "ideal" path with the A* (the full path) and cache it for the next steps. In this step you don´t consider the other troops at all yet.
Then you find only the troops inside your 7x7 and re-do the A* with destination C on (AB) for this part only. Do until you reached B.

Considering that from one round to the next the others´ troops will probably have moved too, it should bring you to the destination still quite quickly.
IMHO this would need some hours of simulation before going public to see if no ships can get stuck circulating around each other (I have seen this effect many times in older games ).

Another idea: move the A* calculations for each user to the client ("delegate" the work LOL). They could supply input like "I want to go to place B using the path (1,1)(1,2),(1,3),..." and you´d only check if it is a valid way to walk or not...

Hi There Guys

I have worked many times using this algorithm. One that that you must remember is that A* calculates the shortest distance from your root to all nodes with a lesser distance from the root than your destination.

If you had to closely trace the algorithm you rarely follow a nice path but the.

Keeping an array for each node of distance from the root and a parent child relationship is the trick to the algorithm.

I studied the theory of this algorihm during University and it can be proved that there is no better, more efficient, way of calculating the shorted path to a node. Using a heuristic like euclidean distance does not ensure you will 100* always get the shortest path.

Hope this helps
Sam

I made a quick drawing to illustrate my concern.

http://maldor.free.fr/holywar/a-star.gif

The top schema is the basic A-star effect on the first attempt of move, the bottom one detail the effect of what i want to implement.

Color code:
-> Blue = affected area by the calculation. Cost are calculated for this whle area. on the second schema, a purple line delimit this area for each turn.
-> Red = start / end / intermediate destinations
-> Yellow = shortest flying path not taking into account obstacles and cost
-> Green = resulting path.

I know that my suggestion can result on weird move and will surely not give the same result as the overall calculation. However, it will optimize the calculation amount drastically.

So my basic aim is now to find the most efficient way to calculate those intermediate red spots. (they should not be occupied as well)

Thanks for your help guys =)
Matt