Главная > Coding > Алгоритм кратчайшего пути шахматной фигуры

Алгоритм кратчайшего пути шахматной фигуры

Недавно мне понадобилось решить задачу поиска кратчайшего пути с клетки A в клетку B алгоритмически, и реализовать это программно. «Наверняка это уже тысячу раз кто-то делал и в интернете полно готовых решений». — подумал я, и каково же было мое разочарование… Несколько дней поисков ничего конкретного не дали. Максимум, что удалось найти, это упоминание, что решить данную задачу можно используя теорию графов и алгоритмом поиска в ширину (BFS — breadth first search). В этой статье я попробую подробно разобрать данный способ нахождения кратчайшего пути шахматных фигур с примерами кода и пояснениями.

Для начала сформулируем четко задачу. И так, имеется шахматная доска размером 8х8 (размерность на самом деле не сильна важна), произвольное количество фигур (препятствия), фигура V и фигура U. Требуется найти кратчайший путь фигуры V до позиции фигуры U. Важное замечание: в данной статье под кратчайшим путем подразумевается минимальное количество ходов.

Условие задачи (без препятствий)

С препятствиями

Сразу приведу псевдо-код решения, а вслед за ним пояснение:

// --- 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

В первую очередь строим ненаправленный граф, число вершин которого равняется количеству клеток, до которых способна добраться фигура V. Такие фигуры, как Ладья, Конь, Ферзь, Король способны посетить любую клетку доски за определенное количество ходов, то есть количество вершин графа у них будет 64. Слон может посетить только клетки того же цвета, как и той, на которой он находится, поэтому его граф содержит максимум 32 вершины. В этот граф не должен включать клетки, на которых находятся препятствия (другие фигуры кроме V и U).
Далее, следует построить рёбра графа. Ребро соединяет две любые вершины графа.
Каждую вершину графа следует соединить ребрами со всеми другими вершинами графа, на которую из данной вершины может сделать ход фигура U. И так, имеем граф со всеми возможными ходами из всех возможных для фигуры S позиций доски.
Следующий этап — непосредственно процедура BFS (поиск в ширину).
Создаем FIFO (first in first out) очередь queue. Помещаем в нее вершину графа, которая соответствует текущей позиции фигуры U. Также создаем коллекцию посещенных вершин explored и словарь для хранения родительских вершин parents. Запускаем цикл while пока очередь не пуста. На каждой итерации цикла извлекаем из очереди последний элемент, который представляет собой вершину. Извлекаем из графа все ребра этой вершины (все возможные ходы из данной вершины) и помещаем в очередь только те ходы, которые отсутствуют в коллекции explored, а также помещаем эти ходы в коллекцию explored и запоминаем в словаре parents родителя для этих ходов. Если очередная вершина возможного хода совпадает с позицией атакуемой фигуры U, завершаем цикл BFS.
После завершения цикла BFS составляем коллекцию вершин, которые и будут являться кратчайшим путем. Начинаем обходить вершины в обратном порядке, то есть с той вершины, в которой находится атакуемая фигура V. Запускаем цикл while пока переменная-родитель не станет пустой (это будет означать, что найден конец пути). Присваиваем переменной цикла значение из коллекции parents.

Теперь реализация на JavaScript (почему на нем? потому что проект, в котором мне понадобилось это реализовать именно на JS)

  var bishop_pos = p(3, 5);
  var target_pos = p(3, 1);
 
  var board = [
    [0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0],
    [0, 0, 0, "b", 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, "t", 0, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 0]
  ];
 
  /**************************************
    Chess board logic functions
  ***************************************/
  function p(x, y) {
    return {
      x: x,
      y: y
    };
  }
 
  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 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 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, target_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 : [];
  }
 
  var path = search_bfs(bishop_pos, target_pos);
  // переменная path содержит искомый путь
  // если path является пустым массивом, значит заданная клетка недостижима для фигуры

Главаня функция — search_bfs, ей в параметре передается позиция атакующей фигуры V и позиция цели.
Ниже приведена реализация алгоритма поиска кратчайшего пути для фигуры Слон.
Ее можно отдельно посмотреть и скачать здесь и на jsfiddle

Categories: Coding Tags: , , , ,
  1. wb77
    20 January 2018 в 13:47 | #1

    А почему не выбрал классический алгоритм Дейкстры?

  2. wb77
    20 January 2018 в 13:58 | #2

    И еще, мне кажется, нужно ребрам присвоить вес — за сколько ходов фигура добирается до вершины, которую соединяет данное ребро.

  3. wb77
    20 January 2018 в 14:02 | #3

    Не, протупил, вес не нужен)
    Условия задачи — как раз это количество ходов и найти)

  4. 23 January 2018 в 19:35 | #4

    @wb77, таки да) я не проверял, но интуиция подсказывает, что Дейкстра дороже стоит.

Подписаться на комментарии по RSS