title: Bishop: find shortest path from A to B
body: <p>I'm currently trying to find a solution for the following problem: given chess board 8x8 with one bishop and number of obstacles, it's required to find shortest path from current bishop position to other particular position.</p>
  
  <p><strong>UPDATE</strong></p>
  
  <p>Thanks to all responders, I've implemented a solution. Here it is:</p>
  
  <p><a href="https://jsfiddle.net/heximal/teya2pcc/" rel="nofollow noreferrer">https://jsfiddle.net/heximal/teya2pcc/</a></p>
  
  <pre><code>  /**************************************
      Chess board logic functions
    ***************************************/
    function p(x, y) {
      return {
        x: x,
        y: y
      };
    }
  
    function pos_equals(p1, p2) {
      if (p1 == null || p2 == null) return false;
      return p1.x == p2.x &amp;&amp; p1.y == p2.y;
    }
  
    function human_pos(pos) {
      return pos2alpha(pos.x, pos.y);
    }
  
    function pos2alpha(x, y) {
      return alpha[x] + (y + 1);
    }
  
    function intpos2alpha(intpos) {
      y = Math.trunc(intpos / 10);
      x = intpos - (y * 10);
      return alpha[x] + (y + 1);
    }
  
    function pos2int(pos) {
      return pos.y * 10 + pos.x;
    }
  
    function int2pos(intpos) {
      var y = Math.trunc(intpos / 10);
      var x = pos_int - (y * 10);
      return p(x, y);
    }
  
    function pos2path(pos, delim) {
      if (pos == null) return "[]";
      var res = [];
      for (var i = 0; i &lt; pos.length; i++) {
        var p1 = pos[i];
        var x = 0,
          y = 0;
        if (typeof p1 === 'object') {
          x = p1.x;
          y = p1.y;
        } else {
          y = Math.trunc(p1 / 10);
          x = p1 - (y * 10);
        }
        res.push(pos2alpha(x, y));
      }
      if (delim == null) delim = "-&gt;"
      return res.join(delim);
    }
  
    function cell_color(location) {
      var color = 1;
      if (location.x % 2 == 0 &amp;&amp; location.y % 2 == 0)
        color = 1;
      if (location.x % 2 != 0 &amp;&amp; location.y % 2 == 0)
        color = 0;
      if (location.x % 2 == 0 &amp;&amp; location.y % 2 != 0)
        color = 0;
      if (location.x % 2 != 0 &amp;&amp; location.y % 2 != 0)
        color = 1;
      return color;
    }
  
    function board_obj(pos) {
      var res = 0;
      if (pos.x &lt; 0 || pos.x &gt; 7 || pos.y &lt; 0 || pos.y &gt; 7)
        res = "o";
      else
        res = board[7 - pos.y][pos.x];
      return res;
    }
  
  
    /**************************************
      Major find path functions
    ***************************************/
    var iterations = 0;
    // let's prevent scanning with particular iterations count
    // to avoid very long execution
    var max_iterations_count = 10000;
  
    /*
        ----------------    
        | nw |    | ne |
        ----------------
        |    | Bs |    |
        ----------------
        | sw |    | se |
        ----------------
    */
  
    var nw_vector = p(-1, 1);
    var ne_vector = p(1, 1);
    var se_vector = p(1, -1);
    var sw_vector = p(-1, -1);
  
    function find_path() {
      if (target_pos == null || bishop_pos == null) {
        alert("bishop and target both must be set");
        return;
      }
      var path = [];
      var start = new Date().getTime();
      if (cell_color(bishop_pos) == cell_color(target_pos)) {
        path = search_bfs(bishop_pos);
      }
      var end = new Date().getTime();
      var dur = end - start;
      output_result(path, dur);
    }
  
    function vector_point(pos, vector, shift) {
      return p(pos.x + shift * vector.x, pos.y + shift * vector.y);
    }
  
    function possible_moves_from(pos) {
      var vectors = [{
        active: true,
        vector: se_vector
      }, {
        active: true,
        vector: sw_vector
      }, {
        active: true,
        vector: nw_vector
      }, {
        active: true,
        vector: ne_vector
      }];
      var shift = 1;
      var res = [];
      while (vectors[0].active || vectors[1].active || vectors[2].active || vectors[3].active) {
        for (var j = 0; j &lt; vectors.length; j++) {
          if (vectors[j].active) {
            iterations++;
            var v_pos = vector_point(pos, vectors[j].vector, shift);
            var l_obj = board_obj(v_pos);
            if (l_obj == "o" || l_obj == "b") {
              vectors[j].active = false;
            } else {
              res.push(v_pos.y * 10 + v_pos.x);
            }
          }
        }
        shift++;
      }
      return res;
    }
  
    function search_bfs(original_pos) {
      // reset global iterations counter
      iterations = 0;
      var original_pos_int = pos2int(original_pos);
  
      // create undirected graphs with all possible bishop positions
      var vertices = {};
  
      var pos = p(0, 0);
      // if bishop cell color differs from color of left-bottom cell color (A1)
      // than start with cell (A2)
      if (cell_color(pos) != cell_color(original_pos)) {
        pos.x = 1;
      }
  
      // let's convert cell positions {x: n, y: m} to integer representation
      // int_pos = y+10 + x, e.g. B2 = 1 * 10 + 1 = 11
      var target_pos_int = pos2int(target_pos);
      for (var i = 0; i &lt; 32; i++) {
        var intpos = pos2int(pos);
        var l_obj = board_obj(pos);
        // if pos doesn't contain obstacle
        // get a collection of all moves that bishop can make from pos
        if (l_obj != "o") {
          var possible_moves = possible_moves_from(pos);
          vertices[intpos] = possible_moves;
        }
        pos.x += 2;
        if (pos.x &gt; 7) {
          pos.x = pos.x % 2 == 0 ? 1 : 0;
          pos.y++;
        }
      }
  
      // initialize BFS queue (enqueue bishop position)
      var queue = [original_pos_int];
      // initialize BFS explored nodes collection
      var explored = [original_pos_int];
      // initialize parent nodes map
      var parents = {};
      while (queue.length &gt; 0) {
        iterations++;
        if (iterations &gt;= max_iterations_count) {
          console.log("max iterations exceeded (" + max_iterations_count + "). stop searching");
          return [];
        }
        var pos_int = queue.pop();
        var y = Math.trunc(pos_int / 10);
        var x = pos_int - (y * 10);
        var pos = p(x, y);
        var possible_moves = vertices[pos_int];
        if (possible_moves == null) continue;
        for (var j = 0; j &lt; possible_moves.length; j++) {
          var possible_move = possible_moves[j];
          if (explored.indexOf(possible_move) &lt; 0) {
            parents[possible_move] = pos_int;
            explored.push(possible_move);
            if (target_pos_int == possible_move) {
              queue = [];
              break;
            } else {
              queue.splice(0, 0, possible_move);
            }
          }
        }
      }
      // start backward traverse from target to bishop position
      // and compose result path
      var path = [];
      var current = target_pos_int;
      while (current != null) {
        path.push(current);
        current = parents[current];
      }
      // if path contains only one element, then path is not found
      return path.length &gt; 1 ? path : [];
    }
  </code></pre>
  
  <p><strong>One important thing</strong> you must keep in mind when using BFS: when you enqueue the element, you have to place it to the beginning but not to the end of queue.</p>
  
  <p>This is why I didn't manage to get the desired result before.</p>