Distance mapping and combat

Note

Most of the ideas and proposed functionality described in this page were merged into the qw-0.2 branch. Much of the specifics propose below changed dramatically in the actual release (see the changelog for details). Hence this page doesn't accurately represent how qw performs its distance mapping and related plans, but I'm keeping it for historical purposes.

Background

qw's current movement reasoning is mostly based on its will_tab() function, which is a a way of finding a path between two positions given a traversal test function. This approach is not too computationally intensive, but can't give paths over long distances because it can't handle circuitous paths that may need to veer relatively far from the the shortest path vector. Even for shorter distances within LOS, it can't detect paths that wind around larger blocks of impassable terrain.

A distance map is a calculation giving the distance for some set of squares that's the number number of steps required to reach a chosen fixed location on the map. This lets us walk towards that location, taking the shortest number of steps to do so. The set of squares mapped are typically one of the entire map or an area one to two times the size of LOS. qw already implements these calculations, but uses them exclusively for finding the path to upstairs.

This proposal extends qw's distance mapping to implement movement towards both types of stairs, branch entrances, altars, or reachable monster locations. This resolves a number of issues where qw gets stuck when reachable monsters prevent travel and autoexplore but will_tab() is unable to find a path to the monster. It also implements the basics of movement towards progression items like runes and the orb of zot, where we might prioritize movement towards these items over engaging distance monsters in combat.

Combat with unreachable monsters

Monsters that are unreachable in a LOS_NO_TRANS sense but are globally reachable via another path on the map will block autoexplore, causing qw to be stuck, but this situation is relatively easy to resolve with the floodfill branch. qw can either move toward its next stair or branch goal or simply toward the monster's position. At some point it will leave LOS of the monster, allowing travel or autoexplore to resume.

The most complicated case to resolve is movement and combat with monsters that are reachable in a LOS_NO_TRANS sense but aren't reachable according to will_tab(). This is challenging because these monsters must be fought using ranged attacks, moved to if distance mapping provides a path, which may additionally require temporary flight, or they must be excluded entirely. This requires several new plan implementations. Additionally, it's a challenge to perform distance mapping at the right time so that we have the minimum required information as to whether such plans are necessary yet we're not performing too many distance maps with every turn.

Terminology and current qw behaviour

Some terminology we define for sake of describing qw's current and forthcoming attack process:

• ranged enemy: A monster with a known ranged attack according to the clua :has_known_ranged_attack() moninfo method.
• incoming melee enemy: A monster that is not currently in qw's melee range but that can move to melee range relative to qw's current position. Determined via qw's will_tab() function combined with the square function mons_tabbable_square(). The latter incorrectly considers deep water and lava to be impassable for all monsters and doesn't consider whether monsters have reach.
• enemy target A monster whose current position qw can move sufficiently close to in order to melee the monster. This only considers qw's traversal capabilities and qw's melee range. Determined via will_tab().
• disconnected enemy A monster that is neither an incoming melee enemy nor an enemy target. These are monsters that will_tab() has determined we can't reach for melee.

Note that a monster can meet any combination of these traits. Currently qw has the following aspects:

1. If an incoming melee enemy exists and a ranged enemy exists, qw will retreat out of its LOS and wait for up to 10 turns for the incoming melee enemy.
2. If an incoming melee enemy exists and no enemy is ranged. qw will execute one of its wait plans, which are to throw a projectile, spit poison (for Naga), or simply perform a single-turn wait. These are executed until the incoming melee enemy is in qw's melee range.
3. If no incoming melee enemy exists and qw finds an enemy target, it will move towards that target.

Forthcoming combat changes

• Have will_tab() consider the monster's unique traversal capabilities as well as its melee range for purposes of determining incoming melee enemies. If the monster has reach and qw doesn't, even if will_tab() is true, a monster will only be considered an incoming melee enemy if qw can close the final one-square gap itself to melee the monster.
• The plan_wait_throw() function will use a copy of the attack plan's get_target(), modified to consider conditions only relevant to throwing attacks. This will improve its target selection by prioritizing.
• We can use spells.path to test whether throwables and eventually wand spells can actually hit a given target. For now we'll use Magic Dart (LOS-range and non penetrating) for boomerangs and large rocks and Quicksilver Breath (LOS-range and penetrating) for javelins.
• Make attacking be its own cascade, since we're adding a number of new attack-related plans.

New plan functions

The first three plans will go in the new attack plan cascade, but the last will go in the emergency plan cascade:

• plan_throw_disconnected_enemy(): attempt throwing at disconnected enemies. Once this plan is activated, set a phase_attack_disconnected_enemy variable that gets unset when no such monsters exist. If we don't have sufficient health, this plan is skipped.
• plan_quaff_flight(): quaff flight if distance mapping with flight shows we could reach a monster and when distance mapping without flight shows that we can't reach any. This plan sets phase_attack_disconnected_enemy.
• plan_move_to_disconnected_enemy(): If any disconnected enemy can be reached according to distance mapping, move towards it. This plan sets phase_attack_disconnected_enemy.
• plan_exclude_enemies_and_flee: If phase_attack_disconnected_enemy is set and we are in emergency conditions (according to HP or certain player debuffs), exclude all monsters in LOS. Setting exclusions doesn't take in-game turns, so the plan's action will be to take a first step towards the nearest upstairs.