The Machine in the Ghost

(Update — check out the updated Frame site and try the new Framepiler tool!)

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.

http://ai.berkeley.edu/project_overview.html

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:

https://jaredemitchell.com/ai-examples/

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.

$GameStart 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#:

#PackManGhost:$GameStart in C# generated by the Framepiler

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

$WanderAroundBase 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:

$WanderAroundBase state

The implementation reveals how to translate the FSM specification into code:

#PackManGhost:$WanderAroundBase in C# generated by the Framepiler

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.

$WanderAroundMaze state

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.

#PackManGhost:$WanderAroundMaze in C# generated by the Framepiler

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.

$FleeFromPlayer state
#PackManGhost:$FleeFromPlayer in C# generated by the Framepiler

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.

$SeekTowardsPlayer state

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.

#PackManGhost:$SeekTowardsPlayer in C# generated by the Framepiler

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:

#PackManGhost:$SeekTowardsPlayer in C# generated by the Framepiler

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.

#PackManGhost:$End in C# generated by the Framepiler

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.

#PackManGhost:$Default in C# generated by the Framepiler

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.

Related Articles

A professional software developer and manager. I believe Agile planning is a real thing.