Depth first search through a maze in a matrix

Question

I have a matrix:

 var matrix = [
        [0, 1, 0, 1, 0],
        [0, 0, 1, 1, 0],
        [0, 0, 1, 1, 0],
        [0, 0, 0, 0, 0],
        [0, 1, 0, 1, 0]
     ];

I need to find a way from the point "start" to point "end" using the depth first search algorithm.

var start = [0,4],
    end = [4,0];

I can move only in four directions. Up, down, left, right.

I tried to implement this algorithm, but my function does not find a way out of deadlocks. The function does not find other paths.

Perhaps I misunderstood how the algorithm works.

You can find my code on JSFiddle and here:

let matrix = [
    [0, 1, 0, 1, 0],
    [0, 0, 1, 0, 0],
    [0, 0, 1, 1, 0],
    [0, 0, 0, 0, 0],
    [0, 1, 0, 1, 0]
 ];

let start = [0,4];
let end = [4,0];
let way = [start];

function findWay(position, prevPosition){

	prevPosition = prevPosition || [-1,-1];

	let left  = [ position[0], position[1] - 1 ];
	let right = [ position[0], position[1] + 1 ];
	let up    = [ position[0] - 1, position[1] ];
	let down  = [ position[0] + 1, position[1] ];

	if( position[0] == end[0] && position[1] == end[1] ) {
		return way;
	} 

	if(checkCondition(left, prevPosition)) {
		way.push(left);
		return findWay(left, position);
	}

	if(checkCondition(down, prevPosition)){
		way.push(down);
		return findWay(down, position);
	} 	

	if(checkCondition(right, prevPosition)){
		way.push(right);
		return findWay(right, position);
	}

	if(checkCondition(up, prevPosition)){
		way.push(up);
		return findWay(up, position);
	} 	

    way = 'No Way!';
	return way;
}


function checkCondition(direction, prevPosition){

	if(direction[0] > 4 || direction[0] < 0 || direction[1] > 4 || direction[1] < 0){
		return false;
	}

	if(prevPosition[0] == direction[0] && prevPosition[1] == direction[1]){
		return false;
	}

	if(matrix[direction[0]][direction[1]] == 0){
		return true;
	}

	return false;
}

findWay(start);

Please help me write the function correctly.

Answer 1

Some issues with your code:

• Be clear what you want to return. I suggest that you use null to indicate that no path was found, for which you can check easily, because it is a false value. You only want to return when you have found a path. When you go left and hit a dead end, you still wanto to explore the other three directions. Your code returns immediately.
• You must check whether you have already been to a cell or not. It is not enough to pass the previously visited cell, because you might walk in a bigger loop. You could check whether the current cell is already in the path, but a common practice is to make all visited cells inacessible by setting them to 1. Of course, when you track back from a dead end, you must make these cells accessible again,so that other paths might still go there.
• Likewise, you can't just add to the way. When you track back, you must remove the cells from the paths again. Otherwise you'll get an incongruent jumble of a path that even includes dead ends. In other words, when you backtrack, you must reset the state of the program to the state that it had when you entered.
• It might be easier to do the check whether a cell is valid up front and return null immediately if it isn't.

So here's a working implementation of the following algorithm:

• Is the cell invalid? If so, return null.
• Has the cell been visited? If so, terurn null.
• Is the cell the target? If so, return the path.
• Mark the cell as visited and add it to the path.
• Walk into all four directions until you find a valid path. If you find one, return it.
• Clean up by resetting the cell and the path and return null.

In Javascript:

function findWay(pos, end, way)
{
    if (way === undefined) way = [];

    if (pos[0] < 0 || pos[0] >= matrix.length) return null;
    if (pos[1] < 0 || pos[1] >= matrix[0].length) return null;

    if (pos[0] == end[0] && pos[1] == end[1]) return way;
    if (matrix[pos[0]][pos[1]] != 0) return null;

    matrix[pos[0]][pos[1]] = 1;
    way.push(pos);

    let res = (findWay([pos[0] + 1, pos[1]], end, way)
            || findWay([pos[0], pos[1] + 1], end, way)
            || findWay([pos[0] - 1, pos[1]], end, way)
            || findWay([pos[0], pos[1] - 1], end, way));

    if (res !== null) return res;

    matrix[pos[0]][pos[1]] = 0;
    way.pop();

    return null;
}

Answer 2

I see two issues with your implementation:

1) Checking for visited nodes. You do have a check that makes sure you don't go back to the node you just came from, but that's not enough. You need to check that you're not returning to any previously visited node.

To do this, i would keep an array of visited nodes. Each time you expand a node, add it to that array. Each time you're considering expanding a node, check if it's already in the visitied array. So something like this:

let visited = [];

function findWay(position) {
  visited.push(position);
  // Rest of function omitted.
}

checkCondition(position) {
  // Code for checking out of bounds omitted

  if (visited.find(v => v[0] == position[0] && v[1] == position[1]) {
    return false;
  }

  // Code for checking passable vs unpassable omitted
}

2) When expanding a node, you're only going in at most one direction; the first direction that happens to be passable. This is because you're returning regardless of what the result of findWay is. A simple fix would be to change this:

if(checkCondition(left, prevPosition)) {
  way.push(left);
  return findWay(left, position);
}

...to this

if(checkCondition(left, prevPosition)) {
  way.push(left);
  const result = findWay(left, position);
  if (result !== 'No Way!') {
    return result;
  }
}

...along with similar changes to the other cases.