Finding an optimal solution in a tile painting game

Question

The Problem

Find the shortest sequence of moves that makes up the optimal solution of a level. If there is more than one optimal solution, just find one of them.

Game Rules

The game level is made up of two types of tiles: walls and floors. The player's task is to paint the whole level using a ball that can be moved in four directions (up, down, left, right). When a direction is chosen, the ball will move in the indicated direction until it hits the wall (it cannot be stopped midway).

The tile the player starts on is automatically painted at the beginning of the game.

There are many games of this type on the Google Play store like Amaze! by Crazy Labs or Roller Splat! by VOODOO.

Here's one you can play in a browser.

Example

Here is an example of a very simple game level.

The optimal solution requires 3 moves: ↓, →, ↑.

Helper Graph

For each level it is possible to create a graph showing in which positions the player can find themselves after a move and in which directions they can move the ball.

For the level above, the graph looks like this, where S is the initial position.

This is how a graph looks overlaid on a level.

These graphs are directional, you can't always go directly back to the previous position.

In the example below, if the player moves the ball to the right and then moves left, they will find themselves at a different vertex of the graph than the initial one.

Solution attempt

The simplest solution is to search all possible paths and choose the shortest one. The maximum length of the solution must be limited to avoid an infinite loop.

Using the DFS algorithm, search through all possible paths:

1. Starting from the spawn position, branches are created to look for a solution in every possible direction.
2. A branch reaches a vertex of the graph, chooses one of the possible directions to go and continues exploring. From the same vertex new branches that will look for a solution in every other possible direction are created.
3. When a branch passes through all the floor tiles of the level, it ends its exploration. The solution found is saved if it is better than the previous best solution.
4. If the length of the branch's solution exceeds the length limit, it gets disposed of.

This algorithm allows to find a solution of levels, but only with a length limit of no more than 12 steps. The complexity of this solution is O(3^n) (because after each step there may be 3 directions to choose from).

By applying a number of optimisations, the computation time for this algorithm can be significantly reduced.

Optimisations

1. Marking unidirectional vertices as fully visited.
   If a vertex has only one edge, we can be sure that once it has been visited once, it will definitely not need to be revisited.

2. Mark vertices with fully visited neighbours as fully visited.
   Edges leading to fully visited vertices need not be taken into account when choosing the next solution step. If a vertex has only one edge that does not lead to fully visited vertices, it can be treated as unidirectional, i.e., it can be marked as fully visited.

3. Removing unnecessary loops.
   If the branch finds itself in a previously visited vertex, and has not painted any additional tiles since visiting it, the solution is bound to be suboptimal. This is the most effective of the presented optimisations, it reduces the number of branches needed to find a solution by 5-30 times, depending on the level layout.

4. Removing branches that are too long.
   Branches longer than the current best solution found can be discarded.

Applying these optimisations allows us to find a solution for levels requiring up to 20 steps (which take about 5 minutes to compute on my computer). Extending the maximum length by each additional step increases the number of branches needed by 1.2 to 2 times (depending on the level layout).

Suggested further optimisations

Further optimisations can be added to this approach, e.g:

1. Using Tarjan's algorithm to split the level into strongly connected components. Once all the floor tiles in a connected component have been painted, the whole component can be marked as fully visited.

2. Earlier discaring of branches that have no chance to paint all remaining tiles in fewer moves than the current best solution.

Certainly such optimizations would speed up the algorithm, but will not overcome its geometrically increasing complexity.

Can you propose a different approach, that could find the optimal solution with a lower complexity, or another optimization that can speed up this approach?

Answer 1

This is the Hamiltonian path problem on partial grid graphs (i.e., graphs which are arbitrary subgraphs of grids) which is known to be NP-complete. Thus, no polynomial algorithm exists unless P = NP.

A good bet here would be to try heuristics and (exact) algorithms designed for Hamiltonian path. In particular, if you model the problem as an instance of Boolean SAT, feed it to a state-of-the-art SAT solver, you might be amazed.