-
Notifications
You must be signed in to change notification settings - Fork 4
Retreating Tactics
The retreating branch has an implementation of retreating tactics for qw. These tactics have qw determine whether monsters in current LOS warrant retreating to a better position to reduce incoming damage, and if so calculate a best retreat position, then move to that location. The algorithms for both determining when to retreat and where to retreat both need tuning and possibly other substantial changes.
The current approach is to score all viable enemies in LOS from 0 to 3 points, using a score of 0/1/2/3 for trivial/easy/dangerous/extremely dangerous monsters as determined by threat level. If the total score of all enemies is at least 5, and if we see that more than 1 monster will be able to melee us at our current position, we want to retreat. The latter melee monster calculation is the same used for evaluating retreat positions as described below.
To be viable, an enemy must have a path to a position near the player's current position where it can melee. This is calculated base on the current terrain and the monsters traversability requirements for each monster. The monster must also not be on a list of specially designated "never consider for retreat" monsters that currently only includes a few monsters whose only pose a threat via full-LOS ranged attacks, like centaurs, yaktaurs, merfolk javelineers, DE master archers, etc. Unviable monsters do not contribute to the retreat score but don't prevent other viable monsters in LOS from triggering a retreat.
We search in a radius of LOS if we have monsters adjacent to our position, or if not, we use a radius of the distance to the nearest upstairs to which we can flee, or if was have no such upstairs, we search the entire map. To begin with, we only consider squares that are reachable by qw, that have no more than 5 adjacent non-solid squares, and are not adjacent to unexplored squares. The non-solid square condition is to put a good enough upper bound on how many monsters might attack us so that we can avoid further processing on many squares that almost certainly won't be good retreat positions.
Each potential retreat position is scored by:
- The number of "blocking" monsters on the path we would take to that position.
- The number of monsters that would be able to melee attack us at that position.
- The distance to that position.
Squares that would have more than 4 monsters melee attacking us are discarded as unviable. Squares are scored to minimize properties (1) through (3) in order of precedence, so property (2) breaks ties for (1) and (3) breaks ties for (2).
If, at any point in our search, our best position has no blocking monsters and (b) has one or zero monsters able to melee attack us at that position and (c) is no further away than the last location we searched, we stop the search and use that best result. Otherwise we keep searching the full radius and take the best resulting position.
Finally, we also assess our current position with the same algorithm and use that as the initial best result. If our current position has the best overall score, we don't retreat. Since our current position will always have 0 blocking monsters, other positions with blocking monsters will only be considered if our current position has more than 4 melee attacking monsters and is hence unviable.
To determine how many monsters can melee us at a potential retreat position, we determine an initial destination position near the retreat position. If the retreat position is in LOS of the monster, we perform a walk calculation to get it in melee range of the retreat position from its current position, considering known terrain and the monster's traversal requirements. The monster's final position is considered its destination. If the the retreat position is not in LOS of the monster, we consider the last position the player would take to get to the retreat destination. This does not consider the monster's traversal requirement but should be a reasonable guess over long-range movement.
With this initial destination in mind, we treat the retreat position itself as impassable (since the player will be at that position) and find the "connected components" for the monster's melee range of the retreat position. Each component is a set of squares that are reachable to each other for the monster and in melee range of the retreat position. We find the component that contains our initial destination and register the monster at any map position in the component that doesn't already have a registered monster.
The idea is that a monster will likely only be able to move within component: the one with its destination position. Hence we can simply count the number of registered monsters to know how many can melee us at a retreat position. Each monster may have its own set of components based on its traversability requirements and its initial destination, but by keeping track of registered monsters by map position, we can accurately see how many will be able to melee us at once.
- qw usually retreats successfully to nearby corridors and choke points.
- Threat level as a monster scoring metric for when to retreat seems to be doing a fairly reasonable job.
- qw sometimes retreats in odd ways as retreat positions are recalculated each turn.
- qw sometimes spends a few turns retreating from adjacent monsters to only marginally better positions.
- Total monster score needed for retreat (currently 5)
- Cutoff for how many monsters may melee us at once to consider a retreat position (currently no more than 4)
How to rank positions in terms of blocking monsters versus count of attacking monsters. A position may be a very good improvement but have a single blocking monster. Currently we penalize very severely for blocking monsters.