First off the question: Is it faster to use A* path finding on 2 lvls, the 2nd lvl being n^2 larger area per node? more importantly is it faster on average. Now to define the question ;) If your thinking of a grid with the sides of legnth n as your micro grid, or your fine tune path. and a grid made up of the same squars but using 4 of them to make one 4 thus a size of 2n. this makes checked the area of the make will be A/(n^2) = sG, small grid. and the big grid will be A/(4*n^2)=bG or big grid. so the ratio is 4sg = bg so the intial path is 4 times as fast. or 9 times as fast if you use a 3 by 3 gid as your macro and not a 2 by 2. now to clean it up you have the take the MACRO node where you change direction, and do a micro path on them, back and forward one square (useing the start and end point of the macro node path (those those nodes where the path changes direction. )) My question is do you save time... or rather enough time on average by useing a 2 teir aproach. also what downfalls can you see to useing this aproach? I would average the G values for the micro nodes for the value of the macro node.

What I think you're describing is called hierarchical pathfinding and it's used fairly commonly in games. However, when you do a micro level pathfinding you usually do it to a node two macro levels away rather than just the next one. This generally gives you better smoothness in the pathing.

Yes, this should make your algorithm run faster, since you're doing lots of short path-finding rather than one large one (the time complexity goes up N^2 with the size, so keeping the size down is a huge help). The time saved could make it possible for you to add many more nodes for better AI as well.

In a RTS game im developing ( taspring.clan-sy.com) we use three tiers of A*. The base one on each square, one on 8x8 and one on 32x32 squares. This lead to very fast path searches over the whole map (meaning we can be lazy and just get an individual path for each unit instead of trying to map them into groups and also dont have to put them in any sort of path que).

The main drawbacks is that you no longer get optimal paths (esp if a 32x32 happens to span several areas with high costs between them) and that it takes time to precompute the costs for the larger squares. Of course the "precompute" cost also comes back as soon as the map changes (new building or terrain changed) meaning we have to have a recompute que instead of a path que.

Just averaging the costs of smaller nodes into the bigger node get really bad results though (although it would alleviate the precompute cost) and instead I propose you define a center for each large node and compute the path costs between those centers which is what we do.

Its released under the GPL so feel free to check out the code if you think it might be usefull.

Here is something I wrote on the subject a few years ago.

What you have to bear in mind is that if the path is quite simple to construct (ie. there are few obstacles and your heuristic is good) then the path can be found in almost O(N) time anyway. The only benefit I'd see to the hierarchy there is that you can quickly reject a large number of nodes during processing - but a good data structure will let you do that anyway. Really what the hierarchy does is quickly find out which parts of the map are probably not worth expanding. The amount of performance benefit you see will depend on how often your algorithm tends to explore in the wrong direction.

One way in which the hierarchy could undoubtedly be a benefit is where you have precomputed paths from one side of a macro-tile to another side. Then your path is 90% done before you even begin.