# Match 3 Algorithm with Regular Expression

While it is surely one of the most famous causal game genres on the market, I haven’t made a match-3 game before. When I decided to choose this genre, I stumbled on the very bases of it: detecting matches and potential matches.

Those aren’t difficult problems and can be solved simply by iterating through every cells and check neighbor cells. However, that has never been my style, I wanted to try something different.

In my perception, the problems are of pattern matching type, hence Regular Expression came to my mind. Once the expression is setup, match operations should be simple and extremely fast.

### Present the Grid as a String

First, I would have to present my gems grid as a string. Since I chose to use one-dimensional array for the grid, this requies only a `map+join` or `reduce` operation. I found `map+join` is more clear and very simple with `lodash`.

``_.map(grid, 'type').join('')``
Here I assume `type` is a variable presenting the type of gem and only takes one character (digit or character). If each type takes more than one character, they should have equals number of characters for each type.

### Detect Matches on a Row

This is the easiest case. For each type `T` of gems, we built an expression to match any continuous series of `T` that has at least 3 characters:

``/(TTT)/g``

There are two issues:

First, there are cases where one of the `T` is on another row. For example:

`|   | T | T |`
`| T |   |   |`

In this case, the string persentation is `…TTT…` but that is not what we are looking for. We should only take matches that have positions at more than 2 cells from the end of the row:

``number_of_columns - match_position % number_of_columns > 2``

Second, since RegEx consumes all characters matched, for `TTTTT` only the first three characters would be captured while the others won’t. There are two solutions for this:

• Make a RegEx for each of the specific case `/(TTTTT|TTTT|TTT)/g`. This is more troubling than useful considering other cases also requires the same process.
• Capture with `RegEx.exec`.
`let pattern = /(TTT)/g,    results = [],    match;while ( (match = pattern.exec(gridString)) != null ) {    results.push(match)}`

### Detect Matches on a Column

This is a bit more complicated since the characters won’t be on the same row hence their position in string are scattered.

Notice that the distance between two characters, on the same column and two consecutive rows, is `number_of_columns - 1` indices (see the figure below).

`|           | T | <index 1> || <index 2> | T |           |`

The expression for each pair of character would be

``/T.{number_of_columns - 1}T/g``

Therefore, the expression for a column match would be:

``/(T.{number_of_columns - 1}T.{number_of_columns - 1}T)/g``

While this case doesn’t suffer from the first issues of detecting matches on a row, it does suffer from the second issue and hence should be handled the same way.

### Detecting Potential Matches on a Row

There expressions, ordering like in the figure, are:

``/(TT.)//(T.T)//(.TT)/``

However, the pattern would also have to take in consider the cells that can be swapped to make a match, which are either above or below the `non-T` cell, as in the figure below:

The distance from the lower row `T` cell to the matched cell is equals to its distance to `non-T` cell substracted by number of `T` cell after `non-T` cell, meaning:

`number_of_columns - 1 - number_of_T_after_non_T_cell`

Our expressions would be:

``/(TT..{number_of_columns - 1}T)//(T.T.{number_of_columns - 2}T)//(.TT.{number_of_columns - 3}T)/``

This also suffers the first issue of detecting matches on a row and should be handled the same way.

We can build expressions for the upper row `T` cell case as well, however, the result would return the index of that upper row cell instead of the first index of the match. It is bad since it makes handling the first issue much harder.

Instead, we can flip the grid (by reversing the string) and then use the same expressions. To find the real match index, the recieved index must be translated back to the index in original string and substracted by 2, since the grid is flipped which also reverse the order of the cells in each match.

For implementation purpose, we can concat the expressions since we only need to know if the current grid has a potential match.

Here I don’t discuss hint feature. The best way to implement that feature would be using lookbehind feature of RegEx which is not supported in javascript yet. Libraries such as XRegExp provides this feature though.

### Detecting Potential Matches on a Columns

If you’ve read so far, this wouldn’t need much explaination, our expressions for the case of the figure above would be:

``/(T.{number_of_columns - 1}T.{number_of_columns}T)//(T.{number_of_columns}T.{number_of_columns - 2}T)//(.T.{number_of_columns - 2}T.{number_of_columns - 1}T)/``

This finds potential matches with swappable cell on the right side of the match. Similar to the the previous section, for the case where the swappable `T` is on the left column, we only need to flip the grid, use the same expression, then translate index back to original string and substract by `2 * number_of_columns`.

This also suffers the first issue of detecting matches on a row and should be handled the same way, though in this case, the minimum distance to the end of row is 1 (leaving one column to the right for swappable cell).

``number_of_columns - match_position % number_of_columns > 1``

That’s it. The source code for a match 3 regex module is available here.