I. What is Flux?

One of my favourite games growing up was a block destruction game called Flux created by MasterWorks. You have to clear a grid of colored blocks by clicking on groups of two or more adjacent blocks of the same color. The goal is to remove as many blocks as possible and you even get a bonus for clearing all the blocks from the screen.

Now, here’s how you play. Every time you remove a group of blocks, all the blocks on top will fall vertically down into place. So, you have to think ahead and plan your moves carefully, because if you remove blocks haphazardly, you could end up with a bigger mess on your hands and you’ll miss that juicy multiplier bonus for clearing the screen.

And if you think that the retro explosion sounds are amazing, it gets even better! You can add special bombs that can blow up larger groups of blocks in case you missed a few straggling blocks.

And the game designers didn’t stop there. There are also different game modes, like puzzle mode where you have to clear a specific set of blocks, or classic mode where you have to reach a high score in a limited number of moves.

So, that’s Flux in a nutshell! It’s a simple concept, but with a ton of depth and strategy. I’ve was playing it for years and even studied for high school exams with the game open so I can listen to the music in the background. If you haven’t tried it yet, I highly recommend it. But beware, it’s highly addictive!

It’s not compatible with most modern Windows systems anymore but you can find a fan copy of it at http://flux.samspel.io/

II. A Flux Solver?

I’ve always been fascinated by how computers can solve problems that humans find difficult, so I decided to tackle the challenge of creating a program to help me find the easiest way to clear the Flux board.

The first step was to create a digital representation of the game board and the blocks. I had to write code to accurately track the state of the game and simulate the different moves that can be made.

Once I had the game board set up, I had to write the algorithms to actually solve the game. This was the most challenging part of the project. I tried different approaches, like a brute force algorithm that tried every possible move, but that quickly became too slow and impractical.

In the end, I settled on some heuristics and used a best-first search to solve the game. The heuristics helped guide the search by prioritizing moves that were more likely to lead to a solution, while the best-first search explored all possible moves until we found an optimal solution.

The results were impressive. My program was able to solve the majority of levels in a matter of seconds, and even some of the hardest levels in just a few minutes.

So, that’s my journey to create a solving program for Flux. It was a fun and challenging project, and I learned a lot about game algorithms and problem solving along the way. If you’re interested in computer science and puzzle games, I highly recommend giving it a try.

If you want to more details about my journey to building the solver from the start, read on!

III. The Struggle is Real

Like any good engineer, we first start with tackling the problem by ourselves. This will give us a feel for how the blocks interact with each other and we can see the constraints of the problem better.

Even though I’ve played this game many times before, it doesn’t hurt to do a little more research… Three hours later and I keep getting stuck.

It’s time to start working on the solver.

IV. The Eureka Moment

If we tackle the game with all the features set up with 4 varieties of blocks as well as bombs, we can be easily overwhelmed by the problem because of how complex it is. A much better way is to find the smallest and simplest version of the game.

When you have a grid that is empty, we know that we have solved the problem without any moves. It seems trivial to mention it, but it’s important to us when we’re writing the code because we’ll be looking for this event as a “base case” so that we know when to stop our search.

The next step is to find a next step up - a grid with two blocks. If they are different colors, we have no clusters to pick from and reach a dead end. If they are the same color, we now have an action to pick - pop the cluster and get to the clear screen.

Now we make these grids bigger and bigger until we can see a pattern emerging from the decisions we make. Eventually, we see that every cluster we destroy, will result in a new, but smaller grid state that we have to solve the same way again.

In the end, the game can be thought of in this way:

• Every state that the grid can take, there are X number of clusters that we can choose from.
• Once you have chosen a cluster, a new grid state appears.
• If it’s not empty, then you’ll have Y clusters to choose from.
• Keep doing this until you have no more clusters left.

Once we realised that this is the path we’re going to take with our program, we can start thinking about the different parts of the solver we need to build to get it working.

• How do we model the grid?
• How do we simulate the tiles dropping?
• How do we find the clusters?
• How do we pick the next best move?
• Which search algorithm should we try for this problem?
• How do we know if there’s no solution?

V. Coding Adventure

We’re using more Python to build this solver!

How do we model the game?

The state is just a snapshot of the game at any given point in time. It only changes when we’ve popped one set of clusters.

We can log the location of each block by using a 2D grid and calling out which row and column they are in. We can create the grid easily using a 2D array like this:

grid = [
    [1,1,1],
    [2,2,2]
]

However, if we wrap this up in a numpy ndarray, we can harness some pretty neat functions for row and column manipulation like insertion, deletion, flipping the grid etc.

import numpy as np

initial_state = np.int_(np.array([
    [1,1,1],
    [2,2,2]
]))

The grid is an M x N array which means we have M rows and N columns. The grid would need to be manually entered.

How do we find the clusters?

For each state, we need to know the available clusters we can choose from.

We can do this by writing a program that iterates through each cell to check for adjacent blocks.

First, let’s write it for one coordinate. The function should work like this: Given a row and a column number, return the set of blocks that belong to the cluster.

current_cluster = get_cluster(grid, coord.row, coord.col, value, set())

def get_cluster(state, row, col, value, reached):
    if row < 0 or row >= ROW_COUNT:
        return {}
    if col < 0 or col >= COL_COUNT:
        return {}

    if state[row][col] != value:
        return {}

    coords = Coordinate(row, col)
    if coords in reached:
        return {}

    reached.add(coords)

    up = get_cluster(state, row - 1, col, value, reached)
    reached.update(up)

    down = get_cluster(state, row + 1, col, value, reached)
    reached.update(down)

    left = get_cluster(state, row, col - 1, value, reached)
    reached.update(left)

    right = get_cluster(state, row, col + 1, value, reached)
    reached.update(right)

    return reached

For each of the up, down, left and right directions, we look for the cluster and add it to set.

We have a few base cases here. Rows and columns should be within the boundaries of the grid. Negative values or values bigger than the row and column count are invalid coordinates so we should return an empty set.

The reached variable holds remembers all the tiles that we’ve seen so we don’t need to double back.

Now that we have a function that can return a cluster, we can get all the available clusters from this method:

def get_moves(grid):
    state_shape = np.shape(grid)
    rows = state_shape[0]
    cols = state_shape[1]

    indices = []
    for i in range(0, rows):
        for j in range(0, cols):
            indices.append(Coordinate(i, j))

    cluster_list = []
    indices = set(indices)
    while len(indices) > 0:
        coord = indices.pop()
        value = grid[coord.row][coord.col]
        if value == 0:
            continue
        current_cluster = get_cluster(grid, coord.row, coord.col, value, set())
        cluster_list.append(current_cluster)
        indices.difference_update(current_cluster)

    return cluster_list

We start by creating a coordinate for every cell in the grid and store it in a list indices. Then, iterate through the list looking for all the coordinates that belong to the cluster connected to that position. Once the cluster is returned, we remove all of the coordinates in that cluster from indices. The remaining coordinates are still yet to be clustered.

If we keep pulling out more coordinates from indices, eventually it will be empty and we’ll have a list of clusters.

How do we simulate the tiles dropping?

When we want to simulate popping a cluster, we set each block’s value on the grid to 0. We then run the simulation to drop suspended tiles in the air and clean up any empty columns.

    def pop(self, cluster):
        for node in cluster:
            self.grid[node.row][node.col] = 0
        self.run_simulator()

    def run_simulator(self):
        self.bubble_up()
        self.clear_empty_cols()
    
    def bubble_up(self):
        for c in range(0, COL_COUNT):
            col = self.grid[:, c]
            nonz = col[col > 0]
            zeroCount = ROW_COUNT - np.shape(nonz)[0]
            sorted = np.append(nonz, np.zeros(zeroCount))
            self.grid = np.delete(self.grid, c, 1)
            self.grid = np.insert(self.grid, c, sorted, 1)

    def clear_empty_cols(self):
        idx = np.argwhere(np.all(self.grid[..., :] == 0, axis=0))
        column_count = len(idx)
        zeros = np.zeros((ROW_COUNT, column_count), dtype=int)
        self.grid = np.delete(self.grid, idx, axis=1)
        self.grid = np.append(self.grid, zeros, axis=1)

Which search algorithm should we try for this problem?

We will try for the best first search algorithm. Although later, I might try an A* search.

With heuristics, we can use them to compare different states. It will help us determine which of the nodes on the frontier is closest to our goal state.

I tried a couple of different ones:

• Number of clusters left
• Number of zeros

I had some issues with Python’s class methods causing funny results when implementing the number of clusters heuristic. Using the number of zeroes was a simpler implementation. With numpy we can use the count_nonzero() method to check how many zeroes are in the array. The method evaluates self.grid == 0 into a boolean. If we get a True then the value is treated as a “non-zero”.

    def zero_count(self):
        return np.count_nonzero(self.grid == 0)

We can then use this to sort out our frontier list as a priority queue zero.

def greedy_best_first_search(node):
    frontier = [node]

    while len(frontier) != 0:
        frontier.sort()
        best = frontier.pop(0)
        expansion_nodes = best.expand()
        if not best.state.grid.any():
            return best

        frontier.extend(expansion_nodes)

    return None

VI. The Big Reveal

Here is the solver in action! I was able to solve the puzzle using 2 type blocks and even 3 type blocks.

VII. Reflections and Lessons Learned

Learning Python

This exercise was my introduction into using the numpy package. I’m sure there are much more advanced uses of it. I only got to touch some of the ndarray operations here.

Improvements

The reason why 4 block type puzzle took too long is because of the branching factor. I think if we used an A* search to prune away some unnecessary searches, we can make the search space a bit faster. Also, I don’t think the recursive cluster matching is the most efficient way. I just wanted it to be good enough to work for small problems before optimising.

Search Algorithms Extra

If you want to find out more of my journey into search algorithms, here are my other blog posts

• Best first search
• Breadh first search
• Depth first search

You can find the full code at my Github