Building a Procedurally Generated Platformer

ProceduralGeneratedPlatformerRecently, I’ve been playing around with a “procedurally generated endless runner” game concept in Unity. It’s really meant to be a set piece for Knox Game Design–a  multiplayer game that we can show off that’s both quick to play and has a lot of replay value. Here’s an explanation of how I accomplished that procedural generation.

First, it’s important to note that “procedural generation” is a general category of technique. There are many ways of doing (or, to put it another way: algorithms for) procedural generation–literally, it just means you’re using a procedure to generate some element of the game. It’s sort of like saying you’re using math to solve a problem (Algebra? Geometry? Calculus? Statistics?) or painting (Oil? Acrylic? Watercolor? What style?).

In my case, I’m building out a platformer. I don’t need a perfect algorithm that generates complex levels that calculates specific paths–just something that lets the player stretch their legs a bit, and gradually throw more traps at them, until survivability is basically impossible. It’s basically meta-level-design: designing the process for designing a level that gives the player a particular experience.

To do this, I start with the basic unit, which I call a chunk. In my game, a LevelChunk is 20 tiles wide by 50 tiles high. (That allows for some variability, but it’s also small enough to generate and instantiate quickly.) Each tile can be empty, a floor piece, a platform, or one of various types of traps. Chunks are created when a player enters the next-to-the-last chunk and destroyed once the player is well past them.

A chunk begins its life as a blank grid that knows the previous chunk’s floor height. (If it’s the first chunk, we randomly pick a floor height that’s not too close to the top of the grid.) In this example, we’ll use a 10×10 grid, with a starting floor height of 4:

ProceduralGeneratedPlatformerBlog0Our first task is to build the chunk’s floor.

To do that, we break up the floor into sections with random lengths. I limited floor sections to being 1-10 tiles wide (or 1-6 tiles wide if it’s a pit).

For each floor section, we generate a possible length (1-10). If it’s the first or last section in a chunk, it must be a floor section. Otherwise, there’s a 30% chance of it being a pit.

If it’s a floor section, we generate a floor height. We use the last floor’s height and add a random value from -3 (we don’t want the player to essentially fall out-of-frame) to +3 (we don’t want to create floor sections the player can’t jump on top of). (If this would go below 1, we set the height to 1 instead–we don’t want to inadvertently create a pit).

Once we have this information, we fill in the floor blocks in the grid. Let’s say that our first section generates a floor length of 3, with a height of +1. We’d fill in the first section like this:

ProceduralGeneratedPlatformerBlog1

If it’s a pit, we regenerate the length (1-6) and skip ahead that many tiles.

Let’s say our second section is a pit of length 2, followed by another section of length 4 and height -2:

ProceduralGeneratedPlatformerBlog2

We continue this process until we reach the end of the chunk:

ProceduralGeneratedPlatformerBlog3

This provides us with a pretty basic platformer level: it’s technically playable, but it’s not going to be interesting.

It’s definitely not going to be interesting for four players hopping around, because everyone’s going to be jumping and falling at roughly the same points. What we need to do is let players “pick a path,” so to speak. To avoid complication, we don’t necessarily want to create branching paths; we just want to let players change how they jump and dodge.

To do this, we make another pass through our grid. This time, we go column-by-column and create platforms. There’s a 20% chance that any given column will be the start of a platform.

Once we start a platform, we have to work out its height. To do this, we simply scan down the column until we find the first non-empty tile:

ProceduralGeneratedPlatformerBlog4

Then, we add a platform 2 or 3 tiles above that. (We don’t want platforms to be too close to the ground, but we also want them to be accessible.) Let’s say we created a platform on the 2nd column that is 3 tiles above the ground:

ProceduralGeneratedPlatformerBlog5

As with floor sections, we then generate a random length for the platform. This may not be the actual length–we’re going to apply some checks to ensure that platforms don’t intersect with other floors or platforms, and that there’s always at least one empty row between a platform and whatever’s below it.

Let’s say our first platform is 4 tiles in length:

ProceduralGeneratedPlatformerBlog6

And we can continue until we have a set of platforms:

ProceduralGeneratedPlatformerBlog7

That’s nice, but it could still be more interesting. Again, since we’re not trying to build complex paths, there’s a simple solution: just keep adding another layer of platforms.

Since our platform logic scans a column to find the highest non-empty tile, it will build platforms on top of platforms. So we could add another row:

ProceduralGeneratedPlatformerBlog8

With only 10 rows to work with, we’re hitting a practical limit, but we could continue this process multiple times to fill out a larger grid.

We’re still creating a very linear platforming stage, but the player has a choice of how they approach it. That’s going to be important when we add traps.

I’ll admit all of my traps are really just rip-offs of Super Mario Bros. Flame and cannon traps are from SMB3’s airships. Laser traps are from SMB’s castles. Spike traps are… well, not a direct rip-off, but a stationary object that will kill the player is literally the simplest trap you could add to a platforming game.

The reason we save traps for last is that we’re always going to place them in relation to an existing platform or floor tile. That way, the player is usually interacting with them in some way.

To do this, we’ll scan the entire grid row-by-row and column-by-column. (Note that traps are always a single tile, so we don’t have to consider areas like we did with floor and platform sections.) When we come to a floor or platform tile, we’ll generate a random number that tells us whether to place a trap, and if so, which trap.

I’m actually doing a little bit of extra logic when placing a trap, so these percentages are technically a bit skewed:

  • Flame and cannon traps have to be pointed at at least one empty tile.
  • Laser traps must have at least one empty tile on one side.
  • Spike traps actually get placed above the platform rather than replace it, but only if the tile above the platform is empty.

In short, there’s a lot of ways for a trap not to be placed.

Using these rules we might end up with the following trap placements:

ProceduralGeneratedPlatformerBlog9

And now we have the data that makes up our chunk. (Actually getting this to show up in Unity is a different matter that deserves its own blog post.)

Now, remember how I said we wanted to scale up the difficulty? The last step in the chunk generation process is to ratchet up the chances of each of the traps, and to increase the maximum drop distance when generating floor sections. This generates a bit of tension, as traps become more complicated and the player’s choice of platform starts to matter more and more. (I’ve found that, as I’ve configured the process right now, you’re lucky if you make it past 100 tiles.)

Eventually this will generate a trap that’s impossible to pass, which is actually fine–we want this to be a quick game, so that once a player’s eliminated, they don’t have to wait too long to get back into the action. In this case, our “good enough” algorithm might actually be more helpful in crafting the experience we want the player to have than a “perfect” algorithm that always generated a playable path.

Ludum Dare 35 “Shifty Shapes” Post-Mortem

Here’s a quick rundown of the ups and downs of my compo entry, Shifty Shapes, which was written in Unity. (You can play it on itch.io.)

What went well

Concept

Shifty Shapes

Usually I make some notes about the top themes in each round of voting, but this time I went in cold. (Honestly: I have a few different game ideas floating around in my head right now, so I was open to doing something off-the-cuff.)

Once I decided to go with the “shape” wordplay, I had all of the rules for the game written down within minutes.

The sliding concept was inspired by a board game called Ricochet Robots that I played in analog gaming at Geek Media Expo, plus standard match-3 mechanics which I’d already figured out an algorithm for in Ludum Dare 30.

Animation

I knew I wanted this game to have some nice visual effects, since I envisioned it as one of those shiny mobile puzzle games.

Fortunately, there weren’t a lot of moving pieces in the concept, and I started building the effects early (even before I’d replaced the placeholder art).

Animation is something I don’t tend to think about (or I think about so late in the jam that it’s complicated to implement), but a little bit seems to go a long way.

Bouncing UI elements and blocks/items flying to their respective counts were easy to implement. I feel like my biggest win was making item and score counts only increment when the block/item reached it.

Music

The main riff was based on something I’ve played around with before on guitar–variants of C, with Am and Em thrown in, followed by a quick “bridge.” It worked pretty well, which means I spent about 10 minutes working out the tune, leaving most of Sunday for recording and mixing.

Unity UI

Because I wanted new blocks to fill in like a circular progress bar, I ended up having to mess with Unity UI early (as it supports “filled” images). I’ll confess, it’s something I’ve avoided for the longest time, because it’s intimidating.

Rather than mess around with the large block of numbers that don’t seem to change anything (Unity just recalculates the X and Y positions when you change them), I’ve preferred to stick to world space, Camera.orthographicSize and Camera.aspect, 2D Toolkit, etc.

However, I feel like I’ve made serious progress learning Unity UI thanks to this game. And because I didn’t need to dip into 2D Toolkit for text, I think this is the first Ludum Dare where I’ve had no Asset Store dependencies.

Coding

There are few things more satisfying as a coder than being able to call a “Reset” method after a Game Over screen (as opposed to “screw it, I’ll just reload the scene”).

What didn’t go well

Block pop-in effect

One of my big plans for visual effects was to have blocks “fill in” like a pie chart. That’s actually pretty complicated if you’re using Unity’s Sprites, and I spent more time than I’d like trying to make it work. Once I realized sprite masking was going to require shader code, I gave up on this approach.

Even though I was reluctant to mess with Unity UI, UI Image supported this exact feature, and I got the effect I wanted. However, I wish there was a way to do this via Sprites, and I spent more time than I’d have liked chasing that solution. (Although, I did do this first thing on Friday night so I could budget my time.)

Graphics

I’ve been playing around with Krita recently, and because of some of its pen and paint effects, I initially picked it over GIMP. However, the art I created didn’t feel right–it had a dark, hard-contrast feel.

This wasn’t Krita’s fault, I just wasn’t familiar with it. It was definitely a case of thinking a tool based more on physical mediums would magically produce something “painterly” without me having to understand how it worked. I ended up redoing everything (except the cloud particles) in GIMP, and was pretty satisfied with the result, despite spending a lot of extra time on unused art assets.

Music

Because I guess I have something to prove, I decided to try to mix in cajon, banjo, and mandolin in with guitar. I can’t tell whether it works or whether it’s all out of tune, because my first impression changes each time I listen to it.

I suspect part of the problem is I changed the speed on the guitar part in Audacity, and then tried to increase the pitch by the same percentage to compensate. Also, I’m not enough of a musician to pull this sort of thing off with consistent quality (which is why you’ll note all of the non-guitar tracks are mixed very low and silenced in places).

Build and release

To be fair, it went OK, but this is the first time I’ve been frustrated with myself for not planning in advance.

I always go in building for the default Unity 960×600, only to remember on Sunday afternoon that it’s slightly too large for the LD site’s embed (and even a little awkward in the browser alone). I really need to standardize on a resolution and aspect ratio before I go into a jam. I tend to just jump in the preview window and forget about this part.

Also, given that WebGL builds seem to take somewhat longer than Unity plugin builds did, I need to start planning for this in advance. Luckily, I did a release to itch.io on Saturday, so I was able to iron out some WebGL issues with particle effect sprites early, but it would’ve been stressful if I had waited until Sunday.

2D Platforming Mechanics in Unity

Building a platformer has been something of a holy grail for me since I first started tinkering with Unity. I grew up playing NES games like Super Mario Bros., so in some ways platformers are what I think of when I think of video games.

It’s not hard to find third-party utilities to help with this, depending on what level of functionality you want and what price you’re willing to pay.

Eventually, however, you’re going to have to bite the bullet and learn what’s going on inside of the black box. Either your third-party script’s settings are just plain confusing, or you want it to interact with the world in a way it doesn’t intend. (For me, it was trying to build Castlevania II-style stairs.) Even if you don’t roll your own, digging into the guts of a platforming script isn’t exactly straightforward.

The Basics

A basic platformer is going to have three mutually exclusive states at a minimum: Grounded, Jumping, and Falling.

unity-platforming-jumping-statesGrounded is what the user perceives as the “default” state. In reality, it’s the state that the character is in only when its lower edge is colliding with a surface. Typically, a player can only jump when they’re in a grounded state (or, in the case of double jumping, the jump limit would be reset as soon as the character is grounded again).

Jumping is the state where a character is moving upwards into the air. It’s an active state–that is, it’s usually triggered by player or AI intervention, not simply interaction with environment like Grounded or Falling. It’s also a temporary, limited state which ends when a maximum height is reached or a timer is up.

Jumping can also end abruptly due to collision. If the character hits their head–that is, their upper edge collides with a surface, the opposite of the check done for grounded–it’s naturally expected that the player immediately start falling.

In games where the player has more control over their character, jumping can end early if the player releases the jump button. This allows for both quick, short jumps and long, floatier jumps.

Falling is actually the character’s “default” state–when they’re neither in a jump nor colliding with the ground. When falling, the character is affected by gravity. Falling ends when the character becomes grounded again, based on collisions with their lower edge.

Thinking in frames

While it may not seem obvious, there are only a few possible state transitions in a typical platformer. You can’t go directly from Jumping to Grounded without encountering a case that would trigger Falling. You can’t go from Falling to Jumping without first encountering a case that would trigger Grounded. Because you can rule out certain state transitions, you can simplify your logic.

I say this isn’t obvious because I’ve never been a hardcore twitch-gamer who can pick out specific frames of animation. To me, playing a Mario Bros. game is a smooth experience–I take in the “big picture,” so to speak. In reality, it’s a series of very tiny moments where the computer is performing very tiny updates and then making decisions based upon them.

This is tricky because it’s easy to work out a “good enough” platformer controller that fails in odd situations if you don’t consider this frame-to-frame precision. For example, 99% of the time the character might behave correctly–but if you end up off by just a fraction, you’ll get weird behaviors. Precision is possible–you just have to figure out how to make it work. One tip is to be aware of Unity’s lifecycle.

Testing for state changes

So how do we detect when the player changes states?

As a Unity newbie, my first attempted solution was to detect collisions with the ground or other platforms using colliders. This isn’t a bad instinct. Colliders take the hard work out of hit detection by turning them into events. You don’t have to constantly check for a state–you simply need to respond to enter, stay, and exit events.

unity-platforming-colliderFor detecting Grounded/Falling states, this can actually be a pain. Each collision is handled as a discrete event, so you don’t know if that OnCollisionExit event means you’re actually grounded or not because that collider doesn’t know whether other colliders are triggering OnCollisionStay and OnCollisionEnter events. Technically, it should be possible to track this, but that’s a lot of bookkeeping, and it’s highly dependent upon the order the events are called in (relative to the Unity lifecycle).

Not to mention that it’s hard to get an accurate picture of which direction a collision came from without multiple colliders. That means it’s not easy to differentiate running into a wall (or an enemy) from hitting the ground. Believe me, I’ve tried testing the collision relative velocity, and I’ve never felt like I could rule out all the false positives.

Raycasting

Unity has various physics casting functions (some which, I suppose, aren’t technically raycasting) that all do variants of the same thing: they test a specified area for colliders.

unity-platforming-raycastpointsCurrently, I tend to lean on Physics2D.OverlapCircleAll, which returns all colliders within a given radius of a point. It returns a set of Collider2D objects which can be used to determine whether any ground layers are hit.

I attach a couple of empty GameObjects as test points, which I then pass into my controller script. For example, in the screenshot here I use two ground and one head (highlighted with red and green icons respectively). Add as many as you need based on the size of your cast area–you want to avoid any case where a character could technically be over a walkable object without returning a raycast hit.

In my last Ludum Dare game, I used something like this:

var colliders = Physics2D.OverlapCircleAll(transform.position, 0.1f,
     LayerMask.GetMask("Terrain"));
// Test colliders to see if there are any ground objects

You call this each Update or FixedUpdate, depending on how you’re adjusting your physics. Test for grounded (or whether a character hits their head in a jump) before you do anything else, because it’s going to determine what state transitions you allow, what movement you apply to the character, and what you allow the player or AI to do. (That is, the character must react to the environment before they can react to the player or AI’s input.)

Let me give a disclaimer: I really need to work out a better approach. I suspect there’s some issues with my circular cast not lining up perfectly with my character’s box collider, and there’s probably a more performant approach than returning all collisions. Still, this should be a good starting point, although I encourage you to try out some of the other methods in Physics2D (or Physics, if you’re using 3D colliders) that may work better for your particular setup.

Admittedly, tinkering is difficult. This stuff is happening at such small intervals, sometimes at varied points in the Unity lifecycle (Update vs. FixedUpdate vs. LateUpdate vs. coroutines). And you can’t easily visualize it without writing your own editor gizmo code. As a newbie, I’ve found there’s a certain level of blind trust (sometimes misplaced) involved.

This is also a case where setting up your physics layers matters: if you do it right, you should minimize the amount of “testing” you have to do with the results.

Note that while I’m using raycasting to determine the player’s overall state, I’m also relying heavily on Unity’s physics and hit detection to handle movement. There’s still a collider on my player character and it still blocks movement when it comes into contact with something.

I use OverlapCircle because I don’t really care how far the character is from the ground, only that it’s near enough to a surface to register as touching. If I didn’t have a collider attached to the character, I’d want to know exactly how far the closest ground object was so that I could adjust falling speed so as not to overshoot.

Speaking of which, that brings us to…

Movement

There are a couple of ways you can handle movement in Unity. For the most part, you should technically be able to get similar results with any of these, assuming you can figure out how.

The approach you take determines how much of Unity’s built-in features you can use (versus how much you have to write yourself) and what mode you’ll have to think in.

You can set an object’s transform position directly. This is sort of a brute-force approach. Triggers and colliders will still fire, but you don’t have the benefit of continuous collision mode, unless you code it yourself. In mathematical terms, this means you have to think about position at a given time, or f(x). (Realistically, you’ll probably be working out speed/velocity, or f'(x), and applying it.)

You can set a Rigidbody’s velocity directly. This is my preferred approach, because it means I don’t have to think too much about physics, but I still get the benefit of the physics system adjusting for collisions. In mathematical terms, this means you’re only working with the player’s velocity at a given time, or f'(x).

Typically, I set Rigidbody velocity in FixedUpdate as long as there’s a change in velocity required from the last FixedUpdate call. I set drag and gravity scale to 0, because I don’t want anything else tinkering with velocity if I can help it. Because Unity velocity represents units per second, it’s possible to use Time.fixedDeltaTime to work out just what velocity needs to be.

Note that one reason I like using Unity’s built-in physics and hit detection is I have to think less about exact collision positions. I’ve seen platformer controllers that don’t require colliders, but that means you have to think about not just the character’s current speed, but the distance to the nearest object. This isn’t impossible, but it’s an extra layer of complexity I’d prefer to get into only if necessary.

You can apply force to a Rigidbody. This takes full advantage of Unity’s physics, but it requires a little more work. You’re not only going to have to determine what force you will apply, but you’ll have to tweak the object’s gravity scale, mass, and drag to get it feeling right. In mathematical terms, you’re indirectly working with acceleration, or f”(x).

I’d avoid this on the player character, because you want those controls to feel tight, which is harder to figure out with several degrees of separation between your code and the character’s actual movement speed.

In a later post, I’ll get into more of the math behind movement, since that’s the difference between a clunky game and a smooth one. (I will say that I find Microsoft Mathematics incredibly useful for this sort of thing, since you can easily plot changes in speed or position over time.)

Writing a Match-3 game in Unity

Dr. Mario (source: Wikipedia)

Dr. Mario (source: Wikipedia)

This year in SeishunCon‘s digital gaming room, I was reintroduced to the match-3 game. I’d played Dr. Mario when I was younger, but more competitive games like Magical DropBust-A-Move, and Tokimeki Memorial Taisen Puzzle-Dama were something very different.

Ultimately, I realized just how many more-or-less neutral decisions are involved in making a match-3 game.

During this year’s Ludum Dare, I decided to jump in head-first. I did a bit of a warm-up the week before, trying to build a Tetris-style algorithm that detected and cleared out lines. This tutorial from Unity Plus was a huge help. Of course, the Tetris matching algorithm–a complete row of tiles–is much simpler than an algorithm that picks out irregularly shaped patches of matching tiles.

If you want to see all of these code samples in context, check out my Ludum Dare 30 repo.

Two worlds

Magical Drop 3 (source: Kazuya_UK)

Magical Drop 3 (source: Kazuya_UK)

The trickiest part of building a puzzle game in Unity is that the game itself doesn’t live in world space. Not fully, anyway.

This isn’t as true in other genres. Platformers, for example, live almost exclusively in the Unity game world. The player’s Transform tells you its location. Colliders (or, in some cases, raycasts) tell you when the player is on the ground, hitting the ceiling, or colliding with an enemy. Even if you aren’t using in-game physics, you’re probably adding force or setting velocity on a Rigidbody so that you get collision detection for free.

Not so with a puzzle game. If your game involves clicking, you might get some coordinates in world space, but you’re probably going to convert that to a cell in a grid that lives entirely in code. There’s a good reason for that–it’s far easier to write the logic for scoring a game like Tetris or Dr. Mario when you’re thinking about blocks or tiles, not individual pixels.

I'm pretty sure this is not how Tetris is supposed to work.

I’m pretty sure Tetris blocks are not supposed to stick to the side of the board.

My warm-up actually tried to live in world space as much as possible. It used physics to determine when a tile had landed, and only transferred data back to a two-dimensional array to detect row completion. That seemed safer–what happens in the game world is real, after all. It’s what the player sees, so if you store your data there, there’s no fear of getting out of sync, right?

I was wrong. No matter how I tweaked it, it never did work right.

The Unity Plus tutorial I linked above was a huge help. If nothing else, it allowed me to trust that moving my logic fully out of the game world and into an abstract data structure was a valid approach. If you haven’t already, go back and at least skim it, because I intend this post to be an extension from Tetris logic into match-3 logic.

Converting from board to world space

Once I figured out this transition was manageable, this part was easy. I created a GameTile class that tracked the color, row, and column of the tile, and updated the tile’s position based on that. Here’s an abridged version:

public class GameTile : MonoBehaviour {

 private Transform _t;
 private SpriteRenderer _s;

 [System.NonSerialized]
 public int TileColor;

 [System.NonSerialized]
 public int Row;

 [System.NonSerialized]
 public int Column;
 
 void Awake () {
   _t = GetComponent<Transform>();
   _s = GetComponent<SpriteRenderer>();
 }

 Vector3 tmpPos;
 public void UpdatePosition()
 {
   tmpPos = _t.position;
   tmpPos.x = (Column * Board.TileSize) - Board.WorldOffset;
   tmpPos.y = (Row * Board.TileSize) - Board.WorldOffset;
   _t.position = tmpPos;
 
   _s.sprite = Board.Current.Textures[TileColor];
 }
Tiles in a grid

Tiles in a grid

Note that, in this case, TileSize is a constant that represents the size of a tile in Unity units. I’m using 64×64 pixel tiles, and the sprite size in unity is 100 pixels per unit, so TileSize works out to 0.64. I’m also using a constant offset so that the middle of the 7×7 board is at 0,0 world space, and the lower-left corner is tile 0, 0 in game space.

I also created an array that represents the gameboard as a static field in a class called Board. (Board started off as a static class and became a singleton because I needed to set some values in-editor, so it’s clumsily straddling the worlds of game object and static class.)

 public const float TileSize = 0.64f;
 public const float WorldOffset = 1.92f;

 public const int BoardSize = 7;
 public static GameTile[,] Tiles = new GameTile[BoardSize, BoardSize];

While the Unity Plus tutorial used a two-dimensional array of integers, I decided to store references to my GameTile objects in this array. This allowed me to pass data to and from tiles directly and (as we’ll see later) made tile-clearing and animation generally easier.

Whenever I made a change to board state, it meant that I could simply loop through the board array and tell each tile where it was supposed to be:

 public static void UpdateIndexes(bool updatePositions)
 {
   for (int y = 0; y < BoardSize; y++)
   {
     for (int x = 0; x < BoardSize; x++)
     {
       if (Tiles[x,y] != null)
       {
         Tiles[x, y].Row = y;
         Tiles[x, y].Column = x;
         if (updatePositions)
           Tiles[x, y].UpdatePosition();
       }
     }
   }
 }

Note that in every case, we’re always converting from abstract game space into world space. Unity game objects aren’t storing the important game state information directly; they’re always a representation of that state.

… and back again

In my game, there was one case where I needed to convert from world to game space, and that’s when the user clicked an empty space to drop a tile. To do this, I simply created a large collider behind the entire gameboard with this script attached:

 void OnMouseDown()
 {
   if (GameState.Mode == GameState.GameMode.Playing)
   {
     mouseClick = Camera.main.ScreenToWorldPoint(Input.mousePosition);
     mouseX = (int)Mathf.Round ((mouseClick.x + WorldOffset) / TileSize);
     mouseY = (int)Mathf.Round ((mouseClick.y + WorldOffset) / TileSize);
     PutNextTile(mouseX, mouseY);
     Soundboard.PlayDrop();
     GameState.ActionsTaken++;
   }
 }

That’s really all there is to it. Note that it’s basically the reverse of UpdatePosition() above, which converts from game to world space.

Detecting and clearing matches

Clearing matches

Clearing matches

This is the trickiest part. Actually, this is probably why you’re reading this blog post.

Horizontal matching (as in Tetris) is pretty easy–you just need to look for contiguous tiles in the same row. Even allowing horizontal or vertical matches (as in Dr. Mario) is just a variation on this theme. However, trying to track a set of contiguous tiles that can vary horizontally and vertically is going to take some recursion.

Each time we take an action that changes the board, we’ll trigger a check. The first thing we do is copy our entire board array into another array:

 static void CopyBoard(GameTile[,] source, GameTile[,] destination)
 {
   for (int y = 0; y < BoardSize; y++)
   {
     for (int x = 0; x < BoardSize; x++)
     {
       destination[x, y] = source[x, y];
     }
   }
 }

 static bool clearedTiles = false;
 public static void MatchAndClear(GameTile[,] board)
 {
   clearedTiles = false;
   // Make a copy of the board to test
   CopyBoard(board, toTest);

//... continued...

Why? We’ll see later that it makes it much easier to tell which tiles we’ve checked.

We start the process with a brute-force approach. We’ll go cell-by-cell (first rows, then columns), testing each cell. For each test, we’ll reset some variables we use to track our testing, and then call a separate function (which we’ll later use for recursion):

// Continued from MatchAndClear() above...

   currentTile = null;
   collector.Clear ();

   for (int y = 0; y < BoardSize; y++)
   {
     for (int x = 0; x < BoardSize; x++)
     {
        TestTile (x, y);

// Continued later...

Let’s take a look at that TestTile function:

 static void TestTile(int x, int y)
 {
   // Tile already tested; skip
   if (toTest[x,y] == null)
   {
     return;
   }
   // Start testing a block
   if (currentTile == null)
   {
     currentTile = toTest[x, y];
     toTest[x, y] = null;
     collector.Add(currentTile);
   }

// ** Skipped lines--we'll come back to these later **

 // If we're processing this tile, test all tiles around it
   if (x > 0)
     TestTile(x - 1, y);
   if (y > 0)
     TestTile(x, y - 1);
   if (x < Board.BoardSize - 1)
     TestTile(x + 1, y);
   if (y < Board.BoardSize - 1)
     TestTile(x, y + 1);
 }

If this function finds that the cell is null, then we skip it. A null cell means that it’s either empty, or we’ve already tested it. (That’s why we copied it into a separate array–we can manipulate the new array at will.).

If the cell has a value, though, we’ll do a few things. First, we’ll remember it as our “current” cell–the one at the top of the chain of recursion. Then, we’ll remove it from our copy of the gameboard so that we don’t test it twice. We’ll also add it to a List so we can remember how many contiguous tiles of the same color we’ve found.

There’s two other conditions we might run into later in the recursion, but we’ll talk about them later. Once we’ve tested a cell, we’ll then grab the four cells around them an run them through the same test.

The “current” cell is now set, indicating this isn’t our first level of recursion. On these function calls, we now have three possibilities for each cell.

First, the cell could be null, which again means we’ve already tested it or it’s empty. Again, we’ll do nothing if that’s the case.

Second, the cell could not match the “current” cell. In that case, we don’t consider it “tested.” Our recursion tests for a single set of contiguous tiles of a single color. Just because this tile isn’t part of the current set doesn’t mean it’s not part of a different one.

// From TestTile() above... 

 // Tile doesn't match; skip
 else if (currentTile.TileColor != toTest[x, y].TileColor)
 {
   return;
 }

Third, the cell could be the same color as our “current” cell. If that’s the case, it’s been “tested,” so we’ll set it to null in our copy of the board. We’ll also add it to that List we use as an accumulator. This is one of the conditions we skipped in the example above:

// From TestTile() above... 

 // Tile matches
 else
 {
   collector.Add(toTest[x, y]);
   toTest[x, y] = null;
 }

The function will continue recursing until it’s exhausted all options, either by hitting an empty cell or the edge of the board. At that point, we return to the main “brute force” loop to handle our results.

If our accumulator has more than three tiles, then this was a successful match. If not, then we’ve tested one or two tiles, but we don’t need to take action:

// Continued from MatchAndClear() above...

       if (collector.Count >= 3)
       {
         foreach (GameTile tile in collector)
         {
           ClearTile(tile.Column, tile.Row);
           clearedTiles = true;
           Soundboard.PlayClear();
         }
       }
       currentTile = null;
       collector.Clear ();
     }
   }

   if (clearedTiles)
   {
     SettleBlocks(board)
   }
 }

Here, as we’ll discuss later, I’m simply triggering some animations. The simplest approach, though, is to loop through our accumulator and call DestroyObject on each matching tile’s game object. That kills two birds with one stone: the in-game objects are gone, and the cells in our board state are set to null.

Dropping tiles

Dropping a tile

Dropping a tile

Certain changes–dropping a tile or clearing tiles, in this case–can leave unsupported tiles which must be resolved (if those are the rules of our puzzle game, of course). This is actually a really simple algorithm.

We’ll go column-by-column this time, then row-by-row. The order is important here.

In each column, we’ll work our way up from the bottom until we find an empty cell. Then, we’ll make a note of that cell. The next time we find a tile, we’ll simply shift it down to that location and add one to our “empty cell” index:

 static int? firstEmpty;
 public static void SettleBlocks(GameTile[,] board)
 {
   for (int x = 0; x < BoardSize; x++)
   {
     firstEmpty = null;
     for (int y = 0; y < BoardSize; y++)
     {
       if (board[x, y] == null && !firstEmpty.HasValue)
       {
         firstEmpty = y;
       }
       else if (firstEmpty.HasValue && board[x, y] != null)
       {
         board[x, firstEmpty.Value] = board[x, y];
         board[x, y] = null;
         firstEmpty++;
       }
     }
   }
   UpdateIndexes(false);
 }

When you’re done, don’t forget to call your matching function again. It’s entirely likely that dropping tiles has created some empty rows.

In fact, if we were scoring points, this would make it easy to award combo bonuses or multipliers. All of these repetitions of dropping and clearing blocks are just recursions of that first call that was triggered by a player action. We could tell both how many total matches resulted from a player action, and how many levels of “chaining” were required for each action.

Animations

This is a working game, but it’s not intuitive, primarily because we have no animations. Tiles disappear, then reappear on lower rows. It’s hard to figure out what’s really going on unless you’re watching closely.

This is tricky to do. Game objects are always a representation of game state, so our tiles are always laid out on a grid. Tiles are always in one space or another; so a tile might be in row 1 or row 2, but it’s never in row 1.5.

What’s the trick? We should never be manipulating the game board and animating at the same time. Think about how Tetris or Dr. Mario work–you don’t drop the next tile until everything has had a chance to settle. This gives a brief reprieve for the player, but it also ensure we don’t have any weird race conditions or interactions.

As an aside, I recommend creating a “game state” enumeration whenever you start a new project. I’ve never written a game where I didn’t need to know whether the game was in play, paused, showing a menu, in dialogue… I could go on. Best to plan for it early–that way you can ensure that every line of code you write tests that it should be running in this state.

Admittedly, my implementation is kludgy, but here’s the basic idea–when we clear or drop a tile, we trigger a state change. Each GameTile object knows how to handle this state change, and (more importantly) it knows when to tell the gameboard that it’s finished with its animation:

 void Update () {
   if (GameState.Mode == GameState.GameMode.Falling && Row != LastRow)
   {
     targetY = (Row * Board.TileSize) - Board.WorldOffset;

     tmpPos = _t.position;
     tmpPos.y -= FallSpeed * Time.deltaTime;
     if (tmpPos.y <= targetY)
     {
       Board.fallingBlocks.Remove(this);
       UpdatePosition();
       Soundboard.PlayDrop();
     }
   }
 }

When a clear animation finishes, the game needs to check if it should be dropping tiles:

 private static float timer;
 private const float DisappearTimer = 0.667f;
 void Update()
 {
   if (GameState.Mode == GameState.GameMode.Disappearing)
   {
     timer -= Time.deltaTime;
     if (timer <= 0)
     {
       GameState.Mode = GameState.GameMode.Playing;
       SettleBlocks(Tiles);
     }
   }

When the drop animation finishes, it needs to check for matches:

   if (GameState.Mode == GameState.GameMode.Falling && fallingBlocks.Count == 0)
   {
     GameState.Mode = GameState.GameMode.Playing;
     MatchAndClear(Tiles);
   }
 }

This cycle repeats until we finally don’t have any more matches, and then the game can go back to doing its thing.