The full code and documentation is available on Github.
Introduction
Facebook Messenger recently launched Instant Games, a new social gaming platform directly integrated into the Messenger application. However, what should have been a fun competition among friends, quickly became an obsession. Tired of waking up every morning to six new notifications about how my high score in Brick Pop had been bested the night before, I set about doing what anyone else would have done in my position - writing an automated solver.
Mechanics
Brick pop is similar to other tile-matching games like Bejewled and Candy Crush. The games begins with a 10x10 matrix of bricks each assigned one of six colors (red, teal, yellow, blue, purple, and gray). The goal of the game is to remove adjacent bricks with matching colors until no bricks remain on the board. Each time that a brick is removed, the bricks above it fall down. Each time an entire column of bricks is removed, the bricks to their right move left. For example, the screenshot below is of a sample game.
Solver
Because the game is relatively small, its sufficient to provide a brute force solution; even the brute force solution terminates in a handful of milliseconds. The brute force algorithm recursively removes adjacent bricks with matching colors and terminates when no bricks remain or all sequences of removals have been tried. By greedily selecting the largest neighborhood of matching color bricks first, the algorithm is likely to find a maximum score path; however, it is not guaranteed to do so.
- Determine the set of all neighborhoods of similarly colored bricks. Neighborhoods can be determined using a variation of flood fill, and is guaranteed to visit each brick exactly once.
- Sort neighborhoods by size. Removing more bricks at a time produces an exponentially higher score. By greedily selecting the largest possible neighborhood, we ensure that the algorithm earns the highest possible score without having to try all possibilities.
- Remove and recurse. Remove each neighborhood and recursively try to solve the remaining board, until some sequence of removals produces an empty board or until all sequences of removals have been tried. Because it is impossible to solve a board in which there exists exactly one brick of any particular color, we can also stop recursing when this condition is met.
Image Processing
Because manual input of individual brick positions proved to be a extraordinarily difficult task, I wrote some simple image processing code that enables you to upload a screenshot of the game from which brick positions are extracted.
Future Work
It would be cool to simulate iPhone touches which would allow the solver to directly play the game without manual intervention.
Cover photograph by Wallpapers Wide.