FrankMatch3LocalScan is an algorithm Frank wrote for War of Matches, the working title of one of our match-3 game projects. Its job is small and constant: every time a tile lands, say whether it completed a pattern, and which one. In that game the shape matters as much as the match itself, because a line of three, an L, a T and a 2×2 square each trigger something different.
The code is now open source under the MIT licence: github.com/imadyTech/FrankMatch3LocalScan. The repository includes a new, minimal Unity sample so that anyone can run it and build on it, and you can also try it in your browser: a small playable board that shows every scan as it happens.
The repository README opens with a line that explains its age: it was Frank's last project written entirely by hand, before AI coding assistants became part of how we work. This post was written afterwards, with AI help, to explain the idea and to compare it with what is already out there.
How match-3 games usually find matches
Before describing our approach, we looked at how publicly documented match-3 code does the job. Four families come up again and again.
- Scan the whole board. Walk every row and every column, count runs of the same colour, and record any run of three or more. Harvard's CS50 games course does this in
Board:calculateMatches(), and Catlike Coding's Unity match-3 tutorial does it inFindMatches(). Swaps are validated by running the full scan and undoing the swap if nothing is found. Cascades run the full scan again after every refill. - Walk outward from the swapped tiles. Kodeco's (formerly Ray Wenderlich) Unity tutorial casts rays from each swapped tile, left/right and then up/down, and clears the tile if either axis reaches three. This is local, but the two axes are checked independently, so an L or a T is cleared as two lines rather than recognised as one shape. Its cascade step goes back to checking every tile.
- Flood fill. A Game Developer article on writing a match-3 game in Unity collects connected same-colour tiles recursively and clears any group of three or more. It handles any shape, but it does not tell you which shape it found.
- Classify the shape afterwards. When a game does need T, L or + shapes, forum advice is typically to collect the matched cells first, then compare their normalised coordinates against shape templates in every orientation.
There is also a well-known speed technique from board-game engines: bitboards, where a whole colour is stored as a bit mask and runs are found with shifts and ANDs. It is fast, but it is still a board-wide operation, and you still have to classify shapes afterwards.
What these approaches have in common is that finding a match and naming its shape are two separate steps, and at least one of them usually touches the whole board.
The idea in three steps
FrankMatch3LocalScan starts from two observations.
- A new match must include the tile that just moved. If the board had no match before, any new one passes through the landing cell. So there is no need to look anywhere else.
- The direction of the move tells you where not to look. The cell the tile came from now holds its swap partner, which has a different colour. It can never be part of the match. Everything behind it is cut off too.
Step 1: overlay the patterns to find the cells that matter
Take every pattern the game recognises, in every position it can take relative to a tile that moved left, and draw them all in the same 5×4 window around the landing cell. The game defines 14 such situations: lines of three in four positions, lines of four and five, L, T, the 2×2 square, and a few game-specific ones.
Overlay them and only 8 cells are ever used. These become the sampling points.
Step 2: hash the 8 cells into one byte, using the direction
For each sampling point, compare its colour with the landing tile. Same colour sets the bit; anything else, including off-board cells, leaves it at 0. Eight comparisons give one byte.
For the other three directions, the same layout is rotated, so bit 5 always means "the cell straight ahead", bit 4 always means "two cells to the side", and so on. The direction is an input to the hash, not something the table has to cover four times.
// Tile moved LEFT onto (x, y). The other directions are rotations of this.
byte hash = 0;
if (Same(x, y - 1)) hash |= 1 << 7;
if (Same(x, y + 1)) hash |= 1 << 6;
if (Same(x - 1, y )) hash |= 1 << 5;
if (Same(x, y - 2)) hash |= 1 << 4;
if (Same(x, y + 2)) hash |= 1 << 3;
if (Same(x - 2, y )) hash |= 1 << 2;
if (Same(x - 1, y - 1)) hash |= 1 << 1;
if (Same(x - 1, y + 1)) hash |= 1;
Step 3: look the byte up
A byte has only 256 values, so every possible neighbourhood can be listed in advance. In the current table, 172 of the 256 values map to a pattern and the rest map to "no match". Each pattern also stores its cells in the un-rotated layout, and the algorithm rotates them back by the move direction to get board coordinates.
| Pattern | Bits that must be set | Example hash |
|---|---|---|
| H3, line of three straight ahead | 5, 2 | 00100100 = 36 |
| V3C, line of three across the landing cell | 7, 6 | 11000000 = 192 |
| S2A, 2×2 square | 7, 5, 1 | 10100010 = 162 |
| L5A, L shape | 7, 5, 4, 2 | 10110100 = 180 |
| T5, T shape | 7, 6, 5, 2 | 11100100 = 228 |
| V5, line of five across | 7, 6, 4, 3 | 11011000 = 216 |
| T7, the largest shape | 7, 6, 5, 4, 3, 2 | 11111100 = 252 |
When a byte contains more than one pattern, the table returns the largest. A hash of 252 contains H3, V5 and T5, and the table returns T7, which covers them all.
Cascades use the same scan
After a match is cleared, tiles fall and new ones are spawned. Each tile that lands is scanned once, with the direction "down". There is never a full-board pass, not even during cascades. Each scan costs eight comparisons and one table lookup, whatever the size of the board.
What is new here
We have not found a public match-3 implementation that works this way. That is not proof that none exists, and we would be glad to hear of one. As far as we can tell, the combination below is new.
- Detection and classification are one step. The byte does not just say "there is a match". It says which shape, directly. Other approaches find runs or groups first and classify them afterwards.
- The move direction is part of the algorithm. Using the direction shrinks the area to look at, removes the cell behind the tile, and lets one table serve all four directions through rotation.
- The work per move is constant. Eight reads, one lookup and a rotation of a few coordinates. Board size does not matter, and cascades only touch the tiles that actually moved.
- The rules are data. The table is just a mapping from bytes to shapes. Changing which shapes a game recognises, or their priority, means editing the table, not the scanning code.
The individual ingredients are not new. Packing a cell's neighbours into a bit mask and looking the result up in a table is a familiar trick elsewhere: auto-tiling in 2D games picks wall and terrain tiles this way, and cellular automata such as Conway's Game of Life are often run from neighbourhood lookup tables. What FrankMatch3LocalScan adds is the match-3 specific part: choosing the sampling points by overlaying the game's patterns, and making the hash depend on the direction the tile came from.
While building the sample we also checked the hand-written table. For every one of the 256 values, it returns exactly the largest pattern whose bits are all present. That means the table does not have to be written by hand: it can be generated from the list of pattern masks, which makes adding a new shape much safer.
Limitations
- The window is fixed. The scan sees at most two cells in each direction from the landing cell. A run that continues beyond that is not included in the returned cells, and a shape that needs a cell outside the 8 sampling points cannot be recognised without adding a ninth bit, which doubles the table to 512 entries.
- One pattern per scan. Each landing returns the single largest pattern through that cell. A game that wants to score two separate shapes created by one move has to combine the scans of both swapped tiles, as the sample does.
- Some patterns are specific to War of Matches. "A tile landing beside a vertical three" and the 2×2 square are that game's rules. Another game would edit the table.
- It assumes the cell behind is different. That is always true for a swap of two different colours. For falling tiles, the tile above has also moved and is scanned in its own right, so vertical runs are still found by the top tile.
- The original code is not thread-safe. It keeps the board size in static fields during hashing.
Performance: not measured yet
We have not published benchmark numbers. A fair comparison needs other implementations running the same boards and the same rules, including shape classification, and we did not find open-source code that we could run side by side on equal terms. Comparing against our own quick reimplementations would mostly measure how well we wrote those.
In theory, the advantage is clear: a full-board scan costs work proportional to the board's area on every step of every cascade, while the local scan costs eight comparisons per tile that moved. Whether that matters in practice depends on board size, target devices, and how much else the game does per frame. If you measure it, please tell us what you find.
Try it, and take it further
The quickest way to see it is the online demo. It is the Blazor WebAssembly version of the sample, built from the same code, and it runs entirely in your browser.
The repository has three parts:
Algorithms/holds the original code from the game: the hash functions for the four directions, the 256-entry table, and the pattern coordinates.UnitySample/is a minimal Unity 6 project. Open it, press Play in the empty scene, and click two neighbouring tiles to swap them. A side panel shows every scan as it happens: the landing cell, the direction, the byte in binary and the pattern it maps to. The 8 sampling points of the latest scan are marked on the board. The board logic is plain C#, with no Unity dependency, and EditMode tests check the table and the hash layout in all four directions.BlazorSample/is the online demo. It compiles the files inAlgorithms/unchanged, shares the board logic with the Unity sample, and needs no server:dotnet runto try it locally, or publish it to any static host.
Some directions we would find interesting:
- generate the table from the pattern list instead of writing it by hand;
- replace the dictionary with a plain 256-element array;
- use the same idea for hint and dead-board detection, by hashing a cell as if a tile had moved there;
- try a 9 or 10 bit layout for games with larger shapes.
The code is MIT licensed. Fork it, change it, and use it in your own games.
Sources
- CS50's Introduction to Game Development, lecture 3 notes (Match-3)
- Catlike Coding, Match 3 prototype tutorial
- Kodeco, How to Make a Match 3 Game in Unity
- Game Developer, Writing a match-3 game in Unity
- Construct forum, detecting shapes in match-3
- Chess Programming Wiki, General Setwise Operations (bitboards)