Find all possible paths through a maze

Question

I'm trying to create a program that will traverse a randomly generated maze where 1's are open and 0's are walls. starting in the top left and ending in the bottom right. The path can go up, down, left, and right.

Currently, my program gives me a solution, but I'm having trouble getting it to print more than one path.

I've read several different versions of this problem, but I'm unable to find one quite with my parameters.

Here's my code, I omitted the part where I randomly generate my maze.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <stdbool.h>

int  n, minMatrix, solIndex = 1, minLen = 10000000; //I use the latter 3 variables in order to find the shortest path, not relevant for now


bool solveMaze(int mat[n][n],int x, int y, int sol[][n], int count){

int i, j;
  if((!(x >= 0 && x <n  && y >=0 && y < n)) || mat[x][y] == 0 || sol[x][y] == 1){
    return false;
  }

  if(x == n-1 && y == n-1){
    sol[x][y] = 1;

    printf("Solution %d is:\n", solIndex);
    for(i = 0; i < n; i++)
    {
      for( j=0;j<n;j++)
      {
        printf("%d", sol[i][j]);
      }
      printf("\n");
    }

    if(count<minLen)
    {
      minLen = count;
      minMatrix = solIndex;
    }
    solIndex +=1;
    sol[x][y] = 0;
    return true;
  }

  sol[x][y] = 1;

  if(solveMaze(mat, x+1, y, sol, count+1)){
    return true;
  }

  if(solveMaze(mat, x-1, y, sol, count+1)){
    return true;
  }

  if(solveMaze(mat, x, y+1, sol, count+1)){
    return true;
  }

  if(solveMaze(mat, x, y-1, sol, count+1)){
    return true;
  }
  sol[x][y] = 0;
  return false;

}

I've omitted the part of my main where I randomly generate my maze.

int main(){

if(!solveMaze(**mat, 0, 0, sol, 0)){
    printf("No possible paths, run program again\n");
  }
  else{
    printf("the shortest path is %d\n", minMatrix);
  }
}

For instance if I have the maze

1100111111
1101111111
1111110110
1110011111
1101101011
1111101011
1110111101
1100111111
1110111011
1101101111

It gives me the first path that it finds

1000000000
1001100000
1111110000
1100011000
1100001000
1100001000
1100001000
1100001011
1100001011
1100001111

Though it takes a roundabout way of getting there, due to the preferences of going in order of down, up, right, and left, it is still one path.

So ultimately, I'm not sure how to iterate for multiple paths.

Grenoble

I'd suggest using A*. There's many easy-to-use implementations out there. It can be configured to find an optimal path based on several factors which you can specify. If you really need to do this by hand, one thing to keep in mind is possible infinite loops since a possible path can include any number of redundant back-to-back "left right" or "left up up right down down" sort of directions. To avoid this, I'd suggest setting the square which the "player" is on to a wall so the player cannot move back to it, avoiding infinite loops. – Hemiterpene

you can flood the maze and try to permutate the 'reachable fields' (a la travelingsalesman problem) to create a great number of possible paths.... – Churrigueresque

Answer 1

Straightforward fully working solution using the example maze from this similar question (which was marked as duplicate but was standalone compilable): Find all paths in a maze using DFS

It uses a simple DFS with straightforward recursion, which seems the same approach as in the question here. It keeps track of the current track in a single string instance and modifies the maze in place to block off the current track.

#include <iostream>
#include <string>

const int WIDTH = 6;
const int HEIGHT = 5;

void check(int x, int y, int dest_x, int dest_y, 
           int (&maze)[HEIGHT][WIDTH], std::string& path) {
  if (x < 0 || y < 0 || x >= WIDTH|| y >= HEIGHT || !maze[y][x]) {
    return;        
  }
  int len = path.size();
  path += (char) ('0' + x);
  path += ',';
  path += (char) ('0' + y);

  if (x == dest_x && y == dest_y) {
    std::cout << path << "\n";
  } else {
    path += " > ";
    maze[y][x] = 0;  
    check (x + 0, y - 1, dest_x, dest_y, maze, path);
    check (x + 0, y + 1, dest_x, dest_y, maze, path);
    check (x - 1, y + 0, dest_x, dest_y, maze, path);
    check (x + 1, y + 0, dest_x, dest_y, maze, path);
    maze[y][x] = 1;
  }

  path.resize(len);
}


int main() {
  int maze[HEIGHT][WIDTH] = {
      {1,0,1,1,1,1},
      {1,0,1,0,1,1},
      {1,1,1,0,1,1},
      {0,0,0,0,1,0},
      {1,1,1,0,1,1}};

  std::string path;
  check(0, 0, 4, 3, maze, path);
  return 0;
}

Runnable version: https://code.sololearn.com/cYn18c5p7609

Herpes

Answer 2

i finally found you the solution to your question. but honestly it's not a solution that i did develope, some other people (namely: Schröder) had this idea before!

the problem is described by Schröder, but have a look at the german translation speaking of permutating a binary tree.

transform your path and all reachable nodes into a binary tree and permutate it! (but be warned, there may be many many solutions)

as you can see these are all solutions for crossing a 4x4 square (missing the mirrored part, but thats alas).

Churrigueresque

note: if you move on your path forward and backward you can ultimately create an infinite amount of paths =) you certainly knew this and certainly didn't intend this ^_^ – Churrigueresque