— Неправда! В этой сказке говорится совсем не то.— Но если ты уже знаешь, что говорится в этой сказке, зачем мне ее читать?
— Затем, что я хочу её услышать!
Тед Чан "История твоей жизни"
Это большое событие, когда что-то вдруг начинает работать. Маловразумительные страницы кода на Java и JavaScript, ещё менее понятный XML, картинки, нарисованные в Paint-е — всё это вместе!
Теперь, это можно запустить и «потрогать». Тесты можно было запускать и раньше, они помогали добраться до этого дня. Но разве можно сравнить тесты с работающей программой? Работоспособный релиз! Для многих, эта веха знаменует конец пути.
Надеюсь, что для меня это только начало…
В качестве первой задачи для пробы сил я выбрал «Sliding Puzzles» — головоломки с движущимися частями. Всё началось с игры "15" и Сэма Лойда. Этот выдающийся предприниматель предложил крупный денежный приз за решение задачи, не имеющей решения. И мир сошёл с ума. Когда градус безумия стих, другие люди предложили склеивать части пятнашек между собой, чтобы получить ещё более интересные (но уже имеющие решение) головоломки.
Папина головоломка — пожалуй самая ранняя из известных головоломок этого рода (под таким именем она продавалась в Америке ещё в 1926 году). Большой квадрат надо переместить в правый нижний угол. Это просто. Здесь (почти) нет тупиков и развилок, сложно сбиться с пути.
Доставить квадрат в левый нижний угол — чуть сложнее. Если разрезать одну из прямоугольных частей на два маленьких квадрата и уложить в коробку по другому, можно получить гораздо более сложную головоломку.
В детстве мне подарили такую. Я так её и не решил. Во Франции эта головоломка известна под названием «L'Ane rouge» (Рыжий осёл). Большой квадрат требуется разместить внизу, ровно по середине (иногда делалось отверстие, через которое его можно было выдвинуть из коробки). Насколько я знаю, минимальное количество ходов требуемое для решения «Рыжего осла», неизвестно. Мартин Гарднер, в своей книге "Математические досуги" описывает решение, состоящее из 81 хода.
Конечно же, «Рыжий осёл» не самая сложная головоломка. Игр такого типа невероятно много (и некоторые из них очень сложны). Известны головоломки с не выпуклыми частями (как "Мамина головоломка" или "Головоломка Эскота"). Некоторые наборы разрабатывались в честь исторических событий (таких как избрание Джорджа Вашингтона президентом Америки или полёты знаменитых лётчиков). Это целый мир, богатый и разнообразный.
В отличии от игры «15» не существует простого способа, для того чтобы определить имеет ли такая головоломка решение. Только перебор! Не удивительно, что программисты к ним так неровно дышат. Меня это поветрие также не миновало. Я делал «Рыжего осла», когда осваивал Delphi. Позже, я разрабатывал мобильное приложение под Android. Теперь я делаю это снова, правда на этот раз сами головоломки не являются целью — они всего лишь способ, для того чтобы убедиться в работоспособности выбранного мной подхода. Частное применение более универсального продукта.
С точки зрения Dagaz, головоломки — это игры для одного игрока. Здесь есть доска и фигуры, есть правила перемещения и условия завершения игры. Нет взаимодействия двух (или большего количества игроков). Для меня этого удобно, поскольку позволяет запустить проект в отсутствии части модулей, необходимых для реализации более сложных игр. Это нулевая итерация. Своего рода пререлиз проекта.
Как выглядит реализация Sliding puzzles на ZRF?
; for (2,1)-pieces
(define shift2x1 ((verify (empty? w)) from w to cascade e e from w to (count-move) add)
((verify (empty? e)) from e to cascade w w from e to (count-move) add)
(w (verify (piece? $1))(verify (empty? w)) e from w to cascade from w to (count-move) add)
(e (verify (piece? $1))(verify (empty? e)) w from e to cascade from e to (count-move) add)
((verify (empty? n))(verify (empty? ne)) e
(verify (piece? $1)) w from n to cascade se from n to (count-move) add)
((verify (empty? n))(verify (empty? nw)) w
(verify (piece? $1)) e from n to cascade sw from n to (count-move) add)
((verify (empty? s))(verify (empty? se)) e
(verify (piece? $1)) w from s to cascade ne from s to (count-move) add)
((verify (empty? s))(verify (empty? sw)) w
(verify (piece? $1)) e from s to cascade nw from s to (count-move) add)
(w (verify (empty? w))
(verify empty?) e from w w to cascade e e e from w w to (count-move) add)
(w (verify (piece? $1)) w (verify (empty? w))
(verify empty?) e e from w w to cascade e from w w to (count-move) add)
(e (verify (empty? e))
(verify empty?) w from e e to cascade w w w from e e to (count-move) add)
(e (verify (piece? $1)) e
(verify (empty? e)) (verify empty?) w w from e e to cascade w from e e to (count-move) add)
)
И это только один из макросов управляющих согласованным перемещением фигур-тайлов! Конкретно этот обеспечивает перемещение плашки размером 2x1, повёрнутой горизонтально (для вертикальной плашки используется другой хардкод). Разумеется, не этот ужасный ужас является моей целью! В Dagaz всё гораздо проще!
(define step (
$1 add
))
Вот и всё! Разумеется, в реальной жизни всё не бывает так просто. Для того, чтобы головоломка работала как надо, фигуры-тайлы, составляющие одну плашку, должны двигаться синхронно. Кроме того, они не должны «наезжать» на тайлы других плашек, расположенных на доске. Всё это невероятно сложно описывается на ZRF. Нет абсолютно никакого смысла этим заниматься.
На JavaScript это делается гораздо проще!
var distinctMode = false;
var isEqual = function(a, b) {
if ((a == 0) || (b == 0)) return false;
return a == b;
}
var isEmpty = function(board, pos, value) {
var piece = board.getPiece(pos);
if (piece === null) return true;
return isEqual(piece.getValue(0), value);
}
var isSubset = function(x, y) {
for (var i = 0; i < x.actions.length; i++) {
var action = x.actions[i];
if (_.chain(y.actions)
.filter(function(a) {
return a[0][0] == action[0][0] &&
a[1][0] == action[1][0];
})
.size()
.value() == 0) return false;
}
return true;
}
Dagaz.Model.getPieceTypes = function(piece, board) {
var tag = piece.getValue(0);
return _.chain(board.pieces)
.compact()
.filter(function(piece) {
return piece.getValue(0) == tag;
})
.map(function(piece) {
return piece.type;
})
.uniq()
.value();
}
var CheckInvariants = Dagaz.Model.CheckInvariants;
Dagaz.Model.CheckInvariants = function(board) {
_.chain(board.moves)
.filter(function(move) {
if (move.actions.length != 1) return false;
var action = move.actions[0];
if (!action[0]) return false;
if (!action[1]) return false;
if (action[0][0] == action[1][0]) return false;
if (board.getPiece(action[0][0]) === null) return false;
return true;
})
.each(function(move) {
var design = board.game.design;
var action = move.actions[0];
var from = action[0][0];
var delta = action[1][0] - from;
var piece = board.getPiece(from);
var value = piece.getValue(0);
if (isEmpty(board, action[1][0], value)) {
_.chain(_.range(design.positions.length))
.filter(function(pos) {
return pos != from;
})
.filter(function(pos) {
if (board.getPiece(pos) === null) return false;
return isEqual(board.getPiece(pos).getValue(0), value);
})
.each(function(pos) {
var target = pos + delta;
if ((Dagaz.find(design.positions[pos], delta) < 0) ||
(target < 0) ||
(target >= design.positions.length) ||
!isEmpty(board, target, value)) {
move.failed = true;
} else {
move.movePiece(pos, target, null, 1);
}
});
} else {
move.failed = true;
}
});
if (distinctMode) {
var moves = [];
_.chain(board.moves)
.filter(function(move) {
return (_.isUndefined(move.failed));
})
.each(function(move) {
if (_.chain(moves)
.filter(function(m) {
return isSubset(m, move) && isSubset(move, m);
})
.size()
.value() == 0) {
moves.push(move);
}
});
board.moves = moves;
}
CheckInvariants(board);
}
Этот модуль делает всё что нам требуется. Да, он сложный, но пишется всего один раз, после чего используется повторно во всех головоломках такого типа. Подключение JavaScript-модуля к ядру Dagaz, написанному на JavaScript — выполняется гораздо проще чем подгрузка DDL-ек, написанных на C++ в Windows-приложение Zillions of Games. Почему бы этим не пользоваться?
(option "smart-moves" from)
(option "sliding-puzzle" true)
Магический модуль подключается второй опцией. Первая включает режим более дружественного перемещения фигур. Что ещё требуется, чтобы описать новую головоломку? Немножко шаблонного кода для описания доски и игрока:
(players You)
(turn-order You)
(board
(grid
(start-rectangle 0 0 100 100)
(dimensions
("a/b/c/d/e" (100 0)) ; files
("3/2/1" (0 100)) ; ranks
)
(directions (n 0 -1) (s 0 1) (e 1 0) (w -1 0))
)
)
Если размер доски не 5x3 потребуется слегка подредактировать линейки grid-а. Далее описываем сами фигуры (тайлы):
(define T
(piece
(name $1$2)
(help " ")
(image You "images/$1.bmp")
(attribute value $2)
(moves
(step n) (step s) (step w) (step e)
)
)
)
(T R0000 1)
(T R0010C 2) (T R0001P 2)
(T R0100C 3) (T R1000C 3)
(T R0010P 4) (T R0001C 4)
(T R0000P 5)
(T R0100P 6) (T R1000P 6)
(T R0000C 7)
(T R0000 8)
(T R0000 9)
Макрос под именем «T» просто избавляет нас от большого количества однообразной писанины. Единички и нолики в имени фигуры кодируют картинку, используемую для отображения тайла на доске. Добавляемое к ним число — идентификатор группы. Тайлы у которых оно совпадает перемещаются вместе (это, а также проверку возможности такого перемещения, обеспечивает наш магический скрипт). Осталось описать начальную расстановку фигур:
(board-setup
(You
(R00001 b3)
(R0010C2 c3) (R0001P2 c2)
(R0100C3 d3) (R1000C3 e3)
(R0010P4 a2) (R0001C4 a1)
(R0000P5 b2)
(R0100P6 d2) (R1000P6 e2)
(R0000C7 b1)
(R00008 c1)
(R00009 d1)
)
)
и цель игры:
(win-condition (You) (and
(absolute-config R0010C2 (a2 b2 c2 d2 e2))
(absolute-config R0100C3 (a2 b2 c2 d2 e2))
(absolute-config R1000C3 (a2 b2 c2 d2 e2))
(absolute-config R0001C4 (a2 b2 c2 d2 e2))
(absolute-config R0000C7 (a2 b2 c2 d2 e2))
))
Собрав всё вместе, получаем практически честный ZRF-файл. Запустить его в Zillions of Games не удастся по двум причинам.
- Традиционный Zillions of Games ничего не знает про опцию "sliding-puzzle"
- Числовые атрибуты он тоже не поддерживает (а стоило бы)
Теперь, в дело вступает Z2J — это такая специальная утилита для превращения ZRF-файлов во что-то более понятное для Dagaz. Написана на Java с использованием XSLT-процессора Xalan:
/usr/bin/java -classpath "./z2j.jar:./log4j-1.2.jar:./xalan-2.7.1.jar:./serializer-2.7.1.jar" com.gluk.z2j.app.App ./twins.zrf
После её запуска, в том же каталоге где лежал ZRF-файл, появляются ещё два файла (на XML-файлы внимание можно не обращать, они для отладки). JavaScript-файл содержит всё необходимое для настройки модели, а html-файл создаётся просто для удобства. Его можно запустить.
В принципе, всю эту часть с написанием ZRF-файла и его трансляцией в JavaScript-код можно опустить, набив все необходимые настройки руками, но набивать, таким образом, придётся довольно много и при этом очень легко ошибиться. Я думаю о том, чтобы создать небольшую библиотеку, поддерживающую создание наиболее употребительных конфигураций досок и шаблонов ходов. Если я это сделаю, ZRF-файл можно будет не писать, ограничившись разработкой JavaScript-кода.
Что в итоге
Выбранный мной подход доказал свою работоспособность. Код выложен под свободной лицензией, желающие могут пользоваться. Промежуточное создание ZRF-файла кому-то может показаться избыточным, но для меня, с моим опытом разработки приложений под Zillions of Games, это удобно. Впрочем, я работаю над тем, чтобы сделать этот шаг не обязательным. Для запуска настольных игр всё ещё не хватает пары важных (и очень сложных) модулей и, разумеется, ботов. Я также работаю над этим. Я не собираюсь останавливаться. Настольных игр очень много. Хватит надолго.
Поделиться с друзьями
Thseru
Странно было упомянуть Сэма Лойда, как того, кто придумал игру 15, прикрепит ссылку на вики, в которой написано, что «Авторству Лойда ошибочно приписывается игра «15»»
GlukKazan
Вы невнимательно читали. Я не написал, что он её придумал. Ну и тёмный это вопрос, на самом деле. Никто уже не помнит как дело было (а в Википедии тоже не всегда правду пишут).
Thseru
Да, Извините. Я это понял, но уже было поздно))
GlukKazan
Ничего страшного.