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

    image

    Когда-то давным-давно придумали люди язык XML и увидели, что это хорошо. И стали использовать его везде, где можно, и даже там, где не следует. Форматы хранения и передачи данных, конфиги, веб-сервисы, базы данных… Казалось, оглянись вокруг — XML, XML повсюду. Время прошло, люди одумались, насочиняли разных других форматов данных (или спрятали XML внутри архивов) и XML-безумие как-бы приутихло. Но с тех славных пор практически любая система умеет в XML и интегрировать такие системы (кто сказал Apache Camel?) лучше и проще всего, используя XML-документы.

    А где XML, там и XSLT — язык, предназначенный для преобразования XML-документов. Язык этот специализированный, но обладает свойством полноты по Тьюрингу. Следовательно, язык пригоден для «ненормального» использования. Вот, например, существует решение задачи о 8 ферзях. Значит, можно и игру написать.

    Для нетерпеливых: рабочая программа на JSFiddle, исходники на GitHub.

    Любая программа занимается преобразованием входных данных в выходные. В программе можно выделить три части: препроцессор, процессор и постпроцессор. Препроцессор готовит входные данные к дальнейшей обработке. Процессор занимается основной работой по преобразованию данных, при необходимости «подмешивая» пользовательский ввод и внешние сигналы и события, в том числе в цикле. Постпроцессор нужен для преобразования результатов работы процессора в пригодный для восприятия человеком (или другими программами) вид.

    image

    В случае интерактивной игры на 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-е. Но лучше для каждой задачи использовать подходящий инструмент.
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама

    Комментарии 8

      –2
      >проснуться богатым и знаменитым.
      По-моему цель была другая — упороться и сделать игру на чем-то, что большинство считает для этого непригодным ;)

      И это удалось!
        0
        Вот интересно, те кто поставил эти минусы — они что, реально думают, что тут высказан негатив или критика? Или что они вообще думают?

        Я автору поставил два плюса сразу. А «упоротый» — это в первую очередь «увлеченный чем либо» (возможно излишне), а уже во вторую негативные значения. По крайней мере — для меня.
        +1
        ну, положим, игра не на xslt, а все таки на js со смесью xslt… и действительно изврат
          +1
          Да, XSLT одновременно мощный и по-хорошему ублюдский язык. Я на нём сделал темку для autoindex'ера в nginx — результат то красивый, но пришлось делать тройную (!) рекурсию, ибо в xslt 1.0 (или какой там поддерживается в nginx, точнее в libxslt) просто критически мало полезных возможностей. Если кому интересно, результат можно глянуть тут.
            +2
            XSLT офигенная вещь. Особенно на серверной стороне, в качестве «шаблонизатора». А некоторые реализации процессоров (правда не 3.0 спецификации) еще и офигенски быстрые.
            0

            Xslt крут! А так как он сам тоже XML (гомоиконность, хе), то можно написать предварительные преобразования, с помощью которых добавить некоторого синтаксического сахара в язык. Прям как Лисп, только XML.


            Хотя есть у него и фундаментальные ограничения. Приходится грузить весь xml документ в память, и одновременно много больших документов не потрансформируешь, оперативы не хватит. А единственная реализация XSLT 3.0 с поддержкой потоковой обработки стоит сотни нефти.

              +1
              Насколько помню, есть еще ограничения у «потокового» (sax?) трансформра, он не умеет выполнять сортировку <xsl:sort select="...."/>
                0

                Понятно, что у потоковых трансформаций есть ограничения, да и чисто потоковые штуки не особо полезны. Но в XSLT 3.0 есть возможность держать в памяти только поддерево, в рамках которого выполнять уже все возможные XSLT трансформации. Сортировку top-level элементов за константную память конечно не сделаешь, но для наших задач хватило бы. Однако из-за дороговизны пришлось запилить свой ограниченный DSL.

            Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

            Самое читаемое