Диплом: танчики и генетическое программирование

При выборе темы диплома учитывалось желание накодить что-то практическое, что и повлияло на выбор темы. Было принято решение разработать платформу для проведения соревнований по программированию ИИ танка. В целом идея не нова и такие вещи уже делались (http://robocode.sourceforge.net, например). Но существует несколько причин, по которым были выбраны именно танчики:

• Эти самые танчики послужили платформой для теоретической части диплома: исследование ГП применительно к задаче управления объектом
• Как уже говорилось выше, хотелось закодить что-то свое, разработать протокол, запрограммировать сервер и клиентов.
• Поработать с OpenGL на практике
• Попробовать C11

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

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

Протокол

Для общение используется двоичных протокол поверх UDP. Почему UDP? Он сохраняет границы сообщений, потому что это message-based протокол. Это значит, что данные приходят точно такими же порциями, какими они отправлялись, что значительно упрощает сетевую часть. В условиях нехватки времени это, по моему мнению, — разумное решение. Вместо UDP можно было бы использовать SCTP, например. Но он не реализован под Windows, а разработка велась под этой ОС.

Протокол состоит из пакетов, каждый из которых начинается с id. Поэтому, размер пакетов зачастую известен наперед — по первому байту. Для пакетов переменной длины в теле пакета предусмотрена статическая часть, которая позволяет определить размер всего пакета.
В коде пакеты описываются C-структурами с отключенными выравниваниями.

Компоненты

Танчики состоят из сетевого сервера, тестового и «генетического» клиентов и программы-просмотрщика.
Сервер обрабатывает запросы, шлет notifications и ведет все расчеты.
Тестовый клиент предназначен для отладки. Он считывает команды управления танком со стандартного ввода и отправляет на сервер. Например,pi (power increase) — увеличить мощность двигателя, s (shoot) выстрелить, ll (look left) — немного повернуть пушку влево.
«генетический» клиент — запускает генетическую программу управления танком на языке Slash/A. Это специально разработанный для ГП язык и ВМ для его исполнения. Набор команд ВМ был расширен специфическими для управления танком командами.

Пример программы на Slash/A:

input/   # gets an input from user and saves it to register F 0/       # sets register I = 0 save/    # saves content of F into data vector D[I] (i.e. D[0] := F) input/   # gets another input, saves to F add/     # adds to F current data pointed to by I (i.e. D[0] := F) output/. # outputs result from F 

Программа-просмотрщик предназначена для наблюдения за боем. Можно парить над картой используя WASD, F, V и крутить камеру мышью.
Во время разработки пара тестовых клиентов (для танка-жертвы и танка-победителя) и просмотрщик были одними из основных инструментов отладки.

Скрин:

C11

В C11 добавили много разных фич. Мне были полезны такие:

• Типонезависимые макросы (математика и math.h)
• Многопоточность

Также, были полезны Variable Length Arrays и Designated Initializers из C99. Ну и возможность объявлять переменные не только в начале scope тоже была очень полезна.

Для сборки C части использовался отличный компилятор pellesc.de/ с отличной справкой по библиотекам, языку и среде.
Для сборки C++ части использовался GCC (MinGW).

Ссылка на исходники: http://code.google.com/p/morrigan. К сожалению, я плохо разбираюсь в лицензиях, поэтому уже для второго своего проекта выбираю «Other Open Source». Как-нибудь обязательно прочту какой-то ликбез.
В принципе, из непортабельная зависимость только одна — Winsock. Почему morrigan — вики. С самого начала я решил назвать проект женским именем, а потом пришла идея про богиню войны.

Сам диплом я сверстал в LaTex, о чем ни разу не жалею и всем советую. Это совсем не так страшно, как может показаться, особенно после года подготовки протоколов к лабораторным в LaTex. При возникновении трудностей меня спасал google (который приводил в основном на tex.stackexchange.com) и хорошая документация к пакетам. Глядя на своих друзей, которые мучительно вручную расставляют номера страниц в рамке, подписи к рисункам и таблицам и ссылки на них, я еще раз убедился в правильности принятого решения.

В целом, я доволен. Удалось немного отвлечься от вездесущего ООП и попрограммировать в свое удовольствие.

Ссылки

• www.gamedev.ru — статьи про ландшафт, карты высот и Collision Detection
• Collision Detection in Interactive 3D Environments — целая книга про Collision Detection
• www.libsdl.org — кроссплатформенная библиотека для работы с графикой, звуком и устройствами ввода
• Стандарт C11
• Библиотека Slash/A
• Справка Pelles C
• c.learncodethehardway.org — интересный учебник по С (даже для тех, кто знает) и чудесный header debug.h