GD50 Lecture 04 - Match 3

Posted on March 09, 2018 by Abhirath Mahipal
Tags  game-developmentnotes

This is a part of a series of notes. You can find notes to other lectures here Please feel free to bring to my attention mistakes, other interesting resources and feedback via the comments section. I’m all ears and will do my best to incorporate them into the blog post.


Game Description

Grid of small objects that you should group into collections of 3 or more. The score is directly proportional to the number of objects you get together. Whenever you match similar object together they disappear and are replaced by more objects. Bejeweled and Candy Crush are some Match style games that you probably are aware of.

timer0 “The Simple Way”

How would you implement a simple timer (1 2 3 and so on)?
Some variable that you keep modifying by adding DT (time between each frame). You could also simply display it on the screen as well.

main.lua => Variables currentSecond and secondTimer are declared. secondTimer stores the time progression since the last tick and is reset once it crosses 1. Every time secondTimer is reset, currentSecond is incremented.

Note that we don’t set secondTimer to 0. We instead do secondTimer = secondTimer % 1 so that if secondTimer is a little above a second, it keeps that value. The excess value reduces the span of the next tick (Check this out for more details). Lines 40 - 47 implement the described functionality.

You can expect every DT to be approximately equal to 1/60th of a second as the screen gets updated 60 times a second.

This is a bad way of doing it. It doesn’t scale.

Also keep in mind that Lua doesn’t differentiate between a float and an int. Lua only has one numerical type. So you can use modulo 1 on a float as well.

timer1 “Also The Ugly Way”

5 timers on the screen this time. 5 times the code as the previous example. He mentioned in the last section that it isn’t scalable. He shows it here. Since there are 5 timers he’s used a loop.

timer2 “The Clean Way”

Global time object which manages everything with the power of anonymous functions. Please note that we could use normal functions as well. The task at hand is very trivial and we don’t use it in more than one place. Hence Colton has resorted to anonymous functions.

We use a library called Timer (it’s a part of the knife ecosystem).

-- interval is in seconds
Timer.every(interval, callback)

Timer.after(interval, callback)

Timer.every(interval, callback) is similar to JavaScript’s setInterval. You can specify a function to be executed every x seconds forever. An anonymous function is passed (you can pass in any function, it doesn’t have to be anonymous). The function gets called everytime the interval runs out.

Line 21 - 32 => Declared the intervals and second counters in a table. Iterate over those values and just set a Timer. Notice the nameless function on line number 29.

Notice how the code falls from 98 lines in the earlier example to 70 lines. We can even specify more timers without increasing the lines of code (just add more timers to the table). This is very scalable. It’s declarative as well (just specify how long you want a timer. No additional logic).

Timer.after(interval, callback) does something once after the given interval.

You should checkout this library called Knife. We only use Tween and Timers but this library has a lot more functionality to offer. Checkout slide #15 for a gist of the modules that Knife provides.

Use Cases

  • The title changes colours. A timer is used to change the colour of the letters every 0.75 seconds.
  • Inside the game there is a countdown timer that goes from 60 to 0. User gains more time by making matches and the game ends when the timer touches 0.

Also remember that you have to remove or unset a timer. Timers are global objects, so if they are not needed in the new state or not needed after a certain point, unset them.

Check resources for the links on anonymous functions and first class objects.

tween0 “The Simple Way”

Tweens are used to change values over time. Say opacity from 100 to 0 in x seconds of time or say move an object from this position to that position in 5 seconds.

Colton then shows a screen where he moves a bird from one end to another in 2 seconds. He also points that it doesn’t do the task in exactly 2 seconds (took 2.01, 2.0089 etc). It depends on the specs of the computer. If it can maintain a high frame rate it’ll be more accurate.

Line 19 => The time the bird should take to move to the final position.
Line 31 => The final x position of the tween is set.
Lines 52 - 61 =>
On every frame just increment the position by the proportion of movement to the time elapsed. Just scaling to the ratio of elapsed time to move duration. math.min is used so that it doesn’t cross the end position.

function love.update(dt)
    if timer < MOVE_DURATION then
        timer = timer + dt

        -- math.min ensures we don't go past the end
        -- timer / MOVE_DURATION is a ratio that we effectively just multiply our
        -- X by each turn to make it seem as if we're moving right
        flappyX = math.min(endX, endX * (timer / MOVE_DURATION))

You can assign multiple variables in a single line in Lua (similar to Python), just separate the values with a comma. A, B = 1, 2 for instance sets A to 1 and B to 2.

tween1 “A Better Way”

Lines 29 - 43 => Insert into a table the positions of 1000 bird with x as 0 and a random value for y (so that they scatter across the screen and cover the left hand side in it’s entirety). Also the rate at which it reaches the end is set. Notice that math.random is used twice. It’s used without any argument so that it returns a float. math.random(8) will return an int between 0 and 8, so by adding the additional float we are sure that rate is a float.

Lines 70 - 85 => love.update() same like before. Keeps updating time as long as it is below TIMER_MAX. Scale each bird’s x coordinate by time passed and the duration it should take to reach the end.

Stress Testing:- Enable FPS and go berserk. He tries rendering 10,000 birds and it works pretty fine. He increases the count and tries moving a million birds across the screen. The frame rate drops below 10.

You get a good idea of the limits of your game and the system as well.

tween2 “The Timer.tween Way”

Changing movement and opacity of the birds over time now. Doable using the previous approach but it gets dirty pretty quick.

Line 89 => You can set an opacity for fonts, graphics and images. Recall that you can specify an opacity when you define a colour to be used. Love uses the last colour set. So to modify the opacity of a drawable independent of it’s colour set colour to white i.e (255, 255, 255, desiredOpacity).

Code is very similar to the earlier example. In addition to the rate and x, we also store the starting opacity.

Lines 54 - 59 => We tween each bird in the birds table. Timer.tween() takes bird.rate and the values to tween. We pass in the bird currently being iterated upon and specify the final values as { x = endX, opacity = 255 }, so over the duration of bird.rate it consistently approaches the specified final values. We can pass in classes, tables and even variables to be changed inside Timer.tween().

With just 2-3 more lines of code, we can now tween two variables. This can be extended to tween even more variables with trivial changes.

Use Cases

  • Level text comes from the top to the center of the screen. It’s opacity and positions are tweened.
  • There’s a rectangle with stats. It’s opacity is tweened from 0 till it appears.

Code Run Through

  • StartState.lua Lines 24 - 31 => The colour table of the title text. Every 0.75 seconds the colours are cycled through. If a letter had colour1 it is now rendered with colour2, letters which were rendered with colour6 are now rendered with colour1 and so on. Check lines 44 - 52 for the implementation of the timer. The timer is removed on line 92 as the timer is no longer needed in the BeginGame state.
  • StartState.lua Lines 81 - 94 => If the user chooses to start the game, we tween our transition rectangle (just a rectangle with some text) from 0 to 255 (it means the rectangle was always present, it just wasn’t invisible until we increased it’s opacity). Also notice that we can pass in an anonymous function that is to be executed once Love’s done tweening the transition rectangle.

chain0 “The Simple (and Hard… and Ugly) Way”

Exploring ways to do stuff in succession. Say you want a non playing character to go walk 5 steps in 3 seconds, start a dialog with you, then do xyz. We want a way to reduce code complexity as well. If void of any special constructs, we’d model it using if statements. If the NPC has reached destination, open dialog box, if the dialog has been read, close it and so on. These conditions would be checked on every frame update. You can probably imagine the code getting complex pretty quickly.

Question:- Colton then shows a bird move around the perimeter of a screen. How would you do that?
You would have a bunch of if statements and variables to keep track of goals (top portion traveled along, right portion traveled along and so on).

Additionaly we need to account for time as well. The bird has to move across the screen in some predetermined time.

The code base becomes ugly pretty quickly. Also we now have to carry state (goals, positions etc).

In chain0 a very similar approach is used. Instead of an if else ladder, we use tables. Basically we store information that will help us do the above task in a table. We store the X and Y values that the bird should travel to in order.

Note that we could use a table because the 4 goals were very similar. Had they been different, we would have resorted to an if else ladder.

destinations = {
    [1] = {x = VIRTUAL_WIDTH - flappySprite:getWidth(), y = 0},
    [2] = {x = VIRTUAL_WIDTH - flappySprite:getWidth(), y = VIRTUAL_HEIGHT - flappySprite:getHeight()},
    [3] = {x = 0, y = VIRTUAL_HEIGHT - flappySprite:getHeight()},
    [4] = {x = 0, y = 0}

Chain.lua Lines 66 - 89

  • timer variable to measure time elapsed since the last destination (i.e reaching a point in the table). It is reset to 0 everytime a goal is achieved.
  • Iterate over the table and move the bird to the destination X and Y over time from the base (current X and Y).
  • Line 82 => Every destination coordinate becomes the base for the next goal.
  • Lines 75 & 76 => Update current X and Y coordinates of the bird in parts. Say the bird has to move 100 units in 2 seconds so at the 1st second it should be 50 units from the initial position. This scaling is handled by (destination.x - base.x) * (timer / MOVEMENT_TIME). (destination.x - base.x) gives the distance it has to cover and (timer / MOVEMENT_TIME) gives the ratio considering the time elapsed and the total time it should take.

chain1 “The Better Way”

We can use this approach for any operation including tweens.

Lines 30 - 47 => Use :finish on every tween to define what’s to be executed next. We further pass in tweens as anonymous functions on the completion of a tween.

Passing in a function to another function to be executed on the completion of the calling function (nested callbacks) can at times lead to callback hell (was a very common phenomenon in the JavaScript community).

There are ways to counter callback hell. The Chain construct can take in functions to be executed and will ensure they are executed in order. It’s very declarative and elegant.

The number of lines drop from 96 to 70. It’s also cleaner, promotes a declarative style to define async behaviour and is much more managable.

swap0 “Just a Board”

This update just renders a board and doesn’t actually deal with swapping tiles.

Generate sprite quads for the tiles from an image by evenly dividing the image into pieces like how we did in Breakout. Each block is 32 x 32 units.

3 or more of the same colour is a match. The lecture code doesn’t care about the inscriptions on the tile (cross, ovals etc).

generateBoard() returns a 8 * 8 2D array. It’s similar in spirit to the basic levelmaker of Breakout.

Why table[y][x] and not table[x][y]?
Look closely how the table we construct maps to the actual grid, you will notice that each row of the grid (therefore height) maps to the first index and so on of the our 2D table (table with tables).

It’s important to keep the fact that we index the table for the grid. So for the sake of convinience we do the bookkeeping in this way.

Lines 66 - 84 =>

  • Create a blank table for filling in the rows.
  • Insert into the this blank table an X coordinate, a Y coordinate and a random number that will be used to index into the quads to generate a random tile.
  • Table indices are 1 based but the coordinate system starts from 0. So we subtract one from the table index and then multiply by 32 (the width of a tile is 32). This gives the X and Y coordinate.

Lines 89 - 102 => drawBoard() takes in an X and Y offset and renders the above grid of tiles starting from that offset. It adds this offset to all the X and Y coordinates of the tiles and also uses the associated tile number in the quad table to render the appropriate sprite.

swap1 “The Static Swap”

How to swap two tiles?
Just swap two tiles (like how you interchange the values of two ordinary variables). In the tiles table we just need to swap places. We use a third variable (that acts as a holder) to swap the values. If we don’t use this temporary variable or holder we’ll lose information pertaining to one of the tiles.

In Lua you don’t have to use a temporary variable to swap (recall that you can assign multiple variables values. Eg x, y, z = y, z, x would swap x’s value with y, y’s value with z and z’s value with x).

A rectangle indicates which the tile the user is on. Arrow keys are used to move the marker across tiles. Currently there are no constraints, any tile can be swapped with any other tile.

If you were to implement constraints (only adjacent tiles can be swapped) you’d probably use the code below. If a tile is adjacent (top, down, left or right) it moves by a single step. So the sum of absolute differences between their X’s and Y’s would be 1. If we were to sum the difference of diagonal tiles we would get 2. Think about it and enumerate a few cases on a piece of paper.

-- To check if two tiles are adjacent (top, down, left or right) or not
if math.abs(tile1.x - tile2.x) + math.abs(tile1.y - tile2.y) == 1 then
 -- swap tiles

We now have to check if a tile is highlighted or not (user presses enter on a tile), we store this boolean flag in a variable. If a tile is highlighted we render a semi transparent rectangle over a tile. The rectangle is rounded for aesthetics.

The first time the user presses enter, it highlights a tile with a semi transparent rectangle and he gets another red marker which he can move around to choose another tile. After he places the second marker on another tile and presses enter again, our game swaps the tiles.

Lines 189 - 200 =>

  • We set an opaque red as the colour. We also set a lineWidth of 4. So when shapes are drawn they are thicker than usual.
  • On line 197 we draw a rectangle like usual but we pass in line so that the rectangle is hollow i.e the rectangle just has a border. By using line it uses the lineWidth we set earlier. Additionally we also pass in 4 as the last paramter so that the rectangle is rounded.
  • Always reset the colour after your change it. If you don’t you will have to be extra careful to ensure that it doesn’t render everything in the last set colour. You could also set the colour everytime just before you use it. That works well too.

Lines 58 - 75 => Takes care of input handling. It changes the appropriate tiles on user inputs.

Lines 85 - 101 => This block is entered when the user has highlighted a tile and then presses enter with the marking box on another tile. It just swaps the tiles.

  • Swap the tiles using temporary holders. We also need additional data like gridX and gridY. We’re using temporary holders for them as well. He also mentioned that we swap stuff in the board (lines 94 & 95) before swapping the coordinates and the positions (lines 98 - 101) as it’d give birth to some weird bugs.
  • We also set highlighted to false. The red rectangle (marker) now is set to tile2 (the tile selected by the second marker).
  • It is worth knowing that we could have used simple multiplications (by 32) and additions (the offset) as well to derive stuff from the table indices instead of swapping internal data like coordinates.

swap2 “The Tween Swap”

This update enables tweening the tiles to their new positions instead of instantly swapping them.

It’s a relatively easy to achieve effect. Just tween tile.x to tile2.x, tile.y to tile2.y and tile2.x to tile.x, tile2.y to tile.y. Tween the positions of the tiles to be swapped to the position of the other.

Lines 99 - 102 => Implements the logic described above spread across a duration of 0.2 seconds.

Calculating Matches

Question:- Any ideas on calculating matches?

A student suggested that we could look at adjacent tiles and if they are of the same colour, find the direction and then go recursively deeper in that direction. Colton pointed out that it’s trickier to implement and it’s probably inefficient as well.

Go over each row horizontally first. If consecutive tiles are of the same colour keep incrementing matchNum until the pattern is broken. If matchNum is 3 or more it’s a match. Also if you’re reached the end of the row stop and skip to the next row. You also have to reset matchNum as you’ll be starting across a fresh row.

Do the same thing vertically across the columns of the table.

If a match if found (3 or more) append them to the table containing the list of matches.

There’s also a possible optimisition. If you’re at the 7th tile and the match count is 0 or 1, you don’t have to check the 8th tile as it wouldn’t form a match anyways.

See slide #25 to slide #66 for a visual explanation. There’s hardly any text you can quickly view it as an animation.

Student Question => If we delete the tiles as and when see matches and there was an intersection of matches (forming a T shape or a cross)?

Colton’ Reply => If we cleared matches as and when we encountered them, we wouldn’t see the second match as one or more of the common tiles of the matches would be cleared and it would no longer be a match.

The current algorithm we implement goes over the entire grid before deleting matches so it would not miss it. It would see the first match of the intersection while going horizontally and then the second one while iterating vertically over the grid.

Colton also suggested that we could reward the user with more points in case of an intersection, clear the entire row and do those sorts of things.

Board.lua Board:calculateMatches()

  • Variables for current colour, matchNum (how many consecutive of the same colour seen), matches etc.
  • A branch for shortcircuiting at 7th or greater tile.
  • Loop to keep counting the same colour if found.
  • If a match is found, insert it into the matches table. Insert into the table all the tiles that are part of the match. We insert all the tiles because it’s easier to find if a tile is in the match table or not. If we inserted match ranges (index positions), we would have to write logic to check if a given tile is a part of the range or not. This takes a little more memory but simplifies stuff quite a bit.
  • We iterate from 2 to 8, so if the last tile of the horizontal row is a part of a match, we will not reach the else block that takes care of calculating the matches since we would have exhausted the for loop. So there’s an if block on line 95 that handles this corner case and adds the match to the matches table.
  • Exact same logic for the vertical matches. Just x & y are inverted.
  • self.matches = matches so that we have a reference to all the matches. They’ll come in handy later on when we want to remove tiles.
  • In the end this function either returns false (if there are no matches) or the matches table. This is a neat API design as we can directly use if Board:calculateMatches().

Removing Matches

You should have realised by now that all the matches are part of a 2D table (a table of matches and each match has a list of tiles). We first have to set all tiles in the matches table to nil. It has the effect of removing the tile from the grid.

Once the matches are removed, we have to bring the impact of gravity. Higher level tiles that still exist should fill lower level spaces.

Jist of the algorithm => Start from the bottom of each column and find an empty tile (i.e look vertically and start from the bottom). If an empty tile is found go upward and look for the nearest tile and swap the tile with the empty space. Then start with the position just above the space you encountered and not the location of the tile you swapped it with because we could still see spaces between them. We don’t have a fixed number of items to check (we just have to ensure that the tiles are at the bottom and if spaces exist, all of them should be above them). So we resort to using a while loop rather than a for loop. It now has a similar look and behaviour of the bubble sort algorithm. If no more tiles are found since the highest tile in the column, the column needs no more swapping.

A student made a nice suggestion that we could just shift all tiled cells to the bottom without having to go through all this. It’s a neat idea. It’s similar to getting rid of spaces in strings and as a result everything moves to the left anyways.

I think Colton took us through the approach described above so that we could get a clearer picture of what’s happening.

Board.lua Lines 182 - 209

  • Line 183 A flag for space (empty tile) or not.
  • Lines 191 - 207 If a space was encountered the flag is set to true. If a tile’s encountered it means that there’s one or more spaces followed by a tile. We then enter the if branch under line 193, tween the tile to fall and then reset space = false. So we’ve accounted for the lowest space and the tile vertically just after it.
  • Notice that we use an outer for loop from 1, 8 (for the columns) since the number of columns in known in advance. The inner loop is a while loop (for going over each column vertically) as the number of tiles we have to fix is not known in advance. Each columns might need different number of swaps, some might not even need any.

See slide #67 to slide #93 for a visual explanation. There’s hardly any text, you can quickly view it as an animation.

Check resources to see bubble sort in action. Also check out string strips in Python to better understand the idea suggested by the student.

Replacing Tiles

Check from the top if there are empty spots. Remember that gridX and gridY are coordinate values, x and y are just indices in the grid table. Set the empty spot to a tile using x and y so that the internal data structure is correct. This is essential as the tile has to be stored in the correct place in memory.

Once that’s done we can manipulate it’s gridX and gridY values to give the right effect, render it in the right place, create visual effects like spins etc. We currently tween it’s gridY value to make it look like it’s falling into place from the top.

Also the inputs are disabled while replacing tiles to avoid bugs.

PlayState.lua Lines 189 - 192 => 50 points for each tile in a match.

PlayState.lua Lines 198 - 211 => We first get the tiles with their respective positions and target positions using getFallingTiles() and tween them to their new positions over 0.25 seconds. After that’s done we also need to get new tiles and tween them to their respective positions (tween gridY to make it look like it’s falling). After that’s done we recalculate matches just in case the new tiles create new matches. calculateMatches() recursively keeps calling itself everytime it finds a match on the new tiles. Say with the new tiles spawned it found a match, it destroys them and generates a new set of tiles again upon which it has to check for matches again.


Taking some sort of image and using some arbitrary number of colours from it. You basically use a limited number of colours that are quite likely to go well with each other.

He briefly mentions about a famous colour palette - DawnBringer’s 32 Colour Palette.

Dithering => Draw two coloured pixel by pixel interleaved (alternation colours colour1, colour2, colour1 and so on). The end result looks like a new colour.

Check slide #109 for the resultant colour by dithering each of the 32 colours with each other. The first row and column are the individual colours. The intersections are the result of the row and column.

You can create loads of cool stuff by using a limited colour set and dithering. Check out slide #110, all of those scenes were created by dithering a small palette of 16 colours.

There’s a famous 32 colour palette by Dawn Bringer which can be put to good use. You can convert images to a particular palette as well. Colton then shows how an image of a cat (with 1000’s or millions) would look if converted to this colour palette. It looks very similar to a cat but had a very inconsistent and blotchy look (anything with blurs develop patches). He then showed an example where he converted a comic with many flat colours into this colour palette. It had a nice feel to it. The gist being that a particular colour palette will not work with all images.

This game and the previous game (Breakout) use this very same 32 colour palette.

By imposing the constraint of a limited colour palette you give the game a consistent look. Can also be used to give a nice retro feel. Old games were limited by hardware. They could only display a limited set of colours and hence resorted to colour palette and dithering.

Palette Swap
Create a gray scale version of a sprite. Have distinct parts which you can identify. Use different colours for each of those distinct parts. The same sprite could just be used as a different game object. Mario actually did this. They had the same sprite but used a different colour palette to colour them.

I’ll just quote Wikipedia here.

A palette swap is a practice used in video games, whereby a graphic that is already used for one element is given a different palette, so it can be reused as other elements. The different palette gives the new graphic another set of colors, which makes it recognizably distinct from the original. Palette swaps are commonly used to distinguish between first and second players, for creating visual hierarchies, and for making visually distinct areas for levels in games.


He briefly explains about the assignment.

If you want to implement mouse functionality, remember that you will have to use the Push library to convert the actual coordinates on the screen to a set of coordinates that are scaled to the VIRTUAL_WIDTH and VIRTUAL_HEIGHT.