Bishop: find shortest path from A to B

Question

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.

UPDATE

Thanks to all responders, I've implemented a solution. Here it is:

https://jsfiddle.net/heximal/teya2pcc/

  /**************************************
    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 && 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 < 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 = "->"
    return res.join(delim);
  }

  function cell_color(location) {
    var color = 1;
    if (location.x % 2 == 0 && location.y % 2 == 0)
      color = 1;
    if (location.x % 2 != 0 && location.y % 2 == 0)
      color = 0;
    if (location.x % 2 == 0 && location.y % 2 != 0)
      color = 0;
    if (location.x % 2 != 0 && location.y % 2 != 0)
      color = 1;
    return color;
  }

  function board_obj(pos) {
    var res = 0;
    if (pos.x < 0 || pos.x > 7 || pos.y < 0 || pos.y > 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 < 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 < 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 > 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 > 0) {
      iterations++;
      if (iterations >= 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 < possible_moves.length; j++) {
        var possible_move = possible_moves[j];
        if (explored.indexOf(possible_move) < 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 > 1 ? path : [];
  }

One important thing 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.

This is why I didn't manage to get the desired result before.

Answer 1

1. Create an undirected graph where the number of nodes is 32 minus the number of obstacles. Each node represents a black square (for a black bishop) or a white square (for a white bishop). Each edge represents a possible move between two squares.

2. Add an edge between any two nodes where a direct move is possible. If you are looking for the minimal number of moves - the graph may be unweighted. If you are looking for the minimum travel distance - set the edge weight according to the move length.

3. All you have to do now is to find the shortest path between the two required nodes. If the graph is unweighted use BFS or modified-DFS. If the graph is weighted - Dijkstra would do.

Finding the shortest path using BFS:

Given undirected unweighted graph G, the shortest path between nodes u and v can be found as follows:

// --- BFS(u, v)-----------------------------
      for each vertex w
      do  flag[w] := false;
          pred[w]  := -1  ;  // predecessor of w
      Q := empty queue;
      flag[u] := true;       // already visited
      enqueue(Q, u)
      while Q not empty
      do    w:= dequeue(Q);
            for each x adjacent to w
                     if flag[x] = false
                        flag[x] := true;
                        pred[x] := w   ;
                        if x = v
                           empty Q;
                           break;
                        else
                           enqueue(Q, x);

// --- ReportShortestPath(u, v)---------------
// backward path - v to u:
      current := v;
      do    output current;
            current := pred[currrent];
      while current != -1

Answer 2

One has to clarify whether shortest path refers to the minimum number of moves or the minimum number of fields travelled. In either case, the problem can be solved by using modified depth-first search; one would have to store the current shortest path, which makes an iterative implementation desireable since it might be impossible to explicitly read information from the call stack.