How big a map area is this 'visual range' (of the high detail interactions) ?

something like a BBox 300 feet in radius around the player. so an area about 600x600 with a rez of 1. humans have a radis of 2, so they would use a 300x300 map with a rez of 2.

big things like mastodons would use a 60x60 map with a rez of 10. 10 foot radius is about as big as they get in the game. i have yet to decide on the map resolutions i'll use. humans are radius 2. only small things like rabbits and birds are radius 1. things like smilodon are around 4-5 foot radius. and big things are around 10. i may just use maps with resolutions of 2, 5, and 10.

one issue that may crop up though is that dense terrain may be too dense for large critters to path through at all. which of course should be able to happen. in such cases i'd get a result of "no path". i guess then i just have them stand around in frustration. or let them knock down trees! <g>.

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*

for short ranges, that's the plan.

and if i'm lucky, long range will degenerate into nothing more than a series of short range cases.

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)

the AI will still use its current methods of determining what to do. only once a goal is determined will A* be invoked, and only in "thick" terrain. so entity awareness will not be limited to the path search area. an appropriate search area will be determined once the ultimate goal is determined. it may be a single high rez map for close range work, it may be some intermediate location, such as an open chunk edge node for longer range work.

it may also be possible to use the low rez maps for simple cross chunk movement to the goal chunk. they just need to get across the chunk. they don't need to access every corner of it so they can whack the player (or whatever their target is).

i'll cleanup the show_collision_map routine and post some screen shots. a picture is worth 1000 words.

OK so this is a generalized simulation for many of the entities (exact bookkeeping isnt needed).

Long ago I looked into this same idea and split entities between :

"Dum' types (local flavoring, move not so much from their area, wake up/auto-generate when player is nearby -- non-persistant)

These probably won't be doing long range pathfinding, and even then only enough medium movement range to appear to be acting naturally.

You can still have them do ecosystem interactions - locally (predators hunting prey, herbivores moving between grazing and water, etc..)

Big map migrations and such is handled by adjusting patterns on high level coefficients which then control the spawning content.

For complex simulation patterns, high level control entities on the 'big map' could be persistant, they effect/control shifts in coefficients of areas (cellular atomata methods).

Pathfinding for these is generally local (still cross chunks) but depending on how realistic and detailed you want them, many might run on schedule driven repetative medium level paths (compute set once, and then local A* immediate steps including dynamic (if you have blocking by other entities).

Unfortunately, dense terrain is a favorite environment for many animals BECAUSE its difficult for their predators OR its where alot of thesustinance is located. But then dense also greatly slows movement, so more real time to decide on any longer pathing)

The high level (persistant) entities will navigate around major blocking obstacles ocean/rivers/mountains deserts and will set direction for long distance migration of herds of animals. High level simulation can be done (group fo predator interacting with group/herds that wander by, etc..) These high level entities still can have migration patterns - precalc'd general paths. When the player comes close, then whatever interactive entities are realized (auto generated). and have general behavior motives set to do their appropriate behavior variants.

--

'Smart' (persistant, entities that have very complex player interactive/motive driven which will/can follow players around the big map with intent, requiring more exact bookkeeping because players see them over and over and result of interactions would be important and persistant)

These, even though they can have 'generalization' when well away from where the player sees them, have to transition to full detail sufficiently far away to be able to 'Act Natural' by the time the player sees them (which can include forcing high detail around where THEY are centered to a sufficient area to all the things THEY interact with). Their long range pathing has to be more exact/realistic/proper so they wont be where they shouldnt be (and are going about their proper 'business') when the player comes near and they are visible.

These entities (probably other humans) have the far more complex AI (and interacting with them is a good(more interesting) part of the game).

You can STILL auto-generate them (like if the game is a life journey and you cross the world and probably will never meet those local 'smart' residents again). You use Templates (hierachical parameterized templates) to generate these local occupants (probably with a largely hand built seed map) and likewise use the high level persistant entity (tribes?) to make their overall simulation flowing/balancing across time. Those Templates and the rules that direct them are the major difficulty (work to get them to be plausible) for the auto generation when used to generate secondary characters ('main' characters probably will be mostly hand crafted)

These can do the long ranged pathfinding (but still probably will have daily/weakly/seasonal reused paths) - alot more data, but there are many fewer of them compared to the 'Dum' background entities. You probably will find that their pathfinding is the LEAST part of their AI processing (you might use things like Planner driven AI which use pathfinding as a mere 'tool')

-

It all depends about how detailed the game is to be (and how much mundane stuff is cut out)

Funny thing is in one design (for a very detailed game) I actually had a 'micro' simulation for crafting activities (you kill an animal and now you have to butcher it and convert it for transport, or 'gathering' of edible/useful plants in a small area (or even just gathering firewood). Game where (if you want to look "there is something interesting under every rock"). Using the same methods to LOD a small area into very fine details .... Thats usually overkill for a 'game' and at that point it was more 'simulation'.

Likewise it is the transitioning -- close high detail with a boundry shifting into the lower detail 'generalized' simulation, which is much of the programming headache.

---

Another thing - once you do the autogeneration to fine detail (can be alot of processing if you have intricate Templates) you dont 'throw it away when the player walks on (he might suddenly decide to turn around and go back, or constantly move around the same large area. So I had a system to save the detailed chunks for an extended time (the 'Dums' were local on them) - roll out to disk, and then 'roll them in' when the player comes back in range and 'patch' the local details to compensate for any intervening time (and have any persistant 'smart' entities added back to them). If you are gone long enough any changes the player made can melt away and you can throw away that saved local chunk. But the autogeneration would have to be sufficiently deterministic for much detail for when the player later comes back again (particularly if your terrain isnt overly generic' and specific terrain matters).

My chunk data was actually encapsulated (a block of map memory with its own local dynamic object heap, internal offset pointers) so that a simple memory copy of the whole thing could save/restore it all with minimal processing. They would constantly get loaded ahead of the players visibility (partial low detail LOD out furthest away). Again depends on your game's detail relevancy if you have to go that far with such a mechanism.

caveman uses an unusual non-level based design.

entities are not associated with any particular area/cell/level of the game world.

instead, entities are added to and removed from the simulation under specific circumstances.

entities are added due to random encounters, or spawn point encounters at shelters or in caverns.

entities are removed when beyond visual range of all PCs.

Human NPCs are persistent. the game tracks something like the first 100 NPCs you meet. and the more NPCs you know the greater the chance of encountering one of them again. NPCs at shelters are 100% persistent. you'll meet the same ones at the same shelter every time until they die or migrate.

pets, followers, and other band members are the only entities who don't get removed when beyond visual range. so they are the only ones who might have to path any farther than 300-400 feet towards or away from the player. and they teleport to the player when the player drops out of cross-country travel mode. so its rather unlikely they will ever have to path very far beyond visual range.

so long range path finding across the world map will probably not be an issue that needs to be addressed.

obviously, this has many advantages. by "forgetting" the location of persistent NPC entities once they're removed, there's no need to store them back in the level, like with level based hard coded spawn point type design. levels and persistent entities become independent of each other. the game keeps a list of known NPCs, totally separate from the game world map data.

by forgetting non-NPC entities entirely once beyond visual range, you don't have to track anything.

in general, random encounters as opposed to spawn points tends to make life simpler. you don't have to place spawn points, you don't to have to check for activation (spawn when near), or deactivation (despawn when far). and you don't have to keep track of who is where, waiting for the player to come by and activate them. i had to do all that stuff for spawn point based shelter encounters. caverns weren't so bad: random spawn points, no de-spawn.

You still might want to have higher level 'entities' which can act upon you spawns

Unless its all static with no season changes or migration patterns or special casing for particular terrain patterns

these high level entities can move about under their own rules (they are not physical objects) but they then make adjustments to the spawning probablities/object mixes within their area of influence on the greater map.

the granularity for those can be very coarse as compared to the mapping used for the physical objects

>> You still might want to have higher level 'entities' which can act upon you spawns. Unless its all static with no season changes or migration patterns or special casing for particular terrain patterns

i seem to have lucked out in that it appears i can implement all required behaviors without resorting to long term persistent entities - except for followers, pets, and other band members.

in general, while designing the game, i'll start by considering the full tilt simulation and modeling was of doing it. if that's too intense (too much work or runs too slow), i'll look to model the effects of such a system, if it did exist. "faking it" this was is often much easier. you don't have to track and model everything, just make it look like you are.

so for example, i don't need persistent leaders for herds to follow when migrating - just til they''re over the next hill will do.

>> You still might want to have higher level 'entities' which can act upon you spawns. Unless its all static with no season changes or migration patterns or special casing for particular terrain patterns

i seem to have lucked out in that it appears i can implement all required behaviors without resorting to long term persistent entities - except for followers, pets, and other band members.

in general, while designing the game, i'll start by considering the full tilt simulation and modeling was of doing it. if that's too intense (too much work or runs too slow), i'll look to model the effects of such a system, if it did exist. "faking it" this was is often much easier. you don't have to track and model everything, just make it look like you are.

so for example, i don't need persistent leaders for herds to follow when migrating - just til they''re over the next hill will do.

It depends on what environment you are simulating. If the 'caveman' group needs to be nomadic or reflects seasonal variations (moving to different regions depending on food supply of seasonal changes) then the spawn patterns will change with those overall temporal trends/patterns.

I suppose a simple table driven (seasonal) spawn differentiation could be sufficient as long as you dont have too complex microcosm patterns. I remember 'water' is one of the biggest environment changers and its often quite localized (near rivers/ponds/lakes and quickly changing with distance)

Another nomadic pattern is exhaustion of local resources forcing change and the high level entity system Ive mentioned could track something like that and eventually be changed sufficiently to force relocation.

Your simulation doesnt have to be too complex, but enough to affect the player in a near realistic pattern (that cellular automata map can only needs to be sized to your general terrain differentiations and nowhere as huge in dimension as your primary map. It also doesn't have to shift that often ... prorated shifts of seasons (ie- even just monthly differences).

Having a more complex simulation might give the player more decision points (whether to follow the 'herds' sometimes or to stay put in a sufficiently rich resource are (til its exhausted).

>> If the 'caveman' group needs to be nomadic or reflects seasonal variations (moving to different regions depending on food supply of seasonal changes) then the spawn patterns will change with those overall temporal trends/patterns.

bands come and go at random, influenced by local resource levels. with the average time in one spot being about 3 months. terrain type affects where they can spawn.

>> whether to follow the 'herds' sometimes or to stay put in a sufficiently rich resource are (til its exhausted

you can follow a migrating herd as long as you can keep at least one band member within visual range. which can actually be quite a challenge. in the past i've tracked herds of 100 or more for 20 miles or more (IE 5 times the width of skyrim). big herds on the move stretch from one horizon to the other.

quick postmortem:

if start and goal are in the same collision map, basic A* is used.

if the goal is more than 1 map square away, map square dx,dz is used for a raycast, else collision map dx,dz is used.

the raycast goes from start until it hits the edge of the current collision map. it then searches the edge for open nodes on both this map's edge and the next map's edge.

this determines the goal for basic A*.

if the critter is at the edge goal, special code (yet to be implemented <g>) moves them to the next collision map's open node, else basic A* is run to path to the edge goal.

the process repeats, pathing across collision maps until the collision map with the goal is reached. at which point basic A* determines the path directly to the goal. if no path is found, line of sight with collision avoidance is used as a fallback until a path can be found again, due to start and/or goal moving.

the implementation at the moment uses the traditional two list method. two 1D arrays of structs, one for open, one for closed. very few optimizations has been performed so far (no heaps or anything), and runtimes are quite swift already. A* runs until it hits the goal, or a path length of 50, which is enough to get it going in the correct direction to find its way out of anything it will encounter in the game. and all it ever does is move to the first node in the path. by the time it gets there, its time to recalc the path.

Its the endcases that get you.

Diagonals for your coarse squares

Ray castings that fail if done too simply (exact line might have an opening 1 (or a few) tile to either side)

So the complexity is in the contigencies AFTER the quick shortcut test (and trying to shortcut that as much as possible before you fall down to the heavyweight A* processing)

If you can have a predigested open path mapping for the chunks, then you can raytrace to prove the near rough path to the target (and later use A* locally then to move across them individually )

One thing - you dont really shouldnt REQUIRE optimal paths, 'good enough' is OK for much movement (particularly when things are moving 'out of sight')

In reality other more important factors may interrupt the long distance movements anyway (making wasting excessinve pathfinding processing towards a far off target frequently wasteful).