I'm considering implementing A* pathing for dense terrain.

"dense" being defined as an 800x800 foot area with 1300 trees (1-2 foot diameter), 1300 fruit trees (2-4 ft diameter), and 1300 rocks (3-15 ft diameter) - placed at random.

the large number of obstacles and random placement can result in large concave obstacles composed of many rocks and trees. needless to say, simple heuristics don't do so well in these conditions.

how to code A* is not the issue. i've done that before.

the question is how to best use it.

the goal will usually be a target, a moving entity, whose location would change every update. if i use the existing collision maps for A*, which have a resolution of 1 foot, the goal node would change every time they moved 1 foot.

running A* every update is probably not happening, even if i limit the are to something like a AABrect that encloses both start and goal with 10 tiles to spare in all directions. ranges can be as great as 300 feet, yielding a max search area of about 320 x 320.

lower resolution grid for A* might help. tiles that are 5 or 10 feet wide, not 1 foot wide. at 10 feet, the search area drops to 32x32 tiles/nodes. but the lower the resolution the greater the chance that a path no longer exists.

round robin A* every N updates is another possibility. but the higher the value of N, the less responsive it is to changes in the goal node location.

right now everything is done every update just before moving an entity, so its always using the target's current location, as well as the true state of the entire simulation at that moment to determine the AI's move. so at the moment, all AI responds immediately to changes in the simulation.

i'm thinking that if the search area must be too limited, or running A* round-robin every N updates will be too slow, that i might as well try a modified version of the heuristic collision avoidance AI

the heuristic collision avoidance AI is your basic look ahead affair, designed to deal with isolated convex obstacles such as trees, rocks, people, and animals.

when an obstacle is detected ahead, it looks ahead left and right, and chooses an open path at random (a new point to move to). when it reaches that point, it exits collision avoidance mode, and normal line of sight pathing takes over again. bang and turn collision recovery is used when collisions occur. in dense terrain, collision avoidance is turned off at the moment, as it can seldom find an open path. so for the moment they bang and turn their way through.

the idea behind the modified collision avoidance would be to use a lower resolution grid. collision avoidance uses the collision maps, which have a resolution of 1 foot. the modified version would use something like 10 feet or perhaps bigger. if there were any obstacle in a tile, the entire tile would be marked impassable. by choosing a sufficiently large tile size, hopefully the map would degenerate to large individual convex obstacles (or at least fewer concave ones) that could be navigated with standard look ahead collision avoidance, perhaps combined with some look ahead wall following. if not, it would first degenerate to a map with so many impassable tiles that no path existed.

any suggestions? thoughts? comments? etc?

what would you try first?

Is there a situation where you won't need A*?

If not, I'd start with that (or rather, I'd switch to Jump Point Search probably, 640,000 square foot area sounds big enough :) )

With it, you're in a position to actually test your ideas to some extent so you can improve your guesses to more accurate values.

Why a grid over a navmesh?

If you have a fixed 800x800 terrain, break it up a bit with quad trees. 800ft tends to be a bit too far for anyone to try and do course correction, usually the most natural thing to do is to run till they are near enough before it's a full chase (following the windy movements tends to tire out both parties).

The AI honestly should not care about an accurate path till he gets close enough. All that matters till then is getting near enough.

You can reduce the number of nodes you need to touch by breaking up mesh into a broader graph, and solve for a general connectivity path. Then you can solve for the detail path.

Your path should only be recomputed when the target leaves the sector, or the AI has entered an adjacent sector.

Though regardless... if it's a target that constantly teleports to some far distance then you're still going to need to recompute it every frame.

Is there a situation where you won't need A*?

many / most situations. most of the game world is sparsely populated with individual small convex obstacles (trees and rocks). some areas have large numbers of obstacles. and some terrain types can as much a triple up on the large number of obstacles (rocks, wood or jungle, AND fruit trees).

for anything less than rocks, woods, or jungle, line of sight with collision avoidance works fine.

Why a grid over a navmesh?

no navmesh (at least not yet). terrain chunks and tile based collision maps are generated on the fly from world map data. navmesh generation is a possibility.

the entire world is randomly generated, down to the size, location, and orientation of every tree, rock, and clump of grass.

the game world is 2500 miles across, stored in a 2d arrray[500][500] of "map squares" (tiles). this "world map" stores info about elevation, water, vegetation, resource levels, etc.

there area also pattern maps 800x800 feet in size implemented as a sparse matrix array[1300]. one each for rocks, trees, berry bushes, and fruit trees.

terrain chunks and collision maps are 300x300 feet in size. a terrain chunks has 4 interleaved ground meshes with different tileable ground textures generated from the heightmap function for the map square. it also has an indexed list of all renderables in the chunk, drawn from the pattern maps, which are repeatedly tiled over a map square.

a terrain chunk is generated on the fly when first required for drawing. a collision map is first generated when required for collision checks. both are cached with LRU algo.

in anticipation of wanting better pathfinding, i've also started thinking about navmesh generation, or perhaps even generating some sort of collision map that can be navigated with heuristics.

since the goal node will change from time to time, odds are i'll never use a full A* path, just the first few nodes before having to run A* again. since this results in a form of incremental pathfinding, i'm thinking heuristics might work, perhaps not quite as precisely, but good enough. at a large enough tile size, concave obstacles become convex. the question is, can you reach that point before the larger tile size results in no path?

,

The AI honestly should not care about an accurate path till he gets close enough. All that matters till then is getting near enough.

that can still take some time with just bang and turn in random terrain approaching 50% (or more?) impassable.

right now its no great challenge for a decent archer with good equipment to drop an approaching hostile caveman as they pick (bang and turn) their way through dense terrain.

in dense terrain (woods, jungle), encounter distances are 200 feet, map squares with rocks are 150 ft as i recall. everything else is 300 feet, and is empty enough to not require A*.

if i only A* when within say 50 feet, i still have to bang and turn (or do something) to get to range 50. and projectiles use very realistic physics, so there's no predetermined max range for missile weapons. so i can't easily limit A* to "max range at which you can be attacked".

a reasonable search area from the point of view of combat would be at least 100x100 feet and no smaller.

and in general for combat, the ability to path out to at least 300 feet in the target's direction would be desirable.

You can reduce the number of nodes you need to touch by breaking up mesh into a broader graph, and solve for a general connectivity path. Then you can solve for the detail path.

a two level approach, coarse grained, and fine grained.

Your path should only be recomputed when the target leaves the sector, or the AI has entered an adjacent sector.

yes, i didn't even consider the fact that occasionally the start node changes - as well as the goal node changing from time to time. but then again, if i only path against terrain, not moving entities (except for the goal), and follow the A* path or return to it after collision avoidance with a moving entity, then i'll always be on the A* path, and it will remain valid until the goal moves. if i include entities in the A* check it would have to be done at least every few seconds, whether the goal moves or not. i doubt standard look ahead heuristic collision avoidance of entities combined with A* would work, the terrain is just too thick for standard heuristics. more advanced heuristics might work though. something designed specifically for dense terrain.

Though regardless... if it's a target that constantly teleports to some far distance then you're still going to need to recompute it every frame.

thankfully, its not that bad. <g>

the target will always be an animal or caveman within 300 feet or so. anything beyond that is not targeted, except for thing like orders to "follow me". in which case the AI, without my designing it to, just by dint of the thoroughness of the code, will walk all the the way across the world, banging and turning in dense terrain, and avoiding collisions in other terrain, until it reaches its goal.

and yes, in such cases, i'd want A* to path across the dense terrain.

i don't ask for much, do i ? <g>

the large number of obstacles and random placement can result in large concave obstacles

You can eliminate this problem by taking convex hulls of groups of objects.
If any single object is concave, or if any group of objects form a concave region through which the object cannot squeeze, then you can eliminate long searches into their concave regions by generating their convex hulls and using those in your A* search.

You only need to search inside a convex hull if the target is inside it.


Just doing this alone will speed up your routine greatly, but you can also do as mentioned before and only generate a new path if your current path no longer leads to the target (the target moved or something moved into your path, etc.)


L. Spiro

You can eliminate this problem by taking convex hulls of groups of objects.
If any single object is concave, or if any group of objects form a concave region through which the object cannot squeeze, then you can eliminate long searches into their concave regions by generating their convex hulls and using those in your A* search.

You only need to search inside a convex hull if the target is inside it.

yes, this is the idea i was trying to articulate with the lower rez collision maps and heuristics. lowering rez converts concave groups to larger (convex) impassable tiles.

i think that last sentence of yours might be THE key.

with conversion of concave to closed convex obstacles, its only the concave one surrounding the goal that really requires A*. everything else degenerates to individual convex obstacles that can be navigated with heuristics. they might be _big_, but they are still essentially individual Bboxes, Brects, or Bspheres, AA or oriented, with path space between them that heuristics can thread its way through. its concave stuff like rooms that heuristics has more trouble with.

all the heuristics has to do is extend the look ahead, ahead left, ahead right algo so it looks left and right until it finds free space (wall following). with convex guaranteed, its like threading your way through a field of randomly placed posts in the ground. some bigger diameter than others, but all with enough space to move between them. so it would "collision avoid" an entire concave pile of rocks and trees as though it were just one very big convex tree or rock in the way.

so the next question would be is there an algo for generating the "convex hull" of a 2D raster/tile based concave obstacle? (such a clump of stuff in a collision map?).

determining a bounding box would be good enough for heuristic look ahead collision avoidance. all it has to do is avoid the entire area.

then A* at close range (just the last clump of stuff) if the target is inside a concave obstacle.