Hi there, im creating an RTS with OGL and i have decided to use A* for path finding. However with maps of size 512/1024 (1024^2) is just to many possible states to do path finding in, and considering that my terrain will be static i had an idea. If i could sub-divide the world into AABBs that had only tiles in them that were either passable/unpassable, cant i just link these AABBs and do my A* on that. It will bring my Expandable nodes down from 1024 to about 100, since my game consists of alot of open spaces with minor bottle necks. I want these AABBs to have only links to other passable aabbs and so i dont even have to check if the AABB is passable. (*and obviously ill just discard unpassable AABBs) That leaves me with a simple direct line distance function for cost and ofcourse ill take into consideration the Distance between the center of the two AABBs. ---------------------------------------------------------------------------- Okay thats all simpe stuff in theory, but now what happens when you add dynamic buildings/units? Well i concluded to solving the path first using the AABBs and then at each link to just do that short distance to the next link on a Tile2Tile scale? Will this work? Yes i forsee the problem of a unit going around only 2 find a friendly building bloking the way, how can this be dealt with?

The problem with you're sollution will work for the pathplanning (shortest route) but not for the pathfinding(avoiding obstacles etc.). A normal grid is dense enough for the type of pathfinding you want to do but has the downside of having big amount of nodes.

The sollution is use local pathfinding methodes (collision detection/avoidence) with your AABB nodes. It would probably be best to use a line of sight checking method aswell where a unit check if a direct line to the intended goal is possible.

Remember to only use the shortest route pathplanning for finding a route, not for precise movement.

Quad and oct tree decompositions of the state space have been used successfully for improving the efficiency of pathfinding algorithms in open spaces (that is, effectively unbounded state spaces). You typically define a local horizon and perform a decomposition within it and then perform heirarchical pathfinding within the tree. You should be able to find information via citeseer. Failing that, check out the proceedings of the Intelligent Autonomous Vehicles conference of last year (IAV2004), published by Elsevier (in book form). I recall a paper on just this topic.

Cheers,

Timkin