Зробимо гру Вовк-Коза-Капуста

Open Source Hardware Project

Знайшов чудову статтю “Самостійне вивчення схемотехніки. Синтез автоматів на тригерах. Частина 1” на Хабрі. У статті розглядався цікавий приклад створення гри «Вовк-Коза-Капуста». Спробую пояснити суть справи.

Завдання: На одному березі річки знаходяться селянин, вовк, коза та капуста. У селянина є човен, але мабуть не дуже гарний Він може взяти з собою в плавання лише один «предмет», у сенсі лише козу або тільки капусту або вовка. Проблема в тому, що когось не можна залишати наодинці з бажаною їжею. Наприклад, не можна спливти залишивши вовка та козу на одному березі – вовк з'їсть козу. Або не можна спливти з вовком, залишивши козу та капусту – адже коза з'їсть капусту. Але селянинові треба обов'язково потрапити в інший берег. Ось такий він упертий. І хоче він довезти всіх у безпеці.

Взагалі це досить відома дитяча головоломка.

Автор цієї статті пропонує використовувати «граф автомата Мура» для опису цієї системи з вовка-кози-капусти та селянина. Ну що ж – у цьому, напевно, є якась здорова думка.

Для зберігання стану системи використовується чотирибітне слово. По одному біту на кожного: на козу (біт 3), на вовка (біт 2), капусту (біт1) та селянина (біт 0). Якщо біт дорівнює одиниці, то сутність першому березі, і якщо нулю, то другому.

Взагалі прочитавши статтю і уважно вивчивши цей граф, мені негайно захотілося спробувати реалізувати цю гру «в залізі». Тим більше, що робити мені за великим рахунком майже нічого не треба – адже я маю платуМарсохід і вона дуже підходить для цієї гри.

Порився в інтернеті і знайшов кілька картинок кіз, капуст,вовків та селян. Вибравши більш підходящі, зібрав їх на одній картинці і надрукував на принтері ось так:

Потім наклеїв цю картинку на картонку вирізав по контуру і двома коротенькими шурупами пригвинтив плату Марсохід до картонки. Вийшло ось так:

Ідея наступного. На платіМарсохід є 8 світлодіодів. Подумки ділимо їх на дві групи. Перші чотири світлодіоди відображають присутність сутностей на лівому березі, а праві чотири світлодіоди відображають присутність сутностей на правому березі. Зрозуміло, що праві світлодіоди – це просто інверсія лівих. Так наочнішою буде гра.

Ось тут і почалося найцікавіше. Насправді є велика різниця між теоретичними дослідженнями та практичною реалізацією. Спробую пояснити мої проблеми та проблеми з існуючим графом:

У існуючому графі вихідний стан це 0000, що у прийнятої термінології означає, що це сутності спочатку перебувають у тому правому березі. Якось це дивно.

Будь-яка подія А1-А4 перевозить всіх відразу на лівий берег з правого стану 0000 в стан 1111. Теж дивно.

Немає явного стану "виграв" або "програв". На графі програш переводить всіх сутностей відразу на правий берег у стан 0000, що як би означає «виграв». Ну як це?

У статті йдеться про чотири програшні ситуації 0011\1100, 1010\0101, насправді їх шість. Є ще дві програшні ситуації 1110\0001 – це коли селянин залишає все своє господарство та пливе сам. Коза з'їдає капусту, а потім вовк козу.

Незважаючи на те, що першу версію гри з існуючого графа я зробив досить швидко, як виявилося, користуватися цим практично не можна. Гра вийшлаДуже незрозуміла.

Після деяких роздумів я дійшов висновку, що треба змінити граф, зробити його більш виразним і чітким. Сказати по правді намалювати новий граф коштувало мені просто дуже великих зусиль. Маю зізнатися, що тут я вперше пошкодував, що вибрав цей шлях – реалізація гри у вигляді «автомата». Мені весь час здавалося, що є інший набагато легший шлях зробити цю гру, але про це трохи пізніше.

Тепер про мій "новий" граф автомата Мура. Початковий стан гри 0000 і це означає, що всі сутності на першому лівому березі. Одиниця у биті стану означає, що відповідна сутність знаходиться на правому березі. Маємо один виграшний стан 1111 та шість програшних. І сутностей і події називаємо в однаковій послідовності, а не тому, що було раніше. Тобто в слові стану Коза – біт нуль. Подія з перевезення Кози - теж біт нуль у слові подій (тобто кнопка нуль).

параметр GOAT = 0; parameter CABBAGE = 1; parameter WOLF = 2; parameter MEN = 3;

Ось так виглядає мій граф:

Тепер вже за новим графом пишемо мовою Verilog опис логіки роботи нашого автомата. Повний текст «програми», що вийшла, можна взяти тут.

Незважаючи на те, що проект запрацював правильно (на мій погляд), все одно залишилося якесь почуття незадоволеності. Я ще коли писав весь цей код на Verilog бачив, що виходить якось «важко».

Насправді вся логіка може бути набагато простішою. Спробую пояснити свою думку. У цьому конкретному прикладі не потрібно ламати голову всіма цими "автоматами". Складання такого графа має на увазі чіткеуявлення які взагалі стану є та його трансформації. А власне кажучи, навіщо все це?

Зрозуміло, що будь-яка подія перевезення, по-перше, обов'язково призводить до переміщення селянина на протилежний берег. Тобто кожна подія завжди «інвертує» біт стану селянина. По-друге, сутності Коза, Капуста і Вовк можуть переміщатися тільки якщо перед подією вони з селянином знаходяться на одному березі. Переміщення всіх сутностей – це інвертування їхнього біта стану. Розпізнавання «аварійних ситуацій», тобто програшів, це окрема пісня. Програші розпізнаються окремою комбінаторною функцією. От і все! Як просто!

Ось уже цей новий код я справді легко написав на Verilog та перевірив за 10 хвилин. Подивитися його можна тут - як кажуть "відчуйте різницю".

Таким чином, мною була 2 рази реалізована гра "Вовк-Коза-Капуста" в платі "Марсохід". Обидва проекти Quartus II Ви можете взяти тут на нашому сайті:

Ну і насамкінець ще пара зауважень.

Після компіляції гри з «автоматом» я бачу, що вся логіка вмістилася в 80 логічних елементах ПЛІС платиМарсохід.
Після компіляції гри «без автомата» - вся логіка займає 49 логічних елементів ПЛІС платиМарсохід (тобто майже в 2 рази менше, ніж у першому випадку!)

Крім того, середовище розробки QuartusII може автоматично витягувати з тексту "програм" Verilog або VHDL описи state machines, тобто "автоматів". Після компіляції проекту у середовищі QuartusII заходимо у менюTools\Netlist Viewers\State machine Viewer. Так ось у першому випадку Quartus II показує граф «автомата», приблизно такий:

У другому випадку QuartusII каже: "Design has no State Machine". Ось такедиво – виявляється немає «автомата» у нашому проекті. Ну що ж, залишимо це на совісті середовища Quartus II.

Таким чином, зробимо дивний висновок – не всі "автомати" однаково корисні. Іноді буває набагато простіше і легше зробити проект «в лоб», не ламаючи голову над графами та станами усієї системи.