Opinion: What Shape Is Your Game?

[In this reprinted #altdevblogaday-opinion piece, AI game researcher Luke Dicken says that before you write AI for a game, you first need to know the shape of the problem you're trying to solve.] "I'm making a game. How do I write AI for it?" This question crops up on a pretty regular basis in a variety of my online haunts. It's understandable – AI is, I feel, one of the trickier (or at least murkier) areas of game development and it's a fundamental area that, if done wrong, is going to get you a bad review very quickly. With that said, though, this kind of question is one a lot of people ask about AI, and it isn't really one that can be answered. There isn't one way to implement AI for a game, there are lots, and which one is most appropriate varies hugely dependent on what kind of game you are making, what you're trying to achieve, and what else is going on in your game. So, how can we make the question more meaningful? What it needs is a lot more information to be included. In an ideal world, the question will look more like "I'm making a game that focuses on , how do I write an AI system that will do ", but in an ideal world you'd maybe instead be looking to hire an AI consultant (I am available should you want to pursue that further… :) ) rather than just asking in relatively relevant places online. That might get you an answer that is specifically tailored to what you are trying to do and the game you are trying to make, rather than just a ten-minute chat on an IRC channel and a bunch of potentially useful links, which is often what this question receives. However, with that said, there are broad classes of problem that lend themselves well to specific techniques. A collection of these properties defines what I call the "shape" of a problem. As a very brief example, the AI required to play Chess is completely different than you would use to play say Whack a Mole. The problems have completely different characteristics (despite both being AI for games) or put another way, they are different shapes. In fact, it's not uncommon for two games to be completely different from each other but have a lot more in common with a non-game problem, being closer in shape to that than other games. For example, from an AI point of view, Poker has a lot more in common with a stock market system than it does with either Chess or Whack a Mole. Defining The Shape If you know what shape your hole is, you can find the peg to match.Genre is one of the best measures of a problem's shape because it allows us to define more or less what we expect from the game environment in one word or acronym. If I say I am making an RPG, then we all understand that I'll probably be talking about quests with objectives to complete, maybe character progression and so forth. From an AI point of view, I'm looking to create a set of characters to inhabit dungeons (or a setting-appropriate equivalent) and towns. If I say I'm making a racing game then I'm talking about AI for racing, so I want to be thinking in terms of an AI that works out how best to navigate a course, how to optimally take turns maybe, and of course I want to factor in the player's position so that the racing AI is beatable. Genre typically encapsulates a lot of information that a more technical analysis would require. For example, the concept of stateful or stateless games is crucial to choosing an AI technique. If you need to have an AI that builds up reasoning and that holds on to what has happened previously, then you are talking about a stateful AI. An example of this might be the RPG I mentioned above – NPCs have tasks to achieve, and you need to know their current state such as what they are trying to achieve and what has previously happened to them, in addition to the circumstances they find themselves, in in order to make decisions about their activity. Contrast this with a simple racing game where decisions are based purely on a cars location and heading and the turns ahead. The former clearly requires an internal model of the worlds state be updated, the latter is massively more simplistic and is stateless, though note that it's not hard to introduce concepts such as refueling that rapidly make a driving game into a more complex system that requires stateful AI. So, How Do I Make An AI For My Game? If your game is stateless, then you might find a Neural Network will work OK for it. It's a straightforward mapping of input values to outputs and works best when there's a reasonably limited number of both. You can get some relatively interesting reactions out of a Neural Network, but you need to get the right connections in the network and the right weights and threshold values. You can do that by training the NN. It can be a bit fiddly but it's not a terrible solution for stateless games. When you consider moving to games, or characters, that have state representations though, it gets very tricky to use a NN. It isn't impossible to get the state representation into the NN (a really good set of essays on doing this kind of thing is Vehicles by Braitenburg – I always encourage people to read this as it's a great primer on a number of AI concepts), but the extra complication it introduces is miserable and it isn't the right way to do it. A better solution, and one that's very much in vogue right now is the Behavior Tree. You can think of a BT as a really advanced flowchart. Before BTs came along, we had Decision Trees, which more or less were flow charts – Is the player present? If yes go down this branch, if no then go down this branch instead. Eventually after a bunch of these type of questions, you get an action to execute in response to the world. Pretty basic stuff. A behavior tree is different in that it allows you to remember where in the tree you ended up at the last iteration, and if there are still things to do there, do them – but at the same time, allows more important things to interrupt and take precedence. Great tutorials laying out Behavior Trees can be found in a few places these days, but for my money, the best one is written by Bjoern Knafla here on AltDevBlogADay. In general, if you're looking to create NPCs that react to their surroundings in an intelligent manner, you can do a lot worse than check out BTs for a starting point. What if you aren't talking about NPC characters? Say it's an RTS, so you're trying to write a system that will play an entire army – that's not really a character is it? Well… yes it is, in a way. Sure, you need to be telling a lot of different units what to do instead of one guy, but the decision processes can be seen as the same kind of thing – really, the ways your AI interacts with the world ("actuators" in scientific-y AI jargon) aren't so important – whether the AI is playing the role of a character that needs to decide whether to shoot or not, or a general that needs to decide whether to order a unit to shoot or not, the decision process could be identical under the hood, the only difference is how it is wired up to interact with the world. In this way, BTs might still be appropriate for driving this kind of AI and allowing you to do things like authoring different characters to behave differently (perhaps one general prefers a certain tactic that another doesn't use for instance). There are a range of other techniques you could use, which I'll cover later. The End… For Now I've not covered half of what I intended to when I first started writing this piece. I've spent a lot of time here focusing on making AI that controls opponents in the game world, but as I've said before, AI is a lot more useful than just making the bad guys shoot. I wanted to talk about AI Directors, content generation, and I haven't even scratched the surface of what's going on with character controllers – there are loads more techniques and aspects of the shape to bear in mind. I'm going to have to leave you with this as merely part 1, and come back to the rest of this material later. I hope that at least what I've laid out here helps you to start thinking about AI in your games in terms of the type of problem you need to solve, rather than some generic black box you can slot in to place. [This piece was reprinted from #AltDevBlogADay, a shared blog initiative started by @mike_acton devoted to giving game developers of all disciplines a place to motivate each other to write regularly about their personal game development passions.]