Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //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)
- */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement