Search code examples
algorithmpathcollision-detectioncollision

Algorithm to find solution to puzzle

I am trying to make a game where a player has 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 programmatically 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.

Solution

  • 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.