[RFC] AI Threat Evaluation and Improvements

[mlangsdorf]

While tracing the code in #25666, I came to the conclusion that AI code to evaluate threats is really wonky. While we're waiting for the great AI rework, I'd like to propose some relatively straightforward (I hope) improvements and get feedback on them.

Currently, NPCs evaluate danger by:

  danger assessment:
    summing the difficulty of all nearby monsters.
    if that is less than 20, reducing is even more.
    if the PC is hostile, adding 10 ( -the PC distance if the PC doesn't have a gun)
  choosing a target:
    set highest_priority = 1, target=nullptr
    for each monster:
      scaled distance is distance to monster / monster_speed.
      critter_danger is monster_difficulty * ( 0.5 + 1/2 percent HP remaining )
      add critter_danger to total_danger
      monster_priority = critter_danger - 2 * ( scaled_distance - 1 ), 
           min 1 if it's within 6 tiles
      if monster_priority > highest_priority
        target to monster and highest_priority to monster_priority
    for each NPC or PC:
      scaled distance is distance to character / character_speed.
      character_danger is character weapon rating (*1.5 if the character has
           a ranged weapon but the NPC doesn't)
      add character_danger to total_danger
      character_priority = character_danger - 2 * ( scaled_distance - 1 )
      if character_priority > highest_priority
        target to character and highest_priority to character_priority
  if the NPC has a target, choose the best weapon to use and the best way to attack

There's a couple of problems here:

1. NPCs can only flee from the player and otherwise either attack enemies in their threat zone or do whatever other thing they were doing.
2. NPCs with ranged weapons will let weak enemies get quite close, even if the NPC could engage earlier.
3. NPCs don't care about their own armor: NPCs in power armor will target a shocker zombie that can't really harm them over a spitter zombie that can.
4. NPCs don't care about other character's armor: an NPC will shoot a heavily armored target that they can barely damage over a lightly armored target that they can kill.
5. NPCs calculate the total danger but then ignore it
6. Redundant calculations all over the place: NPCs assess danger 3 different ways, evaluate threats 2 or 3 different ways, and even though some of this data is cached, they ignore it.

Describe the solution you'd like
First, a new metric for danger: turns_to_kill. This is an estimate of how long it will take a foe to kill the NPC, or how long it will take the NPC to kill the foe, based on best weapon and factoring armor.

The new algorithm should look something like:

assess danger:
  for each visible foe, calculate my_turns_to_kill and turns_to_kill_me,
        as well as distance and speed.
  if the sum of my_turns_to_kill is more than the sum of turns_to_kill_me
      (+/- some fudge factor based on NPC aggression and bravery),
       evaluate if fleeing is possible (NPC can get 30+ tiles away from threats, 
       based on relative speeds). See attitude to fleeing if possible and desirable.
prioritize threats:
  if the NPC isn't fleeing:
    rank foes by distance and 100 / turns_to_kill_me / my_turns_to_kill, 
         so the NPC targets the closest dangerous threats that can be removed the quickest.
    discount foes that are far away, but never discount foes within 6 tiles or
        half the NPC's effective weapon range, whichever is more.
    target the highest ranked foe.
  if the NPC is fleeing
    rank foes by distance and 100 / turns_to_kill_me
    flee from the closest, most dangerous foe.

basic plan: NPC tries to decide if they can survive fighting the current threats and if they can flee or need to go down fighting. If they can survive the current threats, kill the closest threat, favoring the most dangerous threat that can be killed the quickest so as to reduce the threat level as quickly as possible. If they don't think they can survive, they try to flee from the closest, most dangerous threat. Might need to adjust pathfinding to find the safest path but I don't understand pathfinding. This might also be the point where the NPC throws a grenade if they can.

for melee combatants on both sides, turns_to_kill might need to be modified to include the time it will take for the melee combatant to reach melee range. the ideal algorithm would have the NPC with a ranged weapon stay and fight against a dangerous melee enemy if they think they can kill the enemy before the enemy gets to them, but flee if the enemy is too close.

Describe alternatives you've considered
This is an opening for discussion.

[mlangsdorf]

Good point. What do you suggest as an alternative? sort by increasing turns_to_kill_me, increasing my_turns_to_kill, and increasing range?

So NPC has a loaded and ready Glock 17, is wearing light survivor gear, and is facing 6 foes: a dog at range 5, takes 150 turns to kill the NPC, dies in 1 turn a bandit with a crossbow at range 15, takes 30 turns to kill the NPC, dies in 17 turns a thug with a machete at range 15, takes 30 turns to kill the NPC, dies in 19 turns a zombie at range 5, takes 40 turns to kill the NPC, dies in 10 turns a pitbull at range 15, takes 160 turns to kill the NPC, dies in 2 turns an acid zombie at range 15, takes 25 turns to kill the NPC, dies in 10 turns

apparently this NPC is suicidally overconfident, or can't flee. Who should he prioritize? acid zombie, bandit, thug, zombie, dog, pitbull?

there has to be some prioritization on the ratio of turns_to_kill_me and my_turns_to_kill, or you hit a different degeneration situation where you target the guy who can kill you in 30 turns but takes 25 turns to kill over the guy who can kill you in 35 turns to kill but takes 5 turns to kill.

[Marrim]

Er. I deleted my comment after re-evaluating it. Sorry for the confusion.

But: Given human psychology for loss aversion (and NPC code is trying to emulate humans) it would make sense to give greater weight to "turns_to_kill_me" value.

So perhaps the formula for priority can be: 10000 divided by (my_turns_to_kill), and then again divided by (turns_to_kill_me, squared).

This would prioritize enemies that are faster to kill, and especially prioritize enemies than can kill the NPC fast.

[mlangsdorf]

From the previous example:

Hostile	Priority
Dog	0.44
Bandit	0.65
Thug	0.58
Zombie	0.63
Pitbull	0.22
Acid Zombie	1.6

Looks pretty sensible. Doesn't show any obvious bad behavior on a quick examination.

[SunshineDistillery]

Does an NPC have some persistent memory of threats? What happens when you break LOS?

[mlangsdorf]

No persistent memory, and that's not something I plan to address here. Goal is to find relatively straightforward changes within the context of the current algorithm.

[FulcrumA]

Ideally, danger calculation wouldn't only take into account what PC wields, but what the NPC the calculation is running for does, whether it has companions around etc, ending in decision whether/how the attack should be done, if it'd be better to try to negotiate with PC, sound the alarm if there's one's companions nearby or run away. Otherwise things like knife-armed NPC being easily lured and rushing on its own at machinegun-totting PC will be a thing, though even then it's an improvement over "stay there and take a sharp end of a stick to the face".

[mlangsdorf]

I think my_time_to_kill can be modified to account for allies, but that's as far as I would go. If the NPC has 3 allies, and each of them alone have a mttk of 40 against a zombie hulk while the hulk has a ttkm of 3, the fact that the 4 of them working together can kill the hulk (our_time_to_kill of 10) before it can kill all of them (time_to_kill_us 12) doesn't change the fact that 3 of the NPCs would expect to die before killing the hulk.

Again, I'm not trying to generally fix the AI. I'm just trying to make it perform slightly better target selection and get it to run from threats that aren't the player.

[SunshineDistillery]

Anything is better than what we've got now.

One thing for ranged weapons: there should be some sort of ammo check when estimating ttk. NPCs should rate their own empty weapons correctly, but shouldn't have ESP about a player with an unloaded weapon.

[FulcrumA]

@mlangsdorf

Again, I'm not trying to generally fix the AI. I'm just trying to make it perform slightly better target selection and get it to run from threats that aren't the player.

I understand, that's why I did preface it that it'd be an ideal solution, likely as part of the whole NPC overhaul.

I think my_time_to_kill can be modified to account for allies, but that's as far as I would go.

Appreciated. Certainly nearby companions should be taken into account, though if you'd manage to smuggle in also NPCs attempting to raise an alarm to draw nearby allies who themselves may be not aware of threat's presence - it'd help as well.

[mlangsdorf]

So there's the improved complaint structure that makes it easier to have NPCs voice complaints. It should be easy to use that to have NPCs say something when noticeable threats show up, and it might even be possible to have hostile NPCs say stuff.

Okay, version 3: metrics:

• mutual close distance - distance both sides need to move until one is in range, min( distance - hostile range, distance - my range ), always 0 or more.
• my closure time - mutual closing distance/(hostile speed + my speed ) + ( distance - my range )/my speed
• hostile closure time - mutual closing distance/(hostile speed + my speed ) + ( distance - hostile range )/hostile speed
• raw time to kill (raw_ttk) - expected turns it takes to kill a hostile after the hostile in in range, factoring in armor and ammo capacity and reload times.
• my time to kill (mttk) - expected turns it takes the AI to kill a hostile, including my closure time
• our time to kill (ottk) - expected turns it takes the AI and allies to kill a hostile. allies are assumed to be completely identical to the AI, so this is just my closure time + raw_ttk / ( 1 + number of allies ).
• hostile delta kills per turn (hdkpt) - how much closer to death a hostile will bring us each turn, calculated as 1 / (hostile closure time + hostile raw_ttk).
• danger threshold - a measure of the AI's aggressiveness, bravery, etc. between 0.5 for cowardly AIs to 1.5+ for suicidally brave AIs

assess danger:
  calculate number of nearby allies
  foreach potential hostile:
    calculate ottk, hdkpt
    max danger += ottk * hdkpt
    priority is 10000 * hdkpt^2 / ottk
    if the hostile is within 6, or 1/2 our weapon range, or we're within 1/2 his range, priority += 1
  if max_danger > danger threshold
    emergency!
choose_target
  if emergency:
    complain / warn allies
    deploy reserve attacks (explosives, last ditch weapons) if possible
    run if no reserve attacks and escape is possible
  if running
    find the highest priority target, and move away from it
  else
    find the highest priority target with a priority over 1. attack it
    if nothing has a priority over 1, go about your other tasks

rationale: The AI feels there is an emergency when the sum of (turns to kill a hostiles * how much of me the hostile kills per turn) is more than a threshold. At danger threshold 1, that means it will take as long to kill the hostile as it will take to the hostiles to kill the AI. While there is an emergency, the AI attempts to kill hostiles more quickly or flee, as appropriate.

if there isn't an emergency, the AI chooses threat with the biggest payoff: the largest reduction in the risk of AI death for the least investment in AI time. Distance to the target is already accounted for in hdkpt and ottk calculations, so distant threats without ranged weapons are automatically deprioritized, and if no hostile is particularly threatening, the AI isn't threatened and can go do other things.

Each allied AI calculates threats separately, with very imperfect information. One well-armored AI ally might treat a pack of 7 dogs in the distance as not a threat, while another less armored AI ally might feel there is an emergency and want to run from the dogs.

I think all of this is fairly straightforward to calculate and can be explained.

[mlangsdorf]

Sample Combat sequence: A survivor and his 3 NPC companions are attacked by several threats. 1 NPC has good armor and a crossbow, the other 2 have awl pikes and not good armor.

At range 15, here's their threat matrices:

AI 1

Threats	Distance	His Range	His Speed	My Range	My Speed	TTKM	MTTK	dKPT	OTTK	Emergency	Priority
Dog	5	1	2	25	1	150	1	0.0066	0.25	FALSE	2.73
Zombie	5	1	0.7	25	1	40	10	0.0227	2.50	FALSE	2.91
Bandit	15	30	1	25	1	30	17	0.0333	4.25	FALSE	2.61
Thug	15	1	1	25	1	16	19	0.0333	4.75	FALSE	2.34
Pitbull	15	1	2	25	1	150	2	0.0064	0.50	FALSE	0.81
Acid Zombie	15	1	0.7	25	1	25	10	0.0256	2.50	FALSE	1.98

AI 2, AI 3

Threats	Distance	His Range	His Speed	My Range	My Speed	TTKM	MTTK	dKPT	OTTK	Emergency	Priority
Dog	5	1	2	3	1	75	1	0.0128	2.25	FALSE	1.73
Zombie	5	1	0.7	3	1	20	10	0.0417	4.50	FALSE	4.6
Bandit	15	30	1	3	1	15	17	0.0667	16.25	TRUE	2.74
Thug	15	1	1	3	1	8	19	0.0455	16.75	TRUE	1.23
Pitbull	15	1	2	3	1	75	2	0.0114	12.50	TRUE	0.10
Acid Zombie	15	0.7	1	3	1	12.5	10	0.0377	14.50	TRUE	0.92

AI1 is calmly shooting the approaching zombie, while AIs 2 and 3 are warning about the onrushing horde, deploying molotovs, and calculating whether they can outrun dogs. Since they can't, they're running forward to engage as quickly as possible.

After 3 turns the situation has change: the pitbull got caught in a molotov intended for the bandit, and the dog stopped on a hidden nailboard and died. Threat matrices now look like: AI1

Threats	Distance	His Range	His Speed	My Range	My Speed	TTKM	MTTK	dKPT	OTTK	Emergency	Priority
Zombie	2	1	0.7	25	1	40	10	0.0241	2.50	FALSE	3.33
Bandit	15	30	1	25	1	30	17	0.0333	4.25	FALSE	2.61
Thug	12	1	1	25	1	16	19	0.0370	4.75	FALSE	3.89
Acid Zombie	12	1	0.7	25	1	25	10	0.0246	2.50	FALSE	3.41

AI 2, AI 3

Threats	Distance	HisRange	HisSpeed	MyRange	MySpeed	TTKM	MTTK	dKPT	OTTK	Emergency	Priority
Zombie	1	1	0.7	3	1	20	10	0.0500	2.50	FALSE	11.00
Bandit	9	30	1	3	1	15	17	0.0667	10.25	TRUE	5.34
Thug	9	1	1	3	1	8	19	0.0625	10.75	TRUE	3.63
Acid Zombie	9	1	0.7	3	1	12.5	10	0.0468	8.50	TRUE	2.58

AIs 2 and 3 still don't like their odds. Now that the fast dogs are dead, they're going to run for it. AI 1 has switched to the thug as a bigger threat, even though he takes longer to kill than the zombie.

[FulcrumA]

Sound awesome. Should not only make NPCs dangerous now but be something of a standard for future NPC AI and whatnot overhaul, though how well those particular values will hold I'll have to see in practice.

[AbsalomAchitophel526]

Everything looks great - Enemy NPC's should not be loot pinatas. I do second however the suggestion that opposing AI's not know if their opponents weapons are loaded or not - they would have no way to tell.

[mlangsdorf]

Sure, each AI is going to make it's evaluation based on it's known skill, preferred weapon range, ammo reserves, etc while assuming the other side has infinite aim and will shoot as soon as it can.

Which will lead to issues like two hostile NPCs, neither of whom really wants to shoot each other, nevertheless getting within 1/2 each other's weapon's maximum range, getting threatened, and then running toward each other to shoot the other guy before he shoots them. Which is a little weird but it's not crazy behavior for suspicious people after the Cataclysm so I'm okay with it.

[SunshineDistillery]

What will happen to the commands a player can give his allies? There should probably be something to influence NPCs' choices, even if it's just a 'stand and fight' or 'run away' order that alters their bravery levels. Otherwise they'll be difficult to wrangle.

[FulcrumA]

@SunshineDistillery Due to how of a mess it all is, I am not even sure if "wild" NPCs and player-allied ones use the same AI. Certainly the behavior of two groups is completely different. I don't expect current party functionality to be expanded much till actual overhaul (whenever that will happen), though you can somewhat affect allied NPC's willingness to engage through combat options.

[mlangsdorf]

Wild NPCs and friendly NPCs use the same AI, and player commands will continue to override the AI decisions. ie, fleeing friendly NPCs will stay within 4 tiles of the player, friendly NPCs who are only engaging foes they can reach without moving won't move to attack a distant threat.

[AbsalomAchitophel526]

How accurate are enemy NPC's? Do they take extra moves to aim and fire like the player does?

[mlangsdorf]

Beyond the scope of this issue. This about improving NPC target selection, not about how they attack you.

[mlangsdorf]

Clearing from 0.E; will be revisited for 0.F.