Difficulties in converting a recursive algorithm into an iterative

Question

I am trying to implement a recursive backtracking maze generation algorithm in javascript. This was done after reading a large series of related posts here.

While the recursive version of the algorithm was not problematic, the iterative equivalent alerted me.

I thought I understood the concept, but my implementation clearly gives the wrong results. I tried to identify an error that could cause it, but I am starting to believe that my problems are caused by a failure in the logic, but, of course, I do not see where.

My understanding of the iterative algorithm is as follows:

• In the stack, holding representations of cell states are created.

• Each view contains the coordinates of this particular cell and a list of directions for accessing neighboring cells.

• While the stack is not empty, iterate over the directions at the top of the stack, checking neighboring cells.

• If a valid cell is found, place it at the top of the stack and continue with that cell.

Here is my recursive implementation (note: keydown to step forward): http://jsbin.com/urilan/14

And here is my iterative implementation (again, keydown to step forward): http://jsbin.com/eyosij/2

Thanks for the help.

edit: We apologize if my question is not clear. I will try to explain the cause of the problem.

When starting an iterative solution, various unforeseen situations arise. First of all, the algorithm does not exhaust all available options before backtracking. Rather, it seems to select cells in random order when one valid cell remains. In general, however, the movement does not seem random.

var dirs = [ 'N', 'W', 'E', 'S' ]; var XD = { 'N': 0, 'S':0, 'E':1, 'W':-1 }; var YD = { 'N':-1, 'S':1, 'E':0, 'W': 0 }; function genMaze(){ var dirtemp = dirs.slice().slice(); //copies 'dirs' so its not overwritten or altered var path = []; // stores path traveled. var stack = [[0,0, shuffle(dirtemp)]]; //Stack of instances. Each subarray in 'stacks' represents a cell //and its current state. That is, its coordinates, and which adjacent cells have been //checked. Each time it checks an adjacent cell a direction value is popped from //from the list while ( stack.length > 0 ) { var current = stack[stack.length-1]; // With each iteration focus is to be placed on the newest cell. var x = current[0], y = current[1], d = current[2]; var sLen = stack.length; // For testing whether there is a newer cell in the stack than the current. path.push([x,y]); // Store current coordinates in the path while ( d.length > 0 ) { if( stack.length != sLen ){ break;}// If there is a newer cell in stack, break and then continue with that cell else { var cd = d.pop(); var nx = x + XD[ cd ]; var ny = y + YD[ cd ]; if ( nx >= 0 && ny >= 0 && nx < w && ny < h && !cells[nx][ny] ){ dtemp = dirs.slice().slice(); cells[nx][ny] = 1; stack.push( [ nx, ny, shuffle(dtemp) ] ); //add new cell to the stack with new list of directions. // from here the code should break from the loop and start again with this latest addition being considered. } } } if (current[2].length === 0){stack.pop(); } //if all available directions have been tested, remove from stack } return path; } 

Hope this helps you sort this out. If it is still missing, please let me know.

Thanks again.

Answer 1

I am not very good at javascript, but I am trying to implement your recursive code iteratively. You also need to keep the For index on the stack. So the code looks like this:

 function genMaze(cx,cy) { var dirtemp = dirs; //copies 'dirs' so its not overwritten var path = []; // stores path traveled. var stack = [[cx, cy, shuffle(dirtemp), 0]]; // we also need to store `for` indexer while (stack.length > 0) { var current = stack[stack.length - 1]; // With each iteration focus is to be placed on the newest cell. var x = current[0], y = current[1], d = current[2], i = current[3]; if (i > d.length) { stack.pop(); continue; } stack[stack.length - 1][3] = i + 1; // for next iteration path.push([x, y]); // Store current coordinates in the path cells[x][y] = 1; var cd = d[i]; var nx = x + XD[cd]; var ny = y + YD[cd]; if (nx >= 0 && ny >= 0 && nx < w && ny < h && !cells[nx][ny]) { dtemp = dirs; stack.push([nx, ny, shuffle(dtemp), 0]); } } return path; } 

Answer 2

Does this little code help?

 /** Examples var sum = tco(function(x, y) { return y > 0 ? sum(x + 1, y - 1) : y < 0 ? sum(x - 1, y + 1) : x }) sum(20, 100000) // => 100020 **/ function tco(f) { var value, active = false, accumulated = [] return function accumulator() { accumulated.push(arguments) if (!active) { active = true while (accumulated.length) value = f.apply(this, accumulated.shift()) active = false return value } } } 

Credits, explanations and more info on github https://gist.github.com/1697037

Is it possible not to change the code, so it can be used in other situations. Hope that helps :)