Pushdown Automata

A pushdown automaton (PDA) is a state machine with a stack. They can either be deterministic or nondeterministic. Mathematically, they are weird to look at. It is better to be deterministic rather than nondeterministic because you control what your application will do even if you do not know the exact order of user input. They can be used to handle numerous game development tasks like handling the game loop.

The formal definition is that a PDA is a 7-tuple . This is behavior and data wrapped into one. Let’s make this usable. is the set of states you can be in. It needs to be finite. Then you have an input alphabet which essentially is player input. Next we have the stack alphabet which are the items we can put on the stack.

For convenience sake, we are going to use ALLCAPS for symbols on the stack, CamelCase for states, and quoted characters (such as “Escape” or “q”) for input.

The function defines which state we can transition to given the current top of the stack. This is the transition relation. For example, if INIT is currently the top item on the stack, we shouldn’t move around in states that are reserved for GAMEWON. This kind of formalism helps our PDA to be deterministic. More specifically, the transition relation requires five pieces of information which we will discuss shortly.

The is the initial stack symbol that the stack is initialized to when started. And is the set of accepting states. For instance, perhaps we only want to transition when a key is pressed down, but not when a key is released. Often a double circle is used to mark these states.

Let’s return to the transition relation which contains . This means that we are allowed to transition from state to state when the input is received and while is the topmost stack symbol, pop the topmost stack symbol and replace it with .

If we were using a regular state machine, then we might have the player in the GamePlaying state and when the user inputs “Escape” (to pause the game), we might transition to the GamePaused state and wait until “Escape” is pressed again before transitioning back to the GamePlaying state. This is trivial, but if we then decide to add a settings menu that is accessible from the pause menu or from the game, this is going to cause a mess of if-else statements because the way to code this is:

// Init code
int gameState = GamePlaying;

// Game loop
if (gameState == GamePlaying) {
  if (keys[ESCAPE]) {
    keys[ESCAPE] = 0;
    gameState = GamePaused;
    return;
  }
  if (keys[F2]) {
    keys[F2] = 0;
    gameState = GameSettingsMenu;
    return;
  }
}
else if (gameState == GamePaused) {
  if (keys[ESCAPE]) {
    keys[ESCAPE] = 0;
    gameState = GamePlaying;
    return;
  }  
  if (keys[F2]) {
    keys[F2] = 0;
    gameState = GameSettingsMenu;
    return;
  }
}
else if (gameState == GameSettingsMenu) {
  if (keys[ESCAPE]) {
    keys[ESCAPE] = 0;
    gameState = GamePlaying; // What about pause?
    return;
}

So the problem is very clear, we have no way to remember where we currently are. We have to either duplicate the Settings menu as GamePlayingSettingsMenu and GamePausedSettingsMenu or we have to keep track of extra state. With the PDA, we can remember where we are by pushing/popping the current state. Consider the following code:

// Init code
vector<int> gameModes;
gameModes.push(GamePlaying)

// Game loop
if (gameModes.back() == GamePlaying) {
  if (keys[ESCAPE]) {
    keys[ESCAPE] = 0;
    gameModes.push_back(GamePaused);
    return;
  }
}
else if (gameModes.back() == GamePaused) {
  if (keys[ESCAPE]) {
    keys[ESCAPE] = 0;
    gameModes.pop_back();
    return;
  }
  if (keys[F2]) {
    keys[F2] = 0;
    gameModes.push_back(GameSettings);
    return;
  }
}
else if (gameModes.back() == GameSettings) {
  if (keys[ESCAPE]) {
    keys[ESCAPE] = 0;
    // now we go back to where we were
    gameModes.pop_back();
  }
}

This new PDA behavior is far easier to maintain than the previous if-else statement process. The previous Finite State Automaton (FSA) previously had no method of remembering where we were. Hence, if you pressed “ESCAPE” in the settings menu, you would go back to the game even if the game was previously paused. You would have to have a non-deterministic algorithm otherwise. The PDA makes this process deterministic, which we previously mentioned is the ideal case–you always know what your application will do.

So, one modification I like to use is to couple the stack with a main symbol, a secondary symbol, and a pop time. The main symbol is used to control the main logic of the game, the secondary symbol is used as a PDA. I can then pop the main symbol and all the PDA used for the secondary state will go away. The pop time is used to automatically pop a symbol off the stack after a certain period of time. The following pseudocode is then possible:

struct GameState {
  std::string gamemodule;
  std::string alt;
  double popTime;
}
vector<GameState> gameStates;

void init() {
  gameStates.push({"MAINMENU", "", 0});           // When play game is pressed, these next
                                                  // items are popped at 1 second intervals
  gameStates.push({"SHOWCOUNTDOWN", "THREE", currentTime + 1});
  gameStates.push({"SHOWCOUNTDOWN", "TWO", currentTime + 2});
  gameStates.push({"SHOWCOUNTDOWN", "ONE", currentTime + 3});
  gameStates.push({"SHOWCOUNTDOWN", "GO!", currentTime + 4});
  gameStates.push({"MAINGAME", "", 0});
}

void gameloop() {
  if (gameStates.empty()) return;
  GameState &top = gameStates.back();
  if (currentTime > top.popTime) {
    gameStates.pop();
    return;
  }
  if (top.gamemodule == "MAINMENU") {
    // if PlayButton pressed
    gameStates.pop_back();
    return;
  }
  if (top.gamemodule == "SHOWCOUNTDOWN") {
    // do nothing, display() will draw "ONE", "TWO", "THREE", or "GO!"
    return;
  }
  if (top.gamemodule == "MAINGAME") {
    // handle in game logic
    return;
  }
}

void display() {
  // Approach here could iterate through gameStates and render items back to front
}