Now that we have our second demo out of the way (shameless plug), we are focusing our efforts on yet another demo. While Andy works on a few remaining, lingering game mechanics, I've taken it upon myself to completely re-do our enemy AI system, which thankfully, is one of the few remaining ‘large issues'. Just to quickly look at Bevontule development as a whole, Andy has rewritten massive parts of the overall UI and implemented the ability to buy/sell items and try on equipment. We also recently added inventory persistence, which, in addition to saving off character attributes, also will now correctly save off their equipped items. This was a simple thing to add, but is quite significant in that we are slowly piecing together all of the various things that need to be persisted between game loads. On a side note, it's hard to overstate exactly how awesome the terrains and areas actually look, all courtesy of Andy, who is juggling both programming and art. Meanwhile, I am drunk off my ass rambling about our AIioskeewrqejiwrew.
OK, I'm not drunk, but I am going to ramble quite a bit about this particular topic. Luckily, Bevontule only has two real forms of AI. The first involves enemies on the field and their chasing behaviors, which only barely qualifies as AI, and in fact, is just a simple distance check at this point, although we plan to expand on that. The 2nd form of AI is the more complicated one and concerns how enemies should act during battle. If you have tried either of our demos, you know that a rudimentary AI is implemented and sometimes executes a series of actions that ‘seem intelligent', although this is entirely random. Seriously, the old shit is pretty shameful, but like everything else, first pass implementations always suck.
Taking a step back, the main question to ask is, ‘how would a Human player act in a given situation?' In other words, if the enemies were actually controlled by people, what would be the ‘optimal' move? Mostly, the AI in Bevontule is concerned primarily with determining what series of actions is ‘optimal'. The first thing to consider, before going further, is the list of actions common to every enemy. In code, this is referred to as an ‘AIBundle' and is a very basic object that contains a list of ‘AIActions'. An AIAction is a base class that has three derived classes: AIMove, containing a position, AIAttack, containing a target and AISkill, containing the skill itself AND the target.
Each ‘AIAction' also has a ‘Score' parameter, which is a floating-point value that essentially expresses how ‘optimal' that particular AIAction is at a particular moment in battle. An AIBundle itself ALSO has a Score parameter, which is simply the sum of the scores of all contained AIActions. From a high level perspective, then, the main goal is to generate a list of these AIBundles and from this list, select a single AIBundle, which then breaks down into a list of AIActions that the acting enemy then undergoes, in order, thus constituting that enemy's ‘turn.' So, if an AIBundle contained an AIMove, then an AIAttack, the enemy would move to the specified position, then attack the specified target. If the AIBundle contained an AISkill, the enemy would execute the skill, but would not move or attack. AIBundles, in addition, can be arbitrarily large and ordered in any way, although enemies are bound to the same rules as allies as it pertains to the amount of actions (as well as their permutations) able to be undertaken in a single turn.
Now that we have a basic idea in place, the next task is to figure out how to ‘generate' these AIBundles. This list of AIBundles will essentially, contain every permutation of AIActions that the enemy is able to undertake, with the implicit assumption that most of them will be garbage. This is analogous to thinking in terms of controlling a human player and moving right smack dab into a group of enemies, but not actually attacking/using a skill. That would be a bad AIBundle. To elaborate further, most AIBundles that are comprised of just moves are garbage, since there are usually more things that can be done in a single turn. However, at the beginning of battle, enemies are typically not close enough to allies, thus, a ‘garbage' AIMovement actually is the best option in that particular case, in the absence of other actions. Similarly, for an enemy who is programmed to ‘self-preserve', an AIMovement that moves him out of harm's way (or into the path of a friendly heal) is better than a bundle containing a skill that may do damage, but would ultimately end up being a sacrifice. Even worse, it's possible that a chosen action may end up getting the enemy killed before he is even able to execute it.
These are just a few contrived examples, but the main takeaway is that we need to generate ‘every' permutation and then only choose from the ‘best' ones and ultimately, a single ‘best' one. At first, I thought this would be too daunting of a task and that we would just have to leave the video game business altogether. As it turned out though, there are a lot of shortcuts that can be taken. Anyhow, before jumping ahead, let's take a look at the initial AIBundle generation more carefully. What we actually want to do is something like this:
1.) Generate ALL valid movement positions that this enemy can reach based on his size and movement radius. Create an AIBundle for each movement.
2.) ‘Simulate' the enemy moving to every position. Have the enemy iterate through all skills that it can use, as well as its attack, if applicable.
3.) For each target that can be reached, simulate the skill being used on that particular target. This is a nested for loop, essentially.
4.) Generate a new AIBundle for each AISkill, AND each reachable target.
5.) For completeness, also generate AIBundles in which the enemy first attacks, then moves. (Don't have to worry about skills, then movements, because skills end turns)
6.) Generate a ‘score' for each AIBundle.
7.) Sort the AIBundles according to their score.
8.) Return a specific AIBundle as the enemy's actual ‘list of actions'.
Sure, there are a lot of steps, but just to keep things fresh and exciting, we're going to go through each of them in excruciating detail. So, first things first… generate dem movement positions! What we want to do here is put a bunch of tiny circles into a bigger circle. Each tiny circle is a position that the enemy can move to, while the bigger circle is the overall bounding shape. Turns out that this is a well-established problem known as ‘Circle Packing'. Unfortunately, most mathematicians are concerned with packing circles of varying radii into arbitrary positions within a larger circle, which is admittedly, a harder and completely irrelevant problem as far as Bevontule is concerned. IN short, this meant that there was no code to steal, thus, no shortcuts to take, and no wheels to not reinvent.
The next step, then, was to write a shitty little Python script that ‘generates' these positions. This thing is far from perfect, but it definitely is ‘good enough'. Here are a few sample outputs:
All right, we convert that to C#, all the while getting pissed at those annoying, subtle differences between the two languages. There are a few little extra caveats: we can’t move into a position that is already occupied, and we also can’t move into a position that isn’t ‘walkable.’ Add in those checks and there we go… we have something that generates valid positions. Another important thing to note is that the above steps are spread out over multiple frames. If we tried to generate/evaluate all of the resultant AIBundles in a single frame, we’d lock the game up for about half a second, which is obviously a no-no. Another bonus to this is that there is already a ‘forced delay’ of around 1 second before an enemy executes its turn. Instead of sitting there doing nothing, we can run the AI evaluation during this time. There are several parameters in use that both control the number of AIBundles to generate each turn as well as the amount of time to spend generating all AI options.
Anyhow, that’s step one. Step two is fairly straightforward: we check each skill (for future reference, it’s easier to just refer to an ‘attack’ as a ‘special skill’), seeing if first, we can even use the skill and finally, whether or not there are any targets in range. If there are, we create a new bundle as described. Otherwise, we don’t do anything. There are a ton of optimizations that can be done for these checks (for instance, there is no reason to check the bounding spheres of smaller skills if a target can’t be found in the sphere of the largest skill.)
Thirdly, we test the skill against each target in range and generate bundles for each of those, which is also step four. Step five is easy enough. We’re going to ignore Step 6, for now, since that is really the most important part of all of this and will most likely be covered in a later blog post, tentatively titled “Enemy AI Updates (Part Two)”. Assume, for now, that each bundle has a score and we are now going to sort the bundles. Easy.
Finally, we return a specific bundle. Currently, this is implemented as such: the absolute best bundle is contained in index 0 of the array, whereas the worst bundle is contained in the last element of the array. Each enemy has a ‘difficulty’ rating, which is a floating-point value in the range 0 – 1. Essentially, we choose a random bundle based on this ‘difficulty’ rating. For instance, if the difficulty rating is 0, we consider every bundle, thus, the enemy will most likely do some really stupid things. If the difficulty rating is 1, we consider only the 1st bundle. Thus, the group of bundles to randomly select from is the first ‘(NumBundles – (Difficulty * NumBundles))’ number of bundles.
I am not entirely convinced that this method (Step 8) is the best, but it does produce noticeably shittier AI when the number is reduced, as expected. I suspect that there will be some additional ‘pruning’ needed to completely prevent enemies from choosing truly terrible actions, but it’s a start. As I said before, the real essence of this entire scheme resides in the manner in which we score certain actions, which requires a LOT of trial and error and twiddling with different numbers, which is something I’ll talk about in the next update.
Until next time, thanks for reading!
