The Algorithm

The following article is part of a series.  For more articles in this series, see Cloning the Game 2048 in Ruby.  For the complete and final code, see the gist.

Before we can really start laying down some code, we need to know how we're going to be working with our data. I went through a few iterations of this (including one failed iteration I'll outline below), and there are definitely easy ways and hard ways to do this.

If your data is structured in the wrong way, it just makes everything hard.


The Rules of The Game

The game of 2048 is very simple, play with it for 30 seconds and you know everything you need to know. But to recreate it ourselves, we need to lay out the rules of the game formally.

  • All tiles slide past empty spaces. If you move the puzzle to the left, all empty spaces will end up on the right.
  • After sliding to collapse empty spaces, any tiles with the same value combine and the remainder of the row or column slides to fill in the hole.
  • After every move, find an empty tile and give it the value of 2 or 4.
  • If there are no moves to make, it's game over.

By sticking to these few simple rules, the game of 2048 won't be too difficult. There is one subtlety though, which is what caught me on my first attempt.

Doing Everything At Once (and Doing it Wrong)

When trying to think of the simplest way to do something, I often try "unified" rules.

I tried to summarize the entire game of 2048 in a single rule and recursively apply it until no more moves could be made. For example, give the row 4,4,_,8 and wanting to slide to the left, the result should be 8,8,_,_. My first attempt read something like this:

  • Find all blank tiles with something other than a blank tile to the right of it. Slide everything to fit.
  • Find all adjacent tiles with the same value. Combine them, leaving the tile on the right blank.
  • Repeat the previous two steps until there are no more moves to make.

At first, this appeared to work. I didn't play the game much after completing the project, and it wasn't until after I posted the code that I realized my mistake. The test case above? Instead of 8,8,_,_, it came up with 16,_,_,_, making the game virtually impossible to play correctly. While the real solution wasn't much harder or much more complex, it isn't as simply stated.

Another mistake I made was to make separate code for sliding the puzzle horizontally or vertically. This doubled the code required to make it all work, and doubled the amount of work I had to do to write it. This is also something I fixed in the final version. If you're curious to see the failed version, you can see the gist here.

Doing it Right

In order to do this right, you have to prevent tiles from combining more than once. And to do that, the algorithm has to track the state of the tiles somehow. I've seen some other implementations that perform a more generalized algorithm like my failed algorithm but add a "combined" flag to every tile. I wanted to keep the tiles to plain integers only, so the state tracking had to be done in the algorithm itself.

My solution was to have a "pointer" that swept left to right. By never combining anything to the left of the pointer, tiles can never be combined more than once. This pointer is just the column indices of the puzzle excluding the rightmost column (since there's nothing to the right of the puzzle to combine with those, don't bother iterating over them). We also do something similar when collapsing empty tiles, but that's done as a separate step.

For example, given our test case of 4,4,_,8, it goes like this. The empty tile pointer moves left to right. It goes to each 4, then stops on the empty space. It will move all tiles to the right of the pointer left one space, making new empty tiles on the right of the row. So after the empty tile pointer is finished, we end up with 4,4,8,_.

Next, the combiner pointer starts at the left.

If the tile to the right is of the same value, it doubles the value of the tile under the pointer and moves everything to the right of the matching tile (in our case, everything to the right of the second four) to the left, creating new empty tiles if needed. After this first iteration, our row now looks like 8,8,_,_ and we're at the point where the first attempt failed. However, since the pointer keeps track of which rows can combine, and after the first iteration is moves onto the second column (the second 8 in this row), it can no longer combine all the way to the left.

The Code

While future articles will further explain the successful code, you can see it here on this gist.

There's more!  To keep reading, see the next article in this series: Two Dimensional Arrays in Ruby.