А мы тут сделали практически лучший на хакатоне проект и заняли последнее место. Нет, команд было больше одной. Нет, нас не дисквалифицировали, и сами мы не отдавали никому победу.

В общем, вписался я с новыми коллегами в хакатон от 2ГИС. Номинально он был для внешних участников, но в рамках отдельной оценки разрешили поучаствовать и своим. Надо сказать, что внутренний трек был с вдвое меньшими призовыми, защищаться одновременно с остальными было нельзя, и о самом существовании этого трека не упомянули ни в каких публикациях и отчётах об этом хакатоне. Ну да ладно.

Мы решали довольно прикольную задачу, и за двое суток у нас получилась офигенная, на мой взгляд, реализация. Красивая, вполне функциональная, с ворохом фишечек, и полноценно отражающая концепцию. Я бы даже сказал, что это один из наиболее доработанных хакатонных продуктов за всю мою соревновательную карьеру.

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

В итоге мы сделали редактор, который позволяет выбрать область на карте и разметить там зоны: проходимые, непроходимые, газон. Отметить взвешенные точки интереса. Например, вход в здание это менее популярная точка, чем остановка, потому что одной остановкой пользуются жильцы сразу нескольких зданий. В дополнение воспользовались привилегией сотрудников и автоматически грузим первичный набор точек и зон из API 2ГИС. Точки сразу бьются по категориям, чтобы выставить им вес, вокруг зданий рисуются границы, но результат можно редактировать и тюнить.

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

В общем, повозиться пришлось изрядно. В конце второго дня мы всё ещё сидели пилили маршруты, уж было думали, что не успеем, но в итоге отправили решение почти ровно в 23:59, и ушли довольные спать. Получилось и правда круто: полноценный редактор с кучей функций и нормальным UI, работоспособная (хоть и не идеальная) система построения, «one more thing» с предзагрузкой из 2ГИС...

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