How to find the fastest route in a maze (in C)

Question

The maze is defined as a square matrix. For example:

int maze[N][N] =
  { { 1, 1, 1, 1, 1, 1, 1 },
    { 0, 1, 0, 1, 0, 0, 1 },
    { 0, 1, 0, 1, 1, 1, 1 },
    { 0, 1, 0, 0, 0, 1, 1 },
    { 0, 1, 1, 1, 0, 1, 1 },
    { 0, 0, 1, 0, 1, 1, 1 },
    { 1, 1, 1, 1, 0, 1, 1 } };

You can walk only where there's a 1. You can take a step down, up, left, right. You start at the top-left corner and finish at down-right corner.

The output should be the minimum steps to finish any maze. We can assume there is at least one way to finish the maze. i've edited the code and i thought i covered everything.. but obviously i'm missing something. thanks for your help

int path_help(int maze[][N], int row, int col, int count)
{
    int copy1[N][N], copy2[N][N], copy3[N][N];
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            copy1[i][j] = maze[i][j];
            copy2[i][j] = maze[i][j];
            copy3[i][j] = maze[i][j];
        }
    }
    int a, b, c, d;
    if (col == 0 || row == 0)
    {
        if (row == N - 1)
        {
            if (maze[row][col + 1] == 1)
            {
                maze[row][col] = 0;
                return path_help(maze, row, col + 1, count + 1);
            }
            else return N*N;
        }
        if (col == N - 1)
        {
            if (maze[row + 1][col] == 1)
            {
                maze[row][col] = 0;
                return path_help(maze, row + 1, col, count + 1);
            }
            else return N*N;
        }
        if (maze[row][col + 1] == 1 && maze[row + 1][col] == 1)
        {
            maze[row][col] = 0;
            copy1[row][col] = 0;
            return min(path_help(copy1, row, col + 1, count + 1),path_help(maze, row + 1, col, count + 1));
    }
    if (maze[row][col + 1] == 0 && maze[row + 1][col] == 1)
    {
        maze[row][col] = 0;
        return path_help(maze, row + 1, col, count + 1);
    }
    if (maze[row + 1][col] == 0 && maze[row][col + 1] == 1)
    {
        maze[row][col] = 0;
        return path_help(maze, row, col + 1, count + 1);
    }
    else return N*N;
}
if (col == N - 1 || row == N - 1)
{
    if (col == N - 1 && row == N - 1) return count;
    if (row == N - 1)
    {
        if (maze[row - 1][col] == 1 && maze[row][col + 1] == 1)
        {
            maze[row][col] = 0;
            copy1[row][col] = 0;
            return min(path_help(copy1, row, col + 1, count + 1), path_help(maze, row - 1, col, count + 1));
        }

        if (maze[row - 1][col] == 0 && maze[row][col + 1] == 1)
        {
            maze[row][col] = 0;
            return path_help(maze, row, col + 1, count + 1);
        }
        if (maze[row][col + 1] == 0 && maze[row - 1][col] == 1)
        {
            maze[row][col] = 0;
            return path_help(maze, row - 1, col, count + 1);
        }
        else return N*N;
    }
    if (col == N - 1)
    {
        if (maze[row + 1][col] == 1 && maze[row][col - 1] == 1)
        {
            maze[row][col] = 0;
            copy1[row][col] = 0;
            return min(path_help(copy1, row, col - 1, count + 1), path_help(maze, row + 1, col, count + 1));
        }

        if (maze[row + 1][col] == 0 && maze[row][col - 1] == 1)
        {
            maze[row][col] = 0;
            return path_help(maze, row, col - 1, count + 1);
        }
        if (maze[row][col - 1] == 0 && maze[row + 1][col] == 1)
        {
            maze[row][col] = 0;
            return path_help(maze, row + 1, col, count + 1);
        }
        else return N*N;
    }
}
if (maze[row + 1][col] == 1)
{
    maze[row][col] = 0;
    a = path_help(maze, row + 1, col, count + 1);
}
else a = N*N;
if (maze[row - 1][col] == 1)
{
    copy1[row][col] = 0;
    b = path_help(copy1, row - 1, col, count + 1);
}
else b = N*N;
if (maze[row][col + 1] == 1)
{
    copy2[row][col] = 0;
    c = path_help(copy2, row, col + 1, count + 1);
}
else c = N*N;
if (maze[row][col - 1] == 1)
{
    copy3[row][col] = 0;
    d = path_help(copy3, row, col - 1, count + 1);
}
else d = N*N;
return min(min(a, b),min( c, d));

}

What does not work. What is the output of your program and what output do you expect? Have you any ideas what could go wrong? — Randrian, Dec 13 '15 at 21:11
That's evil: a nested `switch` within a `switch` without proper indentation! I'm not surprised it doesn't work. I'm mildly surprised it compiles, but then there is [Duff's Device](https://en.wikipedia.org/wiki/Duff's_device) so I'm not wholly surprised. — Jonathan Leffler, Dec 13 '15 at 21:15
[Dijkstra's algorithm](https://en.wikipedia.org/wiki/Dijkstra's_algorithm) — Weather Vane, Dec 13 '15 at 21:19
How does your code know where it has been? How does it know when it has reached an edge? How does it know when it has got the entire path? — Jonathan Leffler, Dec 13 '15 at 21:20
Jonathan Leffler i dont understand where there is a wrong indentation. — ofer simchovitch, Dec 13 '15 at 21:37
Surely, as others have suggested, it's missing an 'I'm off the grid' failure return? — Martin James, Dec 13 '15 at 21:41
but theres no option for that to happend will . im pretty sure i made sure of that. — ofer simchovitch, Dec 13 '15 at 21:42
suggest implementing a version of Dijkstra's algorithm with a directed goal rather than getting the shortest path to every node. — user3629249, Dec 13 '15 at 21:43
Is the minimum possible answer for any maze `width + height - 2`? — Weather Vane, Dec 13 '15 at 21:44
Also, if the maze is always square, there is no need for passing N twice. In fact, in this case, it's one of those every few cases where I would use a static maze. — Martin James, Dec 13 '15 at 21:45
@ofersimchovitch: After I edited the code, there was no longer improper indentation. Maybe the trouble was that you were using tabs; it is best not to use tabs on Stack Overflow (or the other Stack Exchange sites). I'm not convinced that the choice of nested `switch` statements is the best way to write the code; I think an `if` would be appropriate for the outer `switch` (and I reserve judgement on the inner `switch`). — Jonathan Leffler, Dec 14 '15 at 05:23

Weather Vane · Answer 1 · 2015-12-14T19:36:26.410

Because there is no solution of Dijkstra's algorithm in the question linked by @Jackson, here is a modified algorithm adapted for this maze problem. I take the maze value 0 as no-go, and 1 as the distance for the algorithm.

It looks as though the neigh() function should be recursive, but it is not, it is only there so that 4 neighbours can be examined in the same way. Note that not every path is followed: for a large maze that could be O(no!). Also that the search is not directed to the end point: the end point is encountered, and these features of the algorithm give it its beauty.

#include <stdio.h>
#include <stdio.h>
#include <limits.h>

#define MSIZE  7                            // matrix/maze dims

enum ntype { virgin, listed, visited };     // for status field

typedef struct {
    int x;                                  // grid position of node
    int y;                                  // grid position of node
    int value;                              // 0 or 1 as defined in maze[][]
    int dist;                               // distance from start node
    int status;                             // enum as above
} node_t;

int maze[MSIZE][MSIZE] =                     // maze definition
  { { 1, 1, 1, 1, 1, 1, 1 },
    { 0, 1, 0, 1, 0, 0, 1 },
    { 0, 1, 0, 1, 1, 1, 1 },
    { 0, 1, 0, 0, 0, 1, 1 },
    { 0, 1, 1, 1, 0, 1, 1 },
    { 0, 0, 1, 0, 1, 1, 1 },
    { 1, 1, 1, 1, 0, 1, 1 } };

node_t node [MSIZE][MSIZE];                 // working array
node_t *list[MSIZE*MSIZE];                  // array of current node pointers
int listlen;                                // num elements in list[]

void neigh(node_t *cptr, int dx, int dy)
// examine one neighbour of node cptr, offset by dx,dy
{
    node_t *nptr;                           // pointer to neighbour
    int dist;                               // accumulated distance from start
    int x = cptr->x + dx;                   // work out neighbour coords
    int y = cptr->y + dy;                   // work out neighbour coords
    if (x < 0 || x >= MSIZE || y < 0 || y >= MSIZE)
        return;                             // failed edge test    
    nptr = &node[y][x];                     // point to neighbour
    if (nptr->value == 0)                   // no-go node
        return;
    if (nptr->status == visited)            // do no re-visit
        return;

    dist = cptr->dist + nptr->value;        // accumulate distance from start
    if (dist < nptr->dist)                  // if it's less than what was known...
        nptr->dist = dist;                  // ...update with the new distance
    if (nptr->status == virgin) {           // if it's never been seen...
        list[listlen++] = nptr;             // ... neighbour to list
        nptr->status = listed;              // and set its status
    }
}

int main(void)
{
    int i, j, smallest, smallind;
    node_t *cptr, *eptr;

    // init the struct array
    for (j=0; j<MSIZE; j++) {
        for (i=0; i<MSIZE; i++) {
            cptr = &node[j][i];             // pointer to the array element
            cptr->value = maze[j][i];       // the maze definition
            cptr->x = i;                    // self's position
            cptr->y = j;                    // self's position
            cptr->dist = INT_MAX;           // distance from start (unknown)
            cptr->status = virgin;          // never examined
        }
    }

    eptr = &node[MSIZE-1][MSIZE-1];         // pointer to end node

    cptr = &node[0][0];                     // pointer to start node
    cptr->dist  = 0;                        // distance of start node from itself!

    // main loop
    while (cptr != eptr) {                  // until we reach the target node
        cptr->status = visited;             // we've been here now
        neigh(cptr,  0, -1);                // examine node above
        neigh(cptr, -1, 0);                 // examine node on left
        neigh(cptr,  1, 0);                 // examine node on right
        neigh(cptr,  0, 1);                 // examine node below

        // find smallest distance of nodes in list[] (won't include virgins)
        smallest = INT_MAX;
        smallind = -1;                      // set invalid marker index
        for (i=0; i<listlen; i++) {
            if (smallest > list[i]->dist) { // compare distance with smallest
                smallest = list[i]->dist;   // remembers the smallest
                smallind = i;               // remembers the list index of smallest
            }
        }
        // take smallest for next time and remove from list
        if(smallind < 0) {                  // -1 was the "marker"
            printf("No route found\n");
            return 1;
        }
        cptr = list[smallind];              // smallest becomes current node
        if (listlen)                        // replace in list with last element...
           list[smallind] = list[--listlen];// ... and reduce list length
    }                                       // now examine this node

    printf("Distance = %d\n", eptr->dist);  // show the distance of the end node
    return 0;
}

Program output:

Distance = 12

EDIT The algorithm itself is described in the link, if it breaks there are sure to be other explanations available. I have added more comments to the code.

I use 3 arrays, maze[][] is a simple maze definition like yours. Then node[][] is an array of struct which hold runtime data. I could have initiliased this with the maze definition directly, but because the program this came from had hard-coded test data of one matrix size, and a bigger matrix with data read from file, I left it as it was.

The third array list[] is an array of pointers to the node[][] elements. This is why node[][] elements contain the x,y coordinates within the struct itself: so that I can know the position from the pointer alone. I could have worked with a 1-D maze array, when I could have stored a single index in list[], if so this complication would not have been necessary. But I used a 2-D array, just because it felt "nicer".

I am comfortable working with pointers. In the first nested loop pair in main() headed // init the struct array the first thing I do is to make a pointer, for use in setting the struct fields, because I find the repeated use of array indexing clumsy. So I write for example cptr->x = i; which has the same intent as node[j][i].x = i;.

Weather Vane since we havnt learned yet some of the sintax u've put here, can u describe in words what's happening here? thank u so much! — ofer simchovitch, Dec 14 '15 at 14:09
@ofersimchovitch I have edited my answer to add some explanation. — Weather Vane, Dec 14 '15 at 19:37

score 0 · Answer 2 · answered Dec 13 '15 at 21:47

0

Fundamentally, this is a search problem. There are lots of well written posts on how to solve it, so I'll talk about a few of the finer points that your will need to consider.

Since you specify want the shortest path, and not just a "pretty good" path, you will need to check every possible route. Depth-first search would be my suggestion.

Most obviously, this is search without reuse. The shortest path will not contain any loops or any case where the cursor will return to a place where it has already been. This keeps the search area reasonable.

answered Dec 13 '15 at 21:47

Holly

5,270
1
24
27

I would set the 1's to 0's as I went and, if the path failed, set them back again upon the returns. – Martin James Dec 13 '15 at 21:49
1

Dijkstra's algorithm works *without* following every possible route: that's part of it's beauty - it is not directed at the endpoint, but encounters it. – Weather Vane Dec 13 '15 at 21:58

cemersoz · Answer 3 · 2015-12-14T21:00:48.910

0

If runtime is not an issue, you can write a function to try every possible route, and returning the minimum.

int path_helper(int maze[][N],int height, int width, int row, int col){
  if(row==height-1 && col == width-1) return 0;
  if(maze[row][col]==0) return height*width;
  if(col<0 || row<0 || row>=height || col>=width) return height*width;
  maze[row][col]=0;
  int maze2[7][7]={{0}};
  for(int i = 0; i < height; i++){
    for(int j = 0; j < width; j++)
      maze2[j][i]=maze[j][i];
  }
  return min(min(path_helper(maze2,height,width,row+1,col),
  path_helper(maze2,height,width,row-1,col)),      min(path_helper(maze2,height,width,row,col+1),path_helper(maze2,height,width,row,col-1)))+1;
}

it's ugly but it should do the trick

edited Dec 14 '15 at 21:00

answered Dec 13 '15 at 22:03

cemersoz

43
7

What about the edge conditions? – Weather Vane Dec 13 '15 at 22:04
I did not consider that. I just fixed it. Thx – cemersoz Dec 13 '15 at 22:42
cemersoz i tried your code and it overflood the memory stack. is there any way to fix it? – ofer simchovitch Dec 14 '15 at 14:53
The code did not check for loops so it could go between two points infinitely. making the current point 0 should solve it. sorry foe the issue – cemersoz Dec 14 '15 at 15:30
i dont know why, for some reason it still returns 49 – ofer simchovitch Dec 14 '15 at 18:23
i think since we change maze[row][col] to be 0, the other calls for the function cant enter this index therefore the fastest way has been "ruined" – ofer simchovitch Dec 14 '15 at 19:44
I am getting 16 using the same code. I don't think that is the issue since every point calls the function using its own value. I am working on it. :D – cemersoz Dec 14 '15 at 20:37
Solved it! Turns out I'm a moron. you have to make another array. since what you said is true even though it should not return 49. Editing it rn – cemersoz Dec 14 '15 at 20:59
as u can see in my edited code, i've tried to make 3 copies of the maze but still it didnt work – ofer simchovitch Dec 14 '15 at 21:39

How to find the fastest route in a maze (in C)

3 Answers3

Linked