• Register

Wellspring: Altar of Roots is a dark and plot-heavy tactical RPG that merges old-school, turn-based strategy with modern, fast-paced combat. Featuring gridless battles, roaming enemy encounters, complex character customization and a vast and open world map, Wellspring offers a fresh look at a time-honored genre.

Post news Report RSS AI Updates (Part Two)

Part two of our AI update blog. Focuses on the "math" behind how the enemy chooses which action to use, and how action modifiers can affect their behavior. Part one explained how the enemy decides where to move and scores each available movement/action combination.

Posted by on

The first AI update focused on some of the big-picture ideas behind the newly implemented scheme, while this one will focus more on some of the individual modifiers and implementation details that drive the current AI system. To recap, the current algorithm assigns scores to every single possible ‘action’ than an enemy can take during battle. Furthermore, these actions (or bundles, as they are called) are then placed into a list and sorted. One is then randomly selected based on a threshold, which corresponds to how ‘intelligent’ a particular enemy is, and the enemy then executes the actions contained within the bundle.

Firstly, there are three different types of ‘score modifiers’: Movement modifiers, action modifiers and target modifiers. Starting with movement modifiers, the idea here is that depending on the action itself, a different type of modifier is chosen. For instance, if an AIBundle contains an AIMovement action, we evaluate it using the specified Movement modifiers for that particular enemy. These modifiers are simply floating-point values that can be specified per enemy. If the modifier is a positive value, we ‘reward’ a movement that adheres to the specific modifier conditions by increasing the overall score. When negative, we ‘punish’ that same movement by reducing the overall score. If the modifier is zero, we ignore this particular modifier.

Gastornis


Furthermore, each category of score modifier has its own built-in scaling value, which can also be specified. This can be thought of as a category-specific weighting. As an example, here are all of the current movement modifiers (with many more planned). These modifiers can all be thought of as being under the ‘Movement modifier’ category and thus, they all receive a constant weighting in addition to the values specified. Another way of thinking about these is that they are all functions that take as an input, a vector specifying a desired movement position and return as an output, a floating point value, or ‘score’. The score that is returned is essentially the ‘individual modifier’ multiplied by the ‘category modifier’ multiplied by the result of the function. Anyhow:

Any Movement: The output is 0 when the desired position is the same as the starting position and 1 when the desired position is maximally far away from the starting position.

Movement Towards Allies: The output is 1 when the desired position is the same as the average position of all allies and 0 when the desired position is maximally far away from the average position of all allies.

Movement Towards Enemies: Same as above, but for enemies.

Movement to Avoid Damage: This is a tricky one: even if specified, this only gets applied if the character is actively a target of enemy skills. At every potential movement position, we check the list of all ‘targeters’ and see how many of them this character is able to ‘avoid’ by moving to the desired position. The score returned is the ratio of enemies avoided to enemies targeting this character. Typically, this needs a relatively high value in order to be honored.

Movement to Block Damage: This isn’t exactly the inverse of the above specifier, although it might seem that way, and in certain ways, there is some overlap. The point of this modifier is to return a higher value based on the character’s desired position placing the character in front of a ‘blockable’ skill, which includes things like Bodom’s ‘Lunge’ and ‘Blade Toss’.

Movement to Maintain Friendly Range: This could be thought of as the inverse of ‘Movement to Avoid Damage’, except the targeters, in this case, are of the same allegiance as the character. In other words, this modifier applies to positions in which a character moves and maintains a specific friendly-targeted skill. Imagine an enemy trying to heal another enemy, and the receiving enemy choosing a movement position that ensures that the character will still receive the heal.

Wolf


As stated, there are several more movement modifiers planned. Furthermore, all movement modifiers have a base weighting of 5, which is less than all other actions. To explain, each category has its own modifier. Movement is 5, Target is 8, and Action is 10. A useful way of thinking of this is that these three categories sum to 23 and the ‘weighting’ can be thought of as the ratio of the category to the total. In other words, the sum of all movement modifiers contributes roughly 22% of the total score (5 / 23 = ~22). If the particular AIBundle ONLY has a movement, then the movement portion would take up 100% of the score. The idea here was to make the movement portion less important than the other considerations, which works fairly well in practice. Since the base weightings can be changed per enemy, you could design an enemy who prioritizes movement more so than the other categories.

The next category consists of ‘Action modifiers’. Like movement above, these can be thought of as functions that take as parameters the action itself (a Skill or an attack) as well as the target of the action. One important note is that each of these functions is applied to every target of a particular considered skill. Because of this, skills that target multiple enemies are naturally weighted higher. To illustrate, Stalker enemies have a large AOE attack called Permeate that can potentially hit multiple targets, doing minor damage. However, they also have a skill that targets a single opponent (Injection), dealing moderate damage, but also blinding the opponent. When evaluating Permeate, we iterate through every target that is hit and sum up all the scores. With Injection, however, we only iterate through a single target (can you even say that?) since it is a single-target skill. Honestly, that didn’t really illustrate anything at all. Oh well, here are all the current ‘Action’ modifiers, which of course, will be expanded upon eventually as well:

Action Buff: Prioritizes actions in which the skill grants a positive status effect to the target in question. This automatically takes into account whether or not the target already has the specified buff. Essentially, higher weighting is given for applying multiple buffs.

Action Combo: Prioritizes actions in which the skill extends or begins a combo. This, unlike most modifiers, just returns a 0 if the skill doesn’t extend or begin a combo and a 1 if it does, with no in-between values.

Action Damage: Prioritizes any damage. This simulates the given skill or attack on the target, and returns the ratio of damage dealt versus the target’s total health.

Action Debuff: Just like ‘Action Buff’, but, you know… for debuffs. Similarly, is smart enough not to apply the same debuff.

Action Heal: Just like ‘Action Damage’, but, you know… for healing. There is one minor difference in that this will cap out the calculation for overheals (ie, if you have 30 out of 50 HP, and you get healed for 37, your ‘effective’ heal is only 20, thus, this would return 20 / 50 instead of 37 / 50)

Action Kill: Prioritizes attacks that would reduce the target’s HP to 0 or below. Unlike most modifiers, this returns a 0.0 for alive and a 1.0 for dead.

Action Magical Damage: Like ‘Action Damage’, but specifically for magical damage.

Action Physical Damage: You know.

Action Preempt Turn: This was a trickier one as well… essentially, the idea here is to prevent the enemy from targeting a character that is about to act, thus, dodging the skill. If this is set, the character will attempt to use skills (or more likely, attacks, since they are instant) on characters that cannot possibly avoid them before they execute.

Action Remove Buff: Similar to the other buff/debuff modifiers. The Auvanian Cleric enemy’s ‘Dispel’ skill is an example of this.

Action Remove Debuff: Similar to Remove Buff, but… you know, different as well. Moroch’s ‘Aura’ skill is an example of this. (Oh yeah, this AI can be applied to allies as well…)

Action Revive: Maximize a skill that would revive a target(s). This is a ‘boolean float’ (Although I prefer root beer floats) that is 1.0 if the skill would revive the target and 0.0 otherwise.

Action Target Count: Maximize skills with larger target counts. Keep in mind that skills already implicitly take this into account by summing up the scores for every affected target. This can be used to boost (or more likely, reduce) that behavior.

The last modifier category is called a ‘Target modifier’, and is quite similar to the aforementioned modifiers. The major difference is that these modifiers don’t give a damn about the skill being used, and only consider the primary target. In other words, this doesn’t sum up the scores for all targets of the skill like ‘action modifiers’. These can be thought of as functions that take a single parameter (the Target) and return a value (just like the other ones, if you can believe that)

Target Buff: Prioritizes actions in which the primary target is buffed. Right now, this returns a 0.0 if not buffed and a 1.0 if buffed, but this can be made considerably more complex by taking into account the quality/quantity of buffs…

Target Charging: Prioritizes actions in which the primary target is actively charging a skill. Again, is a ‘boolean float’, but could be modified as well to consider the charging itself. Furthermore, similarly to Final Fantasy Tactics, we may eventually implement a system in which charging combatants incur additional penalties when attacked.

Target Closest: Prioritizes actions in which the primary target is the closest target. This is similar to the Movement modifiers above. I mentioned this, but didn’t elaborate much on the idea that all modifiers can be negated to produce the opposite behavior. In other words, the value for this modifier, when negative, will prioritize targets that are further away.

Target Debuff: Yep.

Target LowestHP: Prioritizes actions in which the primary target is the one with the lowest HP. Note that since this doesn’t actually take into account whether the targets are hostile or not, this can technically have different meanings for different enemies. For instance, for the Auvanian Cleric, who has no real offensive, damaging skills, this could be increased to cause him to always heal the target with the lowest HP. Implicitly, however, this will already happen if ‘Action Heal’ is set to a non-zero value, but setting this higher will reinforce the ‘quality’ of that particular action. Sorry… rambled a bit.

Target Self: You can guess what this does!

Target Taunt: If this character is taunted and the current target is the source of the taunt (aka Apolith), return a 1, otherwise, return 0. Usually this value is set to something really absurdly high. This is convenient because it allows us to easily control how ‘tauntable’ certain enemies are.

So, there you have it… while there are many more of these planned, the current AI already has me mouthing the words ‘son of a bitch’ at least once every five to ten minutes (and every utterance is usually my fault for being a dumbass), which means that I’ve done something right, I think. Sadly, we haven’t even gotten down to the implementation, which I still want to briefly talk about in the hopes that this may be useful to someone out there.

Grott


First things first: this shit is not fast. As touched upon in the previous update, the AI updating step is spread out across multiple frames. The time to compute this can vary wildly, and optimizing this further will be a large task in and of itself. Typically, the process takes around 0.5 seconds, but sometimes jumps up to over 1 second, which is the absolute maximum amount of time that can be spent. There is a metric ass ton of sphere collisions/distance checks going on, and I’m sure I could eliminate a lot of these. (Yes, all of the direct distance checks use squared distance, so there’s that, at least.)

The largest slowdown, without digging into it deeper, probably comes from the movement generation step itself. Trigonometric functions are sloowww, and this particular part is just full of em. Thankfully, it would be about the most trivial thing ever to cache these positions for different movement radii instead of rebuilding them every time. In fact, now that I think about it, this single optimization is probably all that’s needed. Keep in mind also, that every position also has to be checked for collisions against other objects to ensure that the enemy can actually move to the position. It additionally has to be checked to see if it is on a ‘walkable’ NavMesh area (Unity’s built-in pathfinding requires this). Of these two checks, it would be nice if one could be removed, or they could be optimized in some way.

Checking different skills requires more sphere/capsule/ray casts, which again, must happen for every position. However, it should be possible to short-circuit some of these attempts by starting with the highest ranged skill and working backwards. AKA, if the character isn’t within 6 units of another character, then he can’t be within 1 unit either. It might furthermore be possible to just throw out certain AIActions if the score is too low. Basically, keep some kind of running average of the scores of all AIBundles. If one is significantly lower than the others, there is probably no use in even throwing it into the list to be sorted, although, it’s a near uncertainty that the list itself has nothing to do with the overall speed. But, in general, anything that allows us to ‘prune’ certain AIBundles would be useful.

Atonian Cave


The actual calculation of the score is probably not too expensive. Because I have a thing for function pointers, I decided to go that route instead of having a huge chain of ‘if’ statements. Or rather, there is still a huge chain of ‘if’ statements, but they aren’t happening multiple times every frame. What I mean by this is that the Evaluation step would need to do something like this:

if(AIConfig.MovementAny != 0.0)
{

CalculateScore(…)

}

It would have to do that for every single modifier as explained above. Since there are about 20 or so of them, I can’t imagine doing that for every single action would be fast at all. Since these modifiers don’t change during battle, a better approach (in my mind) was to use C#’s version of function pointers, called delegates. Essentially, we build a giant list of delegates at the beginning of an enemy’s turn (although, we only really need to do it once at the beginning of battle.) These delegates actually are the ‘functions’ described above. All we have to do then, is iterate through the delegates and sum up the scores returned by each delegate. We’re trading off some messy initialization code for what, hopefully, will be a more efficient algorithm overall. Then again, I haven’t tested the actual timing for the two different methods, so it’s possible (like 99% likely) that I am completely wrong and having a giant list of if statements is actually, somehow faster. I guess it really just depends on the kind of function inlining done by C#, but I don’t know anything about that, so… still though, guessing that this isn’t the bottleneck.

Overall, I am extremely excited that this works at all. I remember writing a blog post almost 10 months ago, in which we discussed the AI and how big of a challenge it would actually be. It was something I dreaded and put off for a long time. When it finally came time to implement it, I even made a super shitty version of it to put it off even longer, haha. I believe, at the time, I was not thinking about the problem correctly: I figured I would have to program all of the rules directly, which is what the first AI implementation attempted to do. In other words, to get different results, I was thinking that I would need to change code and not data. With this method, however, drastically different results can be obtained by simply tweaking a few numbers, since the AI is built upon very simple foundations, so simple, in fact, that they don’t need to be changed again.

The negative side to this is that the system itself produces more complicated results than I am able to sometimes comprehend at first glance. It’s difficult to know how a particular change may affect the overall AI, and a crucial next step is to rework the AIComponent inspector so that it provides more meaningful feedback. Having a giant list of floating-point numbers, however impeccably named and described, is still, at the end of the day, a giant list of floating-point numbers. It would be easy enough, in the inspector, to have the actual value be accompanied by its ‘weight’, ie, the ratio of the value to the sum of all values.

In summary, there are still a million things to do. With the implementation of the new AI system, however, we’ve at least beaten the shit out of one of the more intimidating tasks, and we are slowly knocking down the rest. From here, we are working very hard to finish our third demo, which will put all of the different pieces together, so to speak. Thankfully, despite there being a lot of them, all of the tasks relating to this demo are relatively small and mainly involve things like creating new enemies (which is a pretty quick process; might make a decent blog post one day), positioning enemies and NPCs, balancing attributes, et cetera. So yeah, we’re getting there, one shit-beating at a time.

Our most recent battle demo can be found here, let us know what you think!

Post a comment

Your comment will be anonymous unless you join the community. Or sign in with your social account: