ihhub / fheroes2

fheroes2 is a recreation of Heroes of Might and Magic II game engine.
https://ihhub.github.io/fheroes2/
GNU General Public License v2.0
2.74k stars 377 forks source link

Adventure AI: calculate influence areas around heroes and castles #6259

Open idshibanov opened 2 years ago

idshibanov commented 2 years ago

Preliminary checks

Describe the problem requiring a solution

Currently enemy threat calculations rely on rough estimates using map regions logic. With the tools available AI can't be sure if hero moving to a map object (like a Mine) will be attacked next turn or not. Only a vague "this is a dangerous area" penalty applies.

AI needs to plan ahead and to know exact enemy strength for every map tile. Friendly heroes should be accounted for as well since they can counter and "defend" weaker heroes. Only max values should be picked.

Describe the possible solution

A possible solution would add a cache layer (vector for O1 access) tracking enemy threat levels (for next turn) and friendly heroes only for every map tile. At the beginning of a turn the cache is reset and visible threats are reevaluated reusing some of the pathfinder logic. We might need a new pathfinder class for it.

When calculating paths to the objects pathfinder should not only tell if object can be reached but also warn if path is dangerous. Do we care about threat in the middle of the path if the final tile is safe? Some things to test and explore here.

We will have to maintain the cache within a single AI turn. Every battle completed should be followed by a check if that was an existing threat. Every tile uncovered should check if we see a new castle/hero followed by an update to the cache.

Additional info

This approach is closer to what we already do on Battle AI side, might be useful to review it.

fheroes2bugs commented 5 months ago

found another example of computer is not calculating area near him: https://www.youtube.com/watch?v=nYjrHK_FFzI