What is the normal way to do pathfinding around threats? Should the pathfinder compute the threat value at each node during evaluating, or should the data be baked into the graph?

I chose the second option for my game. Now I am not so sure if it was the right idea because I am running out of memory for all these graphs (up to one per agent).

Is the threat an area around the threats location (larger than your single grid point -- if you are using one?)

Is the threat something that has a projectile attack that has the danger areas being within "line of sight" to the enemies (threats) locations? need to mark if line of sight within range figured for all each threats reachable nodes

Note ranges for diferent weapons/affect (depending on certainty/uncertainty information evaluation) to judge the 'threats'

Can the threat lob area effect projectiles at you (which can get indirect hits around LOS blocking terrain)?

Is it as simple as you dont want to wind up adjacent to the threat? Or just being at the same node?

Is sighting a different consideration beside being able to affect/attack you (if they spot you then they can start moving to threaten you better...)

If the threat(s) move you have to rebuild the danger cost map (only if they move) and the marked out nodes would be set by one of the threat interaction types listed above

You probably want the 'map' as a seperate value from the movement cost data (which probbaly is static) and a seperate factor summed/combined from ALL of the threats which would be used by a second test when evaluating the node candidates.

For an A* algorithm, it seems to me that you can add it to the traveled path length (as in, if you are under threat, you have to move more careful, so it takes longer to reach the next node). As long as the estimation is not more than the real path length, you should get the optimal path, afaik. You may want to add a weight factor as well, so weak units care more about not having threats.

A* visits each node once, so for a single path-find search, it's not useful to store the threat information.
If you get the same path costs the next time you path-find (ie threats don't change all the time), it may be useful to store the information, but that's a matter of weighing cpu costs against memory costs. The advantage of a path-finder is that it doesn't try all nodes, so normally you would have to compute a sub-set of the nodes only (unless you ask for a non-reachable target).

Maybe a hybrid form is useful, cache "recent" values only. Not sure how to do that though, LRU will probably not work, as units will not often go back immediately.

Edit: Added emphasis to 'not'

I use a grid system. Placing threat info in the graphs has made my save files bloated, and computing the graphs takes forever... I will now have to find a way to compress the grids/graphs, probably by dividing them into larger sectors and layers. The pathfinder will have to do lookup into layers as well. Lots of extra work and complexity.

Why do you have one grid per agent? Can you split it to be per faction? Or per faction, per unit type?

A more burning question: why are you saving threat information - or your A* graphs for that matter - into your savegame files? The graphs can be stored in map/level files, and the threat data can be recomputed on game load.

A more burning question: why are you saving threat information - or your A* graphs for that matter - into your savegame files? The graphs can be stored in map/level files, and the threat data can be recomputed on game load.

Recomputing the graphs take up to 5 minutes on the larger maps and with more average CPUs. It is especially computing the high level representations of these maps that take time. Saving/loading them is actually a lot faster.

And yes, I have already done the grouping by factions, but the map also contains many things like solitary predators.

Is it possible to have your threat information be worked on a lower (coarser) resolution that your movement navigation grid ?

That might greatly lower the processing required (especially the in-game rebuilding for moving threats)

If it is a regular grid then the coordinate system can index directly onto the 'threat map' without extra storage

Nobody is suggesting that you recompute your waypoint graphs completely. We're saying you should compute them once and store that data in a level or map file. Then, recompute the threat data at runtime, without saving it into your savegame file.

If you actually mean that just computing threat data takes 5 minutes, you've done something horrendously wrong.

The grid contains up to 2.4 mio. nodes. This is the root of my performance problem, because it scales linearly with more agents/factions.

I am thinking of changing the pathfinder so there will be one big shared base grid containing terrain nodes, and then layers divided into smaller sectors containing the threat nodes, where each sector will have 2300 nodes. The pathfinder then needs to be modified to handle these layers.

Does that sound sensible?

Also, should the layers be precomputed and override the base grid, or should the pathfinder be required to add them together as it encounters them?