SoftCraft
разноликое программирование

Отправная точка
Программирование
Windows API
Автоматы
Нейроинформатика
Парадигмы
Параллелизм
Проектирование
Теория
Техника кодирования
Трансляторы
Учебный процесс
Прочие вопросы

Разное

Беллетристика
Брюзжалки
Цели и задачи
Об авторе


Открой свое созвездие или тест на воображение

В.С. Любченко

Архив с программой (исполняемый файл) и библиотеками (~ 83 Кб)

Оружие все мощнее, роботы – совершеннее, монстры – страшнее, отметины от пуль и кровь - натуральнее, а интеллект игр … остается примерно на одном уровне. Может потому, что лишь малая часть статей, книг и сайтов разработчиков игр уделяет внимание "душе" объектов? (см., например, [1,2])

О жуках

Каждый воин должен понимать свой маневр.
Суворов А.В. Наука побеждать

Описание задачи о жуках можно найти в [3]: «На полу в точках (xi, yi), i=1, … n, находятся n жуков. Каждый жук гонится за следующим: первый жук гонится за вторым, второй - за третьим, ..., (n-1) гонится за n-м, а n-й - за первым. Каждый из них движется прямо по направлению к преследуемому, и все они движутся одновременно. За каждый отрезок времени каждый жук перемещается на единицу пути в том направлении, где находился преследуемый им жук в конце предыдущего отрезка времени».

Спрашивается: «Что можно сказать об этой задаче аналитически для двух жуков? Для трех жуков? Для четырех жуков? Для n жуков?».

Давайте не только решим задачу, но также попробуем превратить ее в игру. В целях последнего рассмотрим разные варианты поведения жуков, предусмотрим и «ручное» управление жуком/жуками. Ну а графика может быть поначалу весьма простой. Так, в качестве пола может выступать фон окна отображения, а символы будут изображать жуков. На этот «скелет» потом можно будет нарастить любую график, а жуками могут быть уже анимированные человечки, машинки, монстры и т.д. и т.п.

На рис.1 показан автомат, моделирующий поведение жука, которое определяет искомое решение. На переходе из состояния «ST» в «S1» выполняется инициализация модели. – действие y1. Она может заключаться в помещении жука на исходную позицию и выполнении других действий, зависящих от реализации. Далее жук функционирует, переходя между состояниями «S1» и «S2», где действие y2 выполняет расчет новых координат, которые заносятся в промежуточный буфер. Новые значения делает текущими действие y3. Расчет положения жука разбит на два шага для того, чтобы текущие координаты были доступны всем остальным объектам на текущем шаге работы модели.


Рис. 1.

Если модель отдельного жука – это просто автомат (в данном случае – Мили), то модель множества жуков автоматная сеть. В нашем решении это модель СМКА[4] (см. и другие примеры использования СМКА, представленные на сайте SoftCraft[5]).

Говоря об автоматном решении, в противовес СМКА можно было бы рассматривать SWITCH-технологию [6, 7]. Последняя также базируется на модели автоматного типа. Но в ней нет так пригодившегося нам понятия единого времени, с помощью которого просто реализуется «каждый отрезок времени», когда жуки «движутся одновременно» (см. формулировку задачи). Другое существенное отличие технологий – разные подходы к реализации автоматов: в SWITCH необходимо преобразования КА к модели блок-схем, а в КА-технологии в этом нет необходимости. Но, пожалуй, еще больший недостаток SWITCH в том, что в ней не определена параллельная модель процессов. А это важно не только для решения рассматриваемой нами задачи о жуках.

Интеллект

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

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

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

В любом случае именно программист задает уровень интеллекта игровых объектов, т.е. их поведение. От него завит насколько будет привлекательна игра, напоминая при этом, возможно, даже что-то реальное. И не только по графическому изображению, но и по поведению.

Игры с игрой

Когда поведение объектов в общих чертах определено и реализовано, наступает время диалога с игрой в прямом и переносном смыслах. С одной стороны, речь идет об окончательной доводке диалога, включении новых режимов, совершенствовании настроек и т.п. С другой стороны, уже игра подбрасывает идеи программисту, на которые он может откликнуться, подхватить, развить и реализовать их. Нередко появляется и желание изменить поведение объектов, т.к. замысел может выглядеть не так уж привлекательно в реализации и наоборот. Возникают и новые игровые образы… Но совершенству, как известно, нет предела, а потому в дополнении к уже сказанному рассмотрим лишь те идеи, которые показались наиболее интересными.

Все выше перечисленное в рамках игры выполняется путем выбора того или иного поведения жуков в процессе диалога. Конкретно это выглядит так. При запуске игры открывается окно, в котором строго друг за другом, то просто, то, играя в кошки-мышки, носятся жуки в виде «звездочек». Щелчком правой кнопкой мыши по «полу» (окну отображения), вызывается диалог, в котором можно: 1) изменить вид жука, 2) выбрать поведения жука, 3) изменить число жуков, 4) установить величину перемещения жука за единицу времени, 5) выбрать реальное значение для дискретного времени модели. Здесь же предусмотрены и режимы, уточняющие поведение жука: 1) следить первому жуку за указателем мыши, 2) режим решения задачи, при котором жуки ведут себя в соответствии с ее условием, 3) режим «кошки-мышки», когда жук, догнав другого, перемещается в то или иное место пола в соответствии с выбранным типом поведения.

Кстати очень удобным оказалось не последовательное манипулирование кнопками «Разместить» и «Создать фигуру», а простое установка/сброс режима «кошки мышки». При установке режима жуки разбегаются, что соответствует нажатию кнопки «Разместить», а при сбросе они стремятся создать некоторую фигуру. При этом, если установлен «режим решения задачи» это будет замкнутая фигура, а если он сброшен – некоторая кривая линия из жуков. Последней можно управлять, если установлен режим «следить за мышкой».

Тест на воображение

Когда б вы знали, из какого сора
Растут стихи, не ведая стыда...
А.Ахматова.

Воображение - это то, что, видимо, отличает человека от других «тварей». Именно оно позволяет в образе «звездочки» увидеть жука, человечка… В их расположении - хоть и стилизованный, но вполне реальный образ цветка, котенка, машинки и т.д. и т.п. То, что в хаотическом движении точек, звездочек, черточек, цифр позволяет увидеть полет пчел, мушек и т.д. и т.п.

Как ни покажется странным, но в результате игр с игрой привлек внимание ее базовый вариант. Выбрав «режим решения задачи» и нажав последовательно кнопки «Разместить» и «Создать фигуру», мы можем наблюдать эффект подобный тому, который возникает в калейдоскопе. Только здесь картина формируется из хаотического расположения звездочек, а не цветных стеклышек, а перемещение жуков в конечную точку порождает ту фигуру, которая будит Ваше воображение подобно стеклышкам в калейдоскопе. Игра еще больше напоминает калейдоскоп, когда мы просто устанавливаем/сбрасываем галочку «кошки-мышки». Когда она установлена, жуки разбегаются и начинают активно перемешиваться, а при сбросе галочки через какое-то время появляется та или иная фигура из «звездочек» – рыбка, лисенок, человечек и т.д. и т.п.

Интересен режим – «следить за мышкой». Получаем, как уже было сказано, «полоску» или «ленточку», которая стремиться догнать мышку, повторяя ее движения. Это может напомнить и червячка, и хвост воздушного змея и т.д. и т.п. А если организовать множество таких «ленточек», то может получить водопад и т.д. и т.п. И хотя все эти «если» требуют, порой, титанического труда, но на то и есть … геймеры.

Уже с минимумом «графики» и зачатками «интеллекта» жуки привлекают внимании своим «интеллектуальным поведением». А если все это «раскрасить», подключить реальную графику? А если организовать «перетекание» одной фигуры в другую? Можно также фиксировать и обмениваться теми конфигурациями, которые породили наиболее интересные объекты и т.д. и т.п.?

Заключение

У каждого человека свои звезды.
Антуан де Сент Экзюпери. Маленький принц

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

Игры - это сложные программные приложения, которые нуждаются в интеллектуальных параллельных моделях. Модель СМКА – этого типа. На примере решения задачи о жуках мы показали ее возможности…

Созданная игра напомнила мне звездное небо. Теперь имена … Южный крест, Большая и Малая медведицы в рамках игры имеют свои подобные образы. Правда, нужно знать, как расположить жуков на полу, чтобы их создать… Но это уже дело техники.

Разбросай «жуков» и открой свое созвездие, назвав его тем именем, которое тебе подскажет воображение…

Как говорится, - ЗЫ (PS) … в корень

О перспективах... Можно, не изображая жуков, соединить линией точки их текущего положения. В конечном положении жуки тогда, может быть, будут больше походить на тот или иной стилизованный рисунок. Можно организовать перетекание одной фигуры в другую. Или совершенствовать само поведение жуков, например, добавив им «физики», для чего задать им массу. Последнее, безусловно, еще больше приблизит задачу к реальным объектам, к процессу моделирования их поведения.

PPS

Графика – трудоемкое, если не сказать, в чем-то даже нудное занятие (на мой взгляд, конечно). Требует она к тому же определенных творческих способностей. После некоторых колебаний я все же решил добавить элементы графики, а именно, соединить, как было сказано выше, линией соседних жуков, которые могут быть еще и разного цвета, ширины, цвет может меняться в динамике и т.д. и т.п. Тем более, что сделать это не так уж и сложно, т.к. с точки зрения программирования все уже подготовлено на этапе вывода символьного вида жуков.

С линиями в цвете жуки еще больше напоминают калейдоскоп. В какой-то мере «графическую эволюцию» игры отражают образы экранов представленные в приложении рисунками 1-4. Эти и подобные им фигуры можно получить поочередным нажатием кнопок «Разместить» и «Создать фигуру». При этом изображение символа жуков убирается заданием символа пробела в поле окна диалога «вид жука».

Осталось сказать, что для работы приложения необходимо наличие следующих библиотек: 1) среды реализации автоматной модели – fsam532.dll, LwsLib.dll, 2) библиотек Visual Studio - MFC42D.DLL, MSVCP60D.DLL, MSVCRTD.DLL. Приложение и FSA-библиотеки можно скачать с сайта, а остальные компоненты могут либо уже находиться в каталоге системы WINDOWS/System32, или их нужно взять, например, из дистрибутива Visual Studio 6.0.

Литература

  1. Группа: Обсуждение проблем моделирования "искусственного интеллекта"(AI) в играх. Форум сайта DTF. http://dev.dtf.ru/forum/groups.php.

  2. Ла Мот А., Ратклиф Д., Тайлер Д. Секреты программирования игр /Пер. с англ. - СПб: Питер, 1995. - 720 с.

  3. Нивергельт Ю., Фаррар Дж., Рейнголд Э. Машинный подход к решению математических задач: Пер. с англ. - М: Мир, 1977. - 352 с.

  4. Любченко В.С. От машины Тьюринга к машине Мили. «Мир ПК», № 8/02. http://www.osp.ru/pcworld/2002/08/130.htm

  5. Сайт SoftCraft. Раздел Автоматы. http://www.softcraft.ru/auto/

  6. Шалыто А.А. SWITCH-технология. Алгоритмизация и программирование задач логического управления. СПб.: Наука, 1998. 628 с.

  7. Сайт СПбГУ ИТМО, раздел Проекты. http://is.ifmo.ru

Приложение. Скриншоты программы Kinks

Созвездие «Голова мышонка»


В увеличенном масштабе

Рисованный «Мышонок» в цвете


В увеличенном масштабе

Собака и ее … конура


В увеличенном масштабе

Рыба


В увеличенном масштабе