Незнакомый район города, небольшое количество свободного времени и необходимость (или желание) пешком добраться до метро/отеля/вокзала – наверное, каждый хоть раз попадал в такую ситуацию. При этом с одной стороны хочется посмотреть какие-нибудь красивые и интересные места, однако с другой стороны ограниченное время не позволяет слишком сильно уклоняться от прямого маршрута.
Ситуация еще больше осложняется, если рядом нет никаких крупных достопримечательностей, о которых все знают и которые можно было бы включить в свой маршрут после короткого поиска в интернете. Что делать если вы застряли в каком-нибудь Купчино, про которое вы только и слышали, что там лучше не застревать? Приходится идти по навигатору, надеясь, что на пути встретится что-то интересное. Однако популярные навигаторы учитывают лишь расстояние и время в пути, но не принимают во внимание интересность маршрута. Мне попадались еще проекты, пытающиеся учитывать удобство пешего маршрута (ведущие в обход шумных магистралей), но хочется же пройти не только комфортно, но и увидеть какие-нибудь красоты.
Подумав немного, я решил взяться за эту задачу сам. Как всегда, общая идея алгоритма довольно проста, но дьявол кроется в мелочах. А в случае навигации, мелочи могут быть довольно существенны и с риском для здоровья, ведь вряд ли какой-нибудь турист обрадуется, когда навигатор в поисках достопримечательностей заведет его в дебри полузаброшенной промзоны ради маленькой мемориальной таблички (тру стори, один раз так и случилось).
Описание алгоритма и примеры работы под катом, ссылка в конце.
Основная идея
Изначальная идея у меня была такая: скачиваем Open Street Map карту, парсим ее, выдираем из нее информацию обо всех потенциально интересных для пешеходов объектах (с их списком еще предстояло определиться), рисуем вокруг них некие буферные зоны. Ищем пути каким-нибудь стандартным фреймворком, немножко хачим процесс построения навигационного графа, чтобы в этих зонах веса ребер стали ниже и тем самым организуем притягивание пешеходных маршрутов к ним.
Сказано — сделано. Для поиска пути была использована библиотечка GraphHopper, которая умеет из коробки читать OSM карты, строить маршруты для разных типов транспорта (машина, пешеход, велосипед), имеет несколько разных алгоритмов для поиска пути (простой поиск, поиск альтернативных маршрутов, всякие ускореенные-оптимизированные варианты) и умеет препроцессить навигационный граф для ускорения поиска (базовый поиск по городу работает очень быстро, за несколько миллисекунд). Для примера работы был выбран мой родной Санкт-Петербург — тут я мог сам оценить качество и интересность построенных маршрутов.
В итоге базовая версия алгоритма была слеплена на коленке за пару вечеров, а вот потом началось увлекательное путешествие по граблям и мелочам, в которых как известно и кроется дьявол и о котором я расскажу дальше.
Объекты для туристов и проблемы с OSM
В Open Street Map каждый объект — это геометрия (Node, Way или Relation) плюс некоторое количество строковых пар «ключ-значение».
Вот так выглядит Зимний Дворец в OSM:
Проблема в том, что поскольку OSM — это открытая и редактируемая участниками карта, стандартизация там хромает на обе ноги. Для обозначения одного и того же типа объектов может использоваться разный набор тегов и разная комбинация объектов, часть тегов считается «каноничной» и описана на вики, но все равно есть куча вариантов, как просто альтернативных, так и откровенно ошибочных, но тем не менее использующихся. В итоге любой код, работающий с OSM (особенно всякие навигаторы и рендереры) вынуждены все это учитывать и содержать в себе кучу кода для обработки таких вот особых случаев.
Например тег highway=unspecified означает не «какая-то дорога неизвестного типа», как думают многие мапперы, а вполне конкретный тип дороги по европейской классификации, но лепят его куда попало из-за названия. Причем у этого типа дороги предполагается наличие пешеходной обочины или тротуара, поэтому навигатор строит пешеходные маршруты по ней, в то время как по реальной такой дороге в СПб пешеходы не ходят (это проезжая часть улицы). Или вот еще пример: addr:housename тег у нас иногда используют для названия зданий, например почему-то западное крыло здания Главного штаба на Дворцовой площади названо именно через этот тег. В то время как в гайдах самого OSM сказано, что его стоит использовать только в тех странах, где вместо номеров домов используются имена (в Японии вроде так делают), а для официальных названий зданий использовать тег name и подобные.
Еще один бесящий меня момент — разметка зеленых зон. Для этой цели есть два разных тега, leisure=park и landuse=grass. На карте они выглядят примерно одинаково: просто зеленая зона, чуть отличаются цветом. В итоге лепят их вперемешку кто как хочет. Из-за чего часто разделительный газон между проезжими частями улицы становится «парком» и начинает притягивать пешеходные маршруты.
Все эти нюансы приходилось открывать для себя по мере построения и анализа маршрутов.
В качестве набора объектов, представляющих интерес для пешеходов, в итоге был выбран следующий список:
- Туристические достопримечательности отмеченные тегом tourism
- Зеленые зоны. leisure=park, garden. После некоторых размышлений были добавлены landuse=cemetry, кладбища. С одной стороны так себе достопримечательность, с другой — например на Васильевском острове в СПб единственная крупная зеленая зона — кладбище, которую местные используют вместо парка, а настоящих парков там вообще нет.
- Вода: реки, озера, пруды. Тут мешанина из тегов water, waterway и кучи дублирующихся значений. Ведь так приятно бывает пройтись по набережной в жаркий день. Во всяком случае я так думал, пока не попробовал обработать Смоленск — внезапно выяснилось, что в глубинке берега речки — это не красивая набережная как у нас в Питере, а заросший и замусоренный пустырь, от которого пешеходы предпочли бы держаться подальше. Но различить эти ситуации чисто по данным карты пока не удается.
- Исторические здания и сооружения, то что помечено тегом historic. Они как правило просто красивы
- Всякая прочая городская мелочевка, отмеченная тегом amenity. У него очень много значений, я выбрал лишь некоторые, например уличные часы (clock) — часто бывают красивыми, религиозные сооружения (place_of_worship), стрит-арт всякий (graffiti) и некоторые иные
- Пешеходные улицы и площади highway=pedestrian
По ходу исследования я понял, что кроме положительных зон, привлекающих пешеходов, надо добавить еще и негативные, отталкивающие их. В этот список пока вошли:
- Стройки landuse=construction. Пешеходам не очень приятно идти под строительными лесами, в летящей со стройплощадки пыли
- Промзоны и гаражи landuse=industrial, garages. Тут как раз случился тот нюанс с заведением пешехода (а мы в Институте дизайна и урбанистики ИТМО это тестировали на студентах, которые ходили по проложенным маршрутам и потом писали отзывы в рамках исследования пешеходного удобства Петроградского района) в дебри промзоны Ленполиграфмаша. Оказалось что там не весь квартал помечен этим тегом (как делается обычно для разметки крупных промзон), а каждое здание по отдельности.
- В идеале еще хочется уводить пешеходов от широких городских магистралей, где пыльно, шумно, много машин и обычно не на что особо смотреть. Но пока не получилось однозначно их детектировать. В OSM есть по сути только число автомобильных полос, но этого критерия недостаточно (многие важные туристические улицы, например Невский проспект, тоже многополосные)
Тот самый Ленполиграфмаш, содержащий где-то в своих дебрях памятник печатному станку, и куда мой алгоритм потащил бедную студентку
Важность достопримечательностей
Очевидно что достопримечательности бывают разные. Есть крупные, всемирно известные объекты — как Эйфелева башня или вот Исаакиевский собор в Санкт-Петербурге, которые притягивают огромное количество туристов, и ради посещения которых люди могут сделать приличный крюк. И есть какие-то небольшие, местечковые украшения — какой-нибудь стрит-арт, небольшая скульптура во дворе, которые люди готовы осмотреть только по пути и не хотят тащиться к ним издалека. Для корректного построения интересных и удобных маршрутов нужно было научиться как-то разделять разные категории достопримечательностей, при этом все что у нас есть в OSM — это некая геометрия и набор тегов. Пришлось придумать набор эмпирических правил для назначения «важности» достопримечательности, в дальнейшем определяющей изменения весов в графе.
Изначально важность равна нулю и увеличивается при выполнении следующих условий:
- +3 при наличии тега historic — он есть только у важных исторических зданий, да и то не у всех
- +3 за наличие тегов wikipedia или wikidata. Свои страницы на вики есть обычно только у важных объектов
- +1 за наличие link или url — свой сайт, опять же, есть далеко не у всех, но часто этот тег ведет на страницу какого-нибудь каталога и есть у мелких объектов
- +1 за каждый тег name. Имя может задаваться кучей способов, могут быть всякие old_name для исторических названий или имена переведенные на другие языки. Опять же, наличие многих имен свидетельствует о достаточной важности объекта (раз кто-то запарился их все проставить)
- building:architecture — архитектурный стиль, обычно ставится на всякие красивые памятники архитектуры
Этот список определен опытным путем и худо-бедно позволяет отделить Зимний дворец от безымянного граффити на окраине. В итоге важность равная 0 означает какой-то локальный мелкий безымянный объект (клочок зелени, граффити), около 3-4 — это уже что-то интересное (церковь, сквер где можно посидеть и отдохнуть), ближе к 10 начинаются достопримечательности городского уровня, тот же Зимний дворец.
Список не идеален и сильно пологается на данные OSM, которые зачастую неполны. Например, Нарвские ворота изначально имели всего одну единицу важности, так как кроме имени для них ничего не было проставлено. Пришлось сходить самому в OSM и добавить им имена, стиль, годы постройки, высоту (для корректного определения видимости, о чем дальше) и т.п. В общем-то в этом еще и общественная польза есть — для повышения качества маршрутов я время от времени иду в OSM и проставляю там отсутствующие теги, которыми затем могут пользоваться другие навигаторы или программы.
Области влияния
Достопримечательности бывают разного размера. Какую-нибудь небольшую скульптуру надо рассматривать с расстояния не более 5-7 метров. Медный всадник неплохо виден и с 20-30. Исаакиевский собор — одно из самых высоких сооружений в центре города — прилично виден с 200-300 (под этим я понимаю что туристу необязательно подходить вплотную, а вполне комфортно насладиться видом с такого расстояния, так-то его видно и за километр с другого берега Невы, но уже без деталей). Как же определить, на каком расстоянии достопримечательность должна влиять на маршруты пешеходов?
Медный Всадник и купол Исаакиевского собора вдалеке
Во-первых, я эмпирически построил радиусы видимости. Они зависят от всей доступной информации о достопримечательности и превращают ее в один из четырех радиусов: small 30 метров, medium 100, large 250 и huge 350 метров.
Немного особняком стоит видимость рек и парков. Для них я поставил 30 метров, т.е. примерно соответствует ширине набережной или улицы вокруг парка. Так как смотреть на парк издалека довольно бессмысленно, надо идти рядом с ним.
Тип видимости определяется по правилам:
- Точечные (т.е. заданые OSM-типом Point) объекты это Small видимость, это обычно мелкие монументы и стрит-арт
- Но точечные и с тегом historic это Medium, т.к. это часто крупные монументы на высоких постаментах, типа того же Медного всадника
- Области менее 20*20 метров (way или relation) это Medium
- Больше — Large
- Если у объекта есть тег height (высота в метрах) или building:levels (этажность), то при высоте более 50 метров он считается Huge — это как раз сделано специально для Исаакия и прочих больших соборов и зданий, видимых издалека
Но возникла проблема: в условиях плотной застройки исторического центра СПб наивный подход с радиусами не работал, так как реальная область видимости какого-нибудь стоящего в глубине двора храма была намного меньше, по сути он виден только с участка улицы строго напротив него. Пришлось заняться построением честных (ну почти) полигонов видимости.
Церковь Святой Екатерины стоит в глубине двора, окруженная домами со всех сторон:
Сперва надо было определиться с препятствиями. Ну тут все просто, я взял и прочитал из OSM данных все полигоны с тегом building. Это будут полигоны, блокирующие нашу видимость. Затем написал простой наивный алгоритм построения полигона видимости точки с помощью трассировки лучей. Высокая точность мне там ни к чему, хватило десятка лучей на точку. Поначалу я не мудрствуя брал центроид геометрии достопримечательности, но это давало не лучшие результаты для протяженных (длинных и узких) зданий. Поэтому в дальнейшем для больших достопримечательностей я стал брать три точки — центроид и две наиболее удаленные от него и друг от друга точки на внешней границе. Почему я не стал строить видимость честно? Потому что если алгоритм построения области видимости точки тривиален (пускаем из точки лучи во все стороны, смотрим где они пересекли ближайшие препятствия, соединяем эти точки), то вот построить честную видимость ребра (и в итоге — полигона) уже гораздо сложнее (первое приходящее в голову решение — строить видимость двух концов ребра и объединять — очевидно неправильное).
В итоге получилась неплохая аппроксимация. Строит она неидеально, но для нужд пешеходной навигации такой точности нам достаточно. Единственная проблема — она не учитывает высотность зданий, т.е. любая мелкая будка нам перегородит обзор на пятиэтажную колокольню. Но тут уж ничего не поделаешь — OSM данные далеко не везде содержат этажность, да и строить объемы видимости в 3д гораздо сложнее. Хотя возможно я еще к этому вернусь.
Построенные полигоны видимости для этой и соседней церквей
Красота маршрута и как ее повысить
Итак, мы научились считать важность и видимость достопримечательностей и вроде бы стали строить неплохие маршруты. Во всяком случае это было так, пока я тестировал на центральных районах Санкт-Петербурга, имеющих очень высокую плотность красивостей на квадратный километр.
Однако стоило отойти чуть в сторону от центра, как внезапно алгоритм стал признавать свое бессилие. И построенный им маршрут стал совпадать с кратчайшим. Так как достопримечательностей в этих районах — кот наплакал, расположены они далеко друг от друга, поэтому при поиске пути по комбинированной метрике «красота + расстояние» вклад первого слагаемого оказывался околонулевым, в итоге алгоритм строил просто кратчайшие маршруты.
Конечно всегда можно было сказать «это не мы такие, это города у нас такие скучные», но это было бы не очень правильно. Поэтому я задался вопросом, как оценить построенный маршрут, и как можно его улучшить. Самое простое решение, сразу приходящее в голову — давайте удлиним маршрут, принудительно вставив в него крюк до какой-нибудь достопримечательности, оставшейся в стороне.
Теперь в случаях если а) общая сумма важности всех достопримечательностей маршрута на километр меньше некоей величины или б) пользователь сам выбрал построение максимально интересного маршрута мой алгоритм пытается его улучшить. Для этого строится изначальный маршрут, берется буфер вокруг него (его толщина определяется длиной, чем длиннее маршрут — тем более длинный крюк разрешается сделать), внутри этого буфера ищется несколько новых (еще не вошедших в маршрут) достопримечательностей со score>2 (мы не хотим делать крюки в километр к noname скверикам) и прокладываются новые маршруты от начальной точки к этой промежуточной цели, а от нее — к точке назначения. При этом дополнительно контролируется длина, в итоге мы должны получить маршрут не более чем в два раза длиннее кратчайшего пути между начальной и конечной точками.
Первая версия алгоритма (слева) оказалась бессильна найти что-то интересное и построила кратчайший маршрут. А вот версия с добавлением промежуточной достопримечательности (справа) включила в него ДОТ КВ-19, он находится в правом нижнем углу маршрута (на таком уровне зума его не видно, но сервис покажет его в списке и позволит найти на карте по клику на имени).
Тот самый ДОТ. Вообще в Купчино хватает подобных объектов, связанных с обороной Ленинграда, так как именно там проходили оборонительные рубежи города:
Конечно, далеко не всяких пешеход согласится делать крюк ради какой-то незначительной по его мнению достопримечательности. Именно поэтому сервис показывает длину маршрута по сравнению с кратчайшим и список достопримечательностей на нем, а уж пользователь может сам решить, интересен ли ему такой маршрут. Плюс есть ползунок, который позволяет сократить (или наоборот увеличить) максимально допустимый крюк.
На практике пришлось столкнуться еще с некоторыми проблемами и странностями. Во-первых при наивной реализации буфера вокруг маршрута он «вылезал» за начало и конец. И часто получались ситуации когда маршрут шел мимо конечной точки еще на пару сотен метров. Или наоборот, шел в противоположную сторону от конца со старта, и только затем возвращался к нужному направлению. Хоть такие маршруты и позволяли осмотреть больше достопримечательностей, пешеходы очень не любят когда их уводят сильно в сторону от цели. Пришлось сперва «выколоть» на навигационном графе область вокруг конечной точки (сделать ребра непроходимыми при поиске пути к промежуточной), а затем и вовсе строить буфер не вокруг всей линии маршрута, а лишь начиная с определенного расстояния от старта и заканчивая на определенном расстоянии до конца.
Второй проблемой были маршруты с возвратом по той же улице. Не знаю как вы, а я терпеть не могу возвращаться тем же маршрутом, которым я шел вперед. Всегда предпочитаю идти другой дорогой. И поэтому от своего алгоритма я пытаюсь добиться того же поведения. Правда вот с этим пока проблемы. В качестве первой попытки я сделал так, что все ребра (кроме последнего), участвовавшие в пути от старта до промежуточной точки, вырезаются из графа при поиске пути от промежуточной до конца. Это позволяет избежать возврата ровно тем же путем, но не защищает от почти такого же пути — например возврата по другой стороне той же улицы. Вырезание всех ребер в окрестности же часто делает нахождение обратного пути и вовсе невозможным. В общем тут еще остается над чем подумать. Хотя в этом плане мой алгоритм уже работает лучше, чем некоторые из конкурентов, которые на эту тему просто не задумываются и легко строят тупиковые ответвления маршрута.
Примеры работы
Текущая реализация находится на sightsafari.city
Там пока почти нет геокодера (есть OSM-ный, но он довольно плохо работает), поэтому точки лучше ставить прямо на карте, правым кликом или долгим тапом. Ползунок отвечает за тип маршрута: крайнее левое положение ищет кратчайший, без учета достопримечательностей, дефолтное третье дает неплохой баланс, крайнее правое — всегда пытается улучшить маршрут и часто генерирует довольно замысловатые пути.
Вот пара примеров. Маршрут от дома где я раньше жил до метро Московская по мнению Яндекса, скучный путь через дворы и небольшие улочки:
А вот маршрут по мнению моего алгоритма. Проходит через край парка Победы, мимо исторического музея, мимо Чесменской церкви и дворца, по площади Дома Советов мимо фонтанов и крутой сталинской архитектуры.
Чесменская церковь. Я и сам обычно делал небольшой крюк чтобы пройти в этом месте, а не через скучные дворы хрущевок напрямик.
Вот еще пример: кратчайший маршрут от Смольного (где находится администрация СПб) до станции метро «Площадь Восстания» идет по Суворовскому проспекту. Но там рядом, чуть в стороне, есть красивый Таврический сад, куда мой алгоритм предложит вам заглянуть.
Заключение
Пока сервис работает только для Санкт-Петербурга, Пушкина и Смоленска (зоны с доступной навигацией отмечены красным пунктиром). Еще многое предстоит улучшить, а для этого в первую очередь нужны отзывы. Так что пробуйте, пишите отзывы на маршруты (там есть кнопочка над списком достопримечательностей), надеюсь оно кому-то будет интересно и полезно.
По запросу могу подключить новые города — Москву, пожалуй, побоюсь, сервер треснет (хотя можно не всю, а только центр, конечно), вот что-то поменьше можно. Главное чтобы для этого региона был более-менее качественно размечен OSM, ну и чтобы были какие-то достопримечательности, с чем у маленьких городов все не очень интересно (в том же Смоленске, который я добавил для одного своего тамошнего товарища, все интересное кучкуется в 2-3 местах города, и обойти их можно безо всякой умной навигации).
UPD: добавил Москву в пределах ТТК
UPD 2: Геокодер OSM, как я уже написал, работает плохо (знает мало адресов, требует структурированных данных на входе), поэтому лучше ставьте точки на карте вручную, а не вводите адрес. В дальнейшем что-то надо будет с этим придумать, но все нормальные геокодеры (например у Яндекса) стоят слишком ощутимых для хобби-проекта денег, а в бесплатной версии имеют слишком ограничивающую лицензию (например можно отображать результаты поиска только на карте самого Яндекса).
Автор: JediPhilosopher
