Превозмогая трудности: Gravity Defied на sed

в 21:54, , рубрики: gravity defied, sed, Занимательные задачки, разработка игр, Регулярные выражения, системное программирование

image
Итак, эта статья посвящается тем, кто любит решать нестандартные задачи на не предназначенных для этого инструментах. Здесь я опишу основные проблемы, с которыми столкнулся во время создания аналога игры Gravity defied с использованием потокового текстового редактора (sed).

Далее предполагается, что читатель хотя бы немного знаком с синтаксисом sed'ом и и написанием скриптов под bash.

Мирный вечер декабря перестал быть мирным, когда мне пришло сообщение от преподавателя примерно такого содержания:

На sed:
Gravity defied

Это должно быть круто

Признаться, первые полчаса я сидел с мыслью о том, как это вообще возможно. Но потом мне удалось взять себя в руки и я начал разбираться.
Попытки гуглить на тему игр на sed привели к арканоиду и сокобану.

Прежде, чем мы начнём разбор проблем, хочу поделиться репозиторием с проектом и видео-демонстрацией результата

Итак,
Проблема первая: представление в памяти
sed должен как-то хранить текущее состояние игры. В нашем распоряжении два места для магии hold space и pattern space.
Hold space будет хранить состояние игры между итерациями (итерацией я буду называть обработку одного входящего символа), а в pattern space мы будем изменять состояние игры.
Алгоритм примерно такой:

  1. Переходим к действию, которое привязано к символу, который мы получили на вход
  2. Записываем в pattern space содержимое hold space
  3. Изменяем содержимое pattern space в соотвествии с логикой действия
  4. Записываем содержимое pattern space в hold space
  5. Производим наложение эффектов на pattern space (на этом шаге мы из нашего «служебного» состояния игры в то, что будет видеть пользователь)
  6. Выводим содержимое pattern space на экран
  7. Повторить с п.1 для каждого введённого символа

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

Первым делом — инициализация.
Создадим метку print, которая будет создавать поле игры в начальный момент времени. С момента запуска игры лишь один раз возникнет ситуация, когда на вход sed'у передаётся пустая строка: самый старт игры.
Таким образом,

/^$/b print
...
:print
# Начало любого действия, которое иницируется извне
g
s/.*/
+-----------------------+
|BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB1
|BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB2
|BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB3
|BBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB4
|BBBBBBBBBBBBBBBBBBBBBUPPABBBBBBBBBBBB5
|BBBBBBBBBBBBBBBBBBBBUBBBABBBBBAPPPPPP6
|DBBBBBBBBBBBBBBBBBUPBBBBABBBBBABBBBBB7
|BDBSBFBBBBBBBBBBBUBBBBBBABBBBBABBBBBB8
|BBPPPPPPPPPPPPPPPBBBBBBBPPPPPPPBBBBBB9
+-----------------------+
b end

На этом этапе всё зависит от вашего воображения. Вы сами решаете, за что отвечает каждый символ. У меня B — это пустое место, F и S — колёса байка, в A, D, P, U — дорога (четыре вида, для красоты, но об этом — позднее).
Нам необходимо вывести всё полученное на экран. Как вы могли заметить, в конце print мы переходим к метке end.
end — это общее завершение любого действия.

:end
# Сохраняем все изменения в hold space
h
# Здесь позднее провернём всю пост-обработку нашего игрового пространства
# Отправляем символ очистки экрана
i
^[[H
# Печатаем содержимое pattern space на экран
p

Примечание: ^[[H не стоит копипастить, это escape-последовательность. Например, в vim она вводится так: Ctrl+V Ctrl+ESC [ H

Запустим наш скрипт с помощью

sed -nf gravity.sed

Поздравляю с статической картинкой!

Когда у нас есть поле, достаточно просто написать команды, которые будут двигать влево-вправо наши импровизированные колёса:

s/FB/BF/
s/SB/BS/

Движение вверх чуть сложнее но мы же не боимся сложностей, правда?

s/B(.{39})F)/F1B/

Тут вся суть в цифре 39. Это количество символов в строке.

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

Проверить игру не сложно, но нажимать Enter после каждого введённого символа — удовольствие ниже среднего, так что нужно автоматизировать этот процесс.

Проблема вторая: тактование
Так как «сердце» игры — sed, нужна оболочка, которая за нас будет нажимать enter каждый раз, когда мы нажали кнопку. Бесконечный цикл — самое оно.
Примерный код:

(while true 
do
    read -s -n 1 key # считываем одно нажатие клавиши без вывода на экран в переменную key
    echo $key
done) | sed ...

Игра теперь будет станет чуть более радостной, но в ней всё ещё есть большой недочёт: игрок может влиять на ход времени. Чем быстрее тыкает игрок по клавишам, тем быстрее ход игры. Нас такое не устраивает, поэтому нужно тактование. Теперь у нас два источника данных — тактовый генератор и пользователь. Самое простое решение, которое приходит в голову — воспользоваться ключом -t у read. Если пользователь ничего не введёт за указанное кол-во секунд, то read не станет блокировать скрипт. Это решение меня не устроило: на SunOS read отказывался принимать дробное количество секунд, а динамичная игра с одним кадром в секунду — это как-то странно. Второе решение — использовать именнованый pipe:

# Удаляем (на всякий случай) pipe и создаём новый
rm -f gravity-fifo;
mkfifo gravity-fifo;
# Эта строчка будет держать pipe открытым достаточно долго
sleep 99999999 > gravity-fifo &

# Запустим игру
sed -nf gravity.sed gravity-fifo &

# Тактовый генератор, который раз в $TIME * 10^-6 секунд будет записывать символ t в pipe
while true
do
        echo t > gravity-fifo
        usleep $TIME
done &

# Пользовательский ввод
(while true 
do
        read -s -n 1 key 
        echo $key
        [[ $key == "q" ]] && pkill -P $$ 
done ) | $SED -u -e '/t/d' > gravity-fifo

Немного пояснений:
pkill — хороший способ убить тактовый генератор и sleep.
А если вам непонятно, зачем нужен этот sleep, то можете проверить без него: с первым же echo pipe закроется и sed поймает EOF. Попутно мы запрещаем пользователю писать тактирующий символ — мы тут байк водим, а не временем управляем.

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

Проблема четвёртая: пост-обработка
Сразу после того, как мы перешли к метке end и сохранили изменения в hold space, мы можем приступать к наложению эффектов. Ранее я упоминал, что я использую четыре типа дорог. К этому я пришёл методом проб и ошибок. В первых версиях дороги были одного типа: R, а на этапе пост-обработки я пытался написать регулярки, которые бы делали подъем/спуск в зависимости от взаимного расположения дорог.
Идея была отвергнута: алгоритм постоянно сбоил, проще прописать тип дорог.
Вооружаемся таблицей ANSI Escape-последовательностей, я ещё дополнительно воспользовался таблицей Unicode и получилось…

s/A/^[[107;38;5;82m█^[[0m/g
s/D/^[[107;38;5;82m▚^[[0m/g
s/P/^[[107;38;5;82m▀^[[0m/g
s/U/^[[107;38;5;82m▞^[[0m/g

Подводные камни есть и здесь: при использовании юникода pattern поиска не должен содержать точное количество символов. Unicode-символы распознаются как два символа и логика такой регулярки ломается.

Проблема пятая: маленькое пространство
На экран у нас влезает не так уж много символов, а карту хотелось бы сделать больше. Здесь на помощь приходит Scroll Buffer. Это такое место, невидимое для пользователя, которое будет хранить в себе кусочек продолжения карты. Для комфортного скроллинга стоит пронумеровать строчки, а в самом конце добавить строку, которая нумерует зону, например, z1
Алгоритм работы:

  1. Если любая часть игрока ближе, чем на N символов к правому краю карты, переходим к следующему пункту
  2. Удаляем второй символ карты (первый у нас — рамочка)
  3. К концу каждой строки, перед цифрой добавляем #
  4. Если у нас набралось ровно M символов #, то выполняем следующий пункт, иначе — пропускаем
  5. Проверяем номер текущей зоны и заменяем все # на соответствующую данной зоне карту, меняем имя зоны на имя следующей зоны
  6. Переходим к метке end
  7. На этапе пост-процессинга обрезаем видимую часть так, чтобы символы # никогда не попадали в видимую область, а так же удаляем вспомогательные данные, например, номер зоны.

Ура! Теперь у нас есть базовые знания, как создать игру на sed.
Зачем? Потому что можем.

Автор: Firemoon

Источник


* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js