Students
Students get a Tuts+ subscription for just $45! Hurry limited offer.
Advertisement

How to Match Puzzle Shapes Using Bitmasks

by

In this tutorial, I will walk you through how to analyze a board of tiles, iterate through them, and find matches. We will be creating a game where you need to connect lines together to form completely closed paths with no open ends. In order to simplify things, we will use bitmasking as part of our algorithm by assigning each tile (plus its rotation) its very own bitmask number. Don't worry if you don't know what bitmasking is. It's actually very simple!


Play the Demo

I will be creating the project in C# using Unity with the Futile framework, but the code will be applicable to pretty much any 2D framework with few changes. Here is the Github repo with the entire Unity project. And below is a playable demo of the game we'll be making:


Click the arrows to slide rows and columns. Try to make closed shapes.

Going Beyond Match-3

When I started creating Polymer, I wanted to create something other than a match-3 game. My internal nickname for it was a "match-any" game. Match-3 puzzle games are everywhere. While they can certainly be fun, one reason they are so common may be because the algorithm to find a match of three tiles is rather simple.

I wanted to be able to match multiple tiles that could weave in and out of rows and columns, snaking their way across the board. Not only that, but I didn't want a simple color-matching game. I wanted the matches to be based on specific sides of the tiles (for example, one shape could only connect to other shapes on the left and right sides, but not the top and bottom.) This turned out to be much more complex than just a normal match-3 algorithm.

This tutorial will be split up into three sections: The Tile, The Match Group, and The Game Board. In this tutorial, I will try to avoid as much Futile-specific code as possible. If you want to see the Futile-specific stuff, look at the source code. Also, I am not going to show every method and variable in this post. Just the most important ones. So if you think something is missing, again, look at the source code.

What Is a Bitmask?

The word 'bitmask' refers to the way you can store a series of true/false values in a single numeric variable. Because numbers are represented by ones and zeros when represented in binary, by changing the number you can switch on or off values by toggling whether a bit is 1 or 0.

For more detail, please see this article on bitwise operators and this article on binary numbers.


The Tile

Our first class is called LineTile. Before the beginning of the class, let's define each kind of tile.

Here's what the pieces look like:

thePieces

Next, since we will only allow rotations of 90 degrees, let's make an enum for rotation.

Next is a struct called TileIndex, which is basically the same as a Vector2, except with ints instead of floats. It will be used to keep track of where a tile is in the game board.

Finally, let's define the three types of connections between two tiles.

Next, within the class itself, define a bitmask to each side of a generic tile.

tileBitmask

Then define the instance variables each tile will have.

For the constructor, create the sprite and set it up at the correct rotation. There is some Futile-specific code in here but it should be very easy to understand.

Now, one of the most important parts. We assign each tile, combined with its rotation, a bitmask that is determined by which of its sides are solid and which are open.

allPieces

Our tiles are set up and we're ready to start matching them together!


The Match Group

Match groups are just that: groups of tiles that match (or don't). You can start on any tile in a match group and reach any other tile through its connections. All its tiles are connected. Each of the different colors indicates a different match group. The only one that is completed is the blue one in the center—it has no invalid connections.

matchGroups

The match group class itself is actually extremely simple. It's basically just a collection of tiles with a few helper functions. Here it is:


The Game

This is by far the most complicated part of this process. We have to analyze the entire board, splitting it up into its individual match groups, then determine which, if any, are completely closed. I'm going to call this class BitmaskPuzzleGame, since it's the main class that encompasses the game logic.

Before we get into its implementation though, let's define a couple things. First is a simple enum that the arrows will be assigned based one which direction they are facing:

Next is a struct that will be sent from an arrow that gets pressed so we can determine where it is in the board and which direction it's facing:

Next, within the class, define the instance variables we need:

Here is a function that takes a tile and returns all of its surrounding tiles (the ones above, below, to the left, and to the right of it):

Now two methods that return all the tiles in either a column or row so we can shift them:

Now two functions that will actually shift a column or row of tiles in a specific direction. When a tile shifts off an edge, it loops around to the other side. For example, a right-shift on a row of Nub, Cross, Line will result in a row of Line, Nub, Cross.

When we click an arrow (i.e. when the arrow button is released), we need to determine which row or column to shift, and in which direction.

The next two methods are the most important ones in the game. The first one takes two tiles and determines what kind of connection they have. It bases the connection on the first tile input into the method (called baseTile). This is an important distinction. The baseTile could have a ValidWithOpenSide connection with the otherTile, but if you input them in the reverse order, it could return Invalid.

matchExplainer

Finally, UpdateMatches. This is the most important method of all. This is the one that goes through the board, analyzes all the pieces, determines which connect to each other, and which match groups are completely closed. Everything is explained in the comments.

All we have left is the HandleUpdate function! Every frame, update the match groups if they need updating (i.e. matchGroupsAreDirty == true), and set their colors.

Here's what the algorithm would look like if every step were animated:

boardAnimation

And that's it! While some of the code in this is specific to Futile, it should be pretty clear how to extend it to any other language or engine. And to reiterate, there's a lot of non-essential stuff missing in this post. Please look at the source code to see how it all works together!

Advertisement