A* A star vs huge levels

This topic is 958 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

Recommended Posts

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?

Edited by Norman Barrows

Share on other sites

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.

Edited by Ashaman73

Share on other sites

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.

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?

Share on other sites

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.

Share on other sites

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.

Edited by dmatter

Share on other sites

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

Share on other sites

i did a google search for "waypoint graph generation"

this was the first hit:

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.

Edited by Norman Barrows

Share on other sites

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?

Share on other sites

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.

Share on other sites

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.

1. 1
2. 2
3. 3
Rutin
13
4. 4
5. 5

• 26
• 11
• 9
• 9
• 11
• Forum Statistics

• Total Topics
633697
• Total Posts
3013403
×