8945

Recursive function (maze solver) - can't find a bug;(((

Question:

I am studying javascript and all is pretty easy to me except for some things like recursive functions. I do understand the way they work but while working with an example, I realized I can't capture the bug that prevents it from functioning...

I have an array (map) below (0 is a closed cell, 1 means path is open) and the recursive function I am trying to use to "find" path out of this "maze" by going from its top left cell to the bottom-right one.. Basically just make the function to "find" this path of 1s. But it fails;(

var map = [ [1,1,0,0], [0,1,1,0], [0,0,1,0], [0,0,1,1] ] function findpath(x,y) { if (x<0 || x>3 || y<0 || y>3) return false; //if it is outside of map if (x==3 && y==3) return true; // if it is the goal (exit point) if (map[y][x]==0) return false; //it is not open map[y][x]=9; //here marking x,y position as part of solution path outlined by "9" if (findpath(x,y-1) == true) return true; if (findpath(x+1,y) == true) return true; if (findpath(x,y+1) == true) return true; if (findpath(x-1,y) == true) return true; map[y][x]=8; //unmark x,y as part of solution path outlined by "8" return false; }; findpath(0,0);

Answer1:

Quick answer:

Its locking in a loop because the order of the checks.

Start from 0:0 then try 0:1. Then from 0:1 --"Ummm... 0:0 looks promising. Let's go there". So go back to 0:0... so it locks... Try leaving backtracking last :

if(findpath(x+1,y)) return true; if(findpath(x,y+1)) return true; if(findpath(x,y-1)) return true; if(findpath(x-1,y)) return true;

This get you out of the lock just by swapping the issue around. If you start from 3:3 trying to reach 0:0 you'll be locked again. Whats missing its a way to mark visited squares.

I think you are trying to implement an <a href="http://www.policyalmanac.org/games/aStarTutorial.htm" rel="nofollow">a* algorithm</a>

UPDATE:

Here is your idea working. Just added the backtracking checks you almost implemented.

<html> <head> </head> <body> <script> var map = [ [1,1,0,0], [0,1,1,0], [1,1,1,0], [1,0,1,1] ] var goalx = 0; var goaly = 3; console.log(); function findpath(x,y) { // illegal move check if (x < 0 || x > (map[0].length -1) || y < 0 || y > (map.length - 1)) return false; //if it is outside of map if (map[y][x]==0) return false; //it is not open // end move check if (x== goalx && y== goaly){ console.log('Reached goal at: ' + x + ':' + y); return true; // if it is the goal (exit point) } if(map[y][x] == 9 || map[y][x] == 8) return false; console.log('Im here at: ' + x + ':' + y); map[y][x]=9; //here marking x,y position as part of solution path outlined by "9" if(findpath(x+1,y)) return true; if(findpath(x,y+1)) return true; if(findpath(x,y-1)) return true; if(findpath(x-1,y)) return true; map[y][x]=8; //unmark x,y as part of solution path outlined by "8" return false; }; findpath(3, 3); </script> </body> </html>

Answer2:

The description of "it fails" is rarely, if ever, a <strong>useful</strong> error report.

In order for someone to help you, they need much more detail than that.

In this case, the import details came out of the JavaScript error console. You should <em>always</em> include any error messages in your question.

However, since your code was quite short I was able to cut-and-paste it into my console where I got the message:

<blockquote>

RangeError: Maximum call stack size exceeded

</blockquote>

This means that your function is recursing too deeply. You either

<ul><li>Have bad logic in your puzzle and you are recursing into the same values over and over again</li> <li>The puzzle is too complicated and you can't solve it recursively like that.</li> </ul>

You need to add console.log statements and observe what the code is doing and see why it is going so deep.

If it is a logic error, fix the logic error. (Hint: I'm pretty sure it is -- you never mark on the map where you've <em>been</em> so it freely goes back and forth and back and forth over the same spot).

If it isn't, then you need to use some more advanced trick to work around the recursion, such as using a generator function and storing the changes you do in the map separately.

Recommend

  • Android how to highlight a selection in a list
  • HBase REST API Locking Rows
  • Maintaining unique objects for names with concurrent delete
  • Hide JetBrains annotation on popup JavaDoc in IntelliJ
  • Google Analytics - Using Client ID as a custom dimension
  • Could not find goal '' in plugin org.springframework.boot:spring-boot-maven-plugin:1.1.4.R
  • Which devices/recommended sizes should I target with mediaqueries?
  • maven compile fails because i have a non-maven jar
  • Simple app using Windows Workflow and winforms NOT console
  • Make background for table rows extend past the bounds of the table
  • Using LINQ with IBM i
  • Per Machine App Registration
  • maven-dependency-plugin ignores outputDirectory configuration
  • When is locking on types a good idea?
  • R Impute NA's by Linear Increase Depending on Time Interval
  • Maven-Release-Plugin: Force to use specific version of scm provider
  • Objective C - Create a framework for my iphone apps?
  • Quickly or concisely determine the longest string per column in a row-based data collection
  • How to package a jar and all dependencies within a new jar with maven
  • GitHub default README markup
  • Run script file on remote server
  • XSLT foreach repeating nodes to flat
  • Does Apple allow the usage of sysctl.h within iOS applications?
  • How to autopopulate a field in SugarCRM form
  • How to add git credentials to the build so it would be able to be used within a shell code?
  • How to know when stdin is empty if it contains EOF?
  • Spark fat jar to run multiple versions on YARN
  • javaw.exe and eclipse startup problems
  • Check if a string to interpolate provides expected placeholders
  • Timeout for blocking function call, i.e., how to stop waiting for user input after X seconds?
  • Jquery - Jquery Wysiwyg return html as a string
  • RestKit - RKRequestDelegate does not exist
  • Arrays break string types in Julia
  • Traverse Array and Display in markup
  • Rails 2: use form_for to build a form covering multiple objects of the same class
  • WPF Applying a trigger on binding failure
  • Java static initializers and reflection
  • need help with bizarre java.net.HttpURLConnection behavior
  • Running Map reduces the dimensions of the matrices
  • Reading document lines to the user (python)