Собираем игру «Змейка» на макетной плате. Часть 1: конечные автоматы

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


    Игра Snake (она же змейка, питон, удав и т.д.) широко всем известна. Родом она из далёких 70-х, но я не буду повторять её историю, которую вы можете почитать в википедии или множестве статей на Хабре. Игра имеет достаточно простые правила и при этом затягивающий геймплей )) Благодаря этому её часто используют для туториалов или примеров кода. На языках программирования высокого уровня сделать такую игру достаточно легко. Но вот в более ограниченных условиях начинается самое интересное, например реализация на LabVIEW. Есть также множество вариантов на FPGA: ссылка 1, ссылка 2, ссылка 3, ссылка 4. Но ещё не было ни одного варианта на отдельных ТТЛ-микросхемах стандартных серий. Значит этим мы и займёмся.

    Казалось бы, самыми близкими для нас являются решения на FPGA и оттуда можно много позаимствовать? Но во всех вариантах, которые я посмотрел, с лёгкостью разбрасываются регистрами налево и направо. Например, очень часто выделяют для каждой клетки поля отдельный бит или число. С рассыпухой мы так поступить не можем, ведь каждый новый регистр — это отдельная микросхема, которую надо где-то разместить, а потом ещё и соединить. Поэтому мы перечеркнём весь накопленный другими разработчиками опыт и будем делать всё с нуля. В качестве бонуса будем собирать всё на отечественных (а лучше — советских) микросхемах серии к555/кр1533, за исключением ПЗУ, которые придётся взять свежие.

    Постановка задачи


    У нас будут такие ограничения: поле размером 8×8 клеток (китайская светодиодная матрица), длина хвоста 8 клеток. Змейка может проходить через стены, а пересечение с хвостом мы поначалу обрабатывать не будем (дабы не усложнять конструкцию, добавить это можно потом). Чтобы описать всё состояние игры нам понадобится:

    1. Положение головы (X=0..7,Y=0..7, 6 бит)
    2. Направление движения (↑↓←→, 2 бита)
    3. Положение яблока (X,Y, 6 бит)
    4. Длина хвоста (0..7, 3 бита)
    5. Положение клеток хвоста (от 0 до 7 штук по 6 бит каждая)

    Итого получается 65 бит, даже если брать регистры по 8 бит каждый, то только на хранение состояния понадобится 8 таких микросхем (и ещё один триггер), это довольно много.

    Но хвост не может располагаться где ему вздумается, он «растёт» от головы. Поэтому мы можем хранить не полные координаты каждой секции хвоста, а только направление в какую сторону от предыдущей клетки (или головы) его надо нарисовать. Тогда вместо 6×8=48 бит нам понадобится 4×8=16 бит, а это уже экономия целых четырёх корпусов регистров!

    Автоматы


    Попробуем сделать всё на автоматах, похожих на автоматы Мура или Мили. Для реализации такого автомата достаточно иметь немного памяти состояний (регистр) и комбинационную логику для перехода между ними.


    Картинка из википедии

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

    Больше информации и красивых картинок вы можете найти, например, в этой статье на Хабре

    Небольшое отступление
    В отечественной литературе, бывает, делят автоматы на имеющие жёсткую логику и программируемую. Я считаю такую дискриминацию несправедливой, ведь ROM по сути является такой же комбинационной схемой, и любую комбинационную схему можно заменить на ROM. (Как и наоборот, и этим мы воспользуемся чуть позже).

    Такой пример с красивой картинкой можно найти, например, тут.


    Все наши автоматы будут очень сильно напоминать эту схему, но я не буду заниматься «автоматным шовинизмом» и выделять одну реализацию КА среди других.



    У змейки различных состояний (если не учитывать положения яблока) может быть 2^8+2^10+...+2^24 ≈ 32 миллиона. Расписать их в таблице, а уж тем более нарисовать граф переходов не представляется возможным. Но бóльшая часть переходов вполне однотипные (голова передвигается только на одну соседнюю клетку, а хвост продвигается по одной секции за ход). В таком случае мы можем описывать не каждое отдельное состояние, а сформулировать новое состояние в виде функции от предыдущего. Более того, всю игру мы можем разбить на несколько параллельных автоматов: 1) автомат направления, 2) автомат положения головы, 3) автомат для хвоста. И задать каждый из них так, как будет удобнее:

    1) входы, направление │ новое направление
      ────────────────────┼───────────────────
       ←        ←/↓/↑     │ ←
       ←          →       │ →
       ↑        ↑/←/→     │ ↑
       ↑          ↓       │ ↓
       ...итд...          │
    

    2) направление, голова │ новая голова
      ─────────────────────┼──────────────
       ←             (x,y) │ (x-1, y)
       →             (x,y) │ (x+1, y)
       ↑             (x,y) │ (x, y-1)
       ↓             (x,y) │ (x, y+1)
    

    3) направление, хвост                      │ новый хвост
      ─────────────────────────────────────────┼──────────────────────────
       ←            (t1,t2,t3,t4,t5,t6,t7,t8)  │ (←,t1,t2,t3,t4,t5,t6,t7)
       ...итд...                               │
    


    Направление


    Начнём с автомата направления. Если хорошо подумать, то можно собрать его на отдельной логике. Но, поскольку задача в целом и так немаленькая, я решил, что проще будет сделать lookup table из EEPROM, а таблицу переходов записать вручную. Она будет иметь 6 входов, а значит только 64 значения, которые мы можем просто вбить в hex-редактор.



    Голова


    Для автомата положения головы написать такую таблицу будет намного сложнее. Но она содержит по сути только 2 операции: +1 и -1. Их можно реализовать на 4-х разрядном сумматоре К155ИМ6. Для +1 мы будем складывать нашу координату с b'0001, а для -1 с b'1111 (что собственно и есть -1 в дополненительном коде). Нам понадобятся два сумматора (для x и y), немного логики, а хранить состояние мы будем в 8-битном регистре ИР27 (их нам пригодится ещё много):



    Соберём это на плате, а для проверки сразу подключим светодиодную матрицу с двумя дешифраторами. Дешифратор с инверсными выходами — ИД7, а для прямого можно было бы взять К561ИД1 (CD4028), но у меня под рукой его не было. Другой вариант — взять 8 транзисторов в качестве ключей, но делать этого не хотелось, поэтому пришлось бездарно потратить ещё один EEPROM (записав туда всего лишь 8 ячеек).


    Логика нового положения головы на отдельной плате сверху

    Ещё одно отступление
    Сделаем небольшую передышку и сэкономим макетную плату (и несколько корпусов микросхем). Мы снова воспользуемся тем, что любую комбинационную схему можно заменить на LUT, записав таблицу в ROM. Но как это сделать для такой большой таблицы? Воспользуемся другим трюком — сделаем наоборот: заменим EEPROM на нашу логическую схему и засунем её в программатор.


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

    Теперь прочитаем нашу логическую схему как ROM и получим таблицу. Запишем её тем же программатором в реальный EEPROM, который поставим вместо схемы из отдельных элементов.


    Хвост


    Хвост имеет длину (в наших ограничениях) от 2 до 8 клеток. Для хранения этой длины можно воспользоваться обычным счётчиком с входом разрешения счёта. По факту это будет такой же конечный автомат, у которого новое состояние S' будет равно S+1 или просто S (если счёт запрещён). Сам хвост (а точнее, направление, куда он растёт) мы будем хранить в двух регистрах по 8 бит. Теоретически, можно было бы взять готовые сдвиговые регистры (например, ИР8), но их под рукой не оказалось, поэтому в ход пошли те же самые ИР27. На каждом шаге в первый бит регистра записывается текущее направление движения головы, а во второй и последующий — значение предыдущего. Чтобы получить из него направление роста хвоста нам достаточно проинвертировать один бит. Можно сделать это сразу при записи, но я решил, что лучше оставить инверсию для оставшейся схемы.

    Схема


    Итого, наш автомат следующего хода принимает такой вид:


    Эта картинка (как и все остальные) кликабельна.

    Это довольно «чистая» (с теоретической точки зрения) часть схемы. Практически идеальный пример для output coded Moore machine. U1 отвечает за новое направление, U2 за положение головы, которые хранятся в U5. Для хвоста используются U3 и U4, а его длина хранится (и увеличивается) в U6.
    Дальше нам надо будет сделать отображение всего что у нас есть на экране, и там тоже будет КА, только в более грязном виде. А также примитивный генератор случайных чисел, переход между схемами с разным тактирующим сигналом и прочие хаки.

    Подытог


    Надеюсь, что данная статья вас заинтересовала и я постараюсь побыстрее закончить вторую часть.

    А если вы уже рвётесь в бой, запаслись макетными платами, микросхемами и точечными экранами, то к этой статье прилагается файл со схемой и прошивками ROM. Мини-спойлер: для повторения конструкции вам понадобятся примерно 6 макеток, 4 EEPROM 28C16 и чуть больше двух десятков других микросхем.

    Ну и как полагается: лайк, шер, ретвит, подписывайтесь, жмите колокольчик, итд… )) А на сегодня всё, спасибо за внимание! Продолжение следует…



    Архив с прошивками ROM и общей схемой

    UPD: вторая часть доступна по ссылке.
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

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

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

      +1
      Впечатляет. Будете со временем усложнять, добавляя фон, затем два фона, перемещающихся с разными скоростями, различные звуки, пока по сложности не сравнится с «Пониматом» Коковина?
        0
        К сожалению, нет )) Моих сил и интереса ребенка (что важнее) не хватило даже на то чтобы реализовать пересечение с хвостом, мы пошли дальше. Но в теории это всё тоже реально сделать.

        Ещё была мысль сделать в двух цветах (змей каноничного зелёного, а яблоко красного цвета), но почта где-то по пути потеряла RGB-панель…
          0
          Если следовать zanuda mode, в «Понимате» ПЗУ хранят спрайты, фоны, музыку и сэмплы, но в логике игры не участвуют, а здесь — участвуют. Но зато всё документировано, минималистично и повторяемо.
        +2
        Отличная работа!
        Люблю олдскул без ардуин.
        Кстати, когда я учился, подобный автомат на ROM и регистрах называли «секвенсер», а сейчас нигде почему то такой термин не вижу.
        Жду продолжения…
          0
          А я встречал название «микропрограммный автомат».
            0
            про это как раз есть мини-спойлер ))
          0

          Милота!
          Набросай только общие идеи по переводу 4 * 28C16 в более современные ИМС (вплоть до 4 Мб "параллельных флешек", не firmware HUB, с устаревших материнок). Ибо у меня в загашнике есть только 2 (две) штуки 27C16, а эти флэшки нынче найдутся у любого желающего. ИМХО.

            0
            Вообще, я наоборот хотел взять КР573РФ5, но их не нашлось в нужном количестве, да ещё и программатора со стирателем.

            Если делать на современных имс, то это скорее будет что-то типа iCEstick. А 28с16 в виде б/у или выпаяных продают китайцы. Если с ними не охота связываться, то в разных магазинах всё ещё встречаются 28c64b, можно взять их если забить на лишние разряды.
            +3

            Вот прямо ждал что тут будет очередная статья про ардуино! Ан нет. Тут настоящий хардкор! У меня только один вопрос: сколько лет вашему сыну?

              +3
              8 лет. Для «ноликов и единичек» этого вполне достаточно, требуется только умение складывать и вычитать (он поучаствовал в составлении картинки с сумматорами и писал таблицу с кнопками)
              +1

              Мда… Помню, курсовой по электронике у меня и ещё одного товарища свелся как раз к тому, что вместо разработки набора логики мы использовали одну микросхему-стабилизатор питания и одну eeprom. Но сами дошли что так можно, честно-честно.

                0
                Интересно выполненное устройство. Ему бы ещё на светодиодный экран какое нибудь затемнение, чтобы не было видно не горящих диодов, или чтобы их немного приглушить, оставив как сетку-прицел. А как лучше сделать — тонированным стеклом или матовым, надо на примере смотреть. Странно что этого ещё никто не предложил.
                  +2
                  Все же даже для продвинутых 8 лет выкопанная яма слишком глубока. Сложно представить понимание даже трети использованного.

                  Я конечно не буду утверждать, что в 8 это невозможно понять, но все же это больше похоже на материал для очень продвинутого 14-16-летнего
                    0
                    Вот эта первая часть достаточно хорошо зашла, правда не за одно занятие, в спокойном темпе на это ушло недели 3. А вот вторую часть я по большей части делал сам, на картинках объяснял, но нагружать даже не старался…
                    0
                    А напишите пожалуйста по каким ресурсам изучаете?)) думаю многим было бы полезно узнать (включая меня). спасибо
                      0
                      Тут много рекомендуют книгу Харрис и Харрис. Но для младшего школьного возраста это будет слишком тяжелый материал, я использую её как примерный план и какие-то задачки для иллюстраций (пропуская большие её части, физику транзисторов, весь Verilog/VHDL и ещё много чего).
                      Более развёрнутый ответ надеюсь напишу во второй части.
                        0
                        спасибо! буду ждать
                          0
                          Во второй части написал основные материалы. Дополнительно к этому скажу, что в детстве сам изучал по такой книжке: МРБ 1097: Основы цифровой техники. Но она на данный момент уже заметно устарела.

                          Если изучаете для себя, то книжка Харрисов — самое то. Для дальнейшего погружения в тему рекомендую Digital Design. Principles and Practices 4th ed. John F. Wakerly.

                          А если с ребенком, то нужно примерно представлять какие вещи будут легко понятны, а какие стоит пропустить. Тут к сожалению хороших книг не посоветую, опираюсь на свой опыт, что мне самому было понятно в том возрасте, а что уже было тяжело/неинтересно.
                    +2
                    Воспользуемся другим трюком — сделаем наоборот: заменим EEPROM на нашу логическую схему и засунем её в программатор.

                    Гениально! У меня-то первая мысль — сгенерить таблицу на каком-нибудь питоне, но скопировать живую логику я бы не догадался.


                    Жду второй части. Намного интересней наблюдать, как змейку реализуют с учётом минимизации ресурсов (читай: корпусов), чем на сотую реализацию на FPGA.

                      +1
                      я думал я знаю что такое конечные автоматы. оказалось что нет)
                        0
                        Интересно, а _другую_ логику этого автомата вы не рассматривали?
                        В ней нужно иметь «длину тела», которую вначале поставить в одну ячейку массива. Это и будет голова.
                        И направление, в котором голова поедет в следующем ходу.
                        А затем все ненулевые ячейки просто уменьшаются с каждым ходом на 1, и светятся только те точки, где не ноль.
                        В итоге у змеи нет головы и хвоста, а есть только «сегменты», у каждого их которых своё время жизни. И от величины начального значения зависит, сколько тактов он проживёт, а соответственно и видимая длина хвоста. Удлинять просто — вписывай в новые позиции бОльшее число. Обработка коллизий тоже проста — если в новой позиции не ноль, то либо конкретное значение яблока, либо свой же сегмент.

                        Это, конечно, в битах не вывести, нужна работа с другими элементами. НО как подсказывает мой опыт создания автоматов на логике, тут есть потенциал уменьшить число корпусов.
                          0
                          Таким способом как раз работают многие реализации на ФПГА. Если делать на 1533-ей серии, то на это понадобится как минимум 32 корпуса только на хранение клеток, про коммутацию этого всего я даже боюсь думать…

                          Если вам удастся в таком варианте уменьшить количество корпусов (без использования фпга), то будет очень интересно посмотреть на такой вариант. Наверное, можно использовать RAM, но обвязка кажется что будет сложнее.

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

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