Гра «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 - логічна ознака того, що гра тільки почалася, всі комірки порожні і в будь-яку з них можна записати перше значення.

Виходи:

• Значення - це поточне значення комірки.
• Готово - ознака того, що обробка комірки завершена.

Починка макроса:

Основу макроса складає алгоритм «Пам'ять», в якому зберігається поточне значення комірки. Значення, що записується в даний алгоритм, вибирається за допомогою чотирьох послідовних алгоритмів «Вибір». Першим алгоритмом «Вибір» ми перевіряємо, яке значення повинні записати в комірку - «двійку» або «четвірку». Другий алгоритм «Вибір» перевіряє, чи це порожня комірка. Якщо комірка порожня, то ми пишемо туди обрану двійку або четвірку. Третій алгоритм «Вибір» перевіряє початок цього гри чи ні. Якщо це початок гри, без будь-яких перевірок пишеться вибране раніше значення. Четвертий алгоритм «Вибір» найпріоритетніший. Перевіряємо, чи прийшла ознака «Очистити», і якщо прийшов, то примусово записуємо в пам'ять нуль очищаючи комірку. Алгоритм «Порівняння» формує ознаку, порожня це комірка чи ні. Далі за допомогою двох алгоритмів «І» і «АБО» ми перевіряємо, що якщо нам прийшла команда встановити в комірку нове випадкове значення і ця комірка порожня, або це взагалі початок гри, то виставляємо ознаку того, що комірка оброблена і хід завершений.

Макрос обробки

Цей макрос і є основа всієї логіки, реалізованої в грі.

Макрос має два входи і три виходи. Вхід «Команда» - це логічна ознака того, що макросу потрібно обробити 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. «Розумний» алгоритм вибору випадкового значення, для встановлення двійки або четвірки в порожню клітку. Я написав трохи вище як це можна зробити. Але оскільки там нічого цікавого немає, то залишимо це всім бажаючим.

На цьому все. Сподіваюся було цікаво.