Skip to content

Instantly share code, notes, and snippets.

@tony-o

tony-o/gist:114ee474f8a233e595e33daa869ace94

Created August 25, 2023 16:00
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save tony-o/114ee474f8a233e595e33daa869ace94 to your computer and use it in GitHub Desktop.
Save tony-o/114ee474f8a233e595e33daa869ace94 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
gistfile1.txt
o o o o o o o o o o o o o x o o o o o o o o o o
o o o o o o o x x x x x x x o o o o o o o o o o
o o o o o o o o o o o o o o o x o o o o o o o o
o o o o o o o o o x x x o o o o o o o o o o x x
o o o o o o o o o x x x o o o o o o o o o o x x
o o o o o o o o o o x o o o o o o o o o o o x x
o o o o o o o o o o o o o o o o x o x o o o o o
o o o o o o o o o o o o o o o o x x o o o o o o
o o o o o o o o o o o o o o o o x x o o o o o o
o o o o o o o o o o o o o o o o o o o o o o o o
o o o o o o o o o x x o o o o o o o o o o o o x
o o o o x x x o x x x o o o o o o o o o o o o o
o o o o o T x o x x x o U x o o o o o x x o o o
o x o o o o o o x x x o o o o o x x x x x o o o
o o o o o o o o o o o o o o o o o o o o o o o o
o o o o o o o o o o o o o o o x o o o o o o o o
o o o o o o o o o o o o o o o o o o o o o o o o
o o o o o o o o o o o o o o o o o o o o o o o o
o o o o o o o o o o o o o o o o o o o o o o o o
o o o o o o o o o o o o o o o o o o o o o o o o
o o o o o o o o o o o o o o o o o o o o o o o o
o o o o o o o o o o o o o o o o o o o o o o o o
o o o o o o o o o o o o o o o o o o o o o o o o
o o o o o o o o o o o o o o o o o o o o o o o o
@tonyooooooo
Copy link 

const solve = (snode, enode) => {
  let maze = [[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,],
              [0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,],
              [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0,],
              [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1,],
              [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1,],
              [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1,],
              [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0,],
              [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0,],
              [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0,],
              [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,],
              [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1,],
              [0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,],
              [0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0,],
              [0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0,],
              [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,],
              [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0,],
              [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,],
              [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,],
              [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,],
              [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,],
              [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,],
              [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,],
              [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,],
              [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,]];

  let start = { x: snode[0], y: snode[1], f: 0, g: 0, h: 0 };  
  let end = { x: enode[0], y: enode[1], f: 0, g: 0, h: 0 };  
  let open = [start];
  let closed = [];
  const poses = [[0, -1], [0, 1], [-1, 0], [1, 0], [-1, -1], [-1, 1], [1, -1], [1, 1]];

  while (open.length) {
    open.sort((a,b) => a.f < b.f ? -1 : a.f == b.f ? 0 : 1);
    let cnode = open.shift();
    closed.push(cnode);
    if (cnode.x == end.x && cnode.y == end.y) {
      let path = [];
      while (cnode) {
        path.unshift(cnode);
        cnode = cnode.parent;
      }
      return path;
    }

    let children = [];
    for (let idx=0;idx < poses.length;idx++){
      let pos = [cnode.x + poses[idx][0] , cnode.y + poses[idx][1]];
      if (pos[0] >= maze.length - 1 || pos[0] < 0 || pos[1] >= maze.length - 1 || pos[1] < 0) {
          continue;
      }
      if (maze[pos[0]][pos[1]] != 0) {
          continue;
      }
      children.push({
        parent: cnode,
        x: pos[0],
        y: pos[1],
      });
    }
    console.log(children);
    for (let idx=0; idx < children.length; idx++) {
      let cont = false;
      for (let jdx=0; !cont && jdx < closed.length; jdx++) {
        if (children[idx].x == closed[jdx].x && children[idx].y == closed[jdx].y) {
          cont = true;
        }
      }
      if (cont) { continue; }
      children[idx].g = cnode.g + 1;
      children[idx].h = Math.pow(children[idx].x - end.x, 2) + Math.pow(children[idx].y - end.y, 2);
      children[idx].f = children[idx].g + children[idx].h;
      
      for (let jdx=0; !cont && jdx < open.length; jdx++) {
        if (children[idx].x == open[jdx].x && children[idx].y == open[jdx].y && children[idx].g > open[jdx].g) {
          cont = true;
        }
      }
      if (cont) { continue; }

      open.push(children[idx]);
    }
  }
  return [];
};


console.log('[' + solve([12,12], [12, 5]).map(a => `[${a.x}, ${a.y}]`).join(', ') + ']');

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment