Когда-то давным-давно придумали люди язык XML и увидели, что это хорошо. И стали использовать его везде, где можно, и даже там, где не следует. Форматы хранения и передачи данных, конфиги, веб-сервисы, базы данных… Казалось, оглянись вокруг — XML, XML повсюду. Время прошло, люди одумались, насочиняли разных других форматов данных (или спрятали XML внутри архивов) и XML-безумие как-бы приутихло. Но с тех славных пор практически любая система умеет в XML и интегрировать такие системы (кто сказал Apache Camel?) лучше и проще всего, используя XML-документы.
А где XML, там и XSLT — язык, предназначенный для преобразования XML-документов. Язык этот специализированный, но обладает свойством полноты по Тьюрингу. Следовательно, язык пригоден для «ненормального» использования. Вот, например, существует решение задачи о 8 ферзях. Значит, можно и игру написать.
Для нетерпеливых: рабочая программа на JSFiddle, исходники на GitHub.
Любая программа занимается преобразованием входных данных в выходные. В программе можно выделить три части: препроцессор, процессор и постпроцессор. Препроцессор готовит входные данные к дальнейшей обработке. Процессор занимается основной работой по преобразованию данных, при необходимости «подмешивая» пользовательский ввод и внешние сигналы и события, в том числе в цикле. Постпроцессор нужен для преобразования результатов работы процессора в пригодный для восприятия человеком (или другими программами) вид.
В случае интерактивной игры на XSLT каждая из трёх частей программы будет представлять собой отдельный XSLT-файл. Препроцессор подготовит игровое поле. Процессор применит ход игрока-человека, сделает ход игрока-компьютера и определит победителя. Постпроцессор отрисует состояние игры.
Программе на XSLT нужна среда исполнения (рантайм). Самый распространённый рантайм, способный исполнять XSLT — это любой современный браузер. Будем использовать XSLT версии 1.0, так как она поддерживается браузерами «из коробки».
Немного о XSLT и XPath
XSLT — это язык преобразования XML-документов; для доступа к частям XML-документа используется язык XPath. Спецификации этих языков опубликованы на сайте w3.org: XSLT Version 1.0 и XPath Version 1.0.
Основы использования и примеры применения XSLT и XPath легко ищутся в сети. Здесь же я обращу внимание на особенности, которые нужно учитывать при попытке использования XSLT как «обычного» языка программирования высокого уровня общего назначения.
В XSLT есть именованные функции. Они объявляются элементом
<xsl:template name="function_name"/>и вызываются таким образом:
<xsl:call-template name="function_name"/>Функции могут иметь параметры.
Объявление:
<xsl:template name="add">
<xsl:param name="x"/>
<xsl:param name="y"/>
<xsl:value-of select="$x + $y"/>
</xsl:template>Вызов функции с параметрами:
<xsl:call-template name="add">
<xsl:with-param name="x" select="1"/>
<xsl:with-param name="y" select="2"/>
</xsl:call-template>Параметры могут иметь значения по-умолчанию.
Параметры могут быть «глобальными», приходящими извне. При помощи таких параметров в программу будет передаваться пользовательский ввод.
Также язык позволяет объявлять переменные, которые могут быть связаны со значением. Параметры и переменные являются иммутабельными и значения им могут быть присвоены один раз (совсем как в Erlang-е, например).
XPath определяет четыре базовых типа данных: строка, число, булево и набор узлов (node-set). XSLT добавляет пятый тип — фрагмент результирующего дерева (result tree fragment). Этот фрагмент выглядит как node-set, но с ним можно совершать ограниченный набор операций. Его можно скопировать целиком в выходной XML-документ, но нельзя получить доступ к дочерним узлам.
<xsl:variable name="board">
<cell>1</cell>
<cell>2</cell>
<cell>3</cell>
<cell>4</cell>
</xsl:variable>В переменной board находится фрагмент XML-документа. Но к дочерним узлам нельзя получить доступ. Такой код не валиден:
<xsl:for-each select="$board/cell"/>Лучшее, что можно получить, это доступ к текстовым узлам фрагмента и работа с ними как со строкой:
<xsl:value-of select="substring(string($board), 2, 1)"/> вернёт «2».
Из-за этого в нашей игре доска (или игровое поле) будет представлено в виде строки, чтобы ей можно было произвольно манипулировать.
XSLT позволяет проитерировать node-set при помощи конструкции xsl:for-each. Но привычных циклов for или while язык не имеет. Вместо них можно использовать рекурсивный вызов функций (итерация и рекурсия изоморфны). Цикл вида for x in a..b будет организован примерно так:
<xsl:call-template name="for_loop">
<xsl:with-param name="x" select="$a"/>
<xsl:with-param name="to" select="$b"/>
</xsl:call-template>
<xsl:template name="for_loop">
<xsl:param name="x"/>
<xsl:param name="to"/>
<xsl:if test="$x < $to">
<!-- сделать что-нибудь полезное -->
<xsl:call-template name="for_loop">
<xsl:with-param name="x" select="$x + 1"/>
<xsl:with-param name="to" select="$to"/>
</xsl:call-template>
</xsl:if>
</xsl:template>Пишем рантайм
Для работы программы нужны: 3 XSLT, исходный XML, ввод пользователя (параметры), XML внутреннего состояния и выходной XML.
Размещаем в html-файле текстовые поля с идентификаторами: «preprocessor-xslt», «processor-xslt», «postprocessor-xslt», «input-xml», «parameters», «output-xml», «postprocessed-xml». Также размещаем /> для встраивания результата в страницу (для визуализации).
Добавим две кнопки: инициализация и вызов (шаг) процессора.
Напишем немного кода на JavaScript.
function transform(xslt, xml, params) {
var processor = new XSLTProcessor();
var parser = new DOMParser();
var xsltDom = parser.parseFromString(xslt, "application/xml");
// TODO: check errors .documentElement.nodeName == "parsererror"
var xmlDom = parser.parseFromString(xml, "application/xml");
processor.importStylesheet(xsltDom);
if (typeof params !== 'undefined') {
params.forEach(function(value, key) {
processor.setParameter("", key, value);
});
}
var result = processor.transformToDocument(xmlDom);
var serializer = new XMLSerializer();
return serializer.serializeToString(result);
}
function doPreprocessing() {
var xslt = document.getElementById("preprocessor-xslt").value;
var xml = document.getElementById("input-xml").value;
var result = transform(xslt, xml);
document.getElementById("output-xml").value = result;
}
function doProcessing() {
var params = parseParams(document.getElementById("parameters").value);
var xslt = document.getElementById("processor-xslt").value;
var xml = document.getElementById("output-xml").value;
var result = transform(xslt, xml, params);
document.getElementById("output-xml").value = result;
}
function doPostprocessing() {
var xslt = document.getElementById("postprocessor-xslt").value;
var xml = document.getElementById("output-xml").value;
var result = transform(xslt, xml);
document.getElementById("postprocessed-xml").value = result;
document.getElementById("output").innerHTML = result;
}
Вспомогательная функция parseParams() разбирает пользовательский ввод на пары key=value.
function onInit() {
doPreprocessing();
doPostprocessing();
}
function onStep() {
doProcessing();
doPostprocessing();
}
Базовый рантайм готов.
Как им пользоваться. Вставить в соответствующие поля три XSLT-документа. Вставить XML-документ входных данных. Нажать кнопку «Init». При необходимости ввести в поле параметров нужные значения. Нажать кнопку «Step».
Пишем игру
Если ещё кто-то не догадался, интерактивная игра из заголовка — это классические крестики-нолики 3 на 3.
Игровое поле представляет собой таблицу 3 на 3, ячейки которой пронумерованы от 1 до 9.
Игрок-человек всегда ходит крестиками (символ «X»), компьютер — ноликами («O»). Если ячейка занята крестиком или ноликом, соответствующая цифра заменяется на символ «X» или «O».
Состояние игры содержится в XML-документе такого вида:
<game>
<board>123456789</board>
<state></state>
<beginner></beginner>
<message></message>
</game>
Элемент <board/> содержит игровое поле; <state/> — состояние игры (выигрыш одного из игроков или ничья или ошибка); элемент <beginner/> служит для определения того, кто начинал текущую партию (чтобы следующую начал другой игрок); <message/> — сообщение для игрока.
Препроцессор генерирует исходное состояние (пустое поле) из произвольного XML-документа.
Процессор валидирует ввод пользователя, применяет его ход, вычисляет состояние игры, рассчитывает и применяет ход компьютера.
fn do_move() {
let board_after_human_move = apply_move(board, "X", param)
let state_after_human_move = get_board_state(board_after_human_move)
if state_after_human_move = "" {
let board_after_computer_move = make_computer_move(board_after_human_move)
let state_after_computer_move = get_board_state(board_after_computer_move)
return (board_after_computer_move, state_after_computer_move)
} else {
return (board_after_human_move, state_after_human_move)
}
}
fn apply_move(board, player, index) {
// функция заменяет в строке board символ по индексу index на символ player и возвращающая новую строку
}
fn get_board_state(board) {
// функция возвращает "X", если выиграл человек, "O", если выиграл компьютер, "tie" в случае ничьей и пустую строку в остальных случаях
}
fn make_computer_move(board) {
let position = get_the_best_move(board)
return apply_move(board, "O", position)
}
fn get_the_best_move(board) {
return get_the_best_move_loop(board, 1, 1, -1000)
}
fn get_the_best_move_loop(board, index, position, score) {
if index > 9 {
return position
} else if cell_is_free(board, index) {
let new_board = apply_move(board, "O", index)
let new_score = minimax(new_board, "X", 0)
if score < new_score {
return get_the_best_move_loop(board, index + 1, index, new_score)
} else {
return get_the_best_move_loop(board, index + 1, position, score)
}
} else {
return get_the_best_move_loop(board, index + 1, position, score)
}
}
fn cell_is_free(board, index) {
// функция возвращает true, если в строке board по индексу index находится цифра (клетка свободна)
}
fn minimax(board, player, depth) {
let state = get_board_state(board)
if state = "X" {
// выиграл человек
return -10 + depth
} else if state = "O" {
// выиграл компьютер
return 10 - depth
} else if state = "tie" {
// ничья
return 0
} else {
let score = if player = "X" { 1000 } else { -1000 }
return minimax_loop(board, player, depth, 1, score)
}
}
fn minimax_loop(board, player, depth, index, score) {
if index > 9 {
return score
} else if cell_is_free(board, index) {
// если клетка свободна, вычисляем её оценку
let new_board = apply_move(board, player, index)
let new_score = minimax(new_board, switch_player(player), depth + 1)
let the_best_score = if player = "X" {
// человек минимизирует счёт
if new_score < score { new_score } else { score }
} else {
// компьютер максимизирует счёт
if new_score > score { new_score } else { score }
}
return minimax_loop(board, player, depth, index + 1, the_best_score)
} else {
// иначе переход на следующую клетку
return minimax_loop(board, player, depth, index + 1, score)
}
}
fn switch_player(player) {
// функция меняет игрока; X -> O, O -> X
}
Функция выбор хода компьютера использует алгоритм минимакса, где компьютер максимизирует свой счёт, а человек минимизирует. Параметр depth функции minimax нужен для выбора хода, который приводит к победе за наименьшее количество ходов.
Этот алгоритм использует большое число рекурсивных вызовов и первый ход компьютера вычисляется на моей машине до 2-3 секунд. Надо как-то ускоряться. Можно просто взять и предварительно рассчитать наилучшие ходы компьютера для всех возможных допустимых состояний игорового поля. Таких состояний получилось 886. Можно уменьшать это количество за счёт поворотов и отражений поля, но не нужно. Новая версия работает быстро.
Пришла пора красиво отобразить игровое поле. Что использовать, если это что-то а) должно рисовать графику (21 век на дворе, что за игра без графики?!) и б) желательно имело формат XML? Конечно же SVG!
Постпроцессор рисует клетчатое поле и расставляет в нём зелёные крестики, синие нолики и маленькие чёрные платья цифры. А также показывает сообщения об окончании игры.
И вот вроде игра готова. Но что-то не то. Чтобы играть, нужно совершать массу ненужных, скучных и раздражающих действий: ввести в поле номер клетки для следующего кода и нажать кнопку. Вот бы просто щёлкнуть по нужной клетке!
Дорабатываем рантайм и постпроцессор.
В рантайм добавляем функцию реакции нажатия на элемент SVG:
function onSvgClick(arg) {
document.getElementById("parameters").value = arg;
onStep();
}В постпроцессоре добавляем над каждой клеткой прозрачный (прозрачность задаётся стилем rect.btn) квадрат, при нажатии на который вызывается функция с номером клетки:
<rect class="btn" x="-23" y="-23" width="45" height="45" onclick="onSvgClick({$index})"/>После завершения партии щелчок по любой клетке начинает новую. Кнопку «Init» нужно нажать только один раз в самом начале.
Теперь можно считать игру готовой. Дело за малым: спрятать внутренности, запаковать в electron-приложение, выложить в Steam, ???, проснуться богатым и знаменитым.
Заключение
Сильный духом программист может написать что угодно на чём угодно даже на JavaScript-е. Но лучше для каждой задачи использовать подходящий инструмент.
Автор: yakov-bakhmatov
