# Dagaz: Horde

Zillions - you. We - the darkness and darkness and darkness.
Try, fight with us!
Yes, the Scythians - we! Yes, Asians - we ...

Alexander Blok " Scythians "

In the previous article I talked a lot about my discoveries in the design and user interface of board games, but I had to interrupt that story, you can say in the middle, partly because of the large amount of article, partly because that at that moment I was not ready to continue it further. Since then, much has changed. New interesting puzzles were solved, and the games that produced them (not less interesting) were added to the release . This is what I want to talk about today.

If anyone remembers, it was about the game " Abalon ", developed by Michel Lale and Laurent Levy in 1988. Its essence is in pushing the opponent's balls out of the field. Two balls can push one, and three balls - a couple of balls of a different color. A player can move his balls around the board, either one at a time or in groups, two or three balls each (at the same time, three balls must be “row”). What prevented me from making this game last time?

Obviously not the group movement itself. Simultaneous movement of several pieces, in the framework of one move, is even in Chess ( castling ). A puzzle " Sliding puzzles"just built on the fact that such a movement took place synchronously and smoothly. Let's look at one game developed by Robert Abbott in 1975:

It looks like Abalon. The only difference is that the “row” does not “push” the opponent's figure from its place, but simply removes it from the board using a “chess” take. The victory is awarded to the player who was able to hold onto the last row of the board of his pieces more than his opponent managed to do, at the same time. The whole game is built on moving "rows". To achieve victory with moves of only single figures is unlikely to succeed. This is how a simple “pushing” move looks.

ZRF
``````(define push-1 (
\$1 (verify friend?)
(while friend?
\$1
)
(verify not-friend?)
))
``````

The thing is in the magic word cascade - it forces the interpreter to “release” the moving figure to the current field, taking from there “into the hand” another figure (his own or the opponent - not important) and continue moving, already with a new figure “in hand”. In one move, such an operation can be performed multiple times, thus moving an unlimited number of figures simultaneously. Such (and slightly more complex) cases are found in other games - “ Guns ”, “ Dameo ”, “ Leutwhate Game ”, ...

From the point of view of the user interface, “pushing” moves are also implemented rather trivially. The familiar mark of the target field (a green circle) appears on the figure. If (according to the rules of the game) we can eat this piece - we eat (chess taking), otherwise we push. You can push a row and more than one field forward (as in the game Epaminondas). Of course, coding such a move will be a bit more complicated:

ZRF
``````(define push-2 (
\$1 (verify friend?)
(while friend?
mark
\$1 (verify not-enemy?)
\$1
)
\$1 (verify not-friend?)
))
``````

The keyword to (and paired from it ) works in conjunction with cascade . It means that the “out of hand” figure should be put on the board now, and a “take in hand” new figure after a while, after navigating to another field. In general, “pushing” moves are easy, but there is another kind of group movement to Abalon:

I call them "cross" moves. From the point of view of ZRF-coding, there is nothing difficult in them. The problem is in the user interface. How to “tell” the program that a player wants to move not one ball, but a group, if both moves are allowed by the rules? I use the same “blink”, so useful to me in checkers, to mark the “current” shape. Only now there are several “current” figures in the set.

Clicking on the "free" figure adds it to the group if there is a move in which all the figures added to the group are involved (it is even easier not to release the button, selecting the entire group with one mouse movement). If there are no such moves, simply create a new group, while consisting of a single figure. Green circles are always shown for the last added figure (this may not be very obvious, but you can get used to it). Repeated click on any “flashing” figure immediately resets the whole group.

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

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

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

``````(define step (
))
``````

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

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

Relocation does not have to occur in just one field, as in Abalone. In the game Ordo (and especially in Ordo X ), invented by Dieter Stein in 2009, groups of figures can move over much longer distances. The only condition is that the pieces of their color, at the end of their turn, should not be separated (this is the same game invariant as the need for the king to leave the threat in Chess). The winner is the first to reach the last line of the board.

In this game there are both longitudinal and transverse moves of “rows” of figures of any size and for any distance (within the board, of course). There are so many templates used for generating moves that the processing of a ZRF file developed by my converter takes more than 5 minutes (most games are processed in seconds)! One would assume that this would lead to problems at the stage of generating moves, but this is not the case. The overwhelming part of the moves is cut off by the game invariant .

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

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

Вот как он выглядит для 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;
}
``````

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

In this game , the group movement is also implemented, but its mechanics is completely different! Here, the figures are moved by groups of 3x3, and, moreover, the empty fields of the group are also part of the floating “pattern”. The presence of figures on one of the eight external fields shows the directions in which you can move, and the fullness of the central field determines whether the pattern can be moved to an arbitrary or only a short distance, not more than 3 steps. To win, it is necessary to destroy the "ring" of the enemy - an analogue of the royal figure (this is an empty field, surrounded on all sides by eight filled). You have to be very careful not to destroy your ring too.

GESS turned out to be a real nightmare, both in terms of " magic " and in terms of theprototype - the skeleton of the game. Suffice it to say that the board (20x20, taking into account the number of fields abroad the board) consists of two layers. The entire top layer is completely filled with invisible shapes that control the movement. The movements of the stones that make up the "patterns" of players are just the side effects of these moves. Unfortunately, I have not yet managed to develop a bot for this game.

At the end of the article, I want to introduce you to something else that is not directly related to the subject of group movement of figures. This game I was asked to make by one of the subscribers of my project page - Sultan Ratrout. In general, these are ordinary column checkers on a hexagonal board. Even without ladies. Revolutionary concept in another! The field of the game itself is transformable! Enjoy.

And I'm going on vacation ...