Unit AI in Unto Deepest Depths

In any game with a computer controlled opponent, the AI is important to get right. Not only is it where the challenge for the player will come from, but if starts behaving inconsistently or illogically, it can pull the player out of the experience. Even a simple AI should make sense, and in fact simpler AI’s arguably have less room for error since it will be more apparent when they’re not behaving correctly. So today, let’s look at how the AI in my turn based roguelite Unto Deepest Depths (go wishlist!) works.

The basics

You can read the original devlog to get into the weeds of the game’s systems, but as a quick refresher, each unit must move and attack each turn and, in order to make things a bit more chess-like, each unit must follow certain rules and patterns for doing so that are unique to them. The archer, for instance, can only move diagonally and attack cardinally, firing as far as its maximum range allows or stopping early if it hits something. The mage, on the other hand, has limited movement and a single attack choice, but attacks a pattern of cells all around it, allowing for it to attack multiple units at once if the attack is lined up correctly.

Units maintain a list of all possible actions and when it is time for a unit to act, whether via the AI or via player input, that unit will iterate over this list and determine which options are valid given the current game state. The valid options will then be presented either as choices on the map, if the unit is controlled by the player, or will be fed to the AI Controller, which decides what actions should be taken by the opponent team.

AI Controller

The AI Controller is a component that is attached to non-player controlled units at the start of battle. It’s responsible for determining what that unit should do, given the current game state. At a high level, this component simply looks at what actions are valid, scores them based on desired outcomes, and then picks the highest scoring action. If you’ve seen my post on Utility AI, then scoring actions may sound familiar, though this implementation is a simple take on that concept since units are so limited in what they can do each turn.

At the top of the controller are a list of fixed values for scoring how useful a potential action is at this point in time. Looking at them, we can see there is a clear hierarchy of preferences that are quite conventional and expected with basic AI controlled units: anything that harms the opposing team is good, with a preference towards hurting stronger units, while anything that hurts your own team is bad.

# Killing an opponent, great
const kill_value: float = 0.8
# Heal a friendly unit, good
const team_heal_value: float = 0.3
# Attacking an opponent, also good
const attack_value: float = 0.2
# Small benefit to moving towards an opponent
# but small enough that attacking or killing is always preferable
const move_toward_unit_value: float = 0.02
# If multiple attack choices,
# prefer to attack the strongest unit
# This is multiplied by an internal "value" of the unit
const unit_point_cost_mult: float = 0.1
# Don't attack friendlies
const team_attack_value: float = -0.15
# Don't kill friendlies
const team_kill_value: float = -0.5

As units must move and then attack in Unto Deepest Depths, the AI Controller has a limited set of decision to make: 1) What cell should I move to? 2) What cell should I attack after I move?

As the possible combinations are quite small, the decision making is just brute forced in the game and follows this flow: 1) Grab the current game state 1) Grab the list of valid moves 1) For each movement option 1) Score movement based on how much it moves the unit towards its opponents 1) Grab the list of valid actions from this location 1) Score each potential action based on its impact and the point values shown previously 1) Sum and store the scores of moving and attacking 1) Pick the highest scoring move-attack pair

And that’s it as far as determining what an AI should do on its turn - simply iterate over all possible move and attack permutations and pick the pairing that will have the biggest impact towards achieving its goals. In the original demo of the game, that’s all there was to it, but this quickly revealed some problematic gaps in execution, as units don’t exist in a vacuum. They’re part of a team that is working towards the same goal, and having each unit act independently of the others, while perhaps making some sort of thematic sense when fighting against the undead, resulted in turns from the AI controlled team that were so bad as to be unsatisfying to play against. For example, it was not uncommon that the player would find one of their units in a bad spot, due for a loss, and then not have that happen because the AI units acted in the wrong order, blocking each other from taking optimal actions. And when that happens with any amount of regularity, which it did, what’s the point of playing the game? After all, strategy games are meant to mentally engage and test you. To have you design and execute a plan that will allow you to outmaneuver and defeat your enemies, or to develop and learn new strategies if what you tried didn’t work. If the AI can’t form any semblance of its own strategy for you to overcome, then there’s little reason to play the game. So that’s when I decided I needed to implement planning at the team level.

Unit Group Planning

Similar to individual units, unit groups can have a UnitGroupAI component attached to them that lets them coordinate turn planning across units. This component operates similar to the AI Controller in that it scores potential options, but at a higher level: 1) Create permutations of potential turn orders 1) For each permutation 1) Create a snapshot of the current game state 1) For each unit 1) Determine the best possible move-attack pair according to game state snapshot and the rules within the the AI Controller 1) Modify the game state snapshot to account for what the unit chose to do so that future units will have correct information 1) Sum the score of each unit’s choices up to a permutation-level score 1) Pick the permutation with the highest score and execute it

Pretty straightforward, but there are a few gotchas to this. For one, I have to be careful generating turn order permutations, as each additional unit on a team increases the number of permutations by a lot. This game is too small and fast paced to make the player sit and wait while I calculate hundreds or even thousands of potential turn orders, and the scale grows so fast that I’d quickly hit a wall where it’s not possible to wait for a result anyways, so I had to come up with a compromise that is fast, but good enough. For smaller teams with only a few units, I do calculate all potential turn orders and score them, meaning the best possible decision can be made, but for larger teams where that is infeasible, I randomly shuffle the turn order for each permutation and go with that. While this means that larger teams aren’t necessarily acting perfectly optimal, the number of outright bad decisions drops dramatically and the desired outcome of better coordinated AI is still obtained. I do also plan to look at some potential heuristics to help guide the random sampling process further, but that’s lower priority for now.

There’s also a performance concern when running so many AI calculations back to back. The AI is written in GDScript, which is good enough for most operations but does seem to struggle with more data-heavy uses, and while an individual AI calculation is plenty fast, processing and scoring all of these potential turn orders does add up enough that the AI can’t calculate everything it needs to do in a single frame. As I don’t intend to rewrite any of this in C# because I have more important things to do on the game, I instead use a frame budget to keep the game performant. If you’re unfamiliar with how frame budgeting works, you track how long an operation, or set of operations, takes and when the allotted time for it to run has elapsed, you wait one frame before continuing that operation. In the case of unit group planning, that just means checking how much time has elapsed after each call to a unit’s AI Controller. It essentially looks like this:

# pseudocode
const TIME_BUDGET_MS: int = 10

var start_time: int = get_time_ms()

for perm in permutations:
    for unit in perm.turn_order:
        unit.plan_turn()

        if get_time_ms() - start_time >= TIME_BUDGET:
            wait_one_frame()
            start_time = get_time_ms()

In my case, I allow the AI to take 10ms to plan its turn, saving a few ms for other game operations each frame and making sure that I have some flexibility in case there’s a particularly gnarly operation or the game is running on a weaker machine. Whenever that budget is elapsed, I wait one frame and then keep going. This keeps the UI responsive and the graphics smooth, all while doing plenty of calculations in the background. Typically, it only takes a few frames to calculate what the AI will do, which is fast enough you won’t even notice that the game is technically somewhat soft-locked while it’s running. Sometimes, though, it can run just long enough to be noticeable, so I will be continuing to optimize where it makes sense to do so, and informing the user when planning is taking a little longer than expected.

Some of you may also be wondering about running these calculations in parallel, as while each unit relies on the actions of the previous one to update the game state, each permutation can be calculated entirely independently of the others. The short answer is that I have looked into it, but some data, such as the navigation data, is not thread-safe, and to make it so would be more work than it is probably worth at this point considering what I have already works and can be potentially optimized further if needed.

Wrapping it up

And that’s a look at unit AI in Unto Deepest Depths. To sum it up, individual units look at the current game state and test all possible move and attack combos to see which is most effective. At the unit group level, these scores are calculated for various possible turn order combinations, and the most effective turn order is chosen. This results in an effective, but performant, AI that ups the challenge from the original demo release. I will continue to iterate on it, but things are moving in the right direction with the current implementation.