Four Island

Back in 2009, I made a little game called Maze Of Life. In each level, you are placed into a randomly generated maze, and you have to make your way to the centre. The goal is to complete as many levels as possible without getting stuck.

The natural question here would be -- how do you get stuck in a maze? Therein lies the twist with this game. The mazes are generated using a cellular automata similar to Conway's Game of Life, and the rules of the automata continue to apply while you are playing the level. This means that the walls of the maze can shift around you when you walk by them. Every level begins in a completable state, but you can make it incompletable based on your actions. You can get pretty far using skill -- there are patterns to the shifts in the maze that you can pick up on -- but sometimes? Sometimes your luck just runs out.

To make a long story short, despite this game being written in C++, it is now available to play within your browser:

And now I'm going to talk about it, because I have a tooth infection and I'm too dizzy to play video games.

The original Maze Of Life, the one linked to in that blog post, was actually written in Java. Admittedly, I was a fan of Java in the past, before I really learned C/C++, and a lot of my early games were written in it. That version of the game does still exist, and while it's mostly the same as the current iteration, there's a couple of things about it that are a little off. First of all, Levels 0-9 are much simpler in the Java version; trivial, even. Levels 0-9 from the current version are still there, but they're pushed back to 10-19. I likely made the choice to remove the first ten levels in later versions because they really were trivial; many of them didn't even have mazes in them until you walked up to the centre. The other difference is that the cellular automata rules were applied much more quickly. In the current version, if you walk up to a small structure, you can often watch it bloom out to make a full maze. In the original, it would happen instantaneously.

I rewrote the game in C++ only a few months later. I'm not really sure what prompted me to do this. Looking at my blog archive, I don't see anything between April and June that indicates a newfound interest in C++ (although I did find this very silly post about writing a cake recipe in the format of a Makefile). Either way, the first rewrite only took a few days, although highscore lists weren't added back until November of that year.

Four years later, I rewrote the whole game again, still in C++, using SDL2 this time. This was during my second year of university, and I'm sure I must've been learning something adjacent to C++ at the time because my interest in C++ was skyrocketing (it was only a month later that I wrote rawr-ebooks). It was an improvement over the original code, which used an unsettling amount of global variables and did not appear to be thread-safe at all, but the new code was still pretty weird, and there were a lot of places where the same thing was reimplemented over and over again instead of reusing code. I still had a lot to learn about C++ in 2013 (this is a link to a blog post in which past me did not understand that using calloc to initialise an std::string would not work).

class State {
 public:
  virtual State* operator()(SDL_Window* window, SDL_Renderer* renderer) {
    return NULL;
  };
};

This is how the State interface was implemented in the rewrite, which is adorable to me because I'd clearly just learned about operator overloading. It's also scary to me because the game would change states by returning a pointer to a new state object, and you better believe I was not deleting the old pointer in the process. The pre-C++11 era was scary.

Anyway, let's fast forward a bit. In 2018, I was bored at work and I redesigned the algorithm that the game uses to check that a generated maze is not impossible from the start. I think it works pretty well (it's a breadth first search, but it uses a flood fill to reduce the search space to only movements that would actually cause the maze to shift). And around that time, I started to think it'd be fun to port the game to web, so that it was more accessible to people who didn't want to download and compile a little game.

The main problem was JavaScript. I despise JavaScript. JavaScript is arguably the most commonly used programming language on the planet at the moment, and each passing day my contempt for it only grows. And yet, it's the language of the web. If I wanted to have a game that was playable in a web browser, I'd have to write it in JavaScript.

Right?

This is when I learned about Emscripten. It's a build toolchain that can compile C/C++ code to WebAssembly, rather than actual assembly for normal people. It would allow me to continue to develop my game in the language of the gods, and then output something that could be played in a browser, without me having to touch (much) JavaScript. It even has ports of SDL2 and SDL2-related libraries readily available. Porting my game to web couldn't be made easier.

And yet, I didn't actually get around to doing it until this week (five years later).

There were a couple of things about the porting process that were not quite plug-and-play. For one thing, a major stipulation of Emscripten is that you can't sit in an infinite loop; ticking the game, processing input, rendering, and then waiting for the next frame. Yknow, the thing that a lot of video games do. Doing so would hang the browser. You have to instead refactor your code so that the main thread returns immediately, and Emscripten can repeatedly use a provided callback to run your main loop. This, honestly, shouldn't be too difficult a change to make. But that code snippet I posted above -- the one showing how state changes work in this game -- made it a bit tricky.

Maze Of Life v3 did not really have a main loop. Instead, each game state implementation contained a loop within its implementation of operator(). That function call was meant to last until the game needed to change states; so, each state individually performed all the work of ticking itself, processing input, and rendering. I have no idea why I thought this was a good idea, especially when several game states (most notably the multiple states for the "how to play" pages, and the many states for displaying highscore lists) had extremely similar implementations. In order to make this work, I had to tear this out -- a little.

I didn't really want to put in the effort of completely refactoring the code, so what I did was remove the loop from each state implementation, and just allow the function to return nullptr if a state change was not required. That way, each state implementation would return back to the main loop every frame, even if the states themselves still performed all of the work. If I was making a new game, I would absolutely not implement it this way.

This is one of the simplest state classes, and it's still doing way too much work:

std::unique_ptr<State> HowToPlayState::operator()(Game& game) {
  SDL_Event e;

  SDL_RenderClear(game.renderer.get());
  SDL_RenderCopy(game.renderer.get(), background_.get(), NULL, NULL);
  applyTexture(game.renderer.get(), pointer_.get(), selection_ == 0 ? 74 : 216,
               430);
  SDL_RenderPresent(game.renderer.get());

  while (SDL_PollEvent(&e)) {
    if (e.type == SDL_QUIT) {
      game.should_quit = true;
      break;
    } else if (e.type == SDL_KEYDOWN) {
      if ((e.key.keysym.sym == SDLK_LEFT) && (selection_ != 0)) {
        selection_--;
      } else if ((e.key.keysym.sym == SDLK_RIGHT) && (selection_ != 1)) {
        selection_++;
      } else if (e.key.keysym.sym == SDLK_RETURN) {
        switch (selection_) {
          case 0:
            return std::make_unique<HowToPlayPageTwoState>(game);
          case 1:
            return std::make_unique<TitleState>(game);
        }
      }
    }
  }

  return nullptr;
}

Having a state machine like this isn't actually even bad; it's just that there were way too many states. A main menu state and a play state would probably have been sufficient. At least it's the year 2023 and I'm using smart pointers now. In fact I kind of delighted in wrapping all of the SDL stuff in smart pointers. RAII is like ASMR to me.

Another snagging point in porting the game was local storage. The game keeps track of your personal highscores, which it saves in a file in your home directory. That obviously needed to be adjusted for web. Emscripten actually exposes a pretty powerful filesystem API, and it lets you mount an IndexedDB instance to a virtual directory. The one thing that's a bit confusing about this is that the instance has to be synced after each use, and you have to call out to JavaScript in order to do this. But it wasn't that bad.

What was a bit bad was global highscores. Prior to the web release of Maze Of Life, there was a global highscore list that you could submit your scores to if you were good enough. There wasn't really much of a point to this because the game could only show ten scores, so if there ever ended up being any kind of playerbase for this game, you'd almost have no chance of your score being preserved in the global list at all. But still, that feature did exist (and accounted for at least 5 entire state classes).

Porting this to web would be doable, because I could call out to JavaScript to make an Ajax request. The thing is that I didn't really want to bother with this. I could still do it in the future, but it honestly doesn't seem very worth it at the moment. So the game just doesn't have a global highscore list anymore.

One last thing that really did cause some trouble was maze generation. At the start of a new level, the game generates a randomized board, does 50 gens of cellular automata on it, and then checks if the board is solvable. The first part of this doesn't really matter too much, but the solver could potentially take a while, and it would hang your browser in the process. Like I mentioned before, Emscripten requires you to return to the main loop every frame, and the solver certainly took longer to run than a frame.

The simplest solution to this is to spawn a thread for the solver to run on. It's better than trying to find a way to return to the main loop during the solving process and finding a way to maintain the solver's state between calls. Coroutines could also sort of work, but they add overhead and complexity. So I went with a thread, and the main loop just checks to see if the thread is done before continuing to the play state.

Of course, there's still a problem. The Emscripten port of pthread uses SharedArrayBuffer to manage thread memory. And uh. SharedArrayBuffers have been disabled by default in every major browser since 2018, because it was found that they could be used as a vector for a timing attack a la Spectre.

So that's not good.

Luckily, there is a workaround. Browsers eventually did allow access to this feature again, as long as the following HTTP headers are set for your page:

Cross-Origin-Opener-Policy: same-origin
Cross-Origin-Embedder-Policy: require-corp

These headers lock down the cross-origin channels that could be used to exploit SharedArrayBuffers, thus making it safe to use them again. And luckily, itch.io (the website I am hosting Maze Of Life on) allows you to enable these headers on your game's page.

Other than that, porting the game to web was pretty smooth! I modified my CMakeLists.txt to add compiler flags that Emscripten needed, and I tweaked the generated webpage so that the game took up the whole iframe. And that was it! My C++ program was now executable by a browser. I zipped the generated files, uploaded them to itch.io, and now you can play Maze Of Life online!

I'd love it if you gave the game a chance and commented your highscore on this post. Mine is currently 19, but 14-years-ago-me got up to 27, according to the blog post I linked to ages ago (the post says 37, but I'm subtracting 10 because of the first 10 levels being trivial in the original game). And if I look in the database backup from my old server, I can see that I apparently got a ridiculous 87 points one time, which I'm not sure I totally believe. If you can beat that, you deserve some kind of prize.