Некоторое время назад я опубликовал тут свою статью, посвященную проблеме благоустройства дворов: habrahabr.ru/post/257563
В статье рассматривался алгоритм, позволяющий по плану местности предсказать, где пешеходы будут сходить с дорожек и топать по газонам, разнося грязь и портя всю красоту. Алгоритм представлял собой симуляцию движения пешеходов на заданной местности с помощью доработанного A* и модифицируемого во время движения навигационного графа.
Тема неожиданно заинтересовала посетителей хабра, в комментариях многие высказали пожелание попробовать запустить алгоритм на своих данных. В итоге я сделал реализацию алгоритма в виде вебсервиса. Под катом будет описание его возможностей, пошаговая инструкция а также некоторые детали реализации. Приглашаю всех протестировать работу сервиса и алгоритма, ну и использовать ее в своих проектах по возможности.
Продемонстрирую процесс применения сервиса на примере вот этого участка Петергофского шоссе в Санкт-Петербурге:
Само это шоссе — замечательный пример того как не надо проектировать жилые районы. Вполне возможно что неудачная планировка обусловлена фактом что когда-то кроме шоссе рядом ничего и не было, а теперь там крупный жилой массив. Не знаю. Но факт таков, что вдоль него все очень плохо с наличием тротуаров, переходов и пешеходных дорожек. И даже на спутниковом снимке видны широкие народные тропы через газоны. Посмотрим, выдаст ли алгоритм что-то похожее на ситуацию в действительности.
Сразу призанюсь что фронтенд — не моя специализация, поэтому некоторые вещи я делал впервые, а интерфейс наверное оставляет желать лучшего. А сам сервис запущен на бесплатном плане Heroku и под хабраэффектом может лечь. Увы, лишних средств на оплату нормального у меня пока не предвидится.
Итак, чтобы нарисовать свою карту идем на http://antroadplanner.herokuapp.com/tasks/editor
Редактор сделан на основе Яндекс.Карт. Почему именно этот картографический сервис? Потому что все-таки у них карта России обновляется чаще и более подробна. К примеру Парк Победы, упомянутый в прошлой статье, у них содержит обновленный вид, после реконструкции, в то время как карты гугла и OSM все еще рисуют устаревший план.
Итак, притупим к рисованию карты.
Справа находится панель инструментов, которые позволяют добавлять объекты на карту: препятствия и генераторы пешеходов. С точки зрения API карт нажатие на каждую кнопку приводит к вызову
currentPoly = new ymaps.Polygon(...) // Создается полигон и ему назначаются стили рисования в зависимости от типа препятствия
currentPoly.editor.startDrawing() //Собственно вся логика редактирования здесь
Раньше с картами я не работал и поэтому мне очень понравилась легкость редактирования. Всю заботу о работе с вершинами и линиями, обработку кликов апи берет на себя. Очень удобно.
Для начала разметим основные препятствия — дома и группы деревьев. Люди не очень любят ходить между плотно стоящими стволами. Используем для этого инструменты «здания» и «растительность» с панели препятствий.
Затем разметим автомобильные дороги. Это особый вид препятствия: пешеходы не будут ходить по проезжей части вдоль, но смогут ее пересекать поперек.
Как показал опыт тестирования, наибольшее недоумение вызывает именно разница между типами местности «автомобильная дорога» и «пешеходная дорожка» так как и то, и другое чаще всего является поверхностью с асфальтовым покрытием, но вот смысл с точки зрения симуляции у них принципиально разный.
- Автомобильная дорога — это проезжая часть крупных улиц. Пешеходы не ходят по ней «вдоль», а только пересекают.
- Пешеходная дорожка — это все те места где пешеходы могут ходить в любом направлении. Это не только собственно дорожки, но и, например, внутриквартальные проезды или парковки.
Вот как выглядит карта после разметки основных препятствий:
Теперь нужно добавить дорожки и тротуары. Отдельно стоит отметить пешеходные переходы — они должны быть сделаны разрывом в препятствии «дорога» с проложенной внутри пешеходной дорожкой. Не очень удобно, да, но пока так.
После добавления дорожек настает черед добавить генераторы пешеходов — все те места, между которыми они будут передвигаться по нашей карте. В случае рассматриваемого участка это будет:
1) Входы в магазин Максидом (самое большое здание справа-сверху), автосалон и несколько мелких зданий
2) Две остановки трамвая и автобусов вдоль шоссе
3) Все дорожки, ведущие за пределы рассматриваемой зоны.
Генераторы могут быть «большие» и «обычные», отличающиеся количеством генерируемого во время симуляции траффика. Большим в данном случае отметим Максидом и парковку вокруг него.
Вот так выглядит итоговая карта. Дорожки отмечены светло-серым, генераторы — коричневым.
Остался один небольшой штрих — указать точные границы зоны симуляции. Без этого некоторые шибко умные пешеходы могут воспользоваться отсутствием размеченных окрестностей по соседству — ведь сейчас получается что наша карта как бы стоит «в чистом поле» — и обойти препятствия выйдя за пределы интересующей нас области. Для этого воспользуемся элементом «граница».
Итак, карта готова, отправляем на обработку. Опционально можно указать свой email, на который придет извещение о результатах.
Вычисления
Симуляция может занять длительное время (до получаса), поэтому результаты недоступны сразу же. Для вычислений используется распределенная сеть, построенная с помощью фреймворка JPPF. В итоге после отправки карты веб-сервер просто складывает ее в базу данных и ждет пока станет доступен сервер вычислений. Я время от времени запускаю его на своих домашних машинах, но возможности держать его включенным постоянно у меня нет.
Установив соединение с сервером вычислений, вебсервер начинает слать ему задачи, а тот раскидывает их исполнение по вычислительным нодам, а затем собирает результаты.
Вообще JPPF довольно полезная штука, я уже много лет пользуюсь ей в разных проектах требующих длительных вычислений, начинал с версии 2, а теперь там уже 5-с-чем-то. Она включает в себя управляющие сервера, вычислительные ноды, тулзы для мониторинга, с недавних пор работает уже и на андроиде (хотя я слабо представляю кто захочет считать на андроиде что-то тяжелое, долгое и жрущее батарею). Позволяет гибко настраивать требования к нодам при запуске задачи, в общем имеет все чего можно ожидать от подобного решения для распределенных вычислений. Кроме разве что стабильности — она с годами почему-то не улучшается.
В данный момент я могу позволить запустить вычислительные ноды на двух своих машинах. У меня уже спрашивали можно ли подключить свои собственные ноды чтобы помочь проекту. Вот тут я в некотором затруднении. С одной стороны технически ничего сложного в этом нет — достаточно скачать архив с офсайта, прописать в конфиге IP сервера и запустить. С другой — я пока так и не разобрался как защитить сервер от запуска «чужих» задач. Так как если открыть его адрес наружу то на него кто угодно сможет слать свои задания, фактически удаленно выполняя код на нодах. Наверное это не очень безопасно с точки зрения владельцев этих нод (да, конечно, виртуальная машина джавы, security manager, все дела, но кто поручиться что через них нельзя пролезть куда не надо?).
Итак, вычисления завершены, их результат можно увидеть либо по ссылке в письме, либо введя ID карты в форму в хедере сайта.
И что же мы видим: а видим мы примерно то же что и на спутниковом снимке. Программа показал что людям очень хочется ходить от остановок прямо в сторону Максидома, что очень не хватает тротуара идущего вдоль шоссе и люди ходят по большому газону вдоль (эту тропинку можно разглядеть и на яндекс карте, хотя надо приглядеться).
Ну вот не хотят люди поворачивать под прямыми углами! Поэтому люди от остановок транспорта стремятся идти по диагонали, напрямик к цели. Что отлично видно как на сгенерированном алгоритмом плане, так и на реальном спутниковом снимке.
Конечно, полученный результат не идеален. Отчасти это определяется неточностями размеченной нами карты (иногда даже положение одного отдельного дерева может заметно изменить картину дорожек), отчасти — загадочностью человеческой природы и не полным соответствием ей компьютерной модели. Поэтому я не предполагаю пока делать дорожки ровно там где алгоритм это предлагает. Но уже сейчас он может служить мощным средством для обнаружения проблем в планировке.
Заключение
Итак, вебсервис сделан, приглашаю всех заинтересованных протестировать и использовать. Там еще много работы как по части интерфейса, так и по части алгоритма, но я надеюсь что уже даже в таком виде он способен предостеречь проектировщиков от совершения типичных ошибок.
Потрогать рассмотренную в статье карту можно по ссылке antroadplanner.herokuapp.com/tasks/taskstatus?jobId=5720d88ca9855a0003cc72b0 (чтобы увидеть исходную карту надо нажать на кнопку «редактировать карту» внизу)
Справка (помимо примера там еще есть формат входных данных и инструкции по импорту данных из OSM) antroadplanner.herokuapp.com/application/editorhelp
Блог, в котором я пишу об обновлениях сервиса, примерах работы и всяких мыслях на тему благоустройства:
antroadplanner.wordpress.com
UPD 1: Для тех кто получает ошибку «карта не является связной»: если граница карты не нарисована вручную, то за границу принимается bounding box всей геометрии. При этом если у вас есть идущее через всю карту длинное здание — BB будет построен по его краям, при этом карта разобьется на две несвязанные области. Поэтому границу лучше рисовать всегда, оставляя в таком случае зазоры по краям.
Автор: JediPhilosopher
