I am having a problem with a algorithm that is designed to solve mazes. I used an algorithm from here. http://www.cs.bu.edu/teaching/alg/maze/ FIND-PATH(x, y) if (x,y outside maze) return false if (x,y is goal) return true if (x,y not open) return false mark x,y as part of solution path if (FIND-PATH(North of x,y) == true) return true if (FIND-PATH(East of x,y) == true) return true if (FIND-PATH(South of x,y) == true) return true if (FIND-PATH(West of x,y) == true) return true unmark x,y as part of solution path return false It is a recursive solution , i modified it such that it will continue even after finding exit so that it can find other solutions as well. It seems to work , just that it seems to find half the total number of solutions that i know are possible. if (x,y is goal) return true is changed to return false. Anyone know what might be the problem with such an algorithm resulting in half the number of total possible solutions? I also have a problem into finding the total number of dead end paths, any suggestions on that?

Problem with Maze Algorithm

Answers (5)

Reputation: 3859

I tried making a simple-minded implementation of the algorithm in java. My conlusion was that the algorithm you described works, even for finding multiple paths. Or, possibly, you managed to think of a more clever test case than me. (Please post your maze so I can try my algorithm on it)

My implementation of the dead end counter is probably not the most efficient one, but it gets the job done. For each current OPEN node that is visited, it checks the 4 surrounding nodes:

If at least one neighbour is OPEN, current node is not a dead end
If more than one neighbour is VISITED current node is not a dead end
If only one node is VISITED (the one we came from in the previous step) and no other neighbour is OPEN, current node is a dead end

This is the java code I wrote (beware! pretty long). An alternative would be, if you wish, to store the path on a stack, pushing a node each time it is set to VISITED and popping a node each time it is set back to OPEN. Each time the GOAL is reached, the stack holding the current path should be copied and saved.

If the if block marked with a comment as "dead-end-investigation-step" is removed, this implementation is almost exactly equal to the one described in the question.



package test;

import java.util.HashSet;
import java.util.Set;

public class MazeSolver {

final static int OPEN = 0;
final static int WALL = 1;
final static int GOAL = 2;
final static int VISITED = 3;

static int[][] field = { { 0, 0, 0, 0, 0, 1 }, { 1, 0, 1, 1, 0, 1 },
        { 1, 0, 1, 0, 0, 0 }, { 0, 0, 0, 0, 1, 2 }, { 1, 0, 1, 0, 0, 0 } };

// This is what the field looks like:
//  
// 0 1 1 0 1
// 0 0 0 0 0
// 0 1 1 0 1
// 0 1 0 0 0
// 0 0 0 1 0
// 1 1 0 2 0

static int width = field.length;
static int height = field[0].length;
static int xStart = 0;
static int yStart = 0; // Initiated to start position: (x = 0, y = 0)
static int nrSolutions = 0; // Records number of solutions

// Used for storing id:s of dead end nodes.
// The integer id is (x + y * width)
static Set<Integer> deadEnds = new HashSet<Integer>();

public static void main(String[] arg) {
    System.out.println("Initial maze:");
    printField();

    findPath(xStart, yStart);

    System.out.println("Number of solutions: " + nrSolutions);
    System.out.println("Number of dead ends: " + deadEnds.size());
}

private static void findPath(int x, int y) {

    if (x < 0 || y < 0 || x >= width || y >= height) { // Step 1
        return;
    } else if (field[x][y] == GOAL) { // Step 2
        nrSolutions++;
        System.out.println("Solution nr " + nrSolutions + ":");
        printField();
        return;
    } else if (field[x][y] != OPEN) { // Step 3
        return;
    } else if (isDeadEnd(x, y)) { // Extra dead-end-investigation-step
        int uniqueNodeId = x + y * width;
        deadEnds.add(uniqueNodeId); // Report as dead end
        return;
    }

    field[x][y] = VISITED; // Step 4

    findPath(x, y - 1); // Step 5, go north
    findPath(x + 1, y); // Step 6, go east
    findPath(x, y + 1); // Step 7, go south
    findPath(x - 1, y); // Step 8, go west

    field[x][y] = OPEN; // Step 9

    // Step 10 is not really needed, since the boolean is intended to
    // display only whether or not a solution was found. This implementation
    // uses an int to record the number of solutions instead.
    // The boolean return value would be (nrSolutions != 0)
}

private static boolean isDeadEnd(int x, int y) {
    int nrVisitedNeighbours = 0;

    if (y > 0) { // If northern neighbour exists
        if (field[x][y - 1] == VISITED) {
            nrVisitedNeighbours++;
        } else if (field[x][y - 1] != WALL) {
            return false;
        }
    }
    if (x < width - 1) { // If eastern neighbour exists
        if (field[x + 1][y] == VISITED) {
            nrVisitedNeighbours++;
        } else if (field[x + 1][y] != WALL) {
            return false;
        }
    }
    if (y < height - 1) { // If southern neighbour exists
        if (field[x][y + 1] == VISITED) {
            nrVisitedNeighbours++;
        } else if (field[x][y + 1] != WALL) {
            return false;
        }
    }
    if (x > 0) { // If western neighbour exists
        if (field[x - 1][y] == VISITED) {
            nrVisitedNeighbours++;
        } else if (field[x - 1][y] != WALL) {
            return false;
        }
    }

    if (nrVisitedNeighbours > 1) { // Circular path scenario
        return false;
    }

    return true; // The exhaustive result of this check: this is a dead
    // end
}

private static void printField() {
    for (int yy = 0; yy < field[0].length; yy++) {
        for (int xx = 0; xx < field.length; xx++) {

            System.out.print(field[xx][yy] + " ");
        }
        System.out.println();
    }
    System.out.println();
}
}

The algorithm above reports four different solution paths and two dead ends to the example maze which is hardcoded into the code.

<EDIT> Might the reason for why you get too few solution paths be a misinterpretation of what is a solution path? For example, consider this maze:

######
##   #
## # #
#S   #
##E###
######

This maze has only one valid solution path. This is because you are only allowed to visit each node once, so going around the circular path is not a valid solution path since that would visit the node east of S and north of E twice. This definition of a solution path is implied by the algorithm that you use.

If one were to allow visiting the same node multiple times, there would be infinitely many solutions, as you could go around the circle 1, 2, 3 ... to infinitely many times. </EDIT>

<EDIT2>

Exactly as you say, I increase the pathLength each time I set a node to VISITED, and decrease the path length each time I set a VISITED node back to OPEN.

To record the shortest path length I also have a shortestPath int value which I initiate to Integer.MAX_VALUE. Then, each time I have reached the goal, I do this:

if(pathLength < shortestPath){
    shortestPath = pathLength;
}

As for the dead ends... I tried counting them by hand and I thought 9 seemed right. Here is the maze posted by Sareen, but with the dead ends marked (by hand) with a D:

####################
#S # D#      D#D  D#
#  # ##  ##  ### ###
#     #   #   #    #
## #  #   #     ## #
#     ### #####    #
# #   #D  #D #   ###
# ### ### ## # #####
# D#D     #D      E#
####################

Can you find any more? Or did I misinterpret what you meant by dead end? I thought dead end means: A node to which you can only come from one direction.

Example 1:

######
## ###
## ### 
## ### 
#S  E#
######

The maze above has one dead end.

Example 2:

######
##  ##
##  ## 
##  ## 
#S  E#
######

The above maze has no dead ends. Even if you are at one of the accessible nodes furthest to the north, there are still two adjacent non-WALL squares.

Do you have another definition of dead end? </EDIT2>

Upvotes: 0

Sareen

Reputation:

This is a sample maze

####################
#S #  #       #    #
#  # ##  ##  ### ###
#     #   #   #    #
## #  #   #     ## #
#     ### #####    #
# #   #   #  #   ###
# ### ### ## # #####
#  #      #       E#
####################

Upvotes: 0

seanyboy

Reputation: 5693

Rather than trying to find one way through the maze, you need to find (and therefore map) multiple ways through the maze.

In order to do this, you need to mark where you've been (on a particular path). If you reach a point you've already been to, you need to flag that route as a dead end.

A recursive function is still the way to go, but make sure that you pass the (placesIhaveBeen) structure through the recursive function.

The recursive loop needs to break when you get to a point where N,S,E,W are all blocked. (You've been there before, you can't go in that direction, it's outside the maze) The recursive loop also needs to break when you reach your target.

If you get to your target - increase a Global Variable by one. If you've nowhere to go - increase your dead-ends by one.

I can't write the pcode for this (it'll take too long), but I believe that the secret is in a function that returns true if N, S, E and W are all blocked.

Addition to my initial answer

With regard to why I treat areas I've been to as "blocked", and why I treat them as dead ends....

      ########
      #      #  
      # #### #
####### #  # #
        #  # #
####### #  # #
      # #### #
      #      #  
      ########

I would classify the above maze part as a dead end, and I can't see how I can identify it as such without treating places I've been to as blocked areas.

I realise that this would cause the following to also show dead ends, but I can't see a way around it.

      #######
      #     #  
      # ### #
####### #G# #
        # # #
####### #   #
      # ### #
      #     #  
      #######

Upvotes: 1

Erich Kitzmueller

Reputation: 36987

For the number of dead ends, you need something like that:

3.5 if (North of x,y not open) and (South of x,y not open) and (West of x,y not open) and (East of x,y not open) deadends++

Upvotes: 0

Toad

Reputation: 15925

what seems to be missing is the check if X&Y has already been marked as part of the solution, and if so we abort. (this should be somewhere on point 3.5)

If not a maze with a possible loop somewhere would run indefinately and blow up the stack

by the way, from what I read the algorithm is based on a maze with only 1 solution

Upvotes: 2

Problem with Maze Algorithm

Answers (5)

Related Questions