As I was giving a talk on the topic of AI in games recently, I was asked whether I have ever developed an AI system myself, and it inspired me to write about two of my video game projects that required a behavior-controlling component. This is part one, concerning the pixel horror game Ghul from back in 2017. Note that this post will spoil the final twist of the game, so if you haven't played it, please consider doing so before you read (you can beat it in 20 minutes, tops), or watch Lugmilord's Let's Play of it.
Right off the bat, I must qualify that the AI systems for this game were created by two computer science postgraduates, and that all we knew about artificial intelligence back then mostly came from our university lectures on cognitive systems. As such, Ghul's behavior systems are ridiculously over-engineered in some ways and frustratingly reinventive of the wheel in others.
Monster AI
The most visible AI system in the game is the one that controls the monster (whom many players assume to be the "Ghul" of the title, even though nothing in the game says so). It consists of several components that all interact with each other, namely: the main finite-state machine executing different behavior policies depending on its current state, the pathfinding component and the utility-based door selector for navigating the house, and a separate subsystem for estimating the player's current location based on the noises they make in-game.
In terms of my own classification, the monster's AI operates in the unit scope (only controlling the monster) and the ludic cognitive frame: it actually does its honest best to prevent the player from completing the game. A case can be made, however, that being aggressively efficient is in-character for horror game AI, so the monster should be viewed as operating in the diegetic frame as well/instead. As such, it falls somewhere between the Rival and the Character categories, which I find fitting, given the late-game twist/reveal.
Finite-State Machine
At the most abstract level, the monster is a finite-state machine with five distinct states:
- Searching: The monster is aggressively looking for the player by taking the shortest path to the room which, according to its current estimation of the player's position (see below), has the highest probability of the player being there. The only possible state transition from here is to Stalking, which occurs when the uncertainty of the aforementioned estimation drops below a configured threshold (i.e. when the monster is pretty certain it knows where the player is).
- Stalking: This is perhaps the most complicated behavior policy. The monster has a hidden hunger score, which grows over time, is reset whenever it kills the player, and affects its range of engagement: as long as the player is outside said range, the monster will menace, but not attack them. If both end up in the same room, the monster will slowly walk towards the player, tacitly allowing them to escape; otherwise, the monster will attempt to get as close to the room that it estimates the player to be in, without actually entering it, and then stand within striking distance of the door leading to the player's room, ready to pounce. Furthermore, after the player has collected a certain number of items, the monster gains the ability to block the door it lurks at if its current room contains the item the player is supposed to look for. Two state transitions are defined: if the monster is in the same room as the player and is within the engagement range, switch to Pursuing; or if the uncertainty about player position rises back above the threshold, go back to Searching.
- Pursuing: The monster advances within striking range of the player and attacks, using a linear prediction model to estimate the optimal position to attack from if the player is moving. Because the only attack animation in the game has a fixed range, the player can exploit it by moving too close to the monster and stopping – in this case, the monster moves past the player towards the closest viable attack position after a configurable timeout. The only state transition from here is back to Stalking if the monster is no longer in the same room as the player (which entails them respawning in the starting room if killed).
- Wandering: The monster wanders the house randomly, avoiding rooms where it estimates the player to be. If the monster is in the same room as the player, switch to Fleeing.
- Fleeing: The monster runs for the next exit, preferring paths leading away from the player. If the monster is no longer in the same room as the player, go back to Wandering.
You may notice that there is no predefined transition between states 1-3 and 4-5. This is because these are two distinct sets of behaviors that the monster adopts before and after the player completes the ritual and transforms into a monster themselves: the switch to the Fleeing state is hard-coded to occur the moment the transformation cutscene ends. For the sake of resource efficiency, the new hoodie-wearing intruder who appears after the original monster is killed is actually the same game object as said monster, just with the animation controller swapped out. Its behavior policy doesn't change, so it keeps alternating between Wandering and Fleeing. Note also that these states do not map 1-to-1 onto the animation engine states for the monster, which are considerably more granular.
In hindsight, it occurs to me that a behavior tree would probably be a more efficient architecture to use, but oh well.
Pathfinding
Due to how the game world is constructed (see below), the monster never needs to calculate full paths between its current location and its current goal: instead, at every frame, it simply takes the shortest path towards it. Because rooms are effectively linear, with characters only moving left or right, local pathfinding is primitive: the path towards a certain point (the player, a door, an attack position) is always a straight line towards it it, so walking to a local point is as simple as shifting the monster's position in the target direction by its current speed times the duration of the frame.
To transfer to another room, the monster (just like the player) must walk to a door and activate it. The door selection system will be described in detail below, but for the purposes of pathfinding, the monster has full knowledge of the layout of the house in the form of an all-paths shortest distance matrix between all doors and rooms. Because rooms are shuffled and interconnected in a random order (and the connections are potentially rewired every time the player dies, see below), this matrix is precomputed with the Floyd–Warshall algorithm every time the house changes. For the purposes of the algorithm, the edge cost of room transitions is a constant equal to the duration of the door transition "cutscene" times the monster's average movement speed.
Door Utility Selection
Because choosing which door to take next is a crucial part of navigating the game world, a quasi-utility system was written specifically for that purpose. The system calculates a single utility score to each door within the current room every time it is polled, taking into account:
- ...how close the door will take me to the player's estimated position (using the precomputed shortest distances matrix), as well as whether taking it will likely bring the monster face-to-face with the player (which may be more or less desirable depending on the current state/behavior policy),
- ...how long it will take the monster to reach the door,
- ...whether the door leads to the starting room (which is off-limits to the monster until after the transformation ritual),
- ...whether the door leads back to the last room the monster came from (generally undesirable unless escaping), and
- ...whether the player stands between the monster and the door (generally undesirable because the monster just walking past the player looks weird).
Each behavior policy assigns different weights to these factors (negative or positive), and small random values are added to each door's utility to avoid ties and add a layer of unpredictability to the monster's behavior. Apart from this randomness, the monster always selects the door with the highest utility.
Player Position Estimation
Now we are getting to the over-engineered bits. Unless the monster is in the same room as the player, it must rely on its knowledge of the house layout and of the simulated noise propagation rules to estimate the probability of the player being in a particular room. The house layout knowledge is modeled mainly with the shortest distances matrix and several other arrays the monster precomputes from them. The perception system is wholly separate from and runs parallel to the behavior-controlling state machine, processing signals from its surroundings in real time to estimate the player's location.
Before we get to the actual AI, the game's noise propagation system must be explained. Any time the player does anything except standing still (specifically: walking, running, opening a door, picking up an item, or getting zapped by an item they cannot yet pick up), they generate a noise of preconfigured simulated volume (which is only loosely correlated with that of the actual audio played for the player's benefit). The propagation system then calculates the shortest path between the noise origin location and the monster, including the actual distance and the door it takes to reach the monster's room. The volume of the noise is then divided by the square of said distance, according to the inverse-square law, and as long as it is above the configured audibility threshold, the monster perception system receives a signal consisting of the door ID and the reduced noise volume. For added complexity, the house itself produces simulated noises of random volume, at random intervals, from random rooms, which are then propagated and transmitted to the monster in the same way.
The monster's perception system maintains and updates a simple world model: a single vector of size equal to the number of rooms in the house that contains a discrete probability distribution of the player currently being in each of those rooms. Unless the monster is in the same room as the player, this vector is updated every frame using a hidden Markov model of the player, the house, and the noise propagation to predict and to estimate changes in this distribution since the last frame. The prediction step uses a transition matrix precomputed after each house modification using its updated room adjacency graph and the player movement model (see below), then the player's location distribution vector is filtered using the incoming noise signal or the lack thereof.
The filter step uses a simple Bayesian Wonham filter to update the location distribution probabilities with the likelihoods of receiving a signal of particular volume (consisting of the door ID and the propagated noise volume) or not receiving any (a.k.a. "null signal"), depending on whether the monster received a signal last frame or not. The exact computation of these likelihoods is the truly complex part, averaging over all rooms and noise types and taking into account the minimum audibility cutoff and "fake" noises made by the house. Suffice to say that it does its best to extract the most information out of its knowledge of the noise propagation system. This system was so complex, in fact, that we often ended up with inconsistent probability distributions and had to build in a panic switch to soft-reset the world model back to a uniform distribution.
Player Model Learning
Yes, we've actually built machine learning into the game about running away from scary monsters. Did I mention it was a bit over-engineered?
In order to construct a feasible transition matrix for the prediction step of the player position estimation (see above), we needed to estimate how long (i.e. how many frames), on average, players spend in a given room. To this end, we've implemented a system that collected following data about the player (which was then only stored and evaluated locally, so drop your pitchforks, all ye GDPR fanatics):
- While not being pursued by the monster, how many frames in total did the player spend standing in place, moving at the walking pace, or running.
- While not being pursued by the monster, how much of each room did the player actually explore per visit (measured in the total distance they walked in the time between entering and exiting the room).
From the first three numbers, we are able to immediately calculate the a priori probabilities of the player standing, moving, or running at any given frame (when not being pursued). After several playtesting sessions, these probabilities averaged to 55%, 35%, and 10%, respectively. The remaining data was used to estimate the likelihoods of a player exploring the whole room, walking to the nearest item (if any) to try to pick it up, or just moving to the next door, using a weird mix of backpropagation and iterative parameter estimation. These values ultimately converged on 57.5%, 100%, and 74%, respectively.
Together, all six of these parameters are then used to precompute first the player's mean expected movement speed, then their staying time (in frames) in a room, given its size and its door and item placement, and finally, a transition matrix containing the probabilities of the player staying in the current room or moving to an adjacent one at any given frame (assuming an exponential distribution for a given mean staying time).
House AI
Every time you start a new game of Ghul, the house layout is generated randomly from a pool of rooms, interconnected randomly with doors, and peppered with items. What few players realize is that the house is as much a main character and an active antagonist in this game as the much more visible monster.
In terms of my classification, the house AI obviously has the level scope (since it controls the environment) and thus falls squarely into the Director AI category.
House Layout Generation
At the most abstract level, the house is a connected planar graph with rooms for vertices and doors for edges, with the starting room located roughly at its center (as a side note, each door in the game technically consist of two linked game objects, one in each room it connects). I cannot actually say much about the specifics of random planar graph generation, since it was coded entirely by my co-programmer, but suffice to say that it procedurally generates interconnected series of rooms that make as much spatial sense as required in a horror game.
One important restriction we had placed on the layout generator from the early concept stage onward was that the monster could traverse the entire house without entering the central room (which is off-limits to it before the ritual). This necessitated the graph to have very specific cycles in it that interconnected the rooms around the center, preventing the house from breaking down into three separate corridors branching off from the starting room.
Another restriction placed on the layout generation engine that we had to build in during playtesting was that rooms may not be connected by two side doors (left or right) on the same side – not so much because it looked weird, but because it caused unnecessary confusing room-hopping loops when the player ran into the same door repeatedly without changing the direction they ran in.
Gradual Room Unlocking
Another thing we've discovered when we first playtested the game was that new players got hopelessly lost in the house long before they had figured out that they were supposed to bring certain items to the starting room. To counteract this confusion, we came up with the idea of dynamically locking the player (but not the monster!) out of most rooms at the start of the game, then gradually unlocking more and more rooms as the player brings back more items. Specifically, before any items are placed on the pentagram, only five rooms are accessible, eight after the first item, thirteen after the second, and all sixteen after the third.
To make sure all unlocked rooms are actually reachable from the start, they are grouped by the minimum number of "hops" between them: the starting room itself needs 0 hops, its three adjacent rooms need 1 hop, other rooms reachable from those three require 2 hops, and so on. At any given stage of the game, the house unlocks rooms with the lowest available hop count until a) the minimum available room count is reached and b) there is at least one item to be found in the unlocked rooms that is not yet placed on the pentagram. Because all rooms with n hops need to be unlocked before any with n+1 hops are opened up, this ensures that all unlocked rooms are accessible and contain at least one item to be collected.
Item Selection
The next item that the player has to find and to bring back to the starting room is selected dynamically each time they place the current item on the pentagram or the monster kills them. For this selection, only items that are located in the currently unlocked rooms and not yet placed on the pentagram are considered by the AI, and the actual choice is made at random, with each item's weight equal to its distance (calculated using the same all-paths shortest distances matrix used by the monster) to the pentagram center cubed. This exponentiation makes sure that more distant items are a lot more likely to be picked over closer ones. Because only the item's current (rather than spawn) position is considered, this has an extra mean effect that the closer the player brings an item to the goal before dying or dropping it, the less likely it is to be chosen for delivery again when they respawn.
House Layout Modification
The final layer of meanness to the player is the fact that the layout of the house changes dynamically every time the player dies. Specifically, during normal gameplay, the game counts how many times the player took a particular doorway. Then, every time they die and respawn, the game chooses 1 to 4 of their most visited doorways (this number increases as they progress through the game) and attempts to rewire the house layout graph by either removing the corresponding edge completely, or by connecting it to a different room, or by rotating the room it connects to so it looks like the door layout has changed. The same restrictions apply at this point as during the initial generation: the graph must remain planar, connected, may never connect two left or two right doors with each other, and the monster should be able to reach every room without passing through the center.