Since we’re on the topic of animation, I decided to give you another example HTML canvas app today. It’s an old favorite of mine: random maze generation. I’ll give you a brief overview of the maze generation algorithm, and then I’ll show you how I converted it into an animation using Dart’s asynchronous programming constructs.

Etch-A-Maze Screenshot

Before we dive in, make sure you try running the app a few times. It’s surprising how mesmerizing it can be to watch a little purple square fill up with random passageways. Click here to run the app!

What wizardry is this?

Once you understand the basic algorithm, telling a computer how to generate a maze turns out to be a lot simpler than you’d expect. I based this implementation on Prim’s algorithm, which works something like this:

  1. Build a grid of rooms, where each room is separated from its neighbors by four walls.
  2. Pick a random room, mark it as explored, and add its neighbors to a list of frontier rooms.
  3. While there are frontier rooms in the list,
    1. Pick a random frontier room from the list.
    2. Randomly pick one of the room’s explored neighbors, and knock down the wall separating the rooms.
    3. Mark the frontier room as explored, and add all of its unexplored neighbors to the frontier rooms list.

It’s a lot easier to understand this algorithm if you can visualize it, which is exactly why I wanted to make this app into an animation. In the app, walls are dark purple, unexplored rooms are light purple, and frontier rooms are yellow. Once you’ve watched the animation a few times, the algorithm should start to click.

Implementing it all in Dart

Since this app is a little heftier than other example web apps I’ve written, I’ll spare you most of the more mundane details. It’s structured similarly to other canvas-based web apps I’ve written. If you’re curious how I’ve implemented anything, all of the code is available on GitHub.

Like Slithery and It’s Alive, the maze generator’s rendering is done through an update loop. Each frame, Maze’s drawAnimatingTiles method gets called with a timestamp.

void drawAnimatingTiles(CanvasRenderingContext2D context, double time) {
  for (var tile in _tiles) {
    if (tile.isAnimating) {
      tile.updateAnimation(time);

      context.setFillColorRgb(tile.red, tile.green, tile.blue);
      context.fillRect(tile.xIndex * _tileWidth, tile.yIndex * _tileHeight,
          _tileWidth, _tileHeight);
    }
  }
}

As you can see, the method goes through each of the tiles that make up the maze image, and it redraws any that are in the process of animating from one state to another. But something’s clearly missing. Where is the logic for the actual generation of the maze handled?

Generating the maze in parallel

The Maze class has a separate _generateMaze method which gets called from its constructor. Anyone who’s ever written a game or other animated application before may be surprised by this configuration. Typically anything related to the state of an animation must be handled somewhere in the animation’s update loop.

The traditional everything-in-the-update-loop approach has its advantages, and you’ll likely want to stick to it if the application you’re writing gets even slightly complex, or if you need to be able to control its execution tightly. Nevertheless, I wanted to give you an example of Dart’s asynchronous programming features, and the maze generator seemed like a good exercise.

Let’s look at the maze generation logic. Here’s a snippet from maze.dart.

void _markNeighborsAsFrontier(Room room) async {
  await rest(20);

  var neighbors = room.unexploredNeighbors;
  for (var neighbor in neighbors) {
    _frontierRooms.add(neighbor);
    neighbor.state = RoomState.frontier;
    neighbor.tile.animateToState(TileState.frontierRoom, duration: 355.0);
  }

  await rest(60);
}

void _exploreStartingRoom() async {
  var startingRoom = _randomStartingRoom;

  startingRoom.state = RoomState.explored;
  startingRoom.tile.animateToState(TileState.exploredRoom, duration: 240.0);

  await _markNeighborsAsFrontier(startingRoom);
}

void _generateMaze() async {
  isGenerating = true;

  await _exploreStartingRoom();

  while (_frontierRooms.isNotEmpty) {
    var frontierRoom = _removeRandomFrontierRoom;

    var link = frontierRoom.randomCarvableLink;

    link.tile.animateToState(TileState.passage, duration: 120.0);
    await rest(10);
    frontierRoom.state = RoomState.explored;
    frontierRoom.tile.animateToState(TileState.exploredRoom, duration: 240.0);

    await _markNeighborsAsFrontier(frontierRoom);
  }

  await rest(400);
  isGenerating = false;
}

static Future rest(int milliseconds) =>
    new Future.delayed(new Duration(milliseconds: milliseconds));

One of the first things you’ll notice about this code is that it’s written in a very direct, imperative style. It’s nothing more than a series of steps, and those steps are very easy to follow from beginning to end. There are no timestamps or state machines, as a game programmer might expect. The only reason we can get away with this organization is that this code runs independently of the app’s render loop. The code executes one line at a time until we hit an await rest(milliseconds), after which execution halts for the given number of milliseconds. Once that time has elapsed, execution resumes right where we left off. How is this possible? We’re leveraging Dart’s built-in asynchronous features, of course!

When you need to write code that runs in parallel, Dart gives you a few options. The official guide to asynchronous programming does a much better job of explaining them than I could, but in short, you have the concepts of Futures, Streams, and the async/await keywords (and variants).

In this app I’m mostly relying on methods that are marked async, but you’ll notice there’s one Future in my code: the one returned by rest. In a typical use-case, a Future is used as a placeholder for a value that hasn’t been calculated yet. Here however, my Future isn’t returning any value. I’m merely waiting on Future.delayed as a way to pause execution for a set duration. It’s an easy way to illustrate how asynchronous code works, but as I’ll discuss later, this approach has pretty serious limitations. I wouldn’t recommend it for most applications. If you’re writing a game, a regular update loop will do. If you just need to execute code after a delay, the Timer class usually makes more sense–plus you can call cancel on it.

Looks like Lua

If you’re coming from a game development background as I am, there’s a decent chance the await methodCall() pattern will look oddly familiar. That’s because the popular game programming language Lua offers a similar feature in the form of coroutines. In a past life, I used coroutines to create procedural animations that responded to changing game states. I’m very pleased to see that Dart offers the same kind of power, but with far more flexibility and attention to code efficiency and cleanliness.

Earlier I mentioned that this direct, imperative asynchronous style has its caveats. Like Lua’s coroutines, await allows you to pause a function’s execution and return once some other process has completed. Yet also like in Lua, over-relying on await methodCall() constructions can lead to tangled state management problems. You’ll notice that I didn’t include any user controls for this example–not even a Restart button. That’s because there’s no straightforward way to cancel a sequence of asynchronous method calls like this once it’s started. There are certainly cancelable alternatives to the Future class that I could have relied on to delay execution. The problem is that once a delay is cancelled, execution still resumes in the function that called the delay, right where it left off. I’d have to do a whole lot of checking and state management immediately after each delay to prevent execution from picking back up in cases when I don’t want it to. That kind of branching tends to clutter up code, thereby negating any advantages the await style would otherwise provide. The only real way to halt maze generation once it’s started is by refreshing the page.

Fortunately, there are plenty of programming use cases where state and error management is reasonably straightforward, so await will work just fine. And there are instances such as web pages and managed game environments where it’s not a problem simply to tear down the entire application and restart it at any given time. As long as you’re careful to use it for the right kind of problems, await can be a tremendously effective tool to eliminate cruft and keep your code direct and focused.

Asynchrony in summary

Dart offers programmers a variety of options when it comes to writing asynchronous code. Each approach has its advantages and disadvantages, so make sure you’re using an approach that’s well suited to the problem you’re trying to solve. Today I stuck to the most rudimentary usage of the await keyword for illustrative purposes. However, Futures and Streams are equally powerful tools, and I’m looking forward to building more examples that highlight their strengths. As always, the code for this example is available on GitHub. Please download it, modify it, and share it. Thanks for reading!