Pathfinding: Car Puzzle Game

The project

I made this for an algorithms assignment at Forsbergs, where I had to make a game that an algorithm of my choice could solve. I picked the classic car parking puzzle. The cars sit on a grid and can only slide along their own direction, and the goal is to get one specific car out.

Most of the work went into the solver. I built several levels of different sizes and difficulty to see how it handled harder puzzles.

Finding an algorithm

I started with breadth-first search (BFS). It worked on the small puzzles and gave me a working solver early, but the number of states it had to check grew too fast once the puzzles got harder.

So I switched to my own implementation of A*. It tries the most promising states first, which made it much faster.

After that most of the work was on the heuristic, the estimate of how far a state is from being solved. Mine adds the target car's distance to the exit to the number of vertical cars in its row. Later I added a tie-break, so when two states have the same estimate, the one with the target car closer to the exit is tried first. That gave the solver a big speedup on the harder levels.

Solving the puzzle

Each arrangement of the cars is a state. From a state, the solver generates every valid move and the states those moves lead to.

A* then ranks those states by the number of moves it took to reach them plus the estimate of how many are left:

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;
}

When it finds the goal state, the solver walks back through each state's predecessor to get the full sequence of moves, so the solution can be played back in the game.

Showing the solution

I built the parking lots by hand in the Unity editor. When the solver moves to a new state, the game view rebuilds the cars from that state.

The solution plays back one state at a time with a short pause between each, so you can watch every move.

Result

The heuristic could go further. It could check whether the blocking cars can move at all or are stuck behind other cars, but I decided it wasn't needed for this assignment.

The project gave me practice with search algorithms and heuristics, and with showing an algorithm's result in a game.