2
$\begingroup$

I am designing a game solver. I have a binary $m*n$ Matrix, where $0$ stands for a free space, while $1$ stands for an occupied space. In the game we move a ball that we will call $x$. The ball can only move UP, DOWN, RIGHT or LEFT (no diagonal).

Imagine the following matrix:

$ 1 0 0\\ 0 1 0\\ x 0 1 $

We see that the ball is in the lower left corner -- which is "trapped". What efficient algorithm can I use to decide if the ball is trapped, that is if there is no way to get to the other side (like the example given above)?

Another example where the ball is not trapped:

$ 1 0 0\\ 1 0 0\\ x 0 1 $

I am using bits matrices, I would rather not use graphs if possible.

$\endgroup$
3
  • $\begingroup$ Maybe you can find some information here: en.wikipedia.org/wiki/Maze_solving_algorithm $\endgroup$ – miracle173 Dec 23 '15 at 7:04
  • $\begingroup$ You define "trapped" in terms of getting to "the other side" - what exactly does this mean? Should it be able to reach any free space? I ask because in a situation like 0 0 0 0 0 ; 0 0 1 0 0 ; 0 1 0 1 0 ; 0 0 1 0 0 ; x 0 0 0 0, I would say that we can get to the other side despite the isolated free space. $\endgroup$ – Klaus Draeger Dec 24 '15 at 11:34
  • $\begingroup$ @KlausDraeger: This is an interesting case indeed. The game of the game is to explore every single free space. So this board would have no solution and our algorithm should return that "we are trapped" -- although, in that case, my wording finds its limits. $\endgroup$ – Symeof Dec 25 '15 at 17:25
6
$\begingroup$

The problem you're trying to solve is exactly graph connectivity. You don't necessarily need to construct the graph explicitly but this is a graph problem.

By "you don't necessarily need to construct the graph explicitly", I mean that you don't necessarily need to create any new data structures. Every time your graph algorithm says "vertex", you can think "co-ordinates" and every time it says "neighbour" or "adjacent" or "edge", you can think of the squares above, below, to the left and to the right that contain 0.

$\endgroup$
1
  • $\begingroup$ Thank you for your comment -- I see how I can translate a graph algorithm to a matrix algorithm now. What algorithm should I use to decide if the ball is trapped? Because I don't think this is a good idea to have to run the algorithm on every other node... $\endgroup$ – Symeof Dec 22 '15 at 23:10
2
$\begingroup$

From the comments on your post, being trapped means that you cannot reach every free space. You could run a simple depth first search (DFS) or breadth first search (BFS) on x. Each iteration, you would check your neighbors (Up, down, left, right) and check if it is a free space. Each time you visit a node, you could mark it as visited. Once your search has terminated, you could just check if some of the free nodes aren't visited. The worst case time complexity of this would be O(m*n), as you would check every vertex.

DFS

In DFS, you search as deep as you can before returning. Common ways to implement a DFS include a recursive function or a stack. Every iteration, you perform your check to the neighbors and add it to the stack or call your function on the new node.

BFS

In BFS, you search each level. Implementing this is very similar to the non-recursive DFS, but instead of using a stack, you use a queue.

$\endgroup$
1
$\begingroup$

Following from David Richerby answer and your comment, you are right, for this particular problem it is possible to not have to run on every node. But there can be worst cases that force you to visit every node, for example:

0000000
0111111
0000000
1111110
0000000
$x$111111

An algorithm that will prevent visiting every node is to always choose the free space closest to the stopping space. The straight-line distance can be used, which is $\sqrt{(x2-x1)^2 + (y2-y1)^2}$ for two spaces $(x1,y1)$ and $(x2,y2)$. If there are more than one of them then any one is chosen. With this we have the example scenario below on the left:

00089           000000
00670           011111
04500           00000d
23000           101011
10000           $x$0100d

However this algorithm will have an issue with the matrix above on the right. The d means a dead-end. To resolve this issue the algorithm will need to go back to where there was more than one free space, and choose the next non-visited free space closest to the stopping point. A stack can be used to keep track of the path taken, thereby allowing for going back. The travel complexity is O(2nm).

Each time a node is visited it is first checked for whether it was visited before. If the first time, then it is marked as visited and processed. The node (or space) can be marked with a 1 (so is a visited or occupied space). For an array storing the matrix, both marking and checking for if marked will take constant time O(1). For a graph with linked nodes, performance can be improved by using a self-balancing search tree such as the AVL tree. This will enable O(log(nm)) searches and insertions of nodes.

You only know it is a dead-end until you get there (the fun of playing Maze). Notice that the approach of a depth-first-search is used - as deep and close to the stopping point as possible. Performance can be improved if every node in the stack stores a pointer to the last node with a non-visited free space, so that it can directly be jumped onto on going back (violating the pain in playing Maze!)

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.