Детские мечты или Pack-Man своими руками
Каждый в своей жизни делал свой велосипед. В оправдание желания его сделать, можно только сказать, что если бы люди периодически это не делали, то многих вещей мир бы просто не увидел.
Свою игру, а точнее игровой искусственный интеллект (ИИ) сделать желание было очень давно. Не буду кривить душой: сначала банально не хватало знаний, потом как ни странно времени. У меня было несколько недель относительно свободного времени, что бы реализовать мечту своего детства.
Расскажу что получилось, а также опишу путь, по которому шел, и наблюдения, которые по пути сделал. Оговорюсь сразу, что буду описывать не код, а соображения, мысли, и проблемы с которыми столкнулся в процессе реализации мечты.
Этап планирования структуры
При планировании структуры среды обитания ИИ сразу сделал попытку заложить расширяемость и хоть какую-то универсальность. Решено было делать все на динамических массивах, с повсеместным применением подходов объектно-ориентированного программирования, где только возможно будет.
В основе иерархии классов среды обитания ИИ было положено несколько пар классов:
- Ключевая точка – класс, который отражает места пересечений связей графа путей.
- Путь – класс, который обеспечивает связи между Ключевыми точками.
- Объект – класс, который является производным от класса Ключевая точка, экземпляры которого размещаются на Пути.
- Субъект – тот же класс Объект, экземпляры которого имеют функции принятия решений.
Замыкает перечень классов класс Мир, который обрамляет все перечисленные классы, организуя их взаимодействие между собой.
Для работы нужна была какая-то конкретная не сложная игровая концепция. И в качестве такой была выбрана концепция игры Pack-Man, ввиду простого набора правил.
Сразу же были выделены дополнительные подклассы Объектов и Субъектов игры:
- субъект Пакман – тот самый Packman;
- объекты Фрукта – те, что для поесть Пакману;
- субъекты Приведение – те, для которых в игре создан Пакман.
Этап планирования работ
Как показал поверхностный анализ: необходимое количество кода для полноценной работы игры, несмотря на небольшое количество функционала системы, оказался довольно большой. Сделан был естественный вывод, что нужно произвести дробление задач на множество изолированных подзадач, что бы было видно хоть какие-то результаты своей возни – иначе детские желания могли превратиться в недетский затяжной кошмар.
Были сразу же выделены следующие этапы реализации:
- Создание классов обеспечивающих функционирование мира, в котором будет жить искусственный интеллект (классы Мир, Ключевая точка и Путь);
- Отрисовка Мира и заодно создание основы функционала для визуализации данных.
- Создания класса Объект, его взаимодействий со средой.
- Создание первого экземпляра Объекта, а именно Фрукты и ее отрисовка.
- Создание дополнения функционала для Объекта, что бы превратить его в Субъект.
- Создание экземпляра Пакман. Отрисовка. Добавление правил в игру.
- Разработка кода взаимодействия с пользователем, организация работы системы в «реальном масштабе времени».
- Реализация алгоритма поиска кратчайшего пути. Соединение его с управлением Пакмана и автоматическим изменением его состояния Миром во времени.
- Создание экземпляра Приведение. Отрисовка. Добавление правил в игру.
- Улучшение системы по мелочам.
- Получение удовольствия.
С этим планом я приступил к работе.
Реализация
Первые два этапа оказались простыми. Была организованы три класса: Мир, Ключевая точка и Путь: их конструкторы, деструкторы, несколько функций обеспечивающих создание связей между экземплярами классов по ссылке, и собственно все.
Был создан экземпляр класса Мир с пятью точками, где пути образовывали конверт со смещенной центральной точкой, что бы расстояния между точками были явно разной длины. Отрисовка была сделана очень-очень скромно: линиями да кружечками – ровно на столько, насколько можно было понять, что в Мире происходит.
Этапы №3 и №4 тоже особого труда не вызывали – Фрукта не бегала, не вредничала, а только лежала и отрисовывалась.
Начиная с этапа №5 пошла основная работа. Был написан функционал Субъекта с использованием класса Объект в виде списка дел, которые хотел бы сделать Субъект. Дополнен функционал класса Мир, который занимался мониторингом списка дел Субъектов и выполнял их в рамках имеющегося у Субъекта кванта времени и наложенных на действия Субъекта ограничений и правил игры.
Этап 6 Проблемы с появлением экземпляра Пакмана как нестранно не начались. Просто появился экземпляр типа Субъект, а так же отрисовка на дисплее в нужной координате кружочка. И еще были добавлены правила поедания Фрукты.
Даже на этапе №7, когда мышкой генерировалось одно задание в виде команды «беги» к указанной координате, проблем не было. Искалась ближайшая точка, которая попадала бы в Путь, на котором уже стоял Пакман и Пакман послушно туда шел.
Приключения начались на этапе №8, где выполнялась реализация алгоритма поиска кратчайшего пути. Функция поиска кратчайшего пути представляла собой модифицированный алгоритм Ли, адаптированный к динамическим массивам и структурам графа. Основные сложности были при написании кода, где реализован был обратный ход. Для уменьшения количества перестраиваний структуры графа при перемещении экземпляров Объектов Объекты были сделаны не как узловые Ключевые точки, соединенные Путями, а как Ключевые точки, принадлежащие к Пути. Имея на момент написания статьи работающий код, до сих пор не уверен в правильности выбранного решения. Что проще: то ли перестраивать локально граф Мира и заодно маршруты Субъектов, которые перемещаются через измененные фрагменты графа или просто размещать классы Субъектов и Объектов на неизменяемом графе Путей.
Само собой на всех этапах работы постоянно мелькали ошибки доступа к памяти. Наиболее жестокий случай был, когда сообщение вылетало где-то на середине игры. Забывал убирать ссылку между Путями и разрушенными экземплярами Фруктов, когда их съедали. Ошибка проявлялась спустя время после съедения при перезаписи памяти. Пока там хранились данные разрушенного объекта и они были не перезаписанные новым динамическим объектом все было нормально, т.е. крах программы был не мгновенный.
Наконец на этапе №9 было добавлено первое Привидение. Точка назначения была всегда координата Пакмана. Использовалась уже написанная функция поиска кратчайшего пути, которая вызывалась постоянно 24 раза в 1 секунду. После генерации списка действий движение Привидения осуществлялось системой (Миром) автоматически.
Когда пришел к этапу №10, то, как говорится, сани понеслись!
Был сделан генератор случайных карт. При создании карты для генерации Путей было сделано несколько критериев их допустимого создания: в узловых точках должно пересекаться не более 4-х Путей, а узловые точки должны быть не ближе к уже проложенным Путям определенного расстояния, как и пути не должны быть длиннее определенной константы.
Затем были добавлены несколько Приведений, которые настырно преследовали Пакмана.
Играть с такими Приведениями было просто нереально. И тут меня осенило, что нужен «туман войны», тогда бы Приведения более естественно себя вели, а не радикально меняли свой маршрут, когда ты немного изменял маршрут Пакмана где-то на другом конце карты.
Первая мысль было для каждого Субъекта нужно делать массив видимых элементов мира, а также доделать память Субъекту, что бы хранить где, кого и когда он видел. Подумав, понял, что для паука, который хочет съесть муху это все очень сложно и в реализации громоздко.
Выход был найден как нельзя простой. Случайным образом находилась точка на карте, куда следовало Приведение (таким образом, было организовано простое брождение по карте и поиск Пакмена). В случае попадания Пакмена в определенный (заданный константой) диапазон видимости Приведения, у Привидения перестраивался маршрут к нему. При нахождении жертвы в области видимости Приведение постоянно перестраивало к ней свой маршрут, а при выходе Пакмена за пределы видимости Приведение продолжало следовать к точке, где его последний раз видело жертву. По достижении этой точки начиналось опять слепое брождение по карте.
На этом собственно остановился и спокойно перевел дух.
В завершение были достроены декоративные элементы: «Конец игры» (съедение Пакмена), подсчитывание очков (количества съеденных Фрукт), «Завершение уровня» (съедение всех Фруктов).
Итоги мучений.
Несмотря на большое количество пролитого пота и крови были достигнуты сравнительно небольшие результаты: для дальнейших изысканий реализована основа Мира, в котором живет интеллект простейшего хищника типа паук. По видимости дальше необходимо создать модификацию существующего алгоритма ИИ для реализации поведения «Жертвы» (в рамках игры – это убегающие от Пакмана Фрукты), а также комбинированного ИИ («Хищник-жертва»), что позволит сделать бот Пакмана, а затем не тратить силы на «поиграть», а только с удовольствием наблюдать на метания в пробирке этого «Колобка».
Посмотреть воочию, что вышло можно «Здесь» (исполняемый файл для Win32)*. Обратите внимание на тумблер «Режим матрицы». При его включении можно видеть, как система принимает решения, и почувствовать себя немного Нео. К сожалению, додумался его сделать на 10-м этапе, для лучшего понимания работы ИИ. Если бы сделал ранее, потратил меньше время на отладку алгоритма поиска кратчайших путей.
P.S. Не все и не всегда делается из соображений экономической целесообразности и оптимальности, некоторые вещи делаются ради удовольствия. Несмотря на простоту графики, когда «Она» задышала, я испытал неописуемую радость.
* Уже после завершения всех запланированных работ и написания статьи обнаружил еще одну редко выпадающую ошибку. Место выпадения ошибки указывает, что проблема связанна с тем, что моделирование игрового мира выполняется в обработчике обычного таймера, а управление Пакменом в обычном обработчике мыши. В общем, там нет никаких обычных семафоров и других подобных «заумных» вещей, что позволило бы обеспечить целостность данных, к коим идет обращениях в обеих функциях. Думаю до свадьбы заживет к коммерческой версии баг будет исправлен.
Автор: DSparrow
