Square joy: tile crush

✏   ✂ 2024-12-16

This article presents a solution to a programming puzzle using the j programming language. The challenge is implementing mechanics for a tile-matching game using a data-parallel array-oriented approach (no stinking loops).

This article is not an introduction to the j programming language, but it explains enough details to follow the solution even if you aren’t familiar with the language.

The problem: stabilize the game board

Our game is a simplified version of the popular Candy Crash Saga game:

  1. A rectangular board contains square tiles of different types.
  2. When three or more identical tiles appear next to one another in the same row or column, they explode and leave space.
  3. Tiles experience gravity: they fall if there is space below them.
  4. Moving tiles don’t explode.
  5. If there are multiple exploding sections, the explosions happen simultaneously.

The goal is to implement the board update mechanics after the player makes a move. The mechanics of the player moves are out of scope.

The board representation

I will represent the board as a numeric matrix. Zero indicates an empty tile, and integers 1 through K correspond to tile types.

The board’s columns will require more transformations than rows (gravity works column-wise), so our board representation will be transposed compared to the user’s view. Matrix rows will correspond to columns in the interface and vice-versa.

I will use a nine-by-nine board with five tile types for all examples.

NB. The number of tiles types, including the empty zero tile.
   K =. 6

NB. The board I will use for examples (your board may vary).
NB. 9 9 $ K creates a 9x9 board filled with integer K. 
NB. ?. 9 9 $ K fills that board with random integers in range 0..K. 
   Board =. ?. 9 9 $ K
0 2 4 0 5 4 4 4 2
1 3 2 1 5 1 2 3 4
1 5 5 3 1 1 0 4 3
2 4 3 5 0 4 3 5 5
0 1 2 0 4 5 3 5 5
0 3 4 4 0 4 3 1 0
0 0 1 5 1 2 4 0 4
3 2 4 4 4 1 3 1 3
5 1 2 5 1 5 0 5 2

The numeric board is hard to look at, so let’s write a function to visualize it using our old friend, viewmat.

   require 'viewmat'
   viewboard =. {{ (255 255 255 , 0 0 128 ,: 128 128 128) viewmat |: y }}
   viewboard Board

Ah, much better. The whitespace corresponds to the space, and different colors correspond to tile types.

Our tiles seem to float in the air; let’s make them fall.

Implementing gravity

The law of gravity requires heavy stuff to go down and light stuff to bubble. In our board representation, the gravity pulls to the right, so all the empty zero tiles must shift to the front of each row. In the algorithm speak, we need a stable partition, where the partition predicate is equality to zero.

   NB. The first row before and after applying the stable partition.
0 2 4 0 5 4 4 4 2
0 0 2 4 5 4 4 4 2

The simplest reincarnation of stable partition involves selecting matching and non-matching elements and gluing them together. The copy function (#) will help us select items given a boolean mask, and append (,) will glue the results.

   NB. {{ and }} define an anonymous function
   NB. where y is the implicitly defined right argument.
   NB. We can also define the function tacitly as (#~ <:&0),(#~ >&0)"1

   gravity =. {{ ((y=0)#y),(y~:0)#y }}"1
   gravity Board
0 0 2 4 5 4 4 4 2
1 3 2 1 5 1 2 3 4
0 1 5 5 3 1 1 4 3
0 2 4 3 5 4 3 5 5
0 0 1 2 4 5 3 5 5
0 0 0 3 4 4 4 3 1
0 0 0 1 5 1 2 4 4
3 2 4 4 4 1 3 1 3
0 5 1 2 5 1 5 5 2
   viewboard gravity Board

The "1 annotation tells the j interpreter that we intended the gravity function to work on one-dimensional arrays. When we apply this function to a matrix, the interpreter automatically maps the function over each row.

Let’s apply gravity to our example board to simplify further exploration.

   Board =. gravity Board

Matching tiles

We will first find tile matches in columns (rows of the board representation) and then extend the solution to work on both dimensions.

The core idea is to annotate each tile with the size of the longest run it’s a member of. Let’s fix a specific row (the first board row) and the tile type (4) for now.

   R =. 0 0 2 4 5 4 4 4 2

Let’s isolate the tiles we’re focused on.

   R=4
0 0 0 1 0 1 1 1 0

Our life will be easy if we can replace each 1 with the length of the run in which this element appears. For example, 0 0 0 1 0 1 1 1 0 should become 0 0 0 1 0 3 3 3 0.

There are many ways to achieve this outcome; I will implement it in two passes over the boolean array. In the first pass, we compute the running sum within each run, resetting the counter as soon as we hit zero. In the second pass, we traverse the array backward and replace each item with the maximum within its run.

0 0 0 1 0 1 1 1 0  NB. the original mask
0 0 0 1 0 1 2 3 0  NB. sum items left-to-right within each run 
0 0 0 1 0 3 3 3 0  NB. max items right-to-left within each run

The fold operator is a convenient tool to implement the first scan. We will use its version that accepts three arguments: the initial accumulator value (0), the reduce function (x * (x + y)), and the post-processing step (the identity function, same ]).

   S =. 0 ] F:. {{x*x+y}} R=4
   S
0 0 0 1 0 1 2 3 0

The second scan requires a fold that traverses the sequence in reverse (F::). This time, our reduce function takes the maximum of the accumulator and the current item unless the item is zero ((x>0) * (x >. y)). Since reverse fold produces items backward, we must reverse (|.) its result to get the sequence we need.

   0 ] F:: {{(x>0)*x>.y}} S
0 3 3 3 0 1 0 0 0

   |. 0 ] F:: {{(x>0)*x>.y}} S
0 0 0 1 0 3 3 3 0

Let’s capture our progress in the runs function.

   NB. Given a bool mask, compute the longest run for each item.
   NB. [*+ is a shorter way to write {{x*(x+y)}}.

   runs =. {{ |. 0 ] F:: {{ (x>0) * x>.y }} 0 ] F:. ([*+) y }}"1

We solved the problem for a single tile type in a single row. We must extend our solution to handle each row, column, and tile type. j gives us per-row application for free thanks to the runs rank specification ("1):

   runs Board=4
0 0 0 1 0 3 3 3 0
0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1 0
0 0 1 0 0 1 0 0 0
0 0 0 0 1 0 0 0 0
0 0 0 0 3 3 3 0 0
0 0 0 0 0 0 0 2 2
0 0 3 3 3 0 0 0 0
0 0 0 0 0 0 0 0 0

We handle columns by running runs on a transposed board and transposing the result.

   |: runs |: Board=4
0 0 0 1 0 1 1 1 0
0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1 0
0 0 1 0 0 1 0 0 0
0 0 0 0 2 0 0 0 0
0 0 0 0 2 1 1 0 0
0 0 0 0 0 0 0 1 1
0 0 1 1 1 0 0 0 0
0 0 0 0 0 0 0 0 0

transpose ∘ f ∘ transpose is a special case of the g-1 ∘ f ∘ g pattern Transposition is an involution: it undoes itself. that’s so ubiquitous in mathematics that j defines a convenient operator to express it: under (&.).

   runs &. |: Board=4
0 0 0 1 0 1 1 1 0
0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1 0
0 0 1 0 0 1 0 0 0
0 0 0 0 2 0 0 0 0
0 0 0 0 2 1 1 0 0
0 0 0 0 0 0 0 1 1
0 0 1 1 1 0 0 0 0
0 0 0 0 0 0 0 0 0

We can package the row-wise and column-wise transformations into a single function by taking the maximum of their outputs.

   ((runs &. |:) >. runs) Board=4
0 0 0 1 0 3 3 3 0
0 0 0 0 0 0 0 0 1
0 0 0 0 0 0 0 1 0
0 0 1 0 0 1 0 0 0
0 0 0 0 2 0 0 0 0
0 0 0 0 3 3 3 0 0
0 0 0 0 0 0 0 2 2
0 0 3 3 3 0 0 0 0
0 0 0 0 0 0 0 0 0

To extend the solution to all tile types (not just 4), we generate the list of non-zero tiles (}. i. K), match the board against every type, producing a list of disjoint boolean matrices (Board ="_ 0 }. i. K), compute runs for each matrix, and sum the results.

   +/ ((runs &. |:) >. runs)"2 Board ="_ 0 }. i. K
0 0 2 1 2 3 3 3 1
1 1 2 1 2 2 1 1 1
0 1 2 2 1 2 2 1 1
0 1 1 1 1 1 2 2 2
0 0 1 1 2 1 2 2 2
0 0 0 1 3 3 3 1 1
0 0 0 1 1 3 1 2 2
1 1 3 3 3 3 1 1 1
0 1 1 1 1 3 2 2 1

Comparing the result with the explosion threshold gives us the mask of tiles eligible for explosion.

   3 <: +/ ((runs &. |:) >. runs)"2 Board ="_ 0 }. i. K
0 0 0 0 0 1 1 1 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 1 1 1 0 0
0 0 0 0 0 1 0 0 0
0 0 1 1 1 1 0 0 0
0 0 0 0 0 1 0 0 0
Side by side: the board before the explosion (left) and the mask of tiles eligible for explosion (right).

One last annoyance is that our expression depends on the constant K. We can make it less context-dependent by computing the set of unique positive tile types on the board. The nub (~.) and ravel (,) verbs make it easy.

   NB. compute the set of unique tiles on the board.
   ~.,Board
0 2 4 5 1 3

   NB. leave only positive values.
   (#~ >&0) ~.,Board
2 4 5 1 3

   NB. update the tile matching expression to use the tile types from the board.
   3 <: +/ ((runs &. |:) >. runs)"2 Board ="_ 0 (#~ >&0) ~., Board
0 0 0 0 0 1 1 1 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 1 1 1 0 0
0 0 0 0 0 1 0 0 0
0 0 1 1 1 1 0 0 0
0 0 0 0 0 1 0 0 0

Putting it all together

It’s time to combine the gravity and tile matching into the board update function. This function should find matching tiles, explode them by replacing these tiles with zero tiles, and apply gravity.

The expression from the previous section gives us a mask of all the tiles we need to explode. We implement the explosion by multiplying the board by the inverse of that mask.

   explode =. {{ y * 2>: +/ ((runs &. |:) >. runs)"2 y ="_ 0 (#~ >&0) ~., y }}
   viewboard explode Board
Side by side: the board before and after tile explosion.

Let’s see what happens when we add gravity.

Side by side: the board right after tile explosion and after the gravity action.

Look, there are more tiles to explode now! We shall keep updating the board until it stops changing. Luckily, j gives us a perfect operator for that: converge (^:_) The ^:_ glyph reminds me of a curious chicken lying on the grass and looking at the infinite sky. . We compose gravity and tile explosion using the at operator (@:)

   update =. (explode @: gravity) ^:_

   viewboard update Board
Side by side: the example board after the gravity applied and the stabilized final board.

Before we close, let’s see what happens when we imitate the player’s move by swapping two tiles (the fifth row, the second, and the third columns).

   NB. swaps items in the right arg according to the spec in the left arg.
   swap =. {{ (|. x { y) x } y }}

   viewboard (1 4; 2 4) swap update Board
   viewboard update (1 4; 2 4) swap update Board
Side by side: the stabilized board with two tiles swapped and the updated board after the move.

That’s it! We implemented the core game mechanics with only four lines of code:

gravity =. {{ ((y=0)#y),(y~:0)#y }}"1
runs    =. {{ |. 0 ] F:: {{ (x>0) * x>.y }} 0 ] F:. ([*+) y }}"1
explode =. {{ y * 2 >: +/ ((runs &. |:) >. runs)"2 y ="_ 0 (#~ >&0) ~., y }}
update  =. (explode @: gravity) ^:_

Exercises

If you enjoyed the puzzle and want to spend more time with it, here are a few suggestions on how to keep the fun going: