Интерактивная игра на XSLT / Хабр

Когда-то давным-давно придумали люди язык 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.

Ключевая функция - применение XSLT-преобразования.

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-е~~. Но лучше для каждой задачи использовать подходящий инструмент.