ICFPC: Как вы яхту назовёте?..

[singalen]

Наконец-то я пишу, как мы (team Grobocode) играли в ICFPC.

Содержание.
Задача
Команда
Инструменты
Решение
  Рулёжка к заданной точке
  Поиск пути
  Поиск пути-2
  Заносы: считаем инерцию и трение
  Как не попасть в жертву Барзуму
Как вообще было дело
Наши ошибки
Итог

Задача

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

Задачу вы наверняка читали у _adept_-а; если нет, напою совсем кратко.
Луноход с Марса передаёт по сокету поток телеметрии, в котором есть его координаты-скорость, и координаты-скорость препятствий и марсиан, попадающих в поле зрения. Все объекты - круги, заданные на плоскости в вещественных координатах.
Мы ему передаём команды "влево-вправо-газ-тормоз". Линейное и угловое ускорения заранее неизвестны.
Задача - как можно быстрее доехать до базы, не упасть в кратер и не попасться марсианам, которые хотят принести мерс-о-ход в жертву богам Барзума.

Команда

[19:33:12] Andrey Krivtsun says: Саша, вот тебе: T 29800 -- -25.000 25.000 50.0 0.000 h 0.000 0.000 5.000 b -45.312 64.062 0.600 b -31.250 68.750 0.996 b -42.188 57.812 0.401 b -28.125 59.375 0.523 b -18.750 68.750 1.097 b -18.750 56.250 2.124 b -7.812 54.688 0.587
[19:33:46] Alexander Letov says: Это серьёзный удар! :)))
Из командного чата

Команду собрали более-менее заранее. За неделю до начала сделали тренировку, проверили матобеспечение - доступ к SVN и вики, решили три задачки с топкодера и расползлись. Как и следовало ожидать, пара часов ушла только на подключение к сети/клиентский софт/логины/IDE.

Собирались участвовать 8 человек, а к началу туров нас осталось пятеро, в алфавитном порядке:
al_dragon
gabriel_irk
kontiky
sanyok_ua
singalen

Состав всё равно был ущербным:
gabriel_irk был занят переездом через всю страну и написал нам только две компоненты,
sanyok_ua уходил на половину третьего дня,
al_dragon не владел Джавой, и только обсуждал решения, делал кодревю и подкидывал идеи с jabber.ru,
а я в ночь с первого на второй день ехал в поезде, а на половину второго дня уходил на семейный праздник.
Будем считать это каким-то оправданием... хотя похожие результаты показали и команды из 2 человек... или из полных 5... короче %)

Инструменты

Мы не можем похвастаться новыми и продвинутыми тулзами, зато выбрали привычные проверенные в промышленности решения:

• Java, Ant;
• SVN;
• IDEA или Eclipse, JUnit;
• MediaWiki;
• Skype (да, плюйте сюда. Но только скайп даёт конференции, и заодно, бесплатно - чат).

Решение

- Налево пойдёшь - тачку потеряешь.
- Направо пойдёшь - в жертвы Барзуму попадёшь.
- Прямо пойдёшь - об камень навернёшься...
Марсианский былинный дорожный указатель

Про парсер и запоминание карты рассказывать неинтересно - это банальное кодирование. По крайней мере, у нас было так.

Рулёжка к заданной точке

Это не Дийкстра, это "Пьянь-3". Сначала вихляет, потом уходит налево...

Без этого никуда. С этого всё начиналось

Андрей kontiky молодец, он поборол в поворотном модуле "эффект раскачиваний".

Из-за этого эффекта в конференции на jabber.ru появлялись названия роботов вроде "Пьянь-3".

Это когда управляющий модуль считает, что надо поворачивать вправо, и крутит баранку вправо, а поскольку у управляемой системы есть инерция, то она проскакивает нужное положение и теперь смотрит влево. Начинает крутить влево... и так далее.
И хорошо, если эти колебания затухают, а бывают же и нарастающие - от чего нас Бог миловал.

Поиск пути

(О реализациях интерфейса Brain)
- Будет ещё один отдел мозга, который будет тормозить.
- Пьяный у нас уже был, тупой тоже был... этот какой?

Тут я сваял банальный алгоритм Дийкстры на сетке, он же алгоритм волны.
Ячейку делал непроходимой, если её хоть как-то задевало препятствие.
Хотел сделать не регулярную сетку, а quad-tree на плоскости, но потом стало не до того, да и с мелкой сеткой можно было обойтись.
А у quad-tree свои проблемы.

Поиск пути-2

С сеткой в первый же день вылезла проблема: в ней робот ходил по "манхэттенскому расстоянию", по клеточкам.
Переход между клетками стоил 1 единицу расстояния. Добавил переходы по диагонали, стоимостью 1.4. Стало получше, но всё равно плохо.

Придумали спрямление пути: брать на уже полученном пути не следующую точку, а самую дальнюю, на отрезке до которой нет препятствий.
Сделал kontiky. Получилось хорошо.


Итого, вот фрагмент карты spiral, на которой "мерсоход" искал путь:

Большая версия.

Заносы: считаем инерцию и трение

Решили пойти по компромиссному пути: добавить ещё один совершенно независимый модуль, который, если будет видеть, что мы едем в препятствие, будет притормаживать.
Всё остальное время мы давим тапочку в пол; в книге какого-то автогонщика я читал (и это, в общем, очевидно), что самое быстрое прохождение трассы состоит только из разгонов и торможений.
Модуль перед, скажем, кратером, рассчитает "точку невозвращения" и начнёт тормозить незадолго перед ней. В надежде, что основной модуль таки-рулит не в кратер, а отвернёт, и можно будет снова начать ускоряться.
Весь модуль сделал sanyok_ua.

Для этого понадобился датчик, измеряющий ускорения разгона и торможения. Его сделал gabriel_irk, но без юнит тестов, и sanyok_ua потом его ещё пару часов тестировал и доделывал.
Спасибо идее al_dragon, датчик встроили прямо в парсер телеметрии: парсеру известно, ускоряем мы или тормозим, и дельта-вэ (скорости) тоже. То есть, он повис subscriber-ом на руле и спидометре, и он не мешался со своей логикой в другие компоненты.

Как не попасть в жертву Барзуму

- А можно было бы отскакивать от валуна и падать в кратер?
- Я бы сделал. Нефиг от местных ГАИ убегать.
- АИ для ГАИ? Полезно...

Придумали на сетке, по которой мы считаем путь, добавлять штрафного веса к клетке, в которой находится марсианин - чтобы Дийкстра находил путь в обход.
И даже не находится, а будет находиться, когда мы до этой клетки доедем, исходя из его и нашей скорости и направления.
И даже не одной клетке, а набору клеток, в которые он мог бы отвернуть.
Аналогично, убавили стоимость клеток, по направлению к которым мы уже и так несёмся - чтобы более вероятными стали пути, для которых не надо круто поворачивать и улетать в занос.
Придумали на второй день, а на третий наш пасфайндинг так и не заработал в сынтегрированной системе - луноход упрямо пёр в препятствия.

Где-то через два дня я понял, что это признак устаревших данных: то ли в модуле Дийкстры "застревала" старая карта, то ли в карте - старые пути.
Посмотрел - и правда, карта не переинициализируется по приходу новой телеметрии.
Вот почему последние три часа мы с отчаянием смотели, как наш луноход тычется в валуны, которые прекрасно видит...
Вот так я запорол результат всей команды.

Как вообще было дело

- Прикольно, ветерок, прохладно... что работает?
- Ничего не работает. Сквозняк работает.
- А, то есть, вы за это не платите?(третий день, понедельник, провели не в офисе, а у меня дома)

Наши ошибки

По моему мнению, у ребят наверняка будет другое.
0. Главнейшая: не сделали визуализации вычислений.
Когда по логу сложно понять, так ли работает программа (попробуй представь себе движение по таймстампу и десятку пар координат/векторов!), надо смотреть на картинку.

Именно поэтому я полдня не мог понять, почему пасфайндинг в тестах работает правильно, а робот прёт в кратер.

В этом смысле team ryba молодцы, спасибо Адепту за ссылку на видео - вот как надо.

1. Не смогли чётко следовать правилу: застрял - передай задачу товарищу.
Из-за этого не успели сделать рулилку на lightning round, а в конце я так и не поймал баг со старыми путями на карте.
// Да, в чисто функциональном языке проблемы "старого состояния" вообще бы не возникло, но там у нас возникли бы другие проблемы...

2. Не писали тестов на все неочевидные компоненты.
Из-за этого sanyok_ua потратил часа три на отладку датчика ускорений и "тормоза".

Итог

"А что же мы? И мы не хуже многих.
Мы тоже можем много выпивать..."
В. Высоцкий

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