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 M = ( Q, \Sigma, \Gamma, \delta, q_0, Z, F ). This is behavior and data wrapped into one. Let’s make this usable. Q is the set of states you can be in. It needs to be finite. Then you have an input alphabet \Sigma which essentially is player input. Next we have the stack alphabet \Gamma 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 \delta 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 (p, a, A, q, \alpha) which we will discuss shortly.

The Z is the initial stack symbol that the stack is initialized to when started. And F 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 \delta which contains (p, a, A, q, \alpha). This means that we are allowed to transition from state p to state q when the input a is received and while A is the topmost stack symbol, pop the topmost stack symbol and replace it with \alpha.

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
}

Stock Market Game

From the book “Announcing Computer Games for Business, School and Home” by J. Victor Nahigian and William S. Hodges, this post is about two interesting games: Star Trek and Stock Market. There are many good games in this book, but I’ve chosen these two because they are interesting to me today. In the past, I have written these two programs out on the Commodore VIC-20. They are simplifications on previous games, but when you have very limited memory (5KB and 16KB), you have to cut features.

Stock (Market)

The object of this game is to make more money than the opponent (computer). The mechanism for this game is rolling two dice representing shares “A” and “B”. The first die allows you to buy “B” shares and the second allows you to buy “A” shares. The amount of shares is the value on each die. Selling works the same way. There is a 5% brokerage fee on each transaction. At this point, I’m wondering how much the brokerage earns?

The second mechanism is adjusting the price of the stock. This appears completely made up. You can use your turn to raise the price of a stock “A” by “B” dollars or lowering a “B” stock by “A” dollars.

Overall the program is about 2 pages of BASIC code. So the challenge would be to convert it to C++ or use JavaScript and my LibXOR library. I would rather experiment with C++ for the core mechanic and then convert it later if it still remains interesting.

Star Trek

This program is also two pages of BASIC code, but it feels more dense than STOCK. This game reminds me of an RPG or Pokemon battle. You have the U.S.S. Enterprise and a Klingon ship each facing a different angle. You have to figure out the appropriate angle to fire at the opposing ship. You are given the option to fire phasers, fire photon torpedos, print a status report, change movement, or self destruct.

I’m reading the source code and this game is more involved to describe than the STOCK game, so I will delay that until I have experimented with writing this game out. I am thinking this could be fun to expand by allowing several ships, real-time flight, or several star systems. For now, I will also try my hand at doing this in C++.

Gamedev This Year

Furtual Rabbit was my first game in a year. It was revealing how out of practice I had gotten. It might be time to start doing more One Hour Game Jams. On the other hand, I got a lot of experience with computer graphics and simulation techniques which was my main focus during the academic year.

So what will I focus on this coming year? On the top of the backlog is getting some graphics research written up and sent to journals. Next up is improving my LibXOR library for #GameDev so that I can prepare for a 7DRL. And one last goal for good measure is creating a real-time ray tracer to go with my Unicornfish network rendering concept. For this blog post, I will talk about the latter two in a bit more detail.

The 7 Day Roguelike Challenge (7DRL.com) happens in early March. Roguelikes are inspired by the game Rogue. They often feature some combination of turn-based gameplay, grid-based environments, permadeath, and procedurally generated levels. What would mine look like? Topologically speaking, I want a procedurally generated overworld and fairly shallow levels with keyed off areas. I have some concepts in my head how they might play out, but I need to work on some prototypes first.

And finally, graphics wise I want to experiment with Realtime Ray Tracing and to that extent, I want to integrate it with my network rendering API Unicornfish. This means that I need to start decoupling it from the Fluxions Library. There is a lot of work to be done in that department, so I will need to spend some time charting out how the library works. There are a lot of TODOs on the current backlog, so this coming year will be quite busy, but perhaps I can drive two publications out of all that work.

Furtual Rabbit Ludum Dare 44

The Ludum Dare 44 theme is “Your life is currency.” So I created a capitalist virtual pet game called Furtual Rabbit: A Defurred Income Game. The goal of the game is to raise an Angora Rabbit. You have to feed, water, brush, and clean to keep the quality of the rabbit fur high so that you can groom it and sell it. Not all rabbits live forever and poorly maintained ones die even faster.

Link: https://ldjam.com/events/ludum-dare/44/furtual-rabbit-a-defurred-income-game

HTML5: https://microwerx.github.io/ldjam44/

The BSDs and System V

NetBSD, OpenBSD, and FreeBSD. They are all fun. They are different than Linux. I am of course talking about the kernel rather than the GNU software that is typically available on all of them. The BSDs have a vintage feel about them. I like it.

I wish that it was easier to try System V or SVR4 rather. Because instead of the Berkeley line, it is from the AT&T line which was the basis for IRIX, the version of UNIX on SGI systems. I still have a fondness for the MIPS10000 Octane MXE workstation I had many years ago.

The only way to try System V nowadays is to use an OpenSolaris derived system. But I have to admit that I hated Sun systems when I was younger for no good reason. I think it was because the 3D graphics sucked and I do graphics! So, it left a sour taste. Though there is a Sun variant called Tribblex that looks like it could be interesting to try in a virtual machine.

Of course, the BSDs still feel like the best out feel out there. I want to set one up with a nice X11 desktop like MWM. And it would be nice if IBM and HP would release AIX and HP/UX as free software. And maybe SGI will release their source code for their X based desktop and life would be grand.

UNIX could become more available to the common folk. I was watching some classic Computer Chronicles about UNIX. In 1985, it was still crusty and untrustworthy. In 1989, their last chance to prove UNIX was worth using, all they could talk about was how you could use a menu and how there machines cost $5000. Lol.

FreeBSD Part 2

So I tried FreeBSD in VirtualBox. Step 2 was to try and install it on my Thinkpad. Unfortunately, I am having boot issues. Perhaps it was too many operating systems. I deleted everything but Windows 10 and then reinstalled Fedora 29. I may try again on my Intel NUC that I am currently using PopOS with. In the mean time, the Raspberry Pi 3 is getting a go at it. The wifi does not work, so it is tethered to my router so I can install X11. I used the image from the FreeBSD website. When I get everything installed, we’ll see how the experience is.

Playing with FreeBSD 12

So my use case is run FreeBSD in VirtualBox in Windows. The first experiment ended up in failure, but not because I was using Windows, rather because I can’t get the X server to behave. So I will need to attempt this again. I will say that my goal is to do 3D graphics and game development.

However, I did discover some neat things I can use this OS for. For instance, I am rediscovering WindowMaker. I thought it was cool that the PlayStation 2 Linux Kit used it as the default window manager. I used it often in the 1990’s. It still looks good. But, it doesn’t work out of the box for any kind of real work.

There are several packages I am trying: redshift, compton, and xdg-user-dirs, xscreensaver. Anyways, here is my current pkg install command list.

pkg install bash tmux htop vim emacs w3m wget curl nano
pkg install xorg slim windowmaker enlightenment wmakerconf
pkg install redshift compton xdg-user-dirs xscreensaver xeyes
pkg install firefox gimp
pkg install ...

I will note that I find it ironic that it takes 1 gigabyte to do the first line which are supposed to be command line utilities! By using emacs-nox and vim-console, it goes down to 279 MiB instead. These are the dockapps I installed for WindowMaker.

pkg install wmcpuload wmclock wmnetload wmsystemtray wmtop wmmemload
pkg install inconsolata-ttf

The Xdefaults file needs to be updated so that xterm doesn’t look too small. I use the following settings:

*xterm*foreground: #cfcfcf
*xterm*background: #000000
*xterm*font: xft:Inconsolata:size=16

C++ Vector and Matrix Library

I am working on an open source Vector and Matrix Library for C++ and TypeScript. I am calling it FluxionsGTE and FluxionsWebGTE, respectively.

// TypeScript
class Vector3 {
  constructor(public x: number = 0, public y: number = 0, public z: number = 0) { }
}
// C++
template <class T>
class TVector3
{
public:
  T x, y, z;

  TVector3(T x = T(0), T y = T(0), T z = T(0)) { }
};

using Vector3f = TVector3<float>;