It seems like it should be easy to call A* without recalculating the entire grid each time. Are there any articles that discuss this? Are there any gotchas that I need to be wary of? It seems pretty straightforward, just check to see if the new destination has been populated, and calculate it if it hasn't. Thanks in advance, Ralph

Provided the cost of a path can't change, vanilla memoization will work fine. Say you compute an optimal path from A to C, and the path passes through B. Then you want to find the optimal path from A to B. If you memoize all the partial paths when computing the first path, then you've got this path already. The stored path must be optimal, because if it were not, then the path you computed earlier from A to C wouldn't be optimal (since it passes through B); but we know it is, so the path from A to B is optimal.

The only consideration I can think of is that this will be very memory-intensive on a large grid if you're storing this for many pairs of cells.

Quote: Original post by apocnever
Provided the cost of a path can't change, vanilla memoization will work fine. Say you compute an optimal path from A to C, and the path passes through B. Then you want to find the optimal path from A to B. If you memoize all the partial paths when computing the first path, then you've got this path already. The stored path must be optimal, because if it were not, then the path you computed earlier from A to C wouldn't be optimal (since it passes through B); but we know it is, so the path from A to B is optimal.

The only consideration I can think of is that this will be very memory-intensive on a large grid if you're storing this for many pairs of cells.

Thatnks, that what I thought. It's 500x500 max for now, so the memory requirements aren't that bad for a modern computer. There will only be one path stored at a time, so memory requirements are minimal. I"m using the simple array-based implementation, mainly because it's simple and avoids any memory allocation. I'm planning to use this strictly when moving the cursor around to determine possible points that a given unit can go to, or determining the optimal hex to attack from/move to for the AI, so path cost is invariant for a given path.

<sigh> now the the fun of implementing it correctly. It's not very complicated, but I it will be a bit tedius. Given the speeds I need, I'm probably going to just implement it inline to be safe.

Thanks,
Ralph

I believe you can calculate all optimal paths at the same time, as long as you dont cache heuristics. Then, at each a* iteration, when you select the node in the open list, just evaluate the heuristic as the minimum of the heuristics of each unreached destinations.

wouldnt that work?

edit: Since you take the minimum, your heuristic should always be admissible for all destinations, thus the optimal paths...

edit2: of course, Im talking about a selection of optimal paths, if you want all of them, just run disjkstra...

if you cache paths, there are alot of algorithms from virtual-memory-page-swapping which could be used: FIFO / SecondChance / etc...

By storing one path, all sub-paths are there, so it shouldnt be to hard to make 1MB of memory of cached paths improve your overall speed.

Then, if everything is hashed :-)

uncutno, could you give a brief overview of how this might work please? I've not looked into path caching methods, since in general I don't concern myself with highly optimised implementations, although I would like consider this for improving one of my applications that performs pathfinding in a continuous state space (using a discretised action space).

Cheers,

Timkin

ok, you could do it the simple way;

whenever you have calculated a path, store it, then when you calculate a new one, you see if you already have it. To decide what path to throw away, use an algorithm like the ones used to decide what pages to swap... this way, paths that was used often (or got parts of it used often) would stay, and more rare paths would be recalculated...

now you need to give your paths some sort of keys, like how do you know if path X-Y is part of any of the paths in the cache?

This is only usefull if the same paths are used alot, if they not you will only add overhed while looking for paths in the cache...

This is sort of a hybrid between pure A* and preprocessed nodemaps, you could for example divide your map into areas, and then chach the shortest ways from one area to another area... later, when a new path from area X to area Y was needed, you could reduce the searchspace dramatically... look up nodemaps for bots to find stuff about this... A path from base A to base B would be needed all the time (good for caching), but a path from tile X to tile Y would only happend once a while (bad for caching)...

When i created my last A* pathfinder, i had a pretty small area, so a search didnt take to much time, but still i ran it asyncronized in another thread, and
even if the reaction time was 0.5 sec instead of 0.02 sec, it was great (the game seemed to be much more responsive instead of lagging a little every time i calculated a path...)