Привет.
При выборе темы диплома учитывалось желание накодить что-то практическое, что и повлияло на выбор темы. Было принято решение разработать платформу для проведения соревнований по программированию ИИ танка. В целом идея не нова и такие вещи уже делались (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
Автор: aquirel
