A* A star vs huge levels

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?

hierarchical waypoint graphs

...possible?

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.

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.

you could look into quadtrees for the hierarchical structure, and populate them on world/chunk generation.

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.

Norman, I think your initial post was the best way to go about it. Divide your 1million unit world into X chunks. Give each chunk a passability rating and use that as the standard A* cost-to-move. Units outside your immediate play-area would use the Global-A*, but when they're within 1 chunk of the player, they move into the Local-A*.

You can use A* to determine the cost-to-move in each chunk upon world-generation. Since your zone will have 4 sides and 3 possible directions the unit can move - you'll need to run it 12 times. You can then take those 12 measurements and average them to get a generic cost-to-move score or give each chunk 12 costs-to-move - depending on how the unit wants to move across the chunk.

If the player is able to alter the environment, the cost-to-move would change, but you can just mark that chunk as "altered" and run the cost-to-move checker on it again.

I think the downside to this is that you may end up having vast swaths of enemy-less play area, as A* always gravitates towards the easiest path. You'll also end up having some areas that have a flood of AI. If you've got mobs randomly spawning and de-spawning in random zones they'll be more spread out, but if they're persistent, they'll all cluster.

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?

I have seen it where each tile stores a clearance, of how close something can get.

(More, better explanation of the tilegrid clearance:

http://aigamedev.com/open/tutorials/clearance-based-pathfinding

I have seen some research papers that do something similar with a navmesh though. Here's one, though there was another floating around with a code sample. (EDIT: Oh, and I guess Havok's Anarchy engine has clearance: http://anarchy.cn/manual/12/HavokSdk_ProgrammersManual/aiNavMeshPathfinding.html#reusingNavMeshes)

EDIT2: Oh, this one had a code sample somewhere, I definitely recall this being the first paper I saw on it.

I have seen it where each tile stores a clearance, of how close something can get.

interesting.

i saw some stuff where they would specify a max radius for each enter-able edge of a region/triangle.

but it looks like growing obstacles by the radius, and using a few different maps with different radii is one of the more straight-forward, and also more common approaches.

so it looks like i'll be using that.

select the map based on the radius. given heading to target, i can find an open edge node for the current chunk/region to use as a goal. one that's adjacent to an open node in the next chunk. once i hit the goal, just line-of-site move to the adjacent chunk's open node - you already know there's a clear path. then simply repeat until you reach the ultimate goal. off the top of my head, i'd say chunk size would more or less determine the pathing time required per entity. so you simply cut chunk size as needed, if needed. a basic divide and conquer strategy.

and i'll bet you that simple algo there will path all the way across the whole darn world, except for intervening oceans and impassable mountains, which would simply be A* on the world map squares, not in a section of a single map square.

i'm pretty sure this approach will work. i've done both parts of it before - both A* and line of sight between regions. and the edge node goal search is a standard 1D outward expanding search. nothing fancy about that. just keep trying left and right further out 'til you hit something good. IE try x+1, x-1, x+2, x-2, x+3, x+3, and so on, until you find a good node. no good nodes means ocean or impassable mountains, or incredibly bad luck on the part of the random world generation code. i have yet to see an edge that's all impassable that's not ocean or impassable mountains. the terrain is never quite dense enough i think.

Norman, I think your initial post was the best way to go about it. Divide your 1million unit world into X chunks. Give each chunk a passability rating and use that as the standard A* cost-to-move. Units outside your immediate play-area would use the Global-A*, but when they're within 1 chunk of the player, they move into the Local-A*.

at the global or high level hierarchy, all nodes are equally semi-passable, unless i want to get into terrain movement point costs, which i don't think would actually impact the node costs. IE its always faster to cut across denser yet passable terrain that to go around. only thing impassable is ocean and impassable mountains. i can add the code to high level path around those later. all they do is change the ultimate goal every five miles or so. all non-followers are removed from the simulation when no longer near any PC. so its only followers and pets far from their owners who might have to deal with the world map at all. it doesn't do collision checks when you fast travel, instead, it sets your movement rate based on the terrain type / density. when you stop fast travel, all followers and pets teleport to your location, just in case the AI couldn't keep up with you following along with full collision checks, collision avoidance, collision recovery, and fatigue modeling. so its very unlikely that an ocean or impassable mountains would block the path between a follower or pet or other PC, and the owner / one being followed (unless they were on a raft in the ocean). so odds are i can just use line of sight to select the next region to traverse. if not, i just A* the world map, get a list of map squares, and use their centers as the ultimate goals until i reach the target's map square, then i just use the target as the ultimate goal as usual.

A* always gravitates towards the easiest path.

that's actually desirable in this particular case.

If you've got mobs randomly spawning and de-spawning in random zones they'll be more spread out

encounters spawn at random intervals, directions, and ranges from the first PC in a party.

but if they're persistent, they'll all cluster.

they are only persistent as long as a PC is nearby (IE: until a bit beyond visual range). but they have migrate, wander, flock, and fight or flight behaviors while active (and hunt and pack hunt for predators). only the leader migrates. migrate and wander are solitary actions (just one critter going their own way). when a critter flocks, it moves towards the leader (who migrates, thus they all migrate as a herd / pack / group - sort of emergent behavior). with flock in combo with migrate, you'd expect "funneling". go watch the cattle and horse drive scenes in an old western - especially river crossing scenes - that's just what they do - exactly what A* does. they all go for the same choke point at once. so A* should yield rather realistic behavior in this particular case. throw in a little look-ahead collision avoidance for dynamic objects, and a bit of bang and turn collision recovery for when things go south, and you've got stampede AI ! .

this really seems to be easier to solve than i first anticipated.

i think a good data oriented design for the A* code is called for, as its known to be a slow algo.

i think a good data oriented design for the A* code is called for, as its known to be a slow algo.

I ran into this a while ago - it's supposed to be a bit faster than standard A*. Jump-point A*

it's supposed to be a bit faster than standard A*

ah yes jump point. i remember that one. clever eh? but as i recall, its best for levels with some large open areas. while i do get the occasional random clearing in the woods from time to time due to the rand() function, its rather rare. if need be i'll double check. jump * as i call it has always been the "Ace up the sleeve". but since i don't use A* much, i haven't had to play that card yet. but its been sitting there in my bag of tricks, for however many years its been now since they invented it. 2011 it looks like, according to wikipedia.

i actually suspect that long search times will not be an issue. the chunk size can simply be reduced. and unless the target is very far, you won't even traverse the full path before the goal moves and you have to re-path anyway. so a short path to the edge of a small chunk should suffice.

the big concern is when i get about 300 active entities in visual range at once - and yes, i've hit those kind of numbers during actual long term playtesting. then i may have to go round robin and such.

but by and large all it will ever have to do is path thru trees and rocks towards or away from some goal within about 300-400 feet of the start node. but the goal will be moving, not stationary, requiring frequent re-pathing. i actually suspect i'll just be using the first node or two out of each A* path list generated, then re-pathing again.

but by and large all it will ever have to do is path thru trees and rocks towards or away from some goal within about 300-400 feet of the start node. but the goal will be moving, not stationary, requiring frequent re-pathing. i actually suspect i'll just be using the first node or two out of each A* path list generated, then re-pathing again.

Sounds more like steering than pathfinding then. Couldn't you just use A* with a wide step (like pathfind every 10th 'tile') to get the general direction, and use steering for nearby obstacles? Obviously won't work if you've got a maze-like or cluttered environment, but if it's just occasional rocks and trees, it would be faster than itterating through everything with A*.

I used something like this for a side scroller where one type of enemy hovered. They seemed more intelligent than ground-based enemies and only used about 1/10 the overhead. The biggest problem with it though is cluttered terrain and large blocking obstacles. If the obstacle was < the distance between A* steps, A* would try to path through it. Sometimes steering would correct it, but sometimes it would go back and forth until the slightly randomized steering decided to move somewhere that gave it a better path or the target moved.

If that doesn't work, you could just do a 1-step for the 1st 3 nodes, and increase the step for the farther out nodes. If you've got maze-like or cluttered areas, it would probably add some artificial stupidity since the last steps are so inaccurate. It's always kind of annoying when perfect pathfinding lets omnicient AIs traverse the terrain more effeciently than the player can.

""

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.

""

No you originally wrote

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

The "closest open edge node/tile/square" may NOT be a good choice if immediately past/beyond THAT targeted part of the grid-square's edge is largely a 'wall' (and likewise the exit points on that further "node/tile/square" may be poor as well (this all causing alot of inside-a-chunk processing which then is thrown out).

Assuming a regular grid method - When true (optimal path ) exit point is NOT near the 'bee line' path on that chunk the adjacent chunk(s) may have the better path (the chunk corners endcase).

SO your Fine A* really should include processing the adjacent (side) chunks subnodes (probably from the start instead of in a backtracking strategy)

11111112222222

11111112222222

11111112222222

11111112222222 look at the corner 1234 when a simplistic chunk logic would always be trying only through 1 and 3

33333334444444

33333334444444

33333334444444

33333334444444

-

Likewise a simplistic super chunk precomputed evaluation may not give give a good estimation depending on the final destination of any particular point to point path on the entire map.

Creating Better estimations means more info prestored PER chunk containing better 'going thata way-over there' connectivity info for the high level A* to use (now for super 'regions of chunks' where the destination lies - a precalc'd third tier A* and the chunk has a data list for those super regions)

If the data gets too big for that, a 8/16/32 piechart compass 'general direction' best-adjacent candidate set (per chunk) may be good enough for most cases.

"the big concern is when i get about 300 active entities in visual range at once"

How big a map area is this 'visual range' (of the high detail interactions) ? It may be simpler in that case to 'window' the immediate areas map data to fine detail (if its reasonable size) and use plain A* (with window enlarged beyond the visual radius enough to last for a while (be valid) with a typical player movement rate)

The usual problem also is entities transitioning between the realized (window around the players view) area activity and the generalized (big map) mode of operation. Then the problem with the 'window' is (how) Are the other entities behavior responding to other entities that are beyond the windows edge properly. Some entities are more important for interactions than others and might call for 'realization' of the area around themselves (making the 'window' blobby rather than one nice regular grid area)

Sounds more like steering than pathfinding then. Couldn't you just use A* with a wide step (like pathfind every 10th 'tile') to get the general direction, and use steering for nearby obstacles? Obviously won't work if you've got a maze-like or cluttered environment, but if it's just occasional rocks and trees, it would be faster than itterating through everything with A*.

its only the cluttered environments where you really need it. savanna and fruit trees are sparse enough that heuristic avoidance can handle things. its only when you get into woods or jungle, perhaps combined with fruit trees and / or rocks, that things get kind of "thick".

the plan is to switch to A* only in "thick" terrain.

the collision maps for things like dirt, sand, prairie, tall grass, and berry bushes are 100% passable. IE no obstacles at all.

A* really should include processing the adjacent (side) chunks subnodes (probably from the start instead of in a backtracking strategy)

yes, this is a concern, the selection of the area to be considered. a simple bounding rect with start and goal as diagonally opposite corners excludes the surrounding border, and areas behind the start and goal from path considerations.

however, i think random uniform density of the cases i have to deal with will make it so that no path will have to go very far in any general direction other than towards the goal. i'll clean up the textures used to display a collision map (right now it just uses the first 7 or so textures in the texture pool, whether they look good or not). and hookup the screen dump and post a shot so you can see what a typical case looks like.

i may need to go with incremental A*. pathing a limited path length, going to the best node at that range, then repeat.