BoxWorldSolver attempts to solve a boxworld puzzle by creating a tree of all possible moves for the starting grid. It will then recurse through each resultant grid until a solution is found. This basic algorithm will obviously eventually reach the solution, but is massively exponential in character and requires modification to do so efficiently.
Three techniques are used to modify and improve this algorithm
First and foremost, it is important to detect duplication, where the same grid is reached as a result of a different sequence of moves. Grids are viewed as identical if the same locations are occupied by boxes and the avatar is able to reach the same locations in the grid.
Each grid reached is stored in a normalised form in a hash map. Each grid reached as a result of a move is normalised and the map is checked to see whether the grid has been previously visited.
Each grid is scored to determine how close to a solution the grid is. The score is a quick estimate as to the number of moves that are required to move from this grid to a solution, and hence a score of zero means that we have a solution.
The score is calculated by considering the grid without walls and calculating the minimum number of moves needed to reach the desired solution. This will never result in a higher score than in truth and is more accurate the closer the grid is to a solution. Complete accuracy would require solving the puzzle.
The score of a grid is used to improve the efficiency of the solving algorithm.
The move tree is created by setting a maximum number of moves for the solution as the score of the initial grid. All moves are calculated for the grid and the score of each new grid is calculated. New grids are only recursed if a solution can be reached within the maximum moves (calculated as number of moves so far plus the grid score). If the grid is not recursed, it is marked for retry.
If the tree has been completely traversed without a solution being found, the number of moves is incremented and the tree is tried again until a solution is found.
This has the effect of concentrating efforts on the moves that are more likely to produce a solution.
Some puzzles can be described as involving gates, where blocks that are in one area must move through a particular location in order to reach the area which contains the targets. In this case a more accurate score can be calculated by calculate the score for blocks that are outside the gate as involving a move via the gate.
At the present time, gates are configured for those puzzles to which they apply. A future intended enhancement is for the solver to automatically detect gates through analysis.
A characteristic of these types of games is that it is possible to move blocks into a position from which it is impossible to ever achieve a solution. For example, if a block is move into a corner, it is impossible to ever move the block from that position. If the corner is not a target then it is impossible for this grid to be on a path to a solution.
It is key to the efficiency of the algorithm to detect such situations (referred to as dead grids) and to exclude them from the search.
Each new grid is therefore analysed while calculating it score, and if it is dead is marked as such.
Any move that reaches such a dead grid is immediately discarded as irrelevant, although the grid is retained in the hashmap so that it is not analysed multiple times.
Bad locations are defined as locations where a grid becomes dead as soon as any block is moved there, since it can never be moved away from that location to a location that is not also bad. The initial game grid is analysed at the start of the algorithm to detect such squares and moves that involve moving a block to a bad location are discarded immediately without further analysis.
Limited locations are found in places that are saved from being bad locations by there being a target location within reach. However only a limited number of blocks can be moved here (one for each such target location), and grids are viewed as being bad if this limit is exceeded.
Blocked locations are found where a combination of blocks and walls results in blocks becoming trapped without any possibility of being moved subsequently. An easy example to visualise is the one where a block is placed together with other blocks/walls to make a two-by-two square.
A standard problem in these puzzles is where a block ends up in a situation where it is still moveable, but it is not possible for the avatar to reach a position from which to push the block without causing a dead grid. This situation is not currently detected by the solver, but is a planned future enhancement.
Once a solution has been reached, the maximum number of moves will be reduced to match, but the traversal of the move tree will continue in order to find all possible alternatives. The tree is pruned such that all moves that are not on a path to the solution are discarded.
It then remains to choose the best solution from this set of solutions.
At present the solution chosen is that in which we minimise switching between blocks. An intended enhancement to the algorithm is to change this to minimise the movement of the avatar instead.
