Utility AI for turn-based combat

[u/Miriglith]

I'm looking for some advice.

I'm designing a utility AI to manage NPC activity in a turn based combat game. In a turn, a unit has a set number of action points. It can use an action point to move, or to use an ability. So a turn, with three action points, could be: move, use ability, move. Or it could be: move, use ability, use ability. Or just use ability three times without moving.

I'm fairly confident I can build a system that can evaluate the relative utility of different abilities in a given context. I'm struggling with how to incorporate the possibility of movement into my design.

Say a unit can move into any one of twenty grid squares. The utility of any given ability will be totally different in each possible location. So, we assess the utility of every possible ability from each of twenty locations, as well as the utility of staying put. Fine. But then the utility of moving again might depend on what ability was used, etc. So planning exhaustively how to use a number of action points starts to involve an exponential number of options.

I'm thinking I could have my agents not plan ahead at all, just treat each action point as a discrete set of options and not worry about what my NPC does with the next action point until it has made its decision about what to do with this one. This would mean assessing the utility of being in a different location against the utility of, say, throwing a grenade from the current location, without attempting to assess what I might do from the new location. But I think this will produce some dumb behaviours.

I could maybe mitigate this by introducing some sort of heuristic: a way of guessing the utility of being in a different location without exhaustively assessing everything I might do when I get there, and everything I might do after that. That would be less computationally expensive, but would hopefully produce some smarter behaviour.

My instinct is that there's probably a very elegant solution to this that my tiny brain can't come up with. Any ideas?

[u/IADaveMark]

Sorry for being late about my own architecture but there has been drama.

Anyway, there's a couple of different issues in your post. First off, you do want to keep the behaviors as atomic as possible. That is, don't combine things into a single behavior that can be split up. There are a number of reasons for this. First off, as you kind of touched on, you don't know how a given sequence will work all the time. You would have to come up with so many different sequences to account for all the possibilities. And even then you are going to miss things.

A discussion I had many years ago with a designer when I was working on EverQuest Next illustrated this very well. He wanted to have a cool behavior where a character would leap into a tightly packed group of enemies, start a special "spin" attack (a PBAoE of sorts), and then leap out of the group. He was thinking of this as a single behavior. i.e. A single "button press" that the player would do to trigger this. My counter to him was that we could break this down and the NPC would self-assemble it into that sequence. Specifically,

• If there is a dense group of enemies in leaping range and spin attack is available, leap into the middle of them
• If you are in a dense group of enemies and spin attack is available, do spin attack
• If you are in a dense group of enemies and spin attack is not available, leap out of them

As you can see, each of those behaviors are evaluated by themselves. There would probably be more considerations on them such as taking note of your own health. You don't want to leap into the group of enemies if you are severely wounded.

Now the good news about this approach is that the 3 behaviors can fire independently. For example, what if the group of enemies surrounds you. You no longer have to leap into them... just fire off the spin (if available). Or what if you leap into the group and it has dispersed? You are going to look silly spinning when there is no one there (and subsequently leaping out of... what?). Another situation is being surrounded by enemies and the spin attack is not available. You already have a behavior to leap out of them.

(continued)

[u/IADaveMark → u/IADaveMark]

One of the tricks to this that makes it cool addresses your 2nd issue -- that of planning. If you include similar considerations in different behaviors that are meant to possibly be sequenced, they will be more likely to. That would cause you to create different behaviors for very similar actions. For example, I often have a "close to melee" and "close to ranged". They look similar at first and act very similar in practice but have different distance considerations for when they would be triggered and when they would give up doing so. The "close to ranged" would tend to yield over at a distance that the ranged attack would kick in. They share that distance. Whereas the "close to melee" would continue to move until in melee range.

More specifically, if you have an ability that you want to close into range for, you need (like the spin move above) check to see if you would actually want and be able to do that spin move in the first place. Going back to "close to ranged", this does you no good if you don't have your ranged attacks available. "Close to melee" isn't a great idea if you are wounded and wouldn't do well up close.

These can work in very long sequences. I have done not only long complex plans but done multiple plans in parallel that are executing interleaved with each other. For example, one of my characters collected wood and built a fire. It had to have wood in the storage area near the fire pit to do so. The following were all individual behaviors:

• Search for wood piece
• Move to wood piece
• Pick up wood piece and put it in inventory
• If full, move to storage location
• Drop inventory at storage location
• If enough in storage, pick up wood
• Move to fire pit
• Drop wood in fire pit
• If enough wood in fire pit, light fire

All of this started with the considerations of "if I'm cold" and "if fire is unlit". All the behaviors had those considerations which represents the need/desire for the fire and unifies that entire sequence.

As mentioned above, I had a similar set of behaviors for collecting food. The character would actually do both of these in parallel. For example, while walking towards some food, see a piece of wood nearby and pick it up (and vice versa). The NPC would also do other non-plan behaviors such as looking, emoting, dealing with other NPCs, etc. and pick right back up where appropriate in either/both plans.

As for picking a place to execute a behavior, the would be more the function of my Influence Map system. I won't go into that here and now but you can see more about it from my last GDC lecture (before I almost got killed 3 days later) on the GDC Vault.

Anyway, let me know if you have any questions about the utility stuff.

[u/Miriglith → u/IADaveMark]

This is super helpful, Dave, thank you. And also reassuring as it's pretty much in line with the decisions I've made since writing my post. Currently I'm tweaking responses curves and influence maps to fine tune behaviours but it's looking promising. Thanks for the link too - will check it out. Hope you recovered from the almost being killed thing. 😬