The Machine in the Ghost
(Frame is a new Domain Specific Langauge (DSL) focused on enabling developers to easily create programs using automata. See the Frame documentation as well as Getting Started With Frame to find tools and other resources to explore the Frame language.)
According to the website statista.com the global video game market was worth $104.57 billion (US) in 2017 and will be worth $131.23 billion in 2020. Needless to say — video games are a massive business.
One of the most famous and successful video games ever is Pac-Man. Introduced to the world in 1980, it had earned $2.5 billion by the end of the 1990s. Key to its success was the maddening behavior of the ghosts that chased Pac-Man. For the unskilled, escaping the ghosts was a difficult, addictive and (in the arcade days) expensive undertaking.
Surprisingly for such a successful game, this ghostly behavior is straightforward to understand using Finite State Machines (FSMs). Let’s take a look at just how ghosts think about life in the Pac-Man maze:
While there are many FSM diagrams of the ghost AI on the internet, I found the flow diagram from Jared Mitchell nicely informative about the decision criteria for the transitions.
The Framepiler (more on Frame below) also generates UML documentation which shows the same state machine:
As we can see from the diagram, there are 5 main working states:
- WanderAroundBase
- WanderAroundMaze
- SeekTowardsPlayer
- FleeFromPlayer
- ReturnToBase
Next, we will explore how to model and implement this AI using Frame System Notation (FSN).
Game AI with Frame System Notation
Frame System Notation (FSN) is an evolution of UML Statecharts that I have been developing to provide a more precise and expressive language for developing automata.
In this article, I will discuss FSN conditional notation and then show how to apply it to the ghost AI. The code samples have been generated using the Framepiler, a tool I have written in Rust and WebAssembly for turning Frame notation into code and documentation.
The primary goal of FSN syntax is to build an “event map” for events to be routed to the behavior they are to trigger. FSN introduces a parsimonious new syntax for if-then-else conditional tests:
The conditional notation is inspired by the ternary operator in C but is different in that it is used to branch statement blocks rather than just select between two expressions.
Let’s now explore the ghost state machine state by state and see how the FSN notation lines up with the UML diagram.
Ghost Interface and Events
One aspect to real game programming not captured in the UML diagram above was the functioning of the update loop for the game engine. Typically platforms such as Unity call into the important Game Objects for each frame of the rendering cycle to update their state based on the environment. This aspect is not shown in the UML but will be captured in the FSN specification for the ghost.
To begin, the interface supports start, stop and update events:
The interface start and stop methods respectively send “>>” and “<<” messages instead — this is called message aliasing. The update call, however, is sent unaliased directly into the machine. The start and stop aliasing is optional and simply part of Frame’s standard nomenclature but is not required.
Game Start State
The UML diagram shows a simple transition from the initial Game Start state to the Wander Around Base state.
A real implementation would need to initialize the ghost as well as start an update timer unless the engine did that. We will assume, however, that we need to manage our own timer in this implementation and will use this requirement to show how to use Frame start and stop hooks to properly manage resources.
Here is the FSN for our version of the state:
Notice that the $GameStart state passes the event to the $Default state if it does not handle it. Here is the implementation in C#:
We are now able to see three (mostly) equivalent representations of a state:
- Graphical model
- Textual specification
- Code implementation
For this article, we will use the UML notation for the graphical model. However, much of the motivation to create Frame was due to the lack of precision in the UML visual modeling notation and we will see an important example of this. In future articles, we will explore Frame’s Visual Notation which is precise and uses the FSM as its means to define a state’s internal behavior.
On to the first real working state!
Wander Around Base State
Above we see part of the logic for the Wander Around Base state. The transition out is triggered by the guard condition if the timer is greater than some constant “Spawn Time”.
Below we show the FSM specification for the |update| event that triggers the equivalent guard test isPastSpawnTime().
Below we can see all the transitions specified above:
The implementation reveals how to translate the FSM specification into code:
Wander Around Maze State
If the power pellet isn’t active and the player isn’t close, the ghost will transition into the $WanderAroundMaze state where it drifts about in search of Pac-Man. There are two transitions out of this state — one chasing the player and the other fleeing.
These state transitions are a good example of ambiguity inherent to UML statecharts. Notice that the representation of the two transitions out of Wander Around Maze do not define a priority. If both conditions are simultaneously true, we do not know which transition will be taken and which state the ghost should wind up in.
In the FSM implementation below, however, every |update|checks if the power pellet is active first and then if the player is a close second. Therefore the priority is defined and unambiguous using FSM.
Flee From Player State
The Flee From Player state is the only state that the ghost can get eaten in, which starts its journey back to base and a new incarnation. If not eaten, the deactivation of the power pellet will trigger a state change to chasing the player or wandering the maze.
This is the first state where we see nested if-then-else syntax. The rather terse ?-:-:: statement is novel. The key to the syntax is to recognize that every ? (if) or ?! (if not) is terminated by a matching :: (end if). Looking for those matches makes the control flow clear.
Seek Towards Player State
While in the $SeekTowardsPlayer state the ghost is making life hard for Pac-Man.
The state also has two transitions with the same ambiguity about priority as the $WanderAroundMaze state. FSN clarity to the rescue again.
If the player isn’t close, the ghost will go back to wandering while if the power pellet is active our ghost will run away.
Return To Base State
The last UML state to examine is Return To Base. In the diagram, we see a process action in the green rectangle on the transition that resets both the Eaten flag as well as resets the timer.
Up until now, I have been adhering fairly closely to the UML model. In this state, however, I am exploring a slightly different approach regarding what the ghost should do when returning to base:
First of all we see an |>| event handler where the ghost is given the instruction to head back to the base:
|>| headToBase() ^From there, with every |update| event a test is performed to determine “are we there yet”? If so, we do the process block logic of resetting both the timer and eaten flag and then transitioning to $WanderAroundBase again.
This completes our exploration of the states in the UML diagram. Let’s now take a quick look at the remaining FSN states that manage default behavior and cleaning up the ghost controller.
The $End State
The $End state is tasked with cleaning up the only resource owned by the controller which is the update timer. As previously mentioned, if this controller was implemented to be driven by the game engine’s update timer this would not be necessary.
The $Default State
The $Default state is an example of a standard Frame pattern for implementing behavioral inheritance. The only event handler $Default has is one for the stop event |<<| which simply transitions to the $End state.
All states other than the $End state inherit this behavior from $Default.
Here is the full ghostly FSN specification:
Conclusion
In reviewing a number of articles and documents on game AI, I found frequent mention of Finite State Machines (FSM) and the use of UML or something similar to diagram the AI logic. However many of these examples suffered from the ambiguity that UML possesses with regards to a number of important aspects of its models, one of which we saw in this article.
Frame Machine Notation is designed to resolve such ambiguity and only allow the creation of machine specifications that have a clear way to implement them in code.
In future articles, I will return to game AI as a topic for FSN specifications while exploring other interesting applications as well.
