BFS algorithm fails when start and end nodes are too far apart

Question

I am working on a pathfinding visualizer for Breadth-First Search, and the algorithm works while "start" and "end" are around 15 units apart but afterward it either takes really long to compute or just fails to work. I think my code may be inefficient but I am confused about how to fix it. Any help is very appreciated.

This is the JavaScript code I have right now for BFS which uses ids to locate the nodes in the table:

      var start = document.getElementsByClassName("start")[0];

      let q = new Queue();
      q.enqueue(start);
      
      while(!q.isEmpty()){
          var x = q.dequeue();
      
          var row = parseInt(x.id.split('-')[0]);
          var col = parseInt(x.id.split('-')[1]);
          //go up
          if((row-1)>=0){
              var u = document.getElementById((row-1)+"-"+col);
              if(u.className=="end"){
                  break;
              }else if(u.className!="start" || u.className!="visited"){
                  u.className="visited";
                  q.enqueue(u);
              }
          }
          //go down
          if((row+1)<=20){
              var d = document.getElementById((row+1)+"-"+col);
              if(d.className=="end"){
                  break;
              }else if(d.className!="start" || d.className!="visited"){
                  d.className="visited";
                  q.enqueue(d);
              }
          }
          //go right
          if((col+1)<=50){
              var r = document.getElementById(row+"-"+(col+1));
              if(r.className=="end"){
                  break;
              }else if(r.className!="start" || r.className!="visited"){
                  r.className="visited";
                  q.enqueue(r);
              }
          }
          //go left
          if((col-1)>=0){
              var l = document.getElementById(row+"-"+(col-1));
              if(l.className=="end"){
                  break;
              }else if(l.className!="start" ||       l.className!="visited"){
                  l.className="visited";
                  q.enqueue(l);
              }
          }

This is the interface where green is the start node and red is the end node and the blue is the bfs algorithm

Answer 1

A good way to not get confused, is to separate the breath first search algorithm from the rest of the code like this. It will allow you to test each part separately.

function bfs () {

  let q = new Queue();
  q.enqueue(start);

  while (! q.isEmpty()) {
    let x = q.dequeue();

    if (! visited(x)) {
      process(x);
      if (exit()) break;
      q.enqueue( adjacent(x) );
    }
  } 
}

Also if you want to animate the algorithm you will need to use setTimeout and execute only 1 turn of the loop per setTimeout call. If you don't, you will only see the result after the algorithm has found the "end" because of the nature of the event loop of the browser. You see, while the javascript is running the browser can't refresh the screen. If you want to see something change, you need to execute a few instructions then let the browser refresh and continue the execution of a few more instructions. Rinse and repeat, and you have an animation. The setTimeout is the function that allow you to restart the execution.

Here is an example:

let start = "x16y2";
let end   = "x25y4";

function main () {
   init();

   step1();
   
   function step1 () {
     bfs(step2); 
   }
   function step2 () {
     dfs(step1); 
   }
}

// breath first search (bfs)

function bfs (cont) {
   clearVisited();
   
   let queue = new STACK_QUEUE("shift");

   queue.add(start);
   bfs_cont();
/*
   while (! queue.isEmpty()) {
     let x = queue.retrieve();
     if (! visited(x)) {
       process(x);
       if (exit()) break;
       queue.add( adjacent(x) );
     }
   }
*/   
  function bfs_cont () {

     if (queue.isEmpty()) return;

     let x = queue.retrieve();

     if (! visited(x)) {
       process(x);
       if (exit()) {setTimeout(cont, 2000); return;}
       queue.add( adjacent(x) );
     }

     setTimeout(bfs_cont, 10);
  }
}

// depth first search (dfs)

function dfs (cont) {
   clearVisited();

   let stack = new STACK_QUEUE("pop");

   stack.add(start);
   dfs_cont();
/*
   while (! stack.isEmpty()) {
     let x= stack.retrieve();
     if (! visited(x)) {
       process(x);
       if (exit()) break;
       stack.add( adjacent(x) );
     }
  }
*/
  function dfs_cont () {

     if (stack.isEmpty()) return;

     let x = stack.retrieve();

     if (! visited(x)) {
       process(x);
       if (exit()) {setTimeout(cont, 2000); return;}
       stack.add( adjacent(x) );
     }

     setTimeout(dfs_cont, 10);
  }
}



function exit () {
  return visited(end);
}

function visited (id) {
  let e = document.getElementById(id);
  return hasClass(e, "visited");
}

function process (id) {
  let e = document.getElementById(id);
  addClass(e, "visited");
}

function adjacent (id) {
   let pos_y = id.indexOf('y');
   let x = 1 * id.substring(1,pos_y);
   let y = 1 * id.substr(pos_y+1);
   let res = [];
   // up
   if (x > 0)    res.push("x"+(x-1)+"y"+y);
   // left 
   if (y > 0)    res.push("x"+x+"y"+(y-1));
   // down
   if (x < 32-1) res.push("x"+(x+1)+"y"+y);
   // right 
   if (y < 20-1) res.push("x"+x+"y"+(y+1));
   
   return radomizeIt(res);
}

function clearVisited () {
  var list;
  while (true) {
    list = document.getElementsByClassName("visited");
    if (list.length <= 0) break;
    for (let i = 0 ; i < list.length ; i += 1) {
      removeClass(list[i], "visited");
    }
  }
}

function init() {
  let c =  document.createElement("div");
  c.setAttribute("class", "container");
  c.setAttribute("id", "container");
  document.body.appendChild(c);

  let container = document.getElementById("container");
  for (let y = 0 ; y < 20 ; y += 1) {
    for (let x = 0 ; x < 32 ; x += 1) {
      let e = document.createElement("div");
      e.setAttribute("class", "cell");
      e.setAttribute("id", "x"+x+"y"+y);
      e.style.top = ""+(y*8)+"px";
      e.style.left = ""+(x*8)+"px";
      container.appendChild(e);
    }
  }

  addClass(document.getElementById(start), "start");
  addClass(document.getElementById(end),   "end");
}

function addClass(e, cssClass) {
  if (!e) return;
  let _class = e.getAttribute("class");
  if (! hasClass(e, cssClass)) {
    _class += " "+cssClass;
    e.setAttribute("class", _class);
  }
}

function removeClass(e, cssClass) {
  if (!e) return;
  let _class = e.getAttribute("class");
  if (hasClass(e, cssClass)) {
    _class = _class.replace(cssClass, "");
    _class = _class.replace("  ", " ");
    e.setAttribute("class", _class);
  }
}

function hasClass(e, cssClass) {
  if (!e) return false;
  let _class = e.getAttribute("class");
  if (_class === null) return false;
  return _class.indexOf(cssClass) >= 0;
}

function STACK_QUEUE (fn) {
  var self = this;
  self.arr = [];

  self.isEmpty = function () {
    return self.arr.length === 0;
  };

  self.add = function (e) {
    if (Array.isArray(e)) {
      self.arr = self.arr.concat(e);
    } else {
      self.arr.push(e);
    }
    return self;
  };

  self.retrieve = function () {
    return self.arr[fn]();
  };
}

function radomizeIt (arr) {
  let py0 = start.indexOf('y');
  let x0 = 1* start.substring(0,py0);
  let y0 = 1* start.substr(py0);

  let res = arr.slice();
  res.sort((a,b)=>(dist(b)-dist(a)));
/*  
  for (let i = 0 ; i < arr.length-1 ; i += 1) {
    let j = Math.floor(Math.random() * (arr.length - i));
    swap(i,j);
  }
*/
  return res;

  function swap (i,j) {

   if (i === j) return;
    var t = res[i];
    res[i] = res[j];
    res[j] = t;
  }
  function dist (id) {
    let py = id.indexOf('y');
    let x = 1* id.substring(0,py0);
    let y = 1* id.substr(py0);
    let dx = (x-x0);
    let dy = (y-y0);
    return dx*dx+dy*dy;
  }
} 

main();

.container {
  position: relative;
  width: 320px;
  height: 200px;
}

.cell {
  position: absolute;
  width: 5px;
  height: 5px;
  border: 1px solid black;
  backgound-color: white;
}

.visited {
  background-color: #39cccc;
}

.cell.start {
  background-color: #3c9970;
}

.end {
  background-color: #ff7066;
}

.visited.end {
  background-color: #ff0000;
}