0

So I need to make a code that finds the length of the minimal path in a maze.

The maze is an NxN matrix, starting point is (0,0) and ending point is (N,N), if the cell contains 1 I can go through it, if it's 0 I cannot. The maze may or may not have a solution.

This is my code so far, assuming it has a solution:

int path_finder(int maze[][N], int n, int row, int col)    // n equal N
{
int i, j, pth;

if (row == n-1 && col == n-1)    // Return 0 if I get to goal
  return 0;

if (col < 0 || row < 0 || row > n-1 || col > n-1)    // Same
  return n*n;

if (maze[row][col] == 0)    // Return big number to make sure it doesn't count
  return n*n;

maze[row][col] = 0;

pth = min( 1+path_finder(maze,n, row+1, col),    // Assume I already know the path
            1+path_finder(maze,n, row-1, col),    // from the next starting point
            1+path_finder(maze,n, row, col+1),    // just add 1 to it
            1+path_finder(maze,n, row, col-1)  );

maze[row][col] = 1;

return pth;
}

I always get N^2+1, I assume it only counts the last argument I send to the min function, but I don't know how to fix it?

veridisc
  • 1
  • 1
  • 2
    You have `if (maze[row][col] == 0)` *before* you test for off-edge condition, even though they return the same value, always check the limits before use. – Weather Vane Dec 10 '16 at 17:37
  • 1
    Pay attention to compiler warnings: `maze[row][col] == 0; // Make sure...` does nothing. – Weather Vane Dec 10 '16 at 17:40
  • It's a good idea to mark visted spaces as walls, but after you've called the function recursively (within your `min`), you should reset it to a floor again, so that other solutions can explore it. – M Oehm Dec 10 '16 at 17:41
  • Thanks Weather Vane, however I get n^2 as an answer every time. M Oehm if I reset it, wouldn't it go to an infinite loop? I don't really understand how what you're saying is different from not marking the spaces as wall at all – veridisc Dec 10 '16 at 17:50
  • FYI I previously posted a [maze solution](http://stackoverflow.com/a/34257513/4142924) using Dijkstra's algorithm, which does not require an exhaustive search. The question also has a link to a [duplicate question](http://stackoverflow.com/questions/3097556/programming-theory-solve-a-maze) containing various other methods of maze solving. – Weather Vane Dec 10 '16 at 17:54
  • @ Weather Vane I've already seen this thread, quite amusingly the OP is taking the same programming course as I'm taking right now. Efficiency is not important to me, and I need to solve it recursively. I'm trying to call each of the arguments with a new copy (4 different copies) of my maze matrix after I marked maze[row][col] as 0, but this doesn't work either, I think it's because after the first run those copies are reused and don't make new copies... really not sure what to do – veridisc Dec 10 '16 at 18:06
  • My guess is that @MOehm suggests you should remember the state of `maze[row][col]` before walling it and calling the recursion of each neighbour, then replace its original state before returning a value from the function. – Weather Vane Dec 10 '16 at 18:08
  • No, it wouldn't, because it will only reset the current square. The path up to that square will be blocked, but all possible future paths won't. – M Oehm Dec 10 '16 at 18:09
  • @MOehm I edited the code, is this what you meant? It's still not working – veridisc Dec 10 '16 at 18:19
  • I think my problem is that when I call the function with maze under the min function the first time, it is getting a different maze that the function after it gets and so on. Meaning path_finder(maze,n, row+1, col) manipulates maze, and then path_finder(maze,n, row-1, col) gets the manipulated maze instead of the same one. Any idea how to make copies? – veridisc Dec 10 '16 at 18:34
  • When I run your updated code, it works. As far that I can see, you don't change the maze except at the currentsquare. Copying te maze isn't a good idea: You will need more memory for each recursion level and may run out of stack space quickly. What does your `min` function look like? Or is it even a macro? That would call each function more than once. – M Oehm Dec 10 '16 at 18:48
  • You mean it works as in it's giving an answer, or a right answer? Right now it's giving me n^2+1 as an answer (n being the matrix size) regardless of the path. I use the min function from (I think it's from there) – veridisc Dec 10 '16 at 18:57
  • I've tried a 10 by 10 maze and got the correct solution, 32 in my case. As far as I know, C doesn't have a standard `min` function. C++ has ´std::min`, but it can't compare four items. Whereever that `min` comes from, chances are that it is a macro and that this leads to multiple evaluation. I suggest you write your own `min4` function for integers; it's straightforward. – M Oehm Dec 10 '16 at 20:37
  • Wow I cannot believe it... I already tried making my own min function before but got the same results, so I assumed "better keep just using the language's built in function"... but now it finally works! I've been trying to solve this problem for more than 7 hours in total, thank you so much! – veridisc Dec 10 '16 at 21:05
  • Very good, I'm glad it works now. Your idea to use standard functions where possible is good, but you have fallen prey to the [`min` definition](http://stackoverflow.com/questions/4234004/is-maxa-b-defined-in-stdlib-h-or-not) in Visual Studio's ``, which is a macro that [evaluates its arguments twice](http://stackoverflow.com/questions/3437404/min-and-max-in-c) and which isn't part of the C standard. (There's `fmax` for floating-point numbers, though.) – M Oehm Dec 11 '16 at 09:05
  • `min` and similar functions are often implemented as macros, because they will then work for any type that can be compared with `<`. I think the [disadvantage](https://gcc.gnu.org/onlinedocs/cpp/Macro-Pitfalls.html) of multiple evaluation outweighs this advantage and I recomment to write a small function with the type you need instead. If you make such a function `static`(i.e. private to the curret file) the compiler can inline it. – M Oehm Dec 11 '16 at 09:12

1 Answers1

1

If the problem is practical, use A*.

https://github.com/MalcolmMcLean/binaryimagelibrary/blob/master/astar.c

If the problem is contrived so that there are near-optimal distractor paths. Modify the function to take out the heuristic, and do an exhaustive search.

Malcolm McLean
  • 6,258
  • 1
  • 17
  • 18