Jump to content
  • Advertisement
Sign in to follow this  
captain_crunch

Pathfinding around threats

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

If you intended to correct an error in the post then please contact us.

Recommended Posts

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).

Share this post


Link to post
Share on other sites
Advertisement

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.

Share this post


Link to post
Share on other sites
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'

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites

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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites

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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites

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?

Edited by captain_crunch

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!