Lecture 3

Welcome!

  • Today we explore the Match 3 genre, popularized by games like Bejeweled and Candy Crush. Bejeweled was a game that became very popular in the early 2010s, and Candy Crush followed with almost the same exact idea, just candy-themed.
  • The core mechanic is simple: You have a grid of tiles (jewels, candies, etc.) that are all arranged orthogonally to one another. You can swap any two that are directly adjacent. If you create three or more contiguous tiles of the same color, you complete a match and earn points.
  • When tiles are matched, they disappear and new tiles fall from the top to fill the gaps. This can create chain reactions of additional matches. People who have played these games know that the most fun you probably have is when you get chain after chain of matches and the board is exploding with activity.
  • Looking at the game demo, several elements stand out:
    • The title letters are rotating their colors on a timer, changing every fraction of a second.
    • When we press Start, we fade to white and then from white into a new state.
    • The level text translates from the top of the screen to the middle, pauses, then moves off the bottom. This is Y position interpolation.
    • A countdown timer decrements every second in the corner.
    • When we swap two tiles, they do not instantly switch positions. They interpolate smoothly between their positions.
    • When a match occurs, the tiles above fall down smoothly, and new tiles tween in from above.
  • This lecture introduces several powerful concepts:
    • Timers allow us to schedule events over time, such as “every 1 second, do X” or “after 2 seconds, do Y.”
    • Tweening (short for “in-betweening”) allows us to smoothly interpolate values between two points over a period of time.
    • We will learn how to detect matches in a grid and handle falling tiles.
    • We will also discuss sprite art and palettes, which are important for game esthetics.
  • Up until now, we have done everything based on automatic position calculations using physics: Velocity applying to Pong paddles and balls, gravity applying to the Flappy Bird, pipes moving from right to left. Things have been otherwise very discrete and very instantaneous. Now we gain the ability to think of our game as a set of operations over time, for things that should animate or transition smoothly.

Quads and Sprite Sheets

  • Recall from last week that a sprite sheet (or texture atlas) is a single image containing multiple smaller images that we can extract using quads.
  • Our Match 3 game uses a sprite sheet where all tiles are uniformly 32x32 pixels. This is much easier to deal with than last week’s Breakout texture, which had elements of varying sizes. We can split this up into one singular array of quads, all just 32x32 pixels.
  • Each tile can be assigned an ID, which is simply its index in the quads table. If we imagine the texture, the tile at the very top left would be ID 1. The next tile would be ID 2, then 3, 4, 5, 6, and so on, iterating left to right, top to bottom. This allows us to think of tiles as numbers that we can compare for matches.

  • Consider the following code from quads-0/main.lua:

    -- quads-0: Simply loading and drawing the texture
function love.load()
    texture = love.graphics.newImage('match3.png')
end

function love.draw()
    push.start()
    love.graphics.draw(texture)
    push.finish()
end

    Notice that this just draws the entire texture to the screen. This is our starting point: What do we have to work with?

  • To extract a single tile, we create a quad. Consider the following from quads-1/main.lua:

    -- quads-1: Creating a single quad
function love.load()
    texture = love.graphics.newImage('match3.png')
    quad = love.graphics.newQuad(0, 0, 32, 32, texture:getDimensions())
end

function love.draw()
    push.start()
    love.graphics.draw(texture, quad)
    push.finish()
end

    Notice that love.graphics.newQuad() creates a 32x32 window into the texture starting at position (0, 0). When we draw the texture with this quad, only that portion is rendered.

  • Rather than creating quads one at a time, we can generate all of them using a GenerateQuads function. Consider the following from quads-2/main.lua:

    -- GenerateQuads: Slices a texture into uniform quads
function GenerateQuads(texture, width, height)
    local sheetWidth = texture:getWidth() / width
    local sheetHeight = texture:getHeight() / height

    local quadCounter = 1
    local quads = {}

    for y = 0, sheetHeight - 1 do
        for x = 0, sheetWidth - 1 do
            quads[quadCounter] =
                love.graphics.newQuad(x * width, y * height, width, height,
                    texture:getDimensions())
            quadCounter = quadCounter + 1
        end
    end

    return quads
end

    Notice that this function iterates through the entire texture, row by row, column by column, creating a quad for each tile and storing them in a table. The # operator in Lua gives us the length of a table, so we can use math.random(#quads) to select a random tile.

  • If we try to draw random quads each frame, the screen flickers wildly because a new random tile is selected every frame. We are getting closer to a grid, but this is just ephemeral information that is not preservable. We cannot perform any operations on it.

  • To create a persistent board, we must cache the tile IDs. We need to store the random number rather than generating it every frame. Consider the following from quads-4/main.lua:

    -- quads-4: Caching tile IDs in a 2D table
function refreshTiles()
    tiles = {}

    for y = 1, 288 / 32 do
        table.insert(tiles, {})

        for x = 1, 512 / 32 do
            table.insert(tiles[y], math.random(#quads))
        end
    end
end

function love.draw()
    push.start()

    for y = 1, 288 / 32 do
        for x = 1, 512 / 32 do
            love.graphics.draw(texture, quads[tiles[y][x]], (x - 1) * 32, (y - 1) * 32)
        end
    end

    push.finish()
end

    Notice that we store the random tile IDs in a 2D table called tiles. Each tiles[y][x] holds a number that indexes into our quads table. This way, the board remains consistent across frames, and we have a data structure that we can iterate through and check for matches.

  • You can envision our grid as essentially an array of arrays of numbers. These IDs allow us to compare tiles: “Is this color the same as that color? Are three of them contiguous?” This mental model of tiles as numbers is the foundation for Match 3 and will be relevant next week when we look at Mario and tile-based worlds.

Timers

  • Up until now, movement in our games has been driven by physics (velocity, gravity). But what if we want something to happen after a certain period of time, or every N seconds?

  • Consider the following naive approach from timer-0/main.lua:

    -- timer-0: Manual timer implementation
function love.load()
    currentSecond = 0
    secondTimer = 0
end

function love.update(dt)
    secondTimer = secondTimer + dt

    if secondTimer > 1 then
        currentSecond = currentSecond + 1
        secondTimer = secondTimer % 1
    end
end

    Notice that we accumulate dt (delta time) until it exceeds 1 second, then increment our counter and reset the timer using modulo.

  • This approach works for a single timer, but it becomes cumbersome when managing multiple timers with different intervals. Imagine having 5 or 6 timers, each with its own variables and update logic. We would need separate timer variables, separate counters, and separate update logic for each one. The code quickly becomes repetitive, hard to maintain, and not a pleasure to deal with.
  • The Knife library provides a Timer module that solves this problem elegantly. It allows us to think in terms of “every X seconds, do this” or “after X seconds, do that,” rather than manually managing timer variables and modulo operations.

  • Consider the following from timer-2/main.lua:

    -- timer-2: Using the Knife Timer library
Timer = require 'knife.timer'

function love.load()
    intervals = {1, 2, 4, 3, 2, 8}
    counters = {0, 0, 0, 0, 0, 0}

    for i = 1, 6 do
        Timer.every(intervals[i], function()
            counters[i] = counters[i] + 1
        end)
    end
end

function love.update(dt)
    Timer.update(dt)
end

    Notice that Timer.every() takes an interval (in seconds) and an anonymous function that gets called every time that interval elapses. The anonymous function is like data: Timer stores a reference to it and calls it when the time comes. All we need in our update function is Timer.update(dt), and the library handles everything else.

  • The key Timer functions are:
    • Timer.every(interval, callback): Execute callback every interval seconds.
    • Timer.after(duration, callback): Execute callback once after duration seconds.
    • Timer.tween(duration, definition): Smoothly interpolate values over duration seconds.
  • These two ideas alone, “every X seconds” and “after X seconds,” allow us to do so many different things based on time without having to think in terms of managing timer variables and accumulating delta time manually.

Tweening

  • Tweening (from “in-betweening”) is the process of smoothly interpolating a value between two points over a period of time.
  • Rather than instantly teleporting an object from position A to position B, we gradually move it, creating smooth animation. Think about a strategy game where you want to move a unit between two squares. You do not want it to just instantly appear; you want it to move smoothly between the squares.

  • Consider the following manual approach from tween-0/main.lua:

    -- tween-0: Manual tweening with interpolation
MOVE_DURATION = 2

function love.load()
    flappyX, flappyY = 0, VIRTUAL_HEIGHT / 2 - 8
    timer = 0
    endX = VIRTUAL_WIDTH - flappySprite:getWidth()
end

function love.update(dt)
    if timer < MOVE_DURATION then
        timer = timer + dt
        flappyX = math.min(endX, endX * (timer / MOVE_DURATION))
    end
end

    Notice that we calculate flappyX as a ratio: timer / MOVE_DURATION starts at 0 and approaches 1 over 2 seconds. Multiplying this ratio by endX gives us smooth movement from 0 to endX. We could change MOVE_DURATION to 4 seconds, and it would take 4 seconds instead.

  • This formula works when starting from zero, but a more general interpolation formula is: current = base + (destination - base) * (timer / duration)
  • This allows interpolation from any starting point to any ending point. Any value you interpolate needs a base in order for the math to work out such that you go from one position to the other over that span of time.
  • Managing tweens manually becomes complex with many objects. If we have new things that start after the timer has already started, there is difficulty coordinating that. It does not scale very well. We are still manually thinking about things in terms of timers.

  • The Knife library’s Timer.tween() provides a declarative solution. Consider the following from tween-2/main.lua:

    -- tween-2: Using Timer.tween for multiple objects
Timer = require 'knife.timer'

function love.load()
    birds = {}

    for i = 1, 1000 do
        table.insert(birds, {
            x = 0,
            y = math.random(VIRTUAL_HEIGHT - 24),
            rate = math.random() + math.random(TIMER_MAX - 1),
            opacity = 0
        })
    end

    endX = VIRTUAL_WIDTH - flappySprite:getWidth()

    for k, bird in pairs(birds) do
        Timer.tween(bird.rate, {
            [bird] = { x = endX, opacity = 255 }
        })
    end
end

function love.update(dt)
    Timer.update(dt)
end

    Notice that Timer.tween() takes a duration and a definition table. The syntax [bird] = { x = endX, opacity = 255 } means “tween the bird’s x to endX and its opacity to 255.” Lua allows tables as keys, enabling this elegant syntax for describing interpolations.

  • With Timer.tween(), we can interpolate multiple properties simultaneously (position, opacity, scale, etc.) without manually managing timers or interpolation math. We get X movement and opacity changes “for free,” plus any other attribute we want to add. This is very important for all future lectures.

Chaining Tweens

  • What if we want to perform a sequence of movements: Move right, then move down, then move left, then move up? Like an old screensaver bouncing around the screen.
  • We could manage this manually with flags and multiple timers, keeping track of destinations and whether each was reached, but it becomes complex quickly. We would have to think in terms of the actual interpolation, not in terms of “the bird is going to move here, then here, then there.”
  • The Knife library provides a :finish() function that can be chained onto any timer operation. This is similar to the concept of promises in web programming, where you are promised that after some operation finishes, a callback function will be called. In the web world, you might see .then(); here we see :finish().

  • Consider the following from chain-1/main.lua:

    -- chain-1: Chaining tweens with :finish()
Timer = require 'knife.timer'

function love.load()
    flappySprite = love.graphics.newImage('flappy.png')
    flappy = {x = 0, y = 0, opacity = 255}

    Timer.tween(MOVEMENT_TIME, {
        [flappy] = {x = VIRTUAL_WIDTH - flappySprite:getWidth(), y = 0, opacity = 0}
    })
    :finish(function()
        Timer.tween(MOVEMENT_TIME, {
            [flappy] = {x = VIRTUAL_WIDTH - flappySprite:getWidth(), y = VIRTUAL_HEIGHT - flappySprite:getHeight(), opacity = 255}
        })
        :finish(function()
            Timer.tween(MOVEMENT_TIME, {
                [flappy] = {x = 0, y = VIRTUAL_HEIGHT - flappySprite:getHeight(), opacity = 0}
            })
            :finish(function()
                Timer.tween(MOVEMENT_TIME, {
                    [flappy] = {x = 0, y = 0, opacity = 255}
                })
            end)
        end)
    end)
end

function love.update(dt)
    Timer.update(dt)
end

    Notice that each :finish() callback contains another Timer.tween(), creating a chain of sequential animations. The bird moves to the top-right (fading out), then bottom-right (fading in), then bottom-left (fading out), then back to the origin (fading in), like a ghost in Mario.

  • This pattern allows us to describe sequential operations in a linear, readable way. We are thinking about time in a linear fashion: “after this, do that.” Once one tween finishes, the next one begins automatically. Timer stores the callback function and triggers it once its time operation finishes.
  • This is one of the bigger pieces of this lecture: The ability to think about time through your game, to do smoother animations and transitions between states, but also between objects interacting within your states.

Tile Swapping

  • Now we can apply these concepts to our Match 3 game. We need a board data structure that stores tile information, and the ability to swap tiles.
  • In swap-0/main.lua, we create an 8x8 board where each tile is a table containing:
    • x and y: The pixel coordinates for drawing.
    • gridX and gridY: The tile’s position in the grid (1-8).
    • tile: The ID of the tile (index into our quads table).
  • The distinction between grid coordinates and pixel coordinates is crucial:
    • Grid coordinates (gridX, gridY) are discrete (1-8) and determine the tile’s position in the board data structure. These are used for checking matches and swapping positions in the array.
    • Pixel coordinates (x, y) are continuous and can be tweened for smooth animation. These are what actually move left and right, top to bottom as tiles are swapped.
  • When we swap two tiles, their positions in the board array must be swapped instantly (so the data structure is correct for match checking), but we tween their pixel coordinates so the visual swap happens smoothly.

  • Consider the swap logic from swap-2/main.lua:

    -- swap-2: Animated tile swapping with Timer.tween
if key == 'enter' or key == 'return' then
    if not highlightedTile then
        highlightedTile = true
        highlightedX, highlightedY = selectedTile.gridX, selectedTile.gridY
    else
        local tile1 = selectedTile
        local tile2 = board[highlightedY][highlightedX]

        local tempX, tempY = tile2.x, tile2.y
        local tempgridX, tempgridY = tile2.gridX, tile2.gridY

        local tempTile = tile1
        board[tile1.gridY][tile1.gridX] = tile2
        board[tile2.gridY][tile2.gridX] = tempTile

        Timer.tween(0.2, {
            [tile2] = {x = tile1.x, y = tile1.y},
            [tile1] = {x = tempX, y = tempY}
        })

        tile2.gridX, tile2.gridY = tile1.gridX, tile1.gridY
        tile1.gridX, tile1.gridY = tempgridX, tempgridY

        highlightedTile = false
        selectedTile = tile2
    end
end

    Notice that we swap the tiles’ positions in the board array instantly, but we tween their pixel coordinates over 0.2 seconds. This creates the smooth sliding animation while keeping the board state accurate for match detection.

Calculating Matches

  • The core of Match 3 is detecting when three or more tiles of the same color are aligned horizontally or vertically. This is the underpinning of what makes Match 3 work.
  • The algorithm is relatively simple. For any match, we define it as three or more contiguous tiles of the same color on either the X axis or Y axis (not diagonals, just orthogonal). We first calculate all horizontal matches, then do the same thing 90 degrees rotated to calculate vertical matches.
  • For horizontal matches:
    1. Start at the first tile in a row. Note its color.
    2. Check the next tile. Is it the same color? If yes, we are currently in a match. Increment our match count.
    3. If it is a different color, check: Did we have at least 3 in a row? If so, record the match.
    4. Set the new color to match against. Continue.
    5. At the end of the row, check again: We cannot check the next color because there is none, so check if we have at least 3.
    6. Repeat for every row.
  • Then do the same thing for vertical matches, crawling through columns instead of rows.

  • Consider the following from match-3/src/Board.lua:

    -- Board:calculateMatches: Detecting horizontal and vertical matches
function Board:calculateMatches()
    local matches = {}
    local matchNum = 1

    -- horizontal matches first
    for y = 1, 8 do
        local colorToMatch = self.tiles[y][1].color
        matchNum = 1

        for x = 2, 8 do
            if self.tiles[y][x].color == colorToMatch then
                matchNum = matchNum + 1
            else
                colorToMatch = self.tiles[y][x].color

                if matchNum >= 3 then
                    local match = {}
                    for x2 = x - 1, x - matchNum, -1 do
                        table.insert(match, self.tiles[y][x2])
                    end
                    table.insert(matches, match)
                end

                matchNum = 1

                if x >= 7 then
                    break
                end
            end
        end

        if matchNum >= 3 then
            local match = {}
            for x = 8, 8 - matchNum + 1, -1 do
                table.insert(match, self.tiles[y][x])
            end
            table.insert(matches, match)
        end
    end

    -- vertical matches follow same pattern...

    self.matches = matches
    return #self.matches > 0 and self.matches or false
end

    Notice that we track colorToMatch and matchNum as we scan. When the color changes, we check if we had a match and go backwards from the current position to collect those tiles. We also check at the end of each row in case the match extends to the edge. The optimization if x >= 7 then break means we do not need to check the last two tiles if they are not already part of a match.

  • When the board is initialized, we call calculateMatches() repeatedly. If matches exist, we reinitialize the board. This ensures the player always starts with a clean slate with no pre-existing matches.

Falling Tiles

  • After matches are removed (by setting tiles to nil in the board), we cannot just leave empty spaces. We need to:
    1. Let existing tiles “fall” down to fill the gaps.
    2. Generate new tiles at the top to fill the remaining spaces.
  • The algorithm for falling tiles works column by column, from the bottom up:
    1. Start at the bottom of a column. Is there a tile? If yes, move up.
    2. If we find a space (nil), flag it. Continue upward looking for a tile.
    3. When we find a tile above a space, move that tile down to fill the space. Then continue from where that tile was.
    4. Repeat until we reach the top of the grid.
  • After shifting existing tiles down, we count how many spaces remain at the top of each column. We create new tiles above the visible area (at y = -32) and tween them down to their resting positions.

  • Consider the following from match-3/src/Board.lua:

    -- Board:getFallingTiles: Shifting tiles down and generating new ones
function Board:getFallingTiles()
    local tweens = {}

    for x = 1, 8 do
        local space = false
        local spaceY = 0

        local y = 8
        while y >= 1 do
            local tile = self.tiles[y][x]

            if space then
                if tile then
                    self.tiles[spaceY][x] = tile
                    tile.gridY = spaceY
                    self.tiles[y][x] = nil

                    tweens[tile] = {
                        y = (tile.gridY - 1) * 32
                    }

                    space = false
                    y = spaceY
                    spaceY = 0
                end
            elseif tile == nil then
                space = true
                if spaceY == 0 then
                    spaceY = y
                end
            end

            y = y - 1
        end
    end

    -- create replacement tiles at the top
    for x = 1, 8 do
        for y = 8, 1, -1 do
            local tile = self.tiles[y][x]

            if not tile then
                local tile = Tile(x, y, math.random(18), math.random(6))
                tile.y = -32
                self.tiles[y][x] = tile

                tweens[tile] = {
                    y = (tile.gridY - 1) * 32
                }
            end
        end
    end

    return tweens
end

    Notice that this function returns a table of tween operations. Each tile that needs to move has an entry specifying its target Y position. We can pass this directly to Timer.tween() to animate all the falling tiles simultaneously. The new tiles start at y = -32 (above the visible area) and tween down to their grid positions.

  • After tiles fall, we must check for matches again. This is done recursively: If new matches are found, we remove them, let tiles fall, and check again until the board is stable. This is how chain reactions work, and it is the source of much of the fun in these games.

State Transitions

  • To create polished transitions between game states, we can use a simple technique: Draw a full-screen rectangle and tween its opacity.
  • How do we make the screen fully white? There is no easy way other than drawing a rectangle on top of everything else that starts transparent and transitions to full opacity.
  • For a “fade to white” effect:
    1. Start with a white rectangle at opacity 0 (transparent).
    2. Tween the opacity to 1 (fully opaque).
    3. Change to the next state.
    4. In the new state, the rectangle already exists at opacity 1.
    5. Tween the opacity back to 0.
  • This creates the illusion of a smooth transition, even though the state change is still instantaneous and abrupt. We are tricking the viewer into not seeing the abrupt change through clever use of timers.

  • In the game’s start state, when the player presses Enter:

    -- Transition to begin game state with fade effect
Timer.tween(1, {
    [self] = {transitionAlpha = 1}
})
:finish(function()
    gStateMachine:change('begin-game', {
        level = 1
    })
end)

    Notice that we tween transitionAlpha from 0 to 1. The :finish() callback contains our state machine transition, so we change states only after the fade completes.

  • The begin game state has its own transitionAlpha that starts at 1. On enter, it immediately begins tweening to 0. Then, using :finish(), it tweens the level label Y position to the middle of the screen. After a Timer.after(1, ...), it tweens the label to the bottom, and finally transitions to the play state.
  • Everything is very smoothly and cleanly transitioned using nothing but Timer operations and chained callbacks.

Sprite Art and Palettes

  • The esthetics of our game benefit from using a limited color palette. Our Match 3 art uses the Dawnbringer 32 palette, a famous 32-color palette designed for pixel art by an artist known as Dawnbringer.
  • With only 32 carefully chosen colors, artists can achieve a surprising range of tones through dithering: Alternating pixels of different colors in a pattern to create the illusion of intermediate shades. If you create a 32x32 matrix showing all color combinations with dithering, it looks like a full range of color, but it is still only 32 colors.
  • Limited palettes offer several advantages:
    • Coherence: All colors work well together by design. There is a reduced risk of overly harsh contrasts or clashing colors.
    • Reduced decision fatigue: Fewer color choices means fewer opportunities for mistakes. When you have just a set of well-designed colors, your risk of poor esthetic choices is minimal.
    • Nostalgia: This approach mirrors the hardware limitations of classic consoles like the NES and SNES, where color size was limited by bit depth.
  • Palette swapping is a related technique where the same sprite can be recolored by changing the palette. In older consoles like the NES or Super Nintendo, the video processor would look at a range of memory addresses for colors. By pointing to different palette memory, you could instantly change the colors of sprites on the fly. This allowed games to have multiple enemy colors or player skins without storing separate sprite sheets.
  • As an exercise, try limiting yourself to 8, 16, or 32 colors when creating game art. Try two colors like the Game Boy, or four colors. Constraints often spark creativity, and it is interesting what comes about through limitations.

Summing Up

  • This week we learned several powerful techniques:
    • Using the Knife Timer library to schedule events with Timer.every(), Timer.after(), and Timer.tween().
    • Tweening to smoothly interpolate values over time, creating fluid animations.
    • Chaining tweens with :finish() to create sequential animations, thinking about time in a linear fashion.
    • Representing a game board as a 2D array of tile objects with both grid coordinates (for logic) and pixel coordinates (for animation).
    • Calculating matches by scanning rows and columns for consecutive tiles of the same color.
    • Falling tiles logic to fill gaps after matches are removed, with recursive checking for chain reactions.
    • State transitions using full-screen rectangles with tweened opacity.
    • The importance of color palettes in pixel art and the technique of palette swapping.
  • These concepts apply far beyond Match 3. Timers and tweening are fundamental to creating polished, professional-feeling games with smooth animations and transitions. The ability to think about time through your game is one of the bigger takeaways from this lecture.
  • See you next time!