I am trying to write an algorithm solving a type of maze. It could look something like this:
The player character is the red circle and the goal is to collect all the blue squares. The player can move up, down, left or right but only stops when hitting a wall. I start by converting the maze into a graph(going space by space and finding to which other space I can move from there). The blue squares become attributes of the edge(path between one point and another). Now I need an algorithm that will find the shortest path that goes through all the edges with a blue square. I hope someone can help.
Advertisement
Answer
Here’s how I’d model the problem:
Let’s create a directed graph with nodes corresponding to the cells with blue square, and one additional node which is the initial position of the player(red dot). Let’s create an edge between every pair of nodes A and B with weight equal to the Manhattan distance between them (number of steps to reach each other in the grid), so both edges from A to B and from B to A have the same weight except edges between the node that corresponds to the player’s initial position (Let’s call it X) and blue squares, the edges from X to all other nodes are built in the same way mentioned before, but edges from all nodes to X must have weights equal to 0, because we don’t have to actually return to the initial position, we only need to pass through all blue squares and finish at any position.
Now your problem becomes a well known problem called TSP (Traveling Salesman Problem), the problem asks to find a Hamiltonian cycle of minimum weight, a Hamiltonian cycle is a cycle that starts at some node and passes through all nodes exactly once, the weight of the cycle is the sum of edge weights between nodes in it.
There’s a bruteforce solution to the problem where you iterate through all possible permutations of nodes and pick the one that gives the minimum weight. This solution runs in O(N!).
Another solution to this problem is using dynamic programming with bitmasking, which runs in O(2^N * N^2).