Игра «2048» на FBD за час
Здравствуйте.
Этот пост посвящен краткому разбору того, как на FBD написать простейшую игрушку »2048».
Сразу помещу картинку с результатом: 
Если интересно, как это сделано, добро пожаловать под кат.
Исходные данные
Игра »2048». Правила.
1. В каждом раунде появляется плитка номинала »2» (с вероятностью 90%) или »4» (с вероятностью 10%).
2. Нажатием стрелки игрок может скинуть все плитки игрового поля в одну из 4 сторон. Если при сбрасывании две плитки одного номинала «налетают» одна на другую, то они слипаются в одну, номинал которой равен сумме соединившихся плиток. После каждого хода на свободной секции поля появляется новая плитка номиналом »2» или »4». Если при нажатии кнопки местоположение плиток или их номинал не изменится, то ход не совершается.
3. Игра заканчивается поражением, если после очередного хода невозможно совершить действие.
Как мы видим, правила предельно простые. Начинаем реализацию алгоритма.
Генератор случайных чисел
Для решения данной задачи делаем макрос «Случайное». Т.к. чистого «random» в контроллере нет, идем старым и проверенным путем:
Делаем макрос, на выходах которого будут формироваться случайные координаты клетки (строка и столбец), а так же признак того, что в данную клетку должна быть помещена четверка.
Краткое описание.
Алгоритмы 2,3 и 4 служат для получения постоянно меняющегося по «пиле» значения. Алгоритм «Сейчас» выдает на выход текущее время контроллера. Далее делим эти две величины друг на друга. Берем остаток в четвертом знаке после запятой. Сравниваем с »0,1» (вероятность 10%) и формируем соответствующий признак (признак того, что выбрали четверку). Берем остаток в шестом знаке после запятой. Умножаем на 16, округляем до целых в меньшую сторону и делим с остатком на 4. Таким образом мы получаем случайные координаты клетки, где частное от деления это строка, а остаток от деления это столбец. Единица добавлена для того, чтобы значения отображалось «красиво» в диапазоне от 1 до 4. На этом наш генератор случайных чисел закончен.
Макрос «Установка»
Итак, чуть выше мы получили случайные координаты ячейки, в которую должны поместить новое значение (2 или 4). Преобразуем это значение в шестнадцать логических признаков с помощью макроса «Установка».
Краткое описание.
Сам макрос предельно простой и нужен только для того, чтобы не захламлять основную задачу. Есть шестнадцать алгоритмов «И» на которых по логическому «И» собираются по три признака: признак «работать», сигнализирующий, что можно выдавать сигнал на установку ячейки, и два признака координат «строка» и «столбец». Как только все три признака на одном из алгоритмов «И» собрались, выдаем на соответствующий выход логическую единицу, по которой производим попытку установить новое значение в пустую ячейку.
Макрос «Ячейка»
Как понятно из названия, это основной макрос, который будет отображать нам состояние ячейки. Всего таких макросов 16 штук. Но в этом то и весь смысл, что они все абсолютно одинаковые (этого удалось добиться с помощью выноса алгоритмов установки значений, а также отдельной обработки команд от пользователя). Таким образом программа быстро и легко переделывается т.к. при изменении логики достаточно поменять только один алгоритм макроса, и все остальное поменяется автоматом.
У макроса имеется шесть входов и два выхода:
Входы:
- Установ — как мы говорили ранее, это вход для логического признака, что в данную ячейку должно быть установлено новое значение.
- Четверка — логический признак того, что в данную ячейку должна быть записана четверка, а не двойка.
- Очистить — обнуляет все значения в программе для начала новой игры.
- Go — признак того, что обработка всех значений после команды закончена и ячейку можно перезаписывать.
- Вход — значение после обработки очередной команды, которое необходимо записать в ячейку.
- Start — логический признак того, что игра только началась, все ячейки пустые и в любую из них можно записать первое значение.
Выходы:
- Значение — текущее значение ячейки.
- Готово — признак того, что обработка ячейки завершена.
Начинка макроса:
Основу макроса составляет алгоритм «Память», в котором хранится текущее значение ячейки. Значение, записываемое в данный алгоритм, выбирается посредством четырех последовательных алгоритмов «Выбор». Первым алгоритмом «Выбор» мы проверяем, какое значение должны записать в ячейку — «двойку» или «четверку». Второйf алгоритм «Выбор» проверяет — пустая ли это ячейка. Если ячейка пустая, то мы пишем туда выбранную двойку или четверку. Третий алгоритм «Выбор» проверяет начало это игры или нет. Если это начало игры, то без всяких проверок пишется выбранное ранее значение. Четвертый алгоритм «Выбор» самый приоритетный. Проверяем, пришел ли признак «Очистить», и если пришел, то принудительно записываем в память ноль очищая ячейку. Алгоритм «Сравнение» формирует признак, пустая это ячейка или нет. Далее с помощью двух алгоритмов «И» и «ИЛИ» мы проверяем, что если нам пришла команда установить в ячейку новое случайное значение и эта ячейка пустая, или это вообще начало игры, то выставляем признак того, что ячейка обработана и ход завершен.
Макрос «Обработка»
Этот макрос и есть основа всей логики, реализованной в игре.
Макрос имеет два входа и три выхода. Вход «Команда» это логический признак того, что макросу нужно обработать 4 входных элемента и выдать выходные значения. Макрос универсальный и используется для обработки всех четырех команд. Он сделан под команду «вправо», но для обработки команды «влево» достаточно подать на вход элементы строки в обратном порядке и в таком же обратном порядке забрать их с выхода. Для обработки команд «вверх» и «вниз» на вход подаются соответствующие значения из разных строк, формирующие столбец.
Принцип работы:
На вход подаются 4 элемента и команда начала обработки (команда работает на сдвиг элементов от первого к четвертому, т.е. команда вправо).
По переднему фронту команды элементы записываются в память. Далее проверяется, что строка из 4 элементов не содержит пустых ячеек в направлении сдвига. Если эта проверка не выполняется, то проходит циклический сдвиг всех элементов, перед которыми обнаружена пустая ячейка, на одну ячейку вниз. Полученная последовательность опять проверяется на наличие пустых ячеек в направлении сдвига и циклический сдвиг элементов продолжается до тех пор, пока проверка не выполнится.
Это и есть самое слабое место алгоритма. Для обработки строки приходится прогонять программу три раза (в пределе). Из-за того, что проверка может выполнится при первом проходе программы, а может только при третьем, а все 16 ячеек должны отработать одновременно, приходится ставить большое количество элементов памяти и триггеров в программе. Но пока простого и красивого способа реализовать сортировку в один проход я не придумал. Но еще не вечер. Когда будет время, займусь этим плотнее и возможно вся программа упростится раза в два.
Когда наконец-то проверка выполнена, и все элементы у нас расположены по порядку без пропусков, формируется импульс, по которому запускается попарное сравнение элементов, начиная с нижнего. Сравниваем между собой четвертый и третий элементы. Если они равны, то в четвертую ячейку записываем их сумму, а все остальные элементы сдвигаем на одну ячейку вниз. Далее сравниваем между собой второй и первый элементы и поступаем аналогично. Если четвертый и третий элементы между собой не сравнились, то сравниваем третий и второй элементы, и т.д. Тут алгоритм простой благодаря тому, что мы уже отсортировали все ненулевые ячейки и точно знаем, что между заполненными ячейками у нас нет пустых ячеек. Вот эта сортировка выполняется в один проход. В конце получившиеся значения элементов записываются на выход и формируется выходной сигнал «Готово».
Одновременно нам нужно проверять, что при подаче команды хотя бы один набор элементов изменился. В противном случае данная команда не является ходом и делать при ее подаче ничего не надо. Для этой проверки служат элементы внизу макроса, которые у исходной последовательности проверяют, что нужна хотя бы одна перестановка и хотя бы одна пара клеток «схлопнулась». В этом случае формируется выходной сигнал «сработало».
Общие слова
Вот, собственно, и все. Основные элементы программы у нас готовы. Осталось их только связать между собой. Пара слов об остальных вспомогательных элементах.
Это основные элементы управления игрой.
Ручной селектор, алгоритм, формирующий выходы по схеме «один из n», служит для подачи всех 6 команд. 1 — команда «сдвинуть вверх», 2 — «вправо», 3 — «вниз», 4 — «влево», 5 — «старт новой игры», 6 — «сброс».
Блок служит для блокировки команд пользователя (как я говорил ранее, не удалось сделать обработку команды в одном цикле, а значит пока команда обрабатывается нужно заблокировать подачу новых команд). Опыт показал, что максимальное время обработки команды при времени цикла в 5 мсек составило порядка 150 мсек. И хотя вся обработка осуществляется максимум в 5 циклов (там еще два цикла добавляются «про запас» за счет обратных связей), что составляет всего лишь 25 мсек, остальное время тратится на установку нового значения в ячейку. Ведь по мере заполнения поля шанс попасть в пустую ячейку уменьшается. В пределе время ожидания может быть бесконечным. Мат. ожидание 80 мсек. Зафиксированный максимум 150 мсек. Можно подправить алгоритм выброса случайного значения с целью сократить время, затрачиваемое на полную обработку хода. Т.к. у нас всего 16 ячеек, то можно сделать 16 элементов с запомненными значениями от 1 до 16. Далее прочитать значения из клеток игрового поля и ненулевые ячейки отодвинуть назад, а все нулевые с номерами их элементов оставить в начале ряда. Посчитать количество нулевых ячеек и выкинуть случайное число в этом диапазоне. Но это добавляет еще кучу алгоритмов, а усложнять и без того сложную программу очень не хотелось.
Итоговая программа:
Мы рассмотрели все элементы программы. Теперь достаточно их объединить и все будет работать.
На картинке четко видно разделение программы на 4 основных блока.
Левая верхняя часть это блок управления. Там находится селектор, формирующий команды, генератор случайных чисел, блокировки и т.п.
Левая нижняя часть это блок ячеек. Тут находятся 16 ячеек, значение которых отображается в графической части.
Правая верхняя часть это блок обработки команд. Состоит из 4 частей т.к. каждая команда («вправо», «влево», «вверх» и «вниз») обрабатывается отдельно т.к. макрос у нас универсальный.
Правая нижняя часть это вспомогательные элементы для преобразования порядка элементов и формирования признака, что игра закончилась (при условии, что все поля заняты и нет двух соседних ячеек с одинаковым значением).
Приделываем графическую часть
Ну тут все просто и делается за 5 минут.
Рисуем один квадратик. Задаем ему значение равное значению соответствующей ячейки. Меняем цвет фона в зависимости от значения ячейки. Далее копируем квадратик пятнадцать раз и получаем готовое поле. Делаем несколько подписей, добавляем кнопки «старт» и «Сброс» и большую надпись поверх поля «Game over».
Вид окна в режиме «рисование».
Вот и все готово. Запускаем и можно играть.
UPD.1
Пока пил кофе в обед, подумал: «какого хрена?» и решил переделать макрос обработки. Помните, я говорил, что обработка строки проходит в несколько циклов и это самое слабое место всей программы. Решил от этого избавится и выставить все проверки в одну последовательность. С одной стороны мы получаем лишние проверки если даже на старте у нас условие выполнилось. Но с другой стороны это решение (пусть и громоздко и некрасиво выглядящее) позволяет нам избавится от порнографии с кучей триггеров, кучей ячеек памяти и необходимости все это дело синхронизировать. Далее под катом новый макрос обработки и общий вид программы. Можно обратить внимание на то, как упростился макрос обработки (нет ни одной обратной связи) и стали лишними навесные костыли из элементов для синхронизации признаков, возникающих в разных циклах выполнения программы.
Верхняя половина это сортировка ряда «в лоб». Просто проверяются подряд все варианты и при выполнении условий делаются соответствующие перестановки. Нижняя половина осталась без изменений. Обратите внимание на то, что по сравнению с предыдущим вариантом убраны все элементы памяти и обратные связи. Блоки «Память 54 — 57», стоящие в конце, на самом деле для программы не нужны, т.к. обработка проходит в одном цикле. Оставил их исключительно для удобства отображения значений на выходе макроса. Т.к. время цикла у нас 5 мсек, то без этих блоков реальные значения на выходе макроса будут проскакивать только на 1 цикл (5 мсек, практически нереально заметить), а все остальное время на выходах будет висеть »-1».
Тут нужно обратить внимание на обвязку (а точнее ее отсутствие) макросов «Обработка». Если посмотреть на предыдущую версию программы, то можно заметить, что на выходе стоят по триггеру на каждый сигнал готовности, триггер на общий сигнал срабатывания, выделение фронтов и сбросы этих триггеров по обратной связи. Теперь весь этот ужас становится ненужен, и общий вид программы у нас получился чистенький и не захламленный всякими костылями. Все остальные элементы программы остались без изменений.
Подведение итогов
В очередной раз мы сделали пусть и бесполезную, но весьма интересную с точки зрения реализации алгоритмов игрушку. Более того, я специально не стал переписывать пост и заменять старые макросы новыми чтобы показать, как можно быстро кардинально переделать программу, при этом не затрагивая остальную часть. Что касается простоты написания программ на языке FBD, то думаю самым красноречивым здесь будет тот факт, что на написание этого поста я потратил времени раза в 2–3 больше, чем на написание программы.
То, что осталось нереализованным.
1. Подсчет очков. Я не спец в этой игре. Более того играл в нее только во время написания данного поста в своей программе и дальше рекорда в 256 дойти пока не получилось. Так вот, сделать подсчет очков несложно. Просто в макросе «Обработка» нужно при суммировании значений клеток с одинаковым номиналом дополнительно выдавать эту сумму на выход макроса, а снаружи подсчитывать общую сумму этих значений. Но я не вижу в этом никакого смысла, т.к. цель игры «получить плитку с максимальным номиналом».
2. «Умный» алгоритм выбора случайного значения, для установки двойки или четверки в пустую клетку. Я написал чуть выше как это можно сделать. Но т.к. там ничего интересного нет, то оставим это всем желающим.
На этом все. Надеюсь было интересно.
