Pathfinding: Car Puzzle Game

The Project

This project was made as part of an assignment at Forsbergs where I had to create a game that could be solved by an AI algorithm of my choice. I chose a classic car parking puzzle, where the goal is to move the cars around a grid and free a specific car using as few moves as possible.

The main focus of the project was not just making the puzzle playable, but building a pathfinding system that could actually solve it efficiently. I created several levels with different sizes and complexity to demonstrate how the algorithm handles increasingly difficult puzzles.

Finding a Pathfinding Algorithm

I started by experimenting with Breadth-First Search (BFS). It worked well on smaller puzzles and was useful for getting a working solver in place, but the number of states it had to explore grew too quickly as the puzzles became more complex.

I therefore switched to my own implementation of A*. This gave me much better performance by prioritising states that appeared more promising instead of exploring every possible state equally.

A large part of the work was then refining the heuristic used by A*. The solver estimates how costly a state is based on factors such as the distance between the target car and the exit, as well as the number of cars obstructing its path. I experimented with ways of making this estimate more accurate so that the algorithm could avoid spending time exploring paths that were unlikely to lead to an efficient solution.

Solving the Puzzle

Each possible arrangement of the cars is treated as a state. From a given state, the solver generates the valid moves the player could make and uses these to build the search tree.

A* then evaluates these states using the cost of reaching the state combined with the estimated cost of reaching the solution:

public static IEnumerable<State> AStarSearch(State start)
{
    PriorityQueue<State, State.DistanceToGoal> todoPaths = new(); // define a queue of paths:
    Dictionary<State, State> predecessors = new();
    Dictionary<State, int> costs = new();
    costs.Add(start, default);
    todoPaths.Enqueue(start, default); // enqueue the starting node path:

    while (todoPaths.TryDequeue(out var currentState, out _))
    {
        var currentCosts = costs[currentState];
        foreach (var neighbour in currentState.GetNeighbours())
        {
            if (costs.TryGetValue(neighbour, out var neighborCosts) && neighborCosts <= currentCosts + 1)
                continue;

            if (neighbour.IsWin())
            {
                predecessors[neighbour] = currentState;
                var newPath = BuildPath(predecessors, neighbour); // build path (run through all predecessors)
                return newPath;
            }

            predecessors[neighbour] = currentState;
            costs[neighbour] = currentCosts + 1;

            var distanceToGoal = neighbour.EstimateDistanceToGoal();
            distanceToGoal.costs += currentCosts + 1;
            todoPaths.Enqueue(neighbour, distanceToGoal);
        }
    }

    // no path found
    return null;
}

Once the goal state is found, the solver can reconstruct the sequence of states needed to reach it. This makes it possible not only to find a solution, but also to play that solution back in the game.

Presenting the Solution

The parking lots themselves were constructed manually in the Unity editor. When the solver moves from one state to another, the game view rebuilds the cars from that state so the solution can be displayed to the player.

The final solution is played back by iterating through the states found by the solver with a short pause between each one. This makes the algorithm's result visible as an actual sequence of moves rather than just presenting the final answer.

The gif above shows how the solved states are presented in-game.

Result

The final result is a small but complete demonstration of A* pathfinding applied to a puzzle with a large number of possible states. The biggest improvement throughout development came from moving away from BFS and refining the heuristic used by A*, which allowed the solver to handle larger puzzles much more efficiently.

There are still ways the heuristic could be made more sophisticated, for example, by taking into account whether blocking cars themselves are able to move or are blocked by other cars, but I decided that the additional complexity was not necessary for the scope of the project.

The finished project gave me practical experience with search algorithms, state representation, heuristics, debugging algorithmic behaviour, and turning the result of an algorithm into something that can be visualised and interacted with in a game.