say your level size is huge, like 13.2 million units by 13.2 million units, and your collision map resolution is 1 unit.

and you want to A* between any two points A and B on the level (outdoor settings only).

obviously, a search area over 13 million wide is a little on the large side.

so you split it up into manageable sized chunks?

then how do yo set the goal for each chunk?

find the closest open edge node/tile/square in the desired direction that is adjacent to an open node on the next chunk edge?

A* to that edge goal, then move to the adjacent chunk's open edge node, then continue pathing across chunks until the final goal is reached?

does that sound right?

Create a hierarchy of waypiont graphs, you can even map higher level waypoints to certain points of interest (the cave entry, the big rock, the bridge etc.). Get the closest waypoint off your start and end waypoint and start A* on this level. Then go down the level, on each level execute the A* to the next waypoint of the higher level. The benefit of this approach is, that you dont need the hi-resolution graph in memory, just the highest level is necessary and the rest on demand, and it is more natural. A human would not take the shortest path, he would most likely take the rout from town to town to travel over long distance.

Create a hierarchy of waypoint graphs

forgot to mention: random procedurally generated world. is waypoint graph generation possible, given a random arbitrary level design?

when checking into it, nav meshs, A*, and waypoint graphs were commonly mentioned. but with both nav meshes and waypoint graphs they seemed to assume a human edited level map, with the level designer placing the nav points manually by hand, or "painting" the nav mesh tri's.

if i can generate a waypoint graph, life becomes much easier.

this article shows promise:

http://www.gamedev.net/page/resources/_/technical/artificial-intelligence/navigation-graph-generation-r2805

D* is another possible approach that may suit this case well. i have yet to check into it.

i assume waypoint graph / navmesh generation from arbitrary random level maps is possible, correct?

but i understand that they are not necessarily easy, eh?

Norman, what you're describing is known as Hierarchical Pathfinding.

By solving at the coarse-grained level first you get a rough approximation of your overall route and usually this high-level route won't be invalidated by small dynamic objects in the level either, so you can cache it. Then you only need to do a detailed solve of your current map chunk over to the next map chunk. If using A* as your search then this is known as HPA*.

If you're interested in the auto-generation of Nav-Meshes then Recast is the de-facto open-source implementation of navigation meshing. You just chuck in a polygon soup and it spits out a navigation mesh.

i did a google search for "waypoint graph generation"

this was the first hit:

http://www.gamedev.net/page/resources/_/technical/artificial-intelligence/navigation-graph-generation-r2805

while talking about hierarchical waypoint graphs, it says:

"Indeed, first we can identify the super-node corresponding to the region where the agent is located and the super-node for the destination region. An A* run on super graph can return either "no path" if the regions are not connected, or a navigable path in super graph. This path consists of a list of regions the agent needs to visit in order to reach its destination. Navigation within each region is handled by a-star on regular graph."

in my case, the set of collision maps that lie in line of sight from start to goal would be the list of regions to visit. there is no special connectivity. its just a 2d array[500][500] of map squares, and each map square has an array[88][88] of collision maps, and each collision map is an array[300][300] in size, at a resolution of 1 unit = 1 foot. about the only thing special is oceans. in that case, a search of the far edge of an area for an appropriate goal node would fail, as all nodes in the adjacent chunk are impassable.

which means i'm back to my original chunking algo of: A* across a chunk to the next chunk, and repeat, for each chunk along the line from original start to ultimate goal.

whether i use A* on a grid map, use a nav mesh, or a waypoint map.

another thing mentioned in the article was agent radius, and not generating paths too close to walls and such.

they recommended "growing" obstacles by the radius of the agent to compensate.

all fine and good for your typical shooter where everyone is a human with the same radius.

now, what if you have 50 entity classes with radii anywhere from 1 to 20 units?

multiple collision maps at different resolutions for different sized critters?

one collision map for each radii?

or maybe 3 or 4, and choose the closest size that's not too small?

anybody dealt with this before?

Seeing how you need in the hundreds of terabytes of storage for something that size (assuming each node takes only one byte!) if you don't do something hierarchical, I think you simply don't have a choice.

If you can't do a hierarchy of waypoint graphs, then I'm afraid that sadly you can pretty much forget it. Simply not possible.

it looks like i can just use line of sight to generate the list of regions for the meta path. they're all the same, just random obstacles - trees and rocks.

the collision maps (or A* maps if i don't use the collision maps) are generated on the fly as needed and cached with LRU. cache size is 60 maps, as i recall.

only the world_map[500][500], 4 plant_map[800][800]'s, and a generic_pattern_map[100][100] are stored in ram. terrain chunks (60 chunk cache size) and collision maps (60 map cache size) are generated on the fly as needed. plantmaps are tiled over a world map square and give the locations, size, type etc of trees, rocks, berry bushes, fruit trees, and scrub plants. plantmaps are implemented as sparse matrices. the generic_pattern_map is used for a variety of things from prairie and tall grass placement to generating canyons. the world and generic pattern maps are implemented as 2d arrays. so the overall ram hit for a game world 2500 miles across is really quite low. last time i looked, the game had a working set size of just 700 meg. i suspect that's a bit higher now. resource tracking an a per type bases added 15 meg of new variables.