Makin’ Mazes

After my previous post on the subtleties of CSS subpixel rendering, Andrew pointed out that readers might be more interested in how to dynamically generate mazes. It sounded crazy, but here we are.

First of all, if you’re interested in this stuff, there’s a great slideshow on maze generation here and more resources on the procedural content generation wiki.

Basically, your maze is made up of boxes:

single_square

You create the maze by making a grid of these boxes, and then Kool-Aid-maning your way through certain walls.

Ohhh yeah.
Ohhh yeah.

How do you choose which walls? That’s where the algorithm comes in.

First, you choose a square to start the maze at. You add this square to an “active set,” which is the set of squares that you’re currently enmazing:

this.active_set_.push(startNode);

Then you choose one of the square’s neighbors at random. If that square isn’t part of the maze yet, you connect it to the starting square and add it to the active set. If it is already part of the maze, you choose a different neighbor. If all of the neighbors are already part of the maze, you remove the starting square from the active set.

var new_node = startNode.getNeighbor();
if (new_node) {
    this.active_set_.push(new_node);
} else {
    goog.array.remove(this.active_set_, startNode);
}

Now choose a member from the active set and repeat until the active set is empty.

Putting this all together, this looks like the following:

Maze.prototype.generate = function() {
    this.active_set_.push(this.startNode_);
    while (this.active_set_.length > 0) {
        this.run_();
    }
};

Maze.prototype.run_ = function() {
    var node = this.pickActiveNode();
    var new_node = node.getNeighbor();
    if (new_node) {
        this.active_set_.push(new_node);
    } else {
        goog.array.remove(this.active_set_, node);
    }
};

The actual full code for this is a couple hundred lines long and you can get it from my Github repo. However, the two functions above are the “meat,” the rest is just details.

Screen Shot 2014-01-18 at 12.22.27 PM

The most interesting part of the code above is the var node = this.pickActiveNode(); line. Depending on how you pick nodes from the active set, you get different “shaped” mazes. For example, here’s random:

random

30% choosing the first square in the active set:

some_pop_first

60% choosing the first square in the active set:

60p_pop_first

Each maze has a different “character.” Pretty cool!

Fixing CSS antialiasing on Chrome

I’ve been working on creating mazes with LimeJs and I ran into a problem:

Screen Shot 2014-01-18 at 12.42.13 PM

As you can see, this maze looks like it was rendered by a dying printer: there are horizontal white lines all over the place. I was going crazy trying to track down the cause: the squares were perfectly sized/placed and the padding and margins were all zero pixels. It looked fine in Firefox, just Chrome had the issue. Finally, Andrew figured out that it was antialiasing on pixel borders and, if I offset the images by less than a pixel, they wouldn’t be “rounded off.”

I tried offsetting everything by .5 pixels:

Screen Shot 2014-01-18 at 12.41.57 PM

Better, but not perfect. However, with .1 pixels:

Screen Shot 2014-01-18 at 12.41.34 PM

Good enough!

I made a patch for this but I haven’t made it work for masks so I’m not going to do a pull request for it (yet). However, you can cherry-pick it from my fork of LimeJs and use it by adding the following line to your start() function:

lime.Renderer.DOM.ANTIALIAS_OFFSET.y = .1;

If anyone knows anything about why Chrome antialiases stuff like this, I’d be interested in knowing (I found lots of sites complaining that it was weird, but none explaining it).

Happy hacking!

Game Jam Resource List

The best programming thing I found in 2013 was game jams. They are so much fun, a great way to get better at programming, and stretch my artistic chops. They also really makes you focus on finishing the game, which (for me) is the hardest part.

There are downsides: jams take up the entire weekend and, when Monday rolls around, my hands are Friday-level tired.

Anyway, since It’s been such an amazing hobby, I thought I’d share some of the resources I’ve found in case anyone is interested in trying it out.

Finding Gamejams

CompoHub has a calendar of all (or at least most—sometimes it’s a little behind) upcoming jams. Ludlum Dare is the biggest game jam, it’s held once every 4 months.

If you’re looking to “roll your own,” New Year Game Jam has a great idea generator.

Programming

I like using JavaScript because then everyone can run my games: they’re not dependent on having the Java SDK or .NET or something. I use LimeJs as a game engine. It’s pretty basic, but it is flexible and uses Google Closure, which provides a JavaScript API that’s really nice.

Art

I do all of my art with Sprite Something, which is only iOS and costs a couple bucks but works great.

TexturePacker seems to be the de facto standard for spritesheets, and it’s worked great for me so far.

Music

This totally amazes me, but this guy Per Nyblom made an automatic music generator that will create “random” music for your game with a click. He doesn’t have any plans to open source it (yet), but http://rml.pernyblom.com/ is open source.

For sound effects, there’s cfxr/sfxr.

TODO

Next year, I’d like to do at least one of: a game with a server backend, release some of the general libraries I’ve created to work with LimeJs, or integrate a game with Facebook/a chat service/something else.

Also, my goal is to keep updating this as I find more useful resources. Hope this helps someone!

Davy Jones’ Freezer

Last weekend I participated in The Arbitrary Gamejam #5, with the theme “Damn the Torpedoes! Full Speed Ahead.” I came up with “Davy Jones Freezer,” where you’re an ice cream transport that needs to get through a minefield to deliver ice cream to an island.

Screen Shot 2013-12-08 at 11.32.50 PM

This wasn’t as tight a game as The Little Volcano, but I learned a lot of new things. Things that worked:

  • Having a tutorial class. I always loathe doing the tutorial and it was almost painless.
  • Figuring out exactly what to deploy. I deployed exactly three files: the index.html, the javascript, and the spritesheet. Previously, I’ve ended up throwing a ton of unnecessary crap up because I’m not sure if I need it or not.
  • Having a goal for the player. The judge for the last Arbitrary Gamejam pointed out that a goal would have been nice and he was right!

Things that didn’t:

  • The workflow of drawing something in ArtRage, exporting it to Gimp, magic-selecting the canvas away from the edges, resizing it, exporting it again… ugh. I’m sticking with pixel art from now on, the workflow feels a thousand times more efficient.
  • The ocean class kind of got away from me. Not only did it become one of those mutant classes that contain references to everything, but I spent a long time struggling to create an infinite board. I think I probably could have broken the problem down better with a few minutes of thought (and maybe a piece of paper).
  • Up through the end, the background was irritatingly flicker-y. Still not sure why, but I think I need to understand the LimeJs rendering code better.

Screen Shot 2013-12-08 at 11.33.10 PM

I wanted a font that said “Here there be dragons.” When Andrew saw it, his reaction was, “Would you like a Dove bar?” Now every time I see it, I think “Dove bar.” The theme of the game doesn’t help, I guess.

All in all, I’m glad I did it, I learned a lot, but I’m a bit disappointed in the final product. This weekend is Ludum Dare, so hopefully I can create something that I’m happier with.

The Little Volcano that Could

This weekend, I participated in The Arbitrary Game Jam, a once-a-month game jam with randomly-chosen topics. My entry was The Little Volcano that Could, a turn-based strategy game where you’re a little pool of lava in a big scary world.

Screen Shot 2013-11-03 at 6.29.53 PM

The jam started at 10pm on Friday night, at which point I was at a Halloween party. I checked my phone and the topics were lava, “love hurts”, and “be a stranger to fear.” I started thinking about making a platformer and then thought it might be fun to play the lava and try to burn as much as possible.

Saturday morning, I pulled out a pad and some dice and tried out some ideas. It turned out killing villagers was a lot of fun, so I decided to focus on that.

sketch

I created a new Github project for it and got a 3×3 square of grass with lava in the middle:

The beginnings of a game.

I implemented being able to “move” by placing adjacent lava:

Screen Shot 2013-11-02 at 11.58.10 AM

Next, I implemented the villagers who’d throw water at the lava to cool it and a “thermometer” to put a cap on how long the game could last:

Screen Shot 2013-11-02 at 6.12.14 PM

At this point things went a little off the rails. I was thinking I’d implement A* search for the enemies to find lava, but I started freaking out that I wouldn’t have enough time to do it. I ended up scrapping a couple hours of programming and just making the villagers random walk. I was getting pretty tired of programming at this point, so I took a break and worked on art most of the night.

First I came up with a palette I liked in ArtRage:

Screen Shot 2013-11-02 at 6.27.41 PM

It’s really fun using to the palette brush to mush around the colors. Next time I’m going to add a few more shades, I think, this was just too difficult to work with.

I used the palette to implement a bunch of pixel art in Sprite Something (which is a fantastic sprite editor for iOS, by the way).

The grass took hours longer than everything else (even the animations) and ended up looking more like tentacles than I really wanted.
I’m not sure why, but the grass took hours longer than everything else (even the animations). It also ended up looking more like tentacles than I really wanted.

lava

charred

throwing-village

I was pretty happy with this tree, but then I found out it was almost invisible against the grass.
I was pretty happy with this tree, but then I found out it was almost invisible against the grass.

Saturday night I started plugging the art into to the actual game:

Screen Shot 2013-11-02 at 10.14.22 PM

Sunday was mostly getting the animations to do the right thing. I had to slow them down, make the water throwing not repeat endlessly, and set up this nice chain of events:

villager-animation

It involves:

  • The throw animation above.
  • Fading out the lava to reveal the “cooled” surface.
  • Lifting and fading out the cloud of steam.
  • Once the throw animation is complete, the villager can walk away.

And the villagers have to be facing the right direction, which there are still some bugs with on the walking.

Deploying was as annoying as always, but around 4pm Sunday everything was set to go and I tweeted my entry to the organizer.

All in all, it was a lot of fun! It went a lot smoother than the last game jam did and, although there are about 50 things I wish I’d had time to add (ranged weapons, fog of war, lava lamps), I’m pretty happy with how it came out. Theoretically I could have worked on it for 6 more hours than I did, but I was pretty happy with it and tired.

Please give my game a try and let me know what you think!