This week, we’re still primarily working on finishing up the factory tools to make adding and modifying objects in the game easier along with continuing our work on the AI. And the AI is precisely the topic of this weeks blog!
As you guys may remember, we talked about the AI a little bit back in March, and a lot of you told us you’d like a bit more info about it and how it works versus the current AI setup. So, we decided to dive into it a little deeper this week and describe in more detail what we’re doing. The current AI is a large, convoluted, easily confused mess. If it weren’t for the 3D dynamic terrain and the amount of units it has to handle, it would likely work alright. Many games use a system very close to what we’re using and it usually behaves pretty well. However, throw all the rest of the game into the mix and the AI becomes dumb as a box of particularly stupid rocks when you end up with a lot of units.
So, let’s start with what’s there now, shall we?
The current AI system is all encompassing, and this presents us with the first issue with the current system. It’s almost 4000 lines long because every interaction and possible case has to be addressed individually. This means that every time you tell your bricktron to grab a brick, it has to go through it’s internal list of every interaction and determine what the correct interaction is. This results in delays and stupid choices, since it can only operate in this simple plane of ‘if’s and ‘and’s. If it encounters something that’s not explicitly defined, it simply stops, unable to figure out what to do.
As we’ve been going through the refactoring and building our factory editors, we’ve been building all the interactions into the actual objects they’re intended for, which will let us cut back on the amount of code needed in the actual AI by a -massive- margin. Even without the bigger changes planned for the AI, this would make a massive difference in how well the AI behaves. We aren’t changing the current AI to take advantage of this simply because it’s being replaced. There isn’t any good reason to spend development time and resources making significant changes to a system that won’t even be in the game anymore soon.
Beyond all that, the current AI system we have, which is a scripted system, isn’t exceptionally good at looking for tasks, and gives us little (pronounced no) introspection into the system itself. So, when things go wrong, we just have to guess at why they’re going wrong and hope whatever we change fixes it. Spoiler alert, it usually doesn’t.
This was one of the driving reasons behind why we decided to abandon the current AI system altogether. It’s difficult to work with, practically impossible to debug, and not terribly intelligent. We were in a situation a great many developers on the Unity platform have found themselves in. The inbuilt AI sucked, the modular scripting for it sucked, and everything we could find publicly wouldn’t do what we needed. We were left in the situation of having to build our own system. So, we did, and have been doing so for quite awhile at this point. The root functions are working almost perfectly now, and we’re quickly running up on a complete system that will run circles around our old one. Literally.
The system we’ve been building is what’s called a ‘behavior tree’, and it’s really the union of the three primary sorts of AI systems.
Scripted systems, which are easy to work with and let you write in any computation you think may be needed, but are incredibly difficult to debug and don’t have much accessibility.
Hierarchical Finite State Machines, which are very simple and intuitive while giving very comprehensive low-level control, but are very labor intensive to implement and make goal-focused AI difficult.
Planners, which are goal focused by default and use searches for automation, but they’re implementations of procedural code and often ignore control and execution, making them somewhat disconnected from the actual game world.
Behavior trees are a joyous union of these three systems. In each specific area, one of these systems may out-perform a behavior tree, but they would fail horrifically in a different scenario. The behavior trees try to take the best from the three systems, while using those same advantages to lessen or straight up eliminate each system’s drawbacks.
Hierarchical Finite State Machine
This is one of the more important legs. This is what gives us our feedback and ability to very quickly and easily debug AI issues and fix them in real time. These are incredibly difficult to explain with nothing more than words because it’s very much a visual system. So here, have a picture!
Credit for picture to xkcd – http://xkcd.com/627/
And that’s effectively what a HFSM is, a flowchart. When used in the game for debugging, it lets you see exactly where the AI is in it’s decisions, and when it crashes out, it’s very easy to see exactly where it got lost.
The headache with HFSM systems is they don’t handle tasks that aren’t explicitly defined well. Well, more like they don’t handle them at all. Everything needs to loop back manually, which gives it a lot of the same drawbacks you have in a scripted system. In addition, they don’t handle behaviors they don’t link directly to.
For example, let’s say you have a soldier unit with a gun patrolling, and the patrol task checks for enemies, then loops back on itself. If he sees an enemy, he’ll start shooting. Then, if he sees a grenade, he’ll dive for cover. After the grenade detonates, he’ll look for the enemy again, and re-engage. Once he doesn’t see the enemy, he’ll search cautiously, then loop back to the patrol task.
But what if he sees the grenade first, before the enemy? That case isn’t handled, the patrol task was only linked to seeing an enemy, and he’d only react to seeing a grenade if he was already engaged with an enemy. As a result, he’d just stand there.
That’s the failing of the HFSM system, it’s very rigid and every case needs to be handled. With our game as it is right now, that wouldn’t really be a huge task. But later on down the line, as we start to heap complexity on with traps and new enemy types? A pure HFSM would turn into an absolute nightmare that would look like a mess of spaghetti.
As such, while we’re using HFSM’s in the game, it’s only a part of what we’re using, and it’s mainly to make room for the real system to shine
Visually, the behavior trees look very much like the HFSM’s. However, they’re much, much more flexible. Imagine the system as, well, a tree. You’ve got the base of the trunk, which would be the idle case, a Bricktron just standing there. Then the trunk goes up a bit and goes to a task where the bricktron is looking for work or an enemy, depending on the bricktron type. These first two tasks loop back on each other constantly so the unit is constantly on the lookout for a task.
Then the tree starts to branch out, going to individual, specialized tasks. One branch may be running, one branch may be grabbing a brick, another might be grabbing a pick. Let’s go with the pick example.
Our progression from the base of the trunk would be like this:
Idle -> Search for Job -> Locate mining job:have tool=false -> Grab pick
In an HFSM, in order to account for the possibility of the mine not being there anymore or the units job having changed, we’d have to loop all the way back to the base of the tree, which would add time to the process, like so:
Idle -> Search for Job -> Locate mining job:Have Tool=false ->
Grab pick -> Idle -> Search for Job -> Locate Mining Job:Have Tool=true -> Go mine
However, with the behavior tree, each leaf handles it’s own exceptions. If the code isn’t there, it backs up the branch until the case is valid again, as such:
Idle -> Search for Job -> Locate mining job:Have Tool=false ->
Grab pick:no further case, back up -> Locate Mining Job:Have Tool=true -> Go mine
This is a very simple example of how it works. The behaviors trees give us access to a great variety of flexibility beyond that, such as sequential cases, random cases, abstraction, separating goals from behaviors, tons of stuff. If anyone would be interested in hearing about some of the deeper bits in more detail, please say so and I’ll be happy to dedicate some time to it in the future. But, as for now, I think this blog has already run long enough. So, let’s move on to news, shall we?
Sadly for us, next week will be Ahmad’s last week with us. He received an offer that anyone would be crazy to turn down, and it’s an amazing opportunity for him. We wish you will in all your future endeavors Ahmad, and we will all miss you. Keep in touch!
We came across a tool recently, and since we have a lot of developers and/or future developers reading this blog, we wanted to share it. We tested the implementation this week, and it may indeed help you in your work. It’s a very handy package manager for .NET that produces and centralizes those packages. We personally use MyGet, but you can get your own server running very easily too!
As it says at the very top, this is our 99’th blog entry. We’ve got something special planned for blog 100, and we’re changing exactly how we do it and communicate. In line with that, we won’t be having a blog entry next Friday. The following week, on the 11th, we’ll have Dev-Diary 100.
What’s changing? How’s it going to be different? Well, that would take all the surprise out of it, wouldn’t it? Check in with us on the 11th of July and let us know what you think about the new setup. The change to the blog isn’t the only surprise we’ve got in store.
Soundtrack of the week
It’s been a while since I had the chance (or the time) to discover any new artists on bandcamp, but I stumbled upon one this week that really got my attention. I feel a little bit of resemblance to Two Steps From Hell and Immediate Music, both of which have also really good soundtracks.
And, as always, thanks for reading!
20 Comments for Dev-Diary Ninety-Nine: AI-AI-O Part 2