Maze Solver

Posted: 28 Jun 2009. Tags: java algorithms Katas comments

In my spare time this weekend I wrote a maze solving algorithm which is reminiscent of a program I wrote as homework over a year ago but slightly better. Its still wasteful in terms of efficient moves, but the improvements can come later.

`````` 1      private Point findStart() {
2        for(int y = 0; y < mmazeNodes.length; y++) {
3          for(int x = 0; x < mmazeNodes[y].length; x++) {
4            if(mmazeNodes[y][x].getState() == MazeNode.SlotValue.start) {
5              return new Point(x, y);
6            }
7          }
8        }
9        return null;
10      }
11
12      public void solve() {
13        Point start = findStart();
14        solveRecursive(start.x, start.y);
15      }
16
17      private void solveRecursive(int currentX, int currentY) {
18        if(msolved || !isValidLocation(currentX, currentY)) {
19          return;
20        }
21        if(mmazeNodes[currentY][currentX].getState() == MazeNode.SlotValue.end) {
22          msolved = true;
23          return;
24        }
25        if(mmazeNodes[currentY][currentX].getState() == MazeNode.SlotValue.visited) {
26          return;
27        }
28        if(mmazeNodes[currentY][currentX].getState() == MazeNode.SlotValue.wall) {
29          return;
30        }
31        if (mmazeNodes[currentY][currentX].getState() != MazeNode.SlotValue.start) {
32          mmazeNodes[currentY][currentX].setState(MazeNode.SlotValue.visited);
33        }
34        solveRecursive(currentX+1, currentY);
35        solveRecursive(currentX, currentY+1);
36        solveRecursive(currentX-1, currentY);
37        solveRecursive(currentX, currentY-1);
38      }
39
40      private boolean isValidLocation(int x, int y) {
41        if(x < 0) {
42          return false;
43        }
44        if(y < 0) {
45          return false;
46        }
47        if(y > mmazeNodes.length-1) {
48          return false;
49        }
50        if(x > mmazeNodes[y].length-1) {
51          return false;
52        }
53        return true;
54      }
``````