Bloq is an iPhone puzzle game written in Swift, released in January 2016.
The game works like this: you start with a 4x4 grid of four colors and one open space. The goal is to slide blocks into empty spaces, and when two colors are touching, those blocks will disappear. Try to clear the board in as few moves as possible. When you do, you are treated to a nice confetti animation via the iOS SDK particle emitter class:
The AI, which can solve any configuration in the minimum number of moves (or tell you if a solution is impossible), deserves its own explanation.
First, a broad overview of how it works. I originally wrote the AI in Swift, but this took waaaay too long to solve games (Swift has a lot of overhead in its String class, and I was using Strings to represent game states). Since Objective-C and Swift are built off of C, and C is lightning fast, I ended up writing the AI in C.
If the Swift code requests a solution, it will convert the game board to a string (16 cells in the game → string of length 16 with ‘R’, ‘B’, ‘O’, ‘G’ or ‘.’ to represent blocks/blanks). This string is then passed to the C game-solver.
The AI considers all possible moves from a given state, and the resulting game state after each of those moves. The game is effectively played out thousands of thousands of ways, progressing using a breadth-first search. Think of a program which analyzes the best move to make in a Chess game, and it’s similar to that.
Once the BFS recognizes that it has an empty board, it stops. Due to the nature of BFS, the first blank board encountered is automatically reached in the minimum number of moves. Now, I had to figure out how to go backwards to find the moves made to get to the solution. This was accomplished using a Hashmap of preceding moves from a given move (not easy to implement in C).
The AI is used in the app as a "Hint" button which, when clicked, calculates the optimal 2 moves to make from whatever board configuration you currently have.
As far as creating the levels and difficulty settings… I randomly generated boards and ran the AI on each board. With a list of each board and the minimum number of moves to solve it, I was able to sort the boards based on their minimum number of moves and classify them as "Easy" (7-8 moves), "Medium" (9-10 moves), or "Hard" (11+ moves). The app pulls from this list to generate the next board when you move to the next level:
There is another aspect to the AI as well, a preloaded table of common game boards and their solutions. This is loaded into the app as a Hashmap when it starts up, using a game state string representation as the key and a solution as the value:
The lookup table reduces the probability of the AI having to calculate a solution on-the-fly (although it can do this if no entry is found in the Hashmap), thereby improving user experience.