Fair warning: The following is a lengthy deconstruction of a very simple idea (“NPCs that walk around on their own and stuff”). If you just want to see a video of the system in action, you can go here.
The AI for Fix is nearly complete, so I can talk about its overall structure with some confidence now. This part of the code is immensely important to me, since this game is very character-driven. The characters need to behave in a believable way so that players can forget that they’re made of sheets of sprites and just think about them as characters, or maybe even as people.
This game’s AI has turned out to be relatively complicated, and it consists of five layers of abstraction (!!!). From least to most abstracted, they are Trivial Moves, Paths, Behaviors, Scripts, and Triggers.
So what does all that actually mean? Well, we’re going to have to start at the beginning…
1) Trivial Moves
A Trivial Move is an instruction so simple that it requires no analysis to follow. In this particular case, where we’re just talking about making NPCs move around a level, they are capable of three Trivial Moves:
Walk: Walk any distance to the left or right.
Drop: Walk off a ledge and fall.
Jump: Jump up a step, across a gap, etc.
Sometimes, an NPC needs to move somewhere and one of the three Trivial Moves can get him there. These are the simplest problems to solve, since they only need to figure out which of the three Moves is applicable. If none of the three Trivial Moves can reach the destination, though, we need to think of something else. Something like…
If an NPC is physically capable of reaching a particular destination, then their movements to get there can be defined as an ordered list of Trivial Moves. Think about MapQuest or Google Maps–Cars can only drive on roads, so they find the shortest path from A to B that follows the roads. Fix uses a similar system to find a path from A to B that only consists of Trivial Moves.
The general idea is to start at the position of the NPC and find every possible way that they could potentially move. This system examines the collision data that is already being used for the level. It finds all of the possible paths simultaneously, expanding them outward from the character at the same rate. Since they all grow at the same speed, the first one that (accidentally) reaches the destination must be the fastest way to get there. It’s a very brute-force method, but since the NPCs have a pretty limited range of motion (the presence of gravity makes a huge difference in terms of navigation), they never have that many possible paths to test.
But even if we know how to get from A to B, how do we even know where B is? The answer is…
A Behavior defines what an NPC is trying to accomplish at any given time. “Follow the player” is a simple example of a Behavior.
A more complex Behavior is “Move to a hotspot.” A hotspot can be any chunk of the level (and a level can contain any number of hotspots). Though this is an instruction that’s very easy for us to understand, it involves several instructions for different situations.
If the character wants to move to the top floor of a level, for instance, they need to start by checking whether or not they’re already there. If they’re not, they’ll try to find a path to get there. If they can’t find one, they’ll wander around until a path opens. Once they reach the top floor, they’ll wander around some more (making sure to stay inside their destination hotspot) until they receive another instruction.
But wait, where do instructions come from?
Gameplay scripting is becoming very popular. While game engines are written in low-level, high-performance languages like C, scenarios for levels are often written in more abstracted languages. Overgrowth, for instance, uses AngelScript for gameplay scripting. Flash is already built on this type of structure–any code I write for my games is written in Actionscript, an abstracted scripting language. The Flash Player, which is written in a low-level language, interprets this script.
For Fix, gameplay scripts look less like scripts of code and more like theatric scripts. At least at the time that I’m writing this, if you hit the “Fix Demo” tab at the top of the page, you can see a demo that reads the following script.
(The three floors of the level are defined as hotspots which are named bottomFloor, middleFloor, and topFloor.)
(Jack moves to topFloor) Jack: I'm going to the top floor. Jack: …boop boop boop… (Jack moves to bottomFloor) Jack: And now I'm going to the bottom floor… Jack: … (Jack moves to middleFloor) Jack: And now the middle floor.
Aside from the inherent cuteness of this solution, it’s ridiculously easy for me to write these scripts. Also note that the game’s dialogue is read from these same scripts, so it’ll be very easy for me to write and implement conversations (of which there will be…many).
So that’s all well and good, but how do we know when to start a conversation?
Triggers have two parts: A condition and a conversation to start. A condition is something like “Kathryn reaches bottomFloor” or “doorOne is open.” Conditions can be combined, like “Kathryn reaches bottomFloor and Jack reaches topFloor.” Once all conditions for a given Trigger are met, it starts up its target conversation.