Back-tracking through a grid

backtrack.js

//NB: map = grid
// Map dimension
var N = 5;

// Map init
var map = [];
for(var i = 0; i<N; i++) {
	map.push([])
	for(var j=0;j<N; j++) {
		map[i].push(
		{	// Cells in my map are actually objects because
			// objects are cool and I can store multiple things
			t:false,	// wether or not I've walked on it
			i: i,		// row (please call it row and not i)
			j: j 		// cell in row (please call it cell and not j)
		})
	}
}

// Getting the start point cell
var start = map[0][0];
start.t = true;


/**
This is a dirty (bad, bad, filthy code) couple of functions used to find the next possible options
for this game.
I find this to be a clean option because if the rules of the game change
(the rules on what cell I can visit and in what order) I just have to change
this, and not the recursive traversal later
*/
function safeGet(i,j, ns) {
	try{	// This will try to get a cell, if it fails, it means it doesn't exist
		if(!map[i][j].t){	// Test if the cell has been walked on already
			ns.push(map[i][j]);	// put it in the possible options array
		}
	}catch(e){}
}
function findNeighbours(i,j) {
	var neigh = [];
	//safeGet(i-1,j-1, neigh);	// Uncomment if you want euclidian distance
	safeGet(i-1,j, neigh);
	//safeGet(i-1,j+1, neigh);

	safeGet(i,j-1, neigh);
	safeGet(i,j+1, neigh);

	//safeGet(i+1,j-1, neigh);
	safeGet(i+1,j, neigh);
	//safeGet(i+1,j+1, neigh);

	return neigh;
}

/**
A function to make an array of cells (a path) into a string for debugging purpose
*/
function printStack(stack) {
	return stack.map(s=>s.i+','+s.j).join`|`
}

var number = 0; 	// The number of possible paths
/**
That's the actual recursion thing, where the magic happens.
It takes the current node that is being walked on,
and a stack (path) of previously traversed nodes, for debugging only
*/
function go(node, stack) {
	// First flag the current node as traversed
	node.t = true;


	// Check if the node is a leaf (aka the goal node)
	if(node.i === N-1 && node.j === N-1) {	// (aka test if its coordinates are those of the end node)
		console.log(printStack(stack));		// Print the path
		number++;							// Increment the number of valid paths you found
	}

	// Find all "children"/"neighbours" of the cell :
	// All the possible options to go for the next game turn
	var neigh = findNeighbours(node.i, node.j);
	/*
		If this was a search, we would find the best option that we want, and go for it
		but since we want to back-track, aka go through *all* possible options, we're just going to
		iterate through all of 'em
	*/
	for (n of neigh) {	// n is a cell in the neigh array
		stack.push(n);	// Push it on the current path
		go(n, stack);	// Call the recursive function with this new node
		stack.pop(n);	// Pop (unpush) it from the current path to clean up after yourself
	}

	// Clean up after yourself so you can start fresh with the next option of the previous recursion level
	// (Take some time to make sure you understand that sentence)
	node.t = false;
}

// Actually call the thing, get the CPU to work
go(start, [start])
// It's working...
// It's working...
// It's working...
// It's working...


// Now `number` should have been increment for each of our paths
console.log('Total',number)

/* Results
5*5 grid, Manhattan distance, all 4 possible directions : 8512
5*5 grid, Manhattan distance, only right and down : 70
5*5 grid, euclidian distance, all 8 directions : Timeout (exponential, too long)
*/