Dagaz: Орда

imageМильоны — вас. Нас — тьмы, и тьмы, и тьмы.
Попробуйте, сразитесь с нами!
Да, скифы — мы! Да, азиаты — мы…
 
Александр Блок «Скифы»

В предыдущей статье я много рассказывал о своих находках в области дизайна и пользовательского интерфейса настольных игр, но тот рассказ пришлось прервать, можно сказать на середине, отчасти по причине большого объёма статьи, отчасти просто потому, что в тот момент я не был готов продолжать его дальше. С тех пор многое изменилось. Новые интересные задачки были решены, а породившие их (не менее интересные) игры были добавлены в релиз. Об этом я и хочу рассказать сегодня.


Если кто помнит, речь шла об игре «Абалон», разработанной Мишелем Лале и Лораном Леви в 1988 году. Суть её в выталкивании за пределы поля шаров противника. Два шара могут толкать один, а три шара — пару шаров другого цвета. Игрок может перемещать свои шары по доске, как по одному, так и группами, по два или три шара (при этом, три шара должны составлять «ряд»). Что мешало мне сделать эту игру в прошлый раз?

Очевидно, не само групповое перемещение. Одновременное перемещение нескольких фигур, в рамках одного хода, есть даже в Шахматах (рокировка). А головоломки «Sliding puzzles» просто таки построены на том, чтобы такое перемещение происходило синхронно и плавно. Давайте посмотрим на одну игру, разработанную Робертом Эбботом в 1975 году:

kvfpd-kf--0kt2sproxmbidswpi.png


Это похоже на «Абалон». Разница лишь в том, что «ряд» не «выталкивает» фигуру противника с её места, а просто убирает с доски, используя «шахматное» взятие. Победа присуждается тому из игроков, кто сумел провести на последний ряд доски своих фигур больше, чем это удалось сделать его противнику, на тот же момент. Вся игра построена на перемещении «рядов». Добиться победы ходами лишь одиночных фигур вряд ли удастся. Вот как выглядит простой «толкающий» ход.

ZRF
(define push-1 (
  $1 (verify friend?)
  (while friend?
      cascade 
      $1
  )
  (verify not-friend?)
  add
))


Всё дело в волшебном слове cascade — оно заставляет интерпретатор «отпустить» перемещаемую фигуру на текущее поле, взяв оттуда «в руку» другую фигуру (свою или противника — не важно) и продолжить движение, уже с новой фигурой «в руке». За один ход такую операцию можно производить многократно, перемещая, таким образом, неограниченное количество фигур одновременно. Такие (и чуть более сложные) кейсы встречаются и в других играх — «Пушках», «Дамео», «Игре Леутуэйта», …

tscz0-t_xblqjzzxeolgpa-7cjm.gif


С точки зрения пользовательского интерфейса, «толкающие» ходы также реализуются довольно тривиально. Привычная метка целевого поля (зелёненький кружок) появляется на фигуре. Если (по правилам игры) мы можем эту фигуру съесть — едим (шахматное взятие), в противном случае — толкаем. Можно проталкивать ряд и более чем на одно поле вперёд (как в игре Epaminondas). Конечно, кодирование такого хода будет чуть более сложным:

ZRF
(define push-2 (
  $1 (verify friend?)
  (while friend?
      mark
      $1 (verify not-enemy?)
      to back cascade
      $1
  )
  $1 (verify not-friend?)
  add
))


Ключевое слово to (и парное ему from) действует совместно с cascade. Оно означает, что фигуру «из руки» надо поставить на доску уже сейчас, а новую фигуру «взять в руку» чуть погодя, после навигации на другое поле. В общем, «толкающие» ходы — это просто, но в Абалон есть и другая разновидность группового перемещения:

tahnjsqbpx_m2hmguohqdiannb4.gif


Я называю их «поперечными» ходами. С точки зрения ZRF-кодирования, в них нет ничего сложного. Проблема именно в пользовательском интерфейсе. Как «сказать» программе о том, что игрок хочет переместить не один шар, а группу, если и тот и другой ход разрешены правилами? Я использую всё тот же «blink», так пригодившийся мне в шашках, для пометки «текущей» фигуры. Только теперь «текущих» фигур в наборе несколько.

Клик по «свободной» фигуре добавляет её в группу в том случае, если существует ход, в котором задействованы все добавленные в группу фигуры (ещё проще не отпускать кнопку, выделяя всю группу одним движением мыши). Если таких ходов нет, просто создаётся новая группа, пока состоящая из одной фигуры. Зелёные круги всегда показываются для последней добавленной фигуры (это, возможно, не очень очевидно, но привыкнуть можно). Повторный клик по любой «блинкающей» фигуре немедленно сбрасывает всю группу.

Кстати
Зелёные круги вовсе не обязательно будут появляться просто при наличии «блинкающих» фигур. В некоторых случаях, возможна ситуация, в которой все выбранные фигуры входят в какой-то допустимый ход, но при этом не существует допустимого хода, ограничивающегося перемещением лишь этих выбранных фигур. Звучит немного запутанно, но вот вам иллюстрация:
d_3hmeibopemfxnzcfpmwmvztty.gif

В этой игре допускаются одновременные ходы только лишь групп из трёх фигур (если фигур осталось меньше, двигаться должны все). Все выбранные фигуры двигаются на один шаг и в одном и том же направлении. Взятие шахматное, свои фигуры мешают перемещению. Для победы, необходимо провести хотя бы одну из своих фигур на последнюю линию, в лагерь противника.

Сама игра, на мой взгляд, не очень интересна, но, с точки зрения кодинга — это настоящее безумие. Любая попытка «честной» генерации всех возможных ходов групп из трёх фигур приводит к комбинаторному взрыву. Приходится хитрить (благо Dagaz это позволяет). Для начала, генерируем все допустимые ходы одиночных фигур. Это просто:

(define step (
  $1 add
))


Пока можно даже не проверять возможный бой собственной фигуры, всё это потом! Просто идём во все стороны, куда только возможно. Далее, включаем «магию». Просто комбинируем все возможные сочетания трёх ходов различных фигур в одном направлении, строя декартово произведение. После этого, отбрасываем ходы, натыкающиеся на собственные фигуры.

Почему бы не отбросить их сразу? По очень простой причине — фигура имеет право двигаться на занятое поле, если оно освобождается в рамках того же группового хода, а на момент генерации «элементарных» ходов, информация о составе перемещаемых групп отсутствует! Вот за что я так люблю этот проект. Он, время от времени, подкидывает такие вот интересные задачки!


Перемещение не обязательно должно происходить всего на одно поле, как в Abalone. В игре Ordo (и в особенности в Ordo X), придуманной Дитером Штейном в 2009 году, группы фигур могут перемещаться и на гораздо более дальние расстояния. Единственное условие — фигуры своего цвета, по завершении хода, не должны разделяться (это такой же инвариант игры как и необходимость ухода королём из под угрозы в Шахматах). Побеждает игрок первым добравшийся до последней линии доски.

e9eso2wtosdaokcmbftoppjdwqq.gif


В этой игре есть и продольные и поперечные ходы «рядов» фигур любого размера и на любую дистанцию (в пределах доски, конечно). Шаблонов, применяемых для генерации ходов, так много, что обработка ZRF-файла, разработанным мной конвертером, занимает более 5 минут (большинство игр обрабатываются за секунды)! Можно было бы предположить, что это приведёт к проблемам на этапе генерации ходов, но это не так. Подавляющая часть ходов отсекается инвариантом игры.

Здесь подвернулась ещё одна мозголомная задачка
Дело в том, что разработанный мной механизм поочерёдного выделения фигур, для выполнения группового хода, вообще говоря, несовместим с интерфейсом «толкающих» ходов, реализуемым старыми версиями контроллера. Это просто — для выполнения «толкающего» хода, необходимо выделить фигуру, имеющую возможность сходить на поле, пока что занятое другой фигурой перемещаемой группы. Но мы не можем отобразить её целевое поле, поскольку формирование группы не завершено, а ход одиночной фигуры на занятое поле, скорее всего, запрещён правилами игры.

В общем, если всё делать «по правилам», надо поочерёдно кликнуть по всем фигурам перемещаемой группы и только после этого интерфейс отобразит целевые поля для последней добавленной фигуры. Даже в Абалоне, с его группами максимум из трёх фигур это несколько утомительно, а в Ордо — вообще немыслимо! Пришлось придумывать специальный метод, автоматически «расширяющий» группу при обнаружении описанных выше конфликтов.

Вот как он выглядит для Abalone
Dagaz.Model.closure = function(board, move, group) {
  var r = [];
  _.each(group, function(pos) {
      r.push(pos);
  });
  for (var i = 0; i < r.length; i++) {
      var pos = r[i];
      _.each(move.actions, function(a) {
          if ((a[0] !== null) && (a[1] !== null) && (a[0][0] == pos)) {
              var p = a[1][0];
              var piece = board.getPiece(p);
              if ((piece !== null) && (piece.player == board.player) && 
                  (_.indexOf(r, p) < 0)) {
                  r.push(p);
              }
          }
      });
  }
  return r;
}


Но в Ордо допустимы длинные «толкающие» ходы и этот алгоритм не работает! Не беда — все функции, определённые в Dagaz.Model, можно переопределять.
Таким вот образом
Dagaz.Model.closure = function(board, move, group) {
  var design = board.game.design;
  var r = [];
  _.each(group, function(pos) {
      r.push(pos);
  });
  for (var i = 0; i < r.length; i++) {
      var pos = r[i];
      _.each(move.actions, function(a) {
          if ((a[0] !== null) && (a[1] !== null) && (a[0][0] == pos)) {
               var target = a[1][0];
               var x   = Dagaz.Model.getX(pos);
               var y   = Dagaz.Model.getY(pos);
               var dx  = sign(Dagaz.Model.getX(target) - x);
               var dy  = sign(Dagaz.Model.getY(target) - y);
               var dir = design.findDirection(pos, pos + (dy * Dagaz.Model.WIDTH) + dx);
               if (dir !== null) {
                   while ((pos !== null) && (pos != target)) {
                       var piece = board.getPiece(pos);
                       if ((piece === null) || (piece.player != board.player)) break;
                       if (_.indexOf(r, pos) < 0) {
                           r.push(pos);
                       }
                       pos = design.navigate(board.player, pos, dir);
                   }
               }
          }
      });
  }
  return r;
}


Проще всего эта перегрузка выглядит для Такоки. Поскольку в ней «толкающих» ходов нет (всегда необходимо явно выделять все фигуры входящие в группу), достаточно заблокировать эту функциональность, то есть, просто не расширять группу:
Dagaz.Model.closure = function(board, move, group) {
  return group;
}


Извиняюсь за такое никому ничего не говорящее имя функции. Просто не смог придумать лучшего названия для выполняемого действия.


w0ao0ly48ozfetiaojn5ilq9wum.png


В этой игре также реализовано групповое перемещение, но его механика совершенно иная! Здесь фигуры передвигаются группами 3×3, причём, частью перемещаемого «паттерна» являются и пустые поля группы тоже. Наличие фигур на одном из восьми внешних полей показывает направления, в которых можно перемещаться, а заполненность центрального поля определяет, можно ли двигать «паттерн» на произвольное или лишь на короткое расстояние, не более 3 шагов. Для победы, необходимо разрушить «кольцо» противника — аналог королевской фигуры (это пустое поле, со всех сторон окружённое восемью заполненными). Приходится быть очень осторожным, чтобы не разрушить и своё кольцо тоже.

GESS оказался настоящим кошмаром, как с точки зрения «магии», так и в плане самого прототипа — скелета игры. Достаточно лишь сказать, что доска (20×20, с учётом ряда полей за границей доски) состоит из двух слоёв. Весь верхний слой полностью заполнен невидимыми фигурами, управляющими перемещением. Передвижения камней, составляющих «паттерны» игроков — всего лишь побочные эффекты этих ходов. К сожалению, я пока не справился с разработкой бота для этой игры.


В завершение статьи, хочу познакомить вас с ещё кое чем, не имеющим непосредственного отношения к теме группового перемещения фигур. Эту игру меня попросил сделать один из подписчиков моей страничкипроекта — Sultan Ratrout. В общем-то, это обычные столбовые шашки на гексагональной доске. Даже без дамок. Революционность концепции в другом! Само поле игры — трансформируемое! Наслаждайтесь.

А я отправляюсь в отпуск…

© Habrahabr.ru