CODEWITHSUNDEEP
javaalgorithm
drewless
drewless

Reputation: 19

How to correctly write a maze algorithm using loops

I am writing a code for a class assignment to get a character through a maze. I have been working on this for hours and I can't figure out what I am doing wrong. The character moves left to right and right to left. Except when I add the code to have the character move around a block if (maze.moveRight() == false), it causes the character to move up and down at the end of each row a bunch of times before it moves the other direction. Also it messes up my count as the character moves across the rows. I feel like I am making it much more complicated than it should be. Can someone help?

Algorithm

  1. The student always starts at the top left corner, that is row and column zero.

  2. The Java logo can be anywhere in the maze, which also contains obstacles shown as "Wrong Way" signs.

  3. You must traverse every row in the maze from top to bottom according to the rules below, until you find the Java logo.

  4. Row and column numbers are zero based, so the first row and column is index 0. the second row and column is index 1, and so on. The number zero is even.

  5. On even rows, you must move left to right using maze.moveRight(), on odd rows, you must move right to left using maze.moveLeft().

  6. After completing each row, use maze.moveDown() to proceed to the next row, until you reach the last row or find the Java logo.

  7. You can detect that you have encountered an obstacle by checking the return value from move methods in the Maze object, true means no obstacle, false means obstacle.

  8. If you run into an obstacle when when moving left to right: Move down, right, right, and up. Adjustment the loop counter for the extra move right!

  9. If you run into an obstacle when when moving right to left: Move down, left, left, and up. Adjustment the loop counter for the extra move left!

  10. Every time you move left or right, not including when avoiding an obstacle, you must call maze.isDone() to see if you have found the Java logo.

  11. When you find the Java logo, you must immediately break out of all loops, and exit the program.

  12. There are mazes that cannot be solved using the algorithm, but we will not test your program with any of them.

public static void main(String[] args) {
    // Create maze
    String fileName = args[1];
    Maze maze = new Maze(fileName);
    System.out.println("Maze name: " + fileName);

    // Get dimensions
    int mazeWidth = maze.getWidth();
    int mazeHeight = maze.getHeight();

    // Print maze size
    System.out.println("Maze width: " + mazeWidth);
    System.out.println("Maze height: " + mazeHeight);

    int r = 0;
    int c = 0;
    // Move commands

    while (c < maze.getWidth() - 1 && r % 2 == 0 && maze.isDone() == false)
    {
        maze.moveRight();
        maze.isDone();
        c++;

        if (maze.moveRight() == false && maze.isDone() == false){
            maze.moveDown();
            maze.moveRight();
            maze.moveRight();
            maze.moveUp();
        }

        if (maze.isDone() == true){
            System.exit(1);
        }
    }

    while (c == maze.getWidth() - 1 && r % 2 == 0 && maze.isDone() == false)
    {
        maze.moveDown();
        maze.isDone();
        r++;
    }

    while (c != 0 && c <= maze.getWidth() -1 && r % 2 != 0 
      && maze.isDone() == false){
        maze.moveLeft();
        maze.isDone();
        c--;

        if (maze.moveLeft() == false && maze.isDone() == false) {
            maze.moveDown();
            maze.moveLeft();
            maze.moveLeft();
            maze.moveUp();
        }

        if (maze.isDone() == true){
            System.exit(1);
        }
    }
}

Upvotes: 1

Views: 3001

Answers (2)

user3056052
user3056052

Reputation: 1467

Ok so a few problems you are only moving down on the right wall.

You aren't updating your row column counters when you are navigating hazards.

You should be testing the results of every move and isDone method call and breaking or updating your counters accordingly.

Also you shouldn't be updating your counters as you do outside an if statement associated with a move test method call.

Upvotes: 1

CodeMonkey
CodeMonkey

Reputation: 1835

I'm having a hard time following what your intent is and thus what the problem is. Perhaps it's due to lack of understanding of how this maze is set up. I also don't know the scope of the class so I don't know if this is above your current level or not, but here goes how I would personally implement a maze solver:

For each position in a maze that I find myself, I would create a maze "space" object. This object will keep track of remaining options of directions to be traversed and whether or not I have visited that space. If I can turn left and right, I would create new spaces for both, pick one direction, and mark only that one direction to say I've been there. When I reach a dead end, I will turn around until I find a choice of direction to go. If I've not visited a direction, I'd take that. Otherwise, If I've visited all ways, I would call a recursive function to determine if there are any directions available along down any of the paths I've taken previously.

So it's creating objects, using recursion, and flagging an object for whether or not I've been there. (you'd also need a flag to indicate if your recursive algorithm has checked a square as well lest you find yourself in an infinite loop).

Hopefully that's within the constraints of the assignment! Otherwise, we may need more information as to what the limitations are and the true scope of the assignment.

Upvotes: 1

Related Questions