Игра Змейка с автопилотом

Публикация № 1051540

Сообщество - Игры

игра змейка автоматное программирование конечный автомат машина состояний Мура Мили

9
Игра Змейка с автопилотом реализована в парадигме автоматного программирования.

Игра реализована в парадигме автоматного программирования. Для ознакомления с этой парадигмой и вообще с конечными автоматами крайне рекомендую книгу Поликарпова Н.И., Шалыто А.А. Автоматное программирование - http://is.ifmo.ru/books/_book.pdf

Дополнительно рекомендую сайты:

http://is.ifmo.ru/automata/

http://softcraft.ru/auto/

ПС: игра делалась по следующему алгоритму - сначала была написана спецификация, то есть спроектированы конечные автоматы, а уже потом всё было закодировано.

Разработка велась на платформе 8.3.10.2561.

 

Спецификация

А0. Головной автомат

Смешанный автомат событийного типа. Описывает общую логику программного продукта. Запускается только по событию.

Схема связей

Граф перехода (диаграмма состояний)

 
Исходный код 

А3. Обработка событий игры

Автомат Мили событийного типа.

Схема связей

Граф перехода (диаграмма состояний)

 
 Исходный код

А1. Направление змейки

Смешанный автомат событийного типа.

Схема связей

Граф перехода (диаграмма состояний)

 
 Исходный код

А2. Сделать шаг

Автомат Мура.

Схема связей

Граф перехода (диаграмма состояний)

 
 Исходный код

 

9

Скачать файлы

Наименование Файл Версия Размер
Змейка и спецификация к ней
.zip 257,68Kb
22.04.19
0
.zip 1.1 257,68Kb Скачать

См. также

Специальные предложения

Лучшие комментарии
2. RonX01 122 08.07.19 05:09 Сейчас в теме
Обработка и спецификация
Прикрепленные файлы:
Змейка.epf
Спецификация.doc
Остальные комментарии
Избранное Подписка Сортировка: Дата
13. RonX01 122 14.07.19 09:25 Сейчас в теме
(11) Вложил свои 5 копеек коментарием в вашей публикации Сборка автомата (с примерами) :)
12. RonX01 122 14.07.19 08:48 Сейчас в теме
(10) Я читал, что формальных тестов около 32 штук чтоли, но их я не использую.
Да, я делаю трассировку интерактивно. Для этого каждый автомат в режиме предприятия при запуске пишет всё в протокол (текстовый документ на форме).
Я же смотрю граф перехода и инициирую события, потом проверяю по протоколу поведение. Ошибки можно заметить сразу. Обычно это поведение не то, которое я ожидаю, тогда в протокле я почти сразу нахожу место которое, например, не соответствует графу перехода, либо понимаю, что поведение входных либо выходных воздействий не правильное. Опять же по протоколу я знаю какие переменные и действия проверить, потому как в протоколе пишутся например, х1_ЭтоВходнаяПеременная или z1_Действие.
Чтобы быстро находить места, в коде так же именую процедуры и функции как в графе. Поскольку код автомата у меня не генерируется, а пишется в ручную, то и ошибки могут возникать в кодировании графа перехода. Такие ошибки по протоколу легко находятся, в будущем думаю найти способ для генерации кода, тогда и ошибок такого рода не будет (у меня эти ошибки редкие), да и не буду тратить время на кодирование графа.
Следующие типы ошибок - ошибки во входных переменных, либо действиях. Их либо отлаживаю в конфигурации (ставлю точку останова) либо можно обнаружить ошибку прочитав код.
Но в основном всё работает сразу, и если честно тестирование со чтением логов я провожу для того, чтобы выявить скрытые ошибки и проанализировать поведение сложных моментов.
Зацикливание тоже можно увидеть в протоколе. В общем как-то так.
11. pm74 124 12.07.19 10:45 Сейчас в теме
оставлю здесь
обработка(шутка) написана в автоматном стиле
Прикрепленные файлы:
Лампа.epf
10. pm74 124 12.07.19 09:48 Сейчас в теме
(9)
Тестирование тоже заняло мало времени, требовалось лишь проверить правильность поведения во всех состояних нового автомата и переходах.

как вы их тестируете ? подаете некоторые события на вход и делаете трассировку?
Делаете проверку на зацикливание ?
кстати у Шалыто есть книга про формальную верификацию КА я ее полистал по диагонали , очень много математики , но суть (как мне кажется) сводится к тому , что можно верифицировать некоторые атомарные утверждения на графе переходов преобразованом в модель Крипке
9. RonX01 122 11.07.19 17:39 Сейчас в теме
(7) Номерация КА делалась по времени разработки. Сначала я сделал А0, А1 и А2. Это все работало и пару месяцев лежало. После я захотел сделать новую функцию - автопилот и для этого пришлось сделать еще один КА с порядновым номером А3. Таким образом для себя я проверил насколько всё это дело масштабируемо. Оказалось всё очень хорошо. Спустя пару месяцев, глядя на спецификацию я понял, что для автопилота необходимо еще один КА, сначала спроектировал его "на бумаге" и потом закодил. На удивление ничего не поломалось. Тестирование тоже заняло мало времени, требовалось лишь проверить правильность поведения во всех состояних нового автомата и переходах.
8. RonX01 122 11.07.19 17:27 Сейчас в теме
(7) Да, при наступлении события управление передается КА.
В игре "змейка" несколько КА и для них сделана следующая иерархия: А0 -> А3 -> А1 -> А2. Таким образом внешнее событие, например "е1_НажатаКнопкаВерх" всегда передает управление А0. Дальше если А0 в состоянии Игра, то управление передается А3 с тем же событием. В свою очередь А3 передает управление А1, НО в зависимости от своего состояния может передать другое событие (взять из очереди, которую сгеренировал автопилот). И в завершении А1 пределает управление А2. Это похоже на поиск в глубину на графе.
Когда автоматов несколько то приходится думать о схеме взаимодействия, иначе может получиться рекурсия. Поэтому я и сделал передачу событий сверху вниз.

Я посмотрел, у меня на схеме связи А3 написаны события (е1 и др.), на самом деле их правильно перенести в схему А0.
7. pm74 124 11.07.19 14:13 Сейчас в теме
(6) интересно
управляющие состояния (Y) это те случаи когда при наступлении события Y управление передается вложенному КА ?
6. RonX01 122 10.07.19 17:00 Сейчас в теме
(5) Спасибо за отзыв и вопрос.

Конечный автомат здесь рассматривается не как распознаватель языка, а как устройство управления и соответственно оперирует немного другими терминами - входные воздействия (делятся на события (Е) и входные переменные (Х)), выходные воздействия (Z) и управляющие состояния (Y).
Не всегда автомат имеет события (Е). Если же автомат событийный, то он как правило, запускается по событию, а входные переменные (Х) могут быть опрошены в любой момент.

Поиск управляющих состояний (Y) в сущности со сложным поведением часто является сложной творческой задачей.

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

Поэтому "в процессе выделения управляющих состояний приходится внимательно исследовать описание сущности со сложным поведением в поисках набора "ситуаций", в которых поведение сущности имеет качественные особенности".
5. pm74 124 10.07.19 13:13 Сейчас в теме
(0) отлично сделано
если я правильно понял входной алфавит включает управляющие события (e) и условия на переходе (x , y) ?
Х и Y по какому принципу вы их различаете ?
4. RonX01 122 08.07.19 12:53 Сейчас в теме
(3) В самой игре смысла нет, для меня было важно попробовать подход автоматного программирования. А поскольку на инфостарте об этом почти ничего нет, то решил поделиться своим опытом, так сказать.
3. user1249164 08.07.19 12:07 Сейчас в теме
Прикольною Только бессмысленно
2. RonX01 122 08.07.19 05:09 Сейчас в теме
Обработка и спецификация
Прикрепленные файлы:
Змейка.epf
Спецификация.doc
1. wowik 577 23.04.19 10:06 Сейчас в теме
Оставьте свое сообщение