В прошлой статье мы сделали "скелет" генератора ходов. Пора учить фигуры ходить по своим правилам. Начнём пожалуй с коня. У него самая простая логика хода. Да и ходить он может с первого хода, перепрыгивая пешки, что облегчит тестирование. Начнём, как обычно, с небольшого рефакторинга.
Микрорефакторинг
Опять я дал имя методу в "змеиной нотации" - метод figure_type в классе Functions. Меняем имя метода на figureType. И соответственно меняем имя в месте вызова - в классе FigureFactory, строка 6:
$figure_type = Functions::figureType($figure_code);Подготавливаем положение фигур
При генерации ходов мы будем проверять - допустима-ли позиция, которая получится после хода? Например, мы переместили коня, но уходя, он открыл своего короля, и он оказался под атакой дальнобойной фигуры. Нам часто придётся искать - на каком поле расположен наш король. Можно конечно каждый раз перебирать массив $this->game_state->position, но зачем, если можно заранее записать положение короля? Можно записать положение не только короля, но и всех фигур. Кажется нам это понадобится при оценке позиции.
Кроме того, кажется что генерация перемещений будет "узким местом" производительности. Конечно, "преждевременная оптимизация - зло", не будем сейчас ей заниматься. Но положение фигур запишем.
Открываем файл engine/game_state.php с классом GameState. К списку полей класса добавляем поле, где будем хранить положение фигур:
public $figures = null; // ассоциативный массив "фигура => массив с индексами полей, на которых эта фигура находится"Добавляем метод для заполнения нового поля:
public function setFigures() {
$this->figures = array(
FG_KING + COLOR_WHITE => array(),
FG_KING + COLOR_BLACK => array(),
FG_QUEEN + COLOR_WHITE => array(),
FG_QUEEN + COLOR_BLACK => array(),
FG_ROOK + COLOR_WHITE => array(),
FG_ROOK + COLOR_BLACK => array(),
FG_BISHOP + COLOR_WHITE => array(),
FG_BISHOP + COLOR_BLACK => array(),
FG_KNIGHT + COLOR_WHITE => array(),
FG_KNIGHT + COLOR_BLACK => array(),
FG_PAWN + COLOR_WHITE => array(),
FG_PAWN + COLOR_BLACK => array()
);
for($i = 0; $i < BOARD_SIZE*BOARD_SIZE; $i++) {
$figure_code = $this->position[$i];
if ($figure_code !== FG_NONE) {
$this->figures[$figure_code][] = $i;
}
}
}В строках 2 - 15 мы указываем полный список фигур и для каждой указываем пустой массив полей, на которых они находятся. Далее, в цикле проходим по всем полям, и если поле не пустое, добавляем индекс поля в массив для фигуры, находящейся на этом поле.
Зачем нужно предварительное заполнение полного списка фигур пустыми массивами? Мне показалось что так будет удобнее. Например мы захотим узнать, где находятся белые ладьи. И, например, их уже нет на доске. Тогда в $this->figures[FG_ROOK + COLOR_WHITE] будет пустой массив. А если не делать предварительное заполнение для всего списка фигур, то ключа для белой ладьи (FG_ROOK + COLOR_WHITE) вообще не будет в массиве $this->figures. И нужно будет сначала проверять наличие этого ключа. А при предварительном заполнении, можно без проверки сразу делать цикл по "положению ладей".
И вызываем новый метод заполнения фигур в конструкторе генератора перемещений, Т.е. в файле engine/move_generator.php, конструктор класса должен выглядеть так:
public function __construct(GameState $game_state) {
$this->game_state = $game_state;
$this->game_state->setFigures();
}Вспомогательные методы для работы с индексом позиции
Ещё нам понадобится преобразовывать индекс позиции в индекс колонки (столбца) и в индекс ряда (строки).И понадобится обратное преобразование - по столбцу и ряду получить инекс позации. В класс добавляем три статик-метода:
static public function positionToCol(int $position_index) {
return $position_index & 0b111;
}
static public function positionToRow(int $position_index) {
return $position_index >> 3;
}
static public function colRowToPositionIndex($col, $row) {
return ($row << 3) + $col;
}Для получения колонки из позиции (positionToCol) достаточно взять остаток от деления индекса позации на 8. Или, что то-же самое - взять три младших двоичных разряда числа- индекса позиции, что мы в коде и делаем.
Для получения строки из позиции (positionToRow) можно разделить индекс позиции на 8, отбрасывая остаток, или,как мыделаем в коде - сдвинуть индекс позиции на три разряда вправо.
Ну и индекс из позиции (colRowToPositionIndex) получить так-же просто - строку умножить на 8 (сдвинуть на три разряда влево) и прибавить колонку.
Общая логика допустимых ходов фигур
Когда стал реализовывать логику ходов для коня, увидел, что некоторые действия будут одинаковыми и для других фигур. Для каждого варианта хода надо сформировать позицию, которая возникнет после этого хода и проверить её допусимость - не находится ли наш король под ударом.
В итоге решил сделать некую общую логику в абстрактном классе Figure, в методе getAvailableMoves. Т.е., этот метод уже не будет абстрактным. А логику получения "ходов - кандидатов" конкретной фигуры сделать в методе getCandidateMoves. И вот этот метод в классе Figure сделать абстрактным.
Т.е., сейчас идём в класс Figure, переименовываем метод getAvailableMoves в getCandidateMoves. Идём во все классы конкретных фигур (King, Queen, Rook, Bishop, Knight, Pawn) и делаем там такое-же переименование.
Добавляем поля в класс фигуры
Идём опять в класс Figure (engine/figure.php), добавляем поля:
protected int $col; // индекс колонки положения фигуры
protected int $row; // индекс строки положения фигуры
protected int $figure; // фигура, для которой создан экземпляр класса
protected int $color; // цвет фигуры
protected int $enemy_color; // цвет фигур противникаЭти поля понадобятся не один раз, и я добавил их, чтобы не вычислять каждый раз. И сразу добавим заполнение этих полей в конструкторе класса, добавив туда строки:
$this->col = Functions::positionToCol($position_index);
$this->row = Functions::positionToRow($position_index);
$this->figure = $game_state->position[$position_index];
$this->color = Functions::color($this->figure);
$this->enemy_color = $this->color == COLOR_BLACK ? COLOR_WHITE : COLOR_BLACK;Общая логика получения допустимых ходов
Остаёмся пока в классе Figure и пишем общую логику получения допустимых ходов:
engine/figure.phppublic function getAvailableMoves() {
$moves = array();
$board_position = new BoardPosition();
$our_king_position = $this->game_state->figures[FG_KING + $this->color][0];
$candidate_moves = $this->getCandidateMoves();
foreach($candidate_moves as $to_index) {
$to_position = $this->game_state->position; // копируем позицию
$to_position[$this->position_index] = FG_NONE; // убираем фигуру из текущей позиции
$to_position[$to_index] = $this->figure; // перемещаем фигуру на выбранное поле. Если на том поле что-то стояло - оно "убирается"
$board_position->setPosition($to_position);
if ($board_position->isFieldUnderAttack($our_king_position, $this->enemy_color)) {
// ход недопустим, т.к. после него наш король оказывается под атакой
continue;
}
$moves[] = $to_index;
}
return $moves;
}
В строке 2 в переменную $moves записываем пустой массив. Сюда будем накапливать допустимые ходы фигуры, и в конце метода отдадим именно эту переменную (строка 17).
В строке 3 создаём объект класса BoardPosition. Этот класс скоро напишем. Он нужен будет для проверки допустимости позиции после перемещений.
В строке 4 определяем позицию нашего короля. Помните, мы сделали поле figures в классе состояния игры? Вот тут оно и пригодилось. Берём позицию нашего короля, и запоминаем в переменной, она нам неоднократно понадобится. Массив figures для каждого вида фигуры возвращает массив с позициями, так что берём нулевой элемент - он-то должен быть, ведь король должен быть на доске. И второго элемента не должно быть - король нашего цвета всего один.
В строке 5 вызываем метод getCandidateMoves для получения "ходов-кандидатов", т.е. полей, куда фигура могла-бы переместиться, если не учитывать допустимость получившейся позиции. Этот метод является асбтрактным в классе Figure, и должен быть реализован в потомках класса.
Далее (строки 6 - 16) делаем цикл по "ходам - кандидатам". В строке 7 запоминаем копию позиции из поля с "состоянием игры". Дальше, в этой копии делаем перемещение - убираем фигуру из текущей позиции (строка 8), и ставим её в позицию, куда указывает текущий "ход-кандидат" (строка 9). Если в этой позиции стояла какая-то фигура, она просто исчезает из позиции, мы перезаписали на её место нашу фигуру, т.е. "взяли фигуру".
Далее, в строке 10 мы устанавливаем получившуюся позицию в $board_position - экземпляре класса BoardPosition, вызывая метод setPosition. Чуть ниже мы напишем этот класс.
В строке 11 вызываем метод isFieldUnderAttack (терпение, скоро напишем его), передавая ему позицию нашего короля, и цвет фигур противника. Этот метод должен ответить (true или false) - находится ли поле, переданное в первом параметре под атакой фигур цвета, переданного во втором параметре. Если метод вернул true, значит наш король оказался под атакой после совершения текущего хода - кандидата. Значит этот ход-кандидат не "валидный" / неправильный. В такой случае завершаем итерацию цикла, переходим к следующей - строка 13
Иначе проходим дальше. И раз наш король не под атакой после совершения хода-кандидата, значит это допустимый ход, добавляем его в результирующий массив $moves.
Класс BoardPosition
Напишем класс, который только что применяли в методе получения допустимых ходов. В папке engine создаём файл board_position.php:
engine/board_position.php<?php
class BoardPosition {
private $position;
public function setPosition(array $position) {
$this->position = $position;
}
// Метод возвращает булево значение - атаковано-ли поле с индексом $cell_index фигурами цвета $color
public function isFieldUnderAttack($cell_index, $color) {
return false;
}
}
Тут всё просто - одно приватное поле $position, в котором будем хранить позицию. Метод для записи этой позиции - setPosition. И метод для определения, атаковано-ли определённое поле позиции фигурами заданного цвета - isFieldUnderAttack. Пока тут "заглушка" - метод просто всегда возвращает false, т.е. как будто-бы поле не под атакой. Этот метод реализуем позже, не в этой статье.
Ну и конечно надо подключить новый файл к проекту. Открываем engine/chess_game.php, и к списку подключаемых файлов, добавляем новый:
require_once('board_position.php');Ходы-кандидаты для коня
Реализуем собственно правила хода для коня. Открываем файл с классом коня - engine/figures/knight.php. У нас там есть метод getCandidateMoves - помните в начале этой стать мы переименовывали методы getAvailableMoves?
У коня есть восемь вариантов ходов. Он может сместиться на два поля по горизонтали в любую сторону, и из того положения ещё на одно поле по вертикали в любую сторону. Ещё он может сместиться по вертикали на два поля вверх или вниз, и оттуда ещё на одно поле влево или вправо. Создадим массив с возможным смещениями из текущей позиции и будем проверять каждый ход на допустимость. Класс коня будет выглядеть так:
engine/figures/knight.php<?php
class Knight extends Figure {
public function getCandidateMoves() {
$moves = array();
$shifts = array(
array(-2, -1), array(-2, 1), array(-1, -2), array(-1, 2), array(1, -2), array(1, 2), array(2, -1),array(2, 1)
);
foreach($shifts as $shift) {
$col = $this->col + $shift[0];
if ($col < 0 || $col >= BOARD_SIZE) {
continue;
}
$row = $this->row + $shift[1];
if ($row < 0 || $row >= BOARD_SIZE) {
continue;
}
$to_index = Functions::colRowToPositionIndex($col, $row);
$to_figure = $this->game_state->position[$to_index];
if ($this->color == Functions::color($to_figure)) {
continue;
}
$moves[] = $to_index;
}
return $moves;
}
}
Как обычно, сначала создаём пустой массив $moves куда будем записывать ходы - кандидаты. Массив с возможными смещениями $shifts создали в строках 6 - 8. Каждый элемент массива со смещениями - массив из двух чисел. Первое - будем считать смещением по горизонтали, второе - по вертикали. И дальше в цикле (стр. 9 - 24) проходим по возможным смещениям.
Сначала вычисляем новую колонку в строке 10. В классе фигуры есть поле col, к нему прибавляем первый (с индексом 0) элемент смещения (смещение по горизонтали, так что меняется номер колонки, col), и записываем в переменную $col.
В строке 11 проверяем, не вышли ли мы за пределы доски. Индекс колонки (вертикали) меняется от нуля до 7. И если получившееся значение $col меньше нуля или больше или равно 8 (константа BOARD_SIZE), то просто завершаем текущую итерацию цикла, переходим к следующей.
Аналогично всё проделываем со вторым элементом смещения (индекс 1) в строках 14 - 17. Вычисляем индекс строки row. Если вышли за пределы доски - завершаем итерацию цикла.
В строке 18 мы оказываемся только если позиция, характеризуемая координатами $col, $row оказывается внутри доски. С помощью статического метода Functions::colRowToPositionIndex получаем индекс позиции по координатам $col, $row, и записываем его в переменную $to_index.
В строке 18 берём фигуру, находящуюся на поле с индексом $to_index, т.е. на поле, куда собираемся переместить коня. Записываем эту фигуру (а это может быть и FG_NONE, т.е. пустое поле) в переменную $to_figure.
В строке 20 сравниваем цвет текущей фигуры, т.е. фигуры для которой генерируем "ходы-кандидаты", и цвет фигуры $to_figure,т.е. фигуры, находящейся на поле, куда собираемся переместить текущую фигуру. Если эти цвета совпадают, то такой вариант хода невозможен - нельзя брать свою фигуру. В такой случае завершаем текущую итерацию.
К строке 23 все проверки оказываются пройденными, добавляем индекс поля $to_index к результирующему массиву ходов - кандидатов.
Учим фигуры двигаться
Теперь в ответе на запрос get_game_state.php, в поле available_moves появились возможные ходы для коней. И если создать игру "за белых", и кликнуть по своему коню, то увидим выделение полей, куда можно сделать ход. Если кликнуть на поле, отмеченное как возможное для перемещения, конь туда визуально переместиться. Но при обновлении страницы фигуры опять займут начальное положение.
Так происходит потому что фигуры на стороне сервера ещё не умеют "ходить" - не меняется позиция в "состоянии игры". Код на стороне браузера, т.е. javascript переместит визуально фигуру на доске и пошлёт запрос make_move.php. Обработкой этого запроса мы сейчас и займёмся. Настало время научить фигуры двигаться!
Открываем файл make_move.php, видим - мы там уже вызываем метод makeMove у объекта игры. Пока правда тот метод ничего не делает. Им-то мы и займёмся. Но в контроллере, т.е. в файле make_move.php кое-чего не хватает. Мы создаём объект игры, и сразу вызываем метод makeMove. На пустой игре! Нам надо загрузить состояние игры из хранилища. Т.е. сразу после создания объекта игры, т.е. после строки №5, вставляем:
$game->loadGame();makeMove в классе игры
Открываем класс игры (файл engine/chess_game.php), идём к пустому пока методу makeMove, и наполняем его:
engine/chess_game.phppublic function makeMove($cell_index_from, $cell_index_to) {
$color = $this->game_state->current_player_color;
$figure_code = $this->game_state->position[$cell_index_from];
if ($figure_code === FG_NONE || Functions::color($figure_code) != $color) {
$this->game_state->text_state = 'Недопустимый ход: Вы можете ходить только фигурами своего цвета';
return;
}
$figure_factory = new FigureFactory();
$figure = $figure_factory->create($this->game_state, $cell_index_from);
if ($figure->makeMove($cell_index_to)) {
$this->storage->saveGameState($this->game_state);
}
}
Напомню, этот метод нужен для перемещения фигуры в текущем состоянии игры с поля $cell_index_from на поле $cell_index_to. И эти индексы полей к нам пришли из контроллера make_move.php, а туда - из "внешнего мира" в POST-запросе. И нам сначала надо проверить, корректный ли ход нам передали.
Сначала мы берём цвет фигур текущего игрока, т.е. фигуры какого цвета сейчас ходит (строка 2). Потом берём фигуру, которая находится в поле "откуда". В строке 4 проверяем, если в поле "откуда" нет фигуры, или её цвет не совпадает с цветом, чья сейчас очередь хода, то нам пришли некорректные данные, и в строке 5 мы записываем сообщение о недопустимом ходе в состояние игры, в поле text_state. И уходим из метода.
Вообще, хорошо бы проверить и индексы полей "откуда" и "куда" на корректность - они должны находится в интервале от нуля до 63. Но эта мысль пришла в голову уже при описании кода, возможно позже добавим такую проверку.
Далее, в строках 8, 9 с помощью фабричного метода создаём класс фигуры, которая ходит, т.е. которая находится на поле "откуда". Мы так уже делали в генераторе ходов (в классе MoveGenerator). В строке 10 вызываем метод фигуры makeMove, который сейчас напишем. В метод передаём индекс поля куда ходит фигура.
И если метод makeMove возвратил true, т.е. удалось сделать ход, то сохраняем состояние игры (строка 11).
makeMove в классе фигуры
Что надо сделать в методе makeMove? Надо переместить фигуру - собственно сделать ход, и изменить поля состояния игры - увеличить счётчик ходов, передать очередь хода, и прочее. Идём в общий класс фигуры, добавляем метод:
engine/figure.phppublic function makeMove($to_cell_index) {
// проверяем - а корректный ли ход нам передали?
$this->game_state->setFigures();
$available_moves = $this->getAvailableMoves();
if (!in_array($to_cell_index, $available_moves)) {
$this->game_state->text_state = 'Недопустимый ход. Сделайте корректный ход';
return false;
}
$to_figure = $this->game_state->position[$to_cell_index];
// делаем изменение в позиции - двигаем фигуру
$this->game_state->position[$this->position_index] = FG_NONE;
$this->game_state->position[$to_cell_index] = $this->figure;
// Обnull-яем "пересекаемое поле". Для хода пешки это поведение изменим
$this->game_state->crossed_field = null;
// изменяем счётчик числа полуходов, после последнего взятия фигуры или движения пешки
if ($to_figure !== FG_NONE || Functions::figureType($this->figure) == FG_PAWN) {
$this->game_state->non_action_semimove_counter = 0;
} else {
$this->game_state->non_action_semimove_counter++;
}
// изменяем счётчик ходов и очередь хода
if ($this->color == COLOR_BLACK) {
$this->game_state->move_number++;
$this->game_state->current_player_color = COLOR_WHITE;
} else {
$this->game_state->current_player_color = COLOR_BLACK;
}
// изменяем информацию о предыдущих полях "откуда" и "куда"
$this->game_state->prev_move_from = $this->position_index;
$this->game_state->prev_move_to = $to_cell_index;
// изменяем текстовое описание состояния игры
if ($this->game_state->human_color == $this->color) {
$this->game_state->text_state = "#{$this->game_state->move_number} Ход компьютера, подождите";
} else {
$this->game_state->text_state = "#{$this->game_state->move_number} Ваш ход.";
}
return true;
}
В этом методе мы сначала проверяем допустимость хода. Вызываем метод класса getAvailableMoves для получения допустимых ходов фигуры (строка 4), а в следующей строке проверяем - входит ли поле куда нам надо переместить фигуру ($to_cell_index) в список допустимых ходов (который мы тлько что получили). Если не входит - значит ход недопустим, делаем соответствующую запись в "состояние игры" и возвращаем из метода false (строки 6, 7).
Далее делаем перемещение фигуры - убираем её с поля "откуда", записываем в поле "куда". Устанавливаем в null "пересекаемое поле" - поле, которое перепрыгнула пешка при своём ходе, это поле нужно для реализации правила "взятия на проходе". Изменяем счётчик полуходов, за которые не было ни одного взятия и движения пешки. Это нужно для реализации правил 50 и 75 ходов. Ну а дальше всё совсем просто, и описано в комментариях.
Всё! Теперь можно ходить конями, и изменения будут запомнены.
Микрооптимизация
Когда мы сделали ход, сервер присылает в ответ данные, нужные для отображения состояния игры в браузере. Или, когда мы после своего хода обновили страницу, сервер тоже присылает эти данные. Или когда мы создали игру "за чёрных", мы получаем такой-же ответ. Это понятно, ведь во всех случаях сервер нам возвращает в json-виде данные, полученные вызовом $game->getClientJsonGameState().
И знаете что я заметил? В этом ответе заполняется поле available_moves с допустимыми ходами из текущей позиции. Когда наш ход, эти "допустимые ходы" нужны для подсветки при выделении фигуры, для простейшей логики визуализации хода на стороне браузера. Но "допустимые ходы" вычисляются и передаются даже когда ход не наш, а компьютера! Это лишние вычисления. Давайте их уберём.
Открываем файл engine/chess_game.php, идём в метод getClientJsonGameState. Сделаем чтобы в возвращаемом массиве ключ available_moves заполнялся только если сейчас ход человека. А факто того, что сейчас ход человека у нас вычисляется при заполнении ключа is_numan_move:
'is_human_move' => $this->game_state->current_player_color == $this->game_state->human_color,Чтобы не копипастить это длинное логическое выражение, вынесем его отсюда в переменную. Т.е. перед строкой return array( пишем:
'$is_human_move' = $this->game_state->current_player_color == $this->game_state->human_color;Используем эту переменную при заполнении ключа is_numan_move:
'is_human_move' => $is_human_move,Ну и заполнение допустимых ходов меняем на такое:
'available_moves' => $is_human_move ? $this->generateAvailableMoves() : array()Т.е., если сейчас ход человека, то вычисляем допустимые ходы как и раньше, иначе - пишем пустой массив.
Итоги
В этой части мы написали общую логику перемещения фигур, научили ходить коня, и стали менять состояние игры при совершении хода. Теперь фигура (пока только конь) реально перемещается, её положение фиксируется в состоянии игры и сохраняется.
Исходные коды этой части можно посмотреть на github. И конечно можно посмотреть демо №7 игры
Сумашедшие кони
Пока компьютер не научился огрызаться, можно вволю порезвиться конями, которые научились скакать. Можно убрать смену очерёдности хода - идём в класс Figure, в метод makeMove, и комментируем / убираем строку
$this->game_state->current_player_color = COLOR_BLACK;И теперь можно прыгать конями без ограничений. Можно взять все чёрные фигуры, включая короля. Ну и убедиться, что допустимые ходы вычисляются правильно.
На этой картинке видно по "выделениям предыдущего хода", что предыдущий ход был конём с поля b5 на поле c7. И что сейчас выделен конь, находящийся на поле f3, и зелёными кружками отмечены "допустимые ходы".
Я отдельно выложил демо с "сумашедшими конями", пробуйте.