Algorithm to find solution to puzzle.

Question

Hello!

I am trying to make a game where a player have to find his way from Start to End on the Game Board.

As you see this Game Board contains a bunch of red circular obstacles. To win the game the player has to remove a minimum amount of obstacles. So my question is, how do I programatically find out the minimum amount of obstacles to remove, to free a path? A free path would be considered the space between, circles not overlapping and not touching.

So what I really need is the minimum amount of circles to remove, I don't need the actual path. Is there an easy way to do this?

And to supplement understanding of this game board, the circles each have the same radius, and it is restricted by the black lines.

Also it is not necessary to move in a straight line.

Answer 1

One option is to first remove those circles with the most numbers of overlap or touches. After each one you remove, check if its a solution, if not continue removing.

var circle;
circle = findMostOverlapCircle();
while(circle != null) {
    circle.remove();
    circle = findMostOverlapCircle();
}

Answer 2

It is a graph theory maximum flow problem.

Suppose that every circle is a node in the graph. Additionally introduce 2 special nodes: TOP and BOTTOM. Connect circles with these nodes if they intersect with TOP/BOTTOM side. Connect nodes corresponding to circles with each other if the circles intersect.

Now you need to find a minimum cut in this graph, having TOP as source and BOTTOM as sink or vice versa. You can use Max-flow_min-cut_theorem to solve it. What it states is that Minimum-cut problem is equivallent to Max-flow problem. You can find details on how to solve Max-Flow problem on TopCoder.

As we can go through each node only once, we should convert the nodes into a directed edge of capacity one with in-node and out-node for each circle. The max-flow algorithm will solve the problem on the resulting graph and take into account the fact that we are removing circles rather than connections between circles. It is always a better decision for this problem to remove a node in a graph rather than edge, as we can always remove any edge by removing a node. Removing a node additionally can result in removing more than one edge.

By the way, a similar problem can be found on Uva Online Judge. It a good idea to try solve this task on the judge, then you will be sure that your solution is correct.

Answer 3

For a graph translation, something like this might work.

Make a wall(the blue lines) between two circles if they overlap. Don't forget to add in the top and bottom border as well. This creates a couple of regions. These will be all the nodes of the graph.

Next we have to find the edges, the cost of going from one node to another. Take two neighbour regions (sharing a wall.) Then by brute force, or what ever clever method you come up with, determine the cost of moving from this region to the other. If you remove a circle, that means, you remove all the walls that go to that circle. If this makes the two regions into one region, the cost of the edge is 1. If you need to remove two circles(all the walls they have) to combine the two regions, the cost is 2. Etc.

Some of the edges(green) are drawn. We have to go from the start region, to the end region. You now got a everyday weighted graph.

I think this can be improved a lot, but I leave that as an exercise =)

In this case minimum is 3.

Warning, picture is drawn by hand, I did forget a few walls, edges and regions. For illustration purposes only.

Answer 4

In trying to visualize what Leonid wrote, I made the following diagram.