Вдохновленные как и многие другие отчетами Adept мы приняли участие в ICFP 2007 и в итоге заняли 4-е место. Впечатления от прошлого года остались самые положительные и в этом году мы собрались снова, правда немного в другом составе. В этот раз мы тоже получили массу удовольствия и с задачей в целом справились, осталось дождаться конференции и выяснить наскольхо хорошо :)

сетка, граф, пути

Слева направо: адаптивная сетка, граф путей, траектории

Отличное введение для тех кто не знает что такое International Conference on Functional Programming Contest, как он проходит и какое задание было в этом году

Немного о команде.

Team ryba ICFP 2008 crew (in alphabetical order :)
Mike Aizatsky
Alexey Gopachenko
Maxim Mossienko
Roman Shevchenko

Все мы придерживаемся мнения что лучший инструмент — проверенный, тот которым владеешь лучше всего. Так уж вышло что для нас это Java, так что вопрос о выборе языка не возникал, тем более с учетом опыта ICFP 2007.

Как и в прошлом году нас собрал Рома. Лично я подготовился очень основательно — проспал 15 часов перед самым началом %) По результатам прошлого раза были сделаны правильные выводы и мы договорились стараться работать не более 8 часов в сутки — и по возможности все одновременно. Место было выбрано тоже проверенное — офис JetBrains. Все кроме Майка использовали свои рабочие станции под WinXP, в последствии на каждой работал VMWare Server с LiveCD. Майк использовал свой Mac Book Pro и нативный сервер как только он стал доступен. Среда разработки — конечно IntelliJ IDEA.

День первый (пятница 23:00 — суббота 04:30)

Все время состязания Рома следил за сайтом соревнований, списком рассылки и соблюдением формальностей (скрипты, упаковка, проверка работоспособности и отсылка результатов). Так же он зарание скачал и проверил LiveCD и приготовил Subversion репозиторий для проекта.

Как только задание было опубликовано мы на 10 минут погрузились в чтение.
Итоги последовавшего за этим пятиминутного мозгового штурма у доски:

Майк знает точно как сделать поиск пути на карте и немедленно приступит
необходимо сделать так чтобы все как можно быстрее зашевелилось
написать и связать компоненты: входящие/исходящие сообщения, модель мира, поиск пути, рулежка, визуализация
нужен простой симулятор сервера — т.к. не известно когда его выложат организаторы

Решение Майка предполагало построение графа возможных путей и поиск кратчайшего с помощью алгоритма Дейкстры. Граф строится по центрам ячеек сетки, которая получается путем адаптивного рекурсивного деления на квадранты %) Написание и проверка (с помощью миллиметровки и ручки :) всего этого заняла Майка на час-другой.

Тем временем Макс шустро пишет протокол, начиная с наиболее нужных всем объектов Telemetry, Obstacle и т.п. Ромка — визуализацией того как ровер видит мир а я занялся загрузкой карт с прицелом на реализацию сервера. Чтобы не тратить время и не слишком отягощать проект я воспользовался кодом с www.json.org/java. Довольно быстро мы достигли цели: я загружал карту строил представление мира в базовых объектах написанных Максом а Ромка все это нам рисовал. Сервера еще нет и это наш единственный способ увидеть карту. С сожалением видим что карты-примеры весьма простые и очень похожи, да еще и с одинаковыми параметрами роверов и марсиан.

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

Как раз когда я собрался с духом чтобы симулировать физику стал доступен образцовый сервер. У Макса как раз был готов сетевой код, мы подняли LiveCD и увидели ползающих марсиан. Посмотрев на то как все работает решили что свой симулятор нам не понадобится. Очень вовремя :)

Я быстро набросал «наивный» рабочий цикл, 1 телеметрия => 1 команда (УскорятьсяПрямо). Запускаем и зачарованно наблюдаем на сервере как ровер шустро катит вперед, отскакивает от стен и камней.

Приходим к выводу что физика вполне разумная, а марсиане удивительно тупые. Тем не менее как и планировалось включаем всех видимых марсиан в граф как «временное» препятствие.

Тем временем с начала соревнования прошло 6 часов. Договорились отоспаться как следует и начать завтра в 15:00 и разошлись.

В конце дня мы умеем:
соединяться с сервером и разбирать поток сообщений
тупо ползти вперед :)
делить карту на сетку проходимых/запрещенных зон (для простоты пока описываем вокруг препятствий квадраты)
строить кратчайший путь на карте, включая любые лабиринты

День второй (суббота 16:00 — воскресенье 03:00), Lightening round

Появившись первым я приступаю собственно к заезду — слушаю телеметрию, обновляю внутреннюю карту и статус ровера. После этого включаю расчет пути на текущей карте от текущего положения ровера в цикл обработки телеметрии. Вижу что на моей (весьма мощной) машине не успевает «в реальном времени» и латентность накапливается. С учетом того что Майк сразу предупредил что обсчет он серьезно ускорит я решил не обращать на это внимание.

Наблюдаю как на клиенте постепенно проявляется карта, мимо проносятся марсиане. Обрабатываем конец раунда и счет. Какое-то время наблюдаем как на ровер один за другим бросаются марсиане и почти всегда промахиваются если он движется. Ромка продолжает работу над визуализацией.

Тут я придумал способ существенно повысить комфорт разработки под виндой — запустить сервер в цикле: while true; do server map.wrld; done — таким образом можно было просто в любой момент запускать клиента и смотреть работу не отвлекаясь на консоль сервера. В дальнейшем я добавил туда svn up и получил возможность удобно и оперативно менять карту.

Приходит Макс и мы решаем что пора учиться рулить. Тут мы обнаруживаем что совершенно забыли тригонометрию :( не буду описывать этот позора… В общем пока мы перечитывали определение элементарных тригонометрических функций объявился опоздавший Майк и спас всех с помощью псевдоскалярного произведения векторов :) Более того, оказывается он все утро просидел над оптимизацией своего кода и пришел уже с новым поиском пути.

Как только мы сложили все части вместе ровер сразу стал весьма успешно доезжать до базы. Иногда не справлялись с управлением, т.к. не учитывали переменную латентность системы телеуправления.

учли свои проблемы с обсчетом телеметрии

учли то что сервер может прислать устаревшее положение руля

К 22:00 мы получили вполне стабильные результаты на тестовых картах, и после мелкого тюнинга и проверки под LiveCD послали код на ligntning round.

Час-два мы игрались с кодом и обсуждали что и как нужно улучшить и наконец заставили себя отправиться отдыхать.

День третий (воскресенье 16:00 — понедельник 03:00)

Латентность, оптимизация

День четвертый (понедельник 13:00 — 23:00)

Да-да, из-за нашего расписания у нас получиолось 4 дня :) В этот день мы остались втроем — Майк не мог к нам присоединиться.

Во первых мы решили выбросить марсиан с карты поиска пути. Поскольку на большой скорости они всегда промагивались (что немудрено) Мы решили что будем ехать по пути и уворачиваться в последний момент. Это позволило перерасчитывать путь только в том случае если стали видны новые объекты.

Тюнинг
Макс — скорость пасфайндинга

Заключение

Да, задание сильно отличалось от предыдущих лет но мы нашли его достаточно интересным. Да, подготовка явно подкачала, но конкретно наша команда не встретила никаких препятствий. Хотя было бы удобнее получить сервер под win, пусть и без графики. Действительно не понравилось то что было мало тестовых данных и полное отсутствие официального способа оценить свои успехи…

Круто
колокейшн
график

ТуДу
стабильные интерфейсы модулей
статистика результатов тюнинга
переключение на другие стратегии

Сылки

Отчеты команд на официальном вики projects.cecs.pdx.edu/~jgmorris/icfpc08/index.cgi/wiki/TeamPages
Статья habrahabr.ru/blog/icfpc/46589.html

ICFP 2008 report: team ryba