В прошлой статье я описал алгоритм, позволяющий строить более интересные (в противовес более коротким, как делают всякие яндексы-гуглы) пешеходные маршруты между двумя точками. Алгоритм загружал достопримечательности, парки и прочие приятные и интересные для пешеходов объекты из Open Street Map и прокладывал маршрут через них. В итоге путь мог оказаться на 10-20% длиннее, но гораздо живописнее и интереснее.
Фото города — Alex 'Florstein' Fedorov
В комментариях многие написали, что кроме маршрутов между двумя точками им интересно было бы строить круговые маршруты, которые бы начинались и заканчивались в одной и той же точке и укладывались в заданный лимит времени. Например, если у вас есть два часа до поезда или до встречи с друзьями, съездить куда-то далеко вы за это время не успеете, а вот погулять и посмотреть красоты поблизости вполне можно.
После некоторого количества экспериментов я сочинил генетический алгоритм, который строит достаточно неплохие (для меня) маршруты в такой ситуации. Под катом описание принципа работы и несколько примеров.
Итак, пользователи хотят иметь возможность совершить небольшой тур по окрестностям и вернуться обратно в точку начала за указанное время (обычно 1-2 часа). Как оказалось, такой тип прогулок довольно востребован. Например, в статье "Movement patterns of tourists within a destination" описано исследование треков 250 туристов в Гонконге, при этом 40% туристов начинали знакомство с городом с кругового маршрута в радиусе 500 метров от отеля. Однако зачастую люди просто бродят вокруг, не зная что интересного можно увидеть поблизости.
Задача осложняется, если дело происходит не в туристическом центре (где куда ни пойди — везде найдешь что-то интересное), а где-нибудь на окраине, где достопримечательности надо искать.
Радиус и отбор достопримечательностей
Для построения маршрута нам сперва надо отобрать достопримечательности, которые мы хотим посетить. А для этого нужно определить область их поиска вокруг стартовой точки. Если пользователем определено максимальное время прогулки в M минут, то максимально удаленной точкой, до которой можно дойти и успеть вернуться, будет точка на расстоянии (V * M / 2), где V – скорость пешехода.
Средней предпочитаемой скоростью пешехода можно считать 1.4 метра в секунду. Однако при осмотре достопримечательностей человек идет несколько медленнее, так как тратит дополнительное время на осмотр. Я построил немного маршрутов по городу и погулял по ним, сравнивая хронометраж прогулки с тем, что предсказывало приложение. В результате оказалось, что средняя прогулочная скорость моя оказалась примерно на 20% меньше, т.е. примерно 1.1 м/с. Так как я периодически останавливался чтобы пофотографировать, свериться с картой, иногда лишний раз переходил дорогу чтобы выбрать лучший ракурс или купить мороженого.
Эксперименты я проводил в незнакомых районах города, с помощью моего алгоритма там можно найти всякие интересные штуки про которые раньше и не слышал. Вот, например, памятник первой листовке.
Выбор достопримечательности на максимальном расстоянии приведет к построению вырожденного кругового маршрута. Поскольку у пешехода уже не будет времени сходить с кратчайшего пути по прямой, он сможет посетить только эту достопримечательность, пройдя к ней и вернувшись обратно по той же улице, как показано красной стрелкой.
Тут мы можем или сходить в парк подальше, или посетить сразу несколько точек поближе
Но такая ситуация противоречит идее интересных круговых маршрутов, ведь по сути мы увидели только одну улицу и один объект, а хочется посмотреть побольше всего. Поэтому по результатам экспериментов был выбран радиус равный одной трети максимального расстояния. При таком радиусе поиска у пешехода хватит времени дойти до самой удаленной достопримечательности по радиусу, затем при необходимости пройти такое же расстояние по хорде в поисках других интересных объектов, и затем вовремя вернуться.
Проблемы лобового подхода
Окей, список достопримечательностей-кандидатов мы собрали. Осталось теперь выбрать, какие из них и в каком порядке мы хотим осмотреть. Посетить их все мы, скорее всего, не успеем, так что надо выбрать самое интересное их подмножество.
Сперва я попробовал сформулировать и построить обычный последовательный алгоритм. Однако быстро наткнулся на ряд проблем.
Если рассмотреть ситуацию с рисунка выше, то непонятно откуда начинать строить маршрут. Если парк — самая важная, но самая удаленная достопримечательность, то начав с нее мы получим вырожденный вариант, о котором писали раньше.
Следующее очевидное решение — как-то кластеризовать достопримечательности и пытаться искать путь до самого выгодного кластера, а затем ходить внутри него. Но тут опять все непонятно: с какого кластера начинать, в какую сторону идти. Всегда можно попасть в ловушку типа что мы пошли не в ту сторону и уперлись в "пустыню" — область без достопримечательностей, которую нам уже не хватит времени перейти и вернуться в стартовую точку.
В какой-то момент мне стало понятно, что я практически выполняю работу генетического алгоритма: рисую на карте разные маршруты и пытаюсь определить, насколько они понравились бы лично мне.
Генетический алгоритм
Получив пронумерованный список достопримечательностей, алгоритм должен выбрать упорядоченное подмножество, которое и составит основу кругового маршрута. Итоговый маршрут в таком случае является одним из размещений множества ключевых достопримечательностей (мы не хотим повторов и не обязаны использовать все возможные объекты).
Зная формулу для количества размещений из n по k можно прикинуть возможное количество вариантов. Если рассматривать часовой маршрут вокруг Дворцовой площади в Санкт-Петербурге, в радиусе 1320 метров (который определен, как описано выше) после фильтрации и кластеризации окажется 54 кандидата в ключевые достопримечательности.
Адская каша из кучи достопримечательностей в центре, дебажный вывод областей видимости, рассчитанных по алгоритму из прошлой статьи
Принцип отбора и сортировки описан в прошлой статье, плюс мы дополнительно удаляем объекты с интересностью меньше 3 (ради таких незначительных объектов человек вряд ли будет готов далеко идти, разве что рядом вообще больше ничего нет). Таким образом возможное число маршрутов можно вычислить по формуле числа размещений из 54 по 5, оно равно 379501200. Для 2 часового маршрута, в радиус которого попадает уже 151 достопримечательность, это количество будет равняться 73423236600. Ну так, многовато для простого перебора.
Хромосомы и генетические операторы
Хромосомы в данном случае представляют собой строку, в которой каждый элемент – номер соответствующей ключевой достопримечательности. Для подобных задач, в которых хромосомы являются перестановками или размещениями, существуют специальные оптимизированные варианты генетических операторов. Такие операторы сохраняют свойство хромосомы оставаться перестановкой или размещением начального множества элементов.
- Для скрещивания используется Partially-Mapped Crossover (PMX).
- Для мутации используется обмен местами двух случайных генов (Swap Mutator).
Описание работы этих операторов с примерами можно найти, например, в работе "Genetic algorithms for the travelling salesman problem: A review of representations and operators".
Фитнес-функция
Фитнес-функция должна учитывать следующие факторы для построения интересного кругового маршрута:
- Суммарная интересность всех посещенных ключевых достопримечательностей должна быть как можно больше.
- Суммарное время в пути должно быть как можно ближе к заданному пользователем, маршрут не должен быть ни сильно длиннее, ни сильно короче. Короткие маршруты допустимы лишь тогда, когда поблизости нет достаточного количества достопримечательностей.
- Маршрут не должен пересекать сам себя. За каждое самопересечение мы добавляем штрафные проценты к итоговому значению функции.
- Форма маршрута должна быть приближена к кругу, он должен захватывать как можно большую область города и избегать вырожденных случаев. Для этого мы в функцию закладываем отношение площади фигуры, описанной маршрутом, к площади круга, в котором искались достопримечательности.
Вот пример хорошего кругового маршрута. Он проходит через два парка и нигде не посещает одно и то же место дважды
А вот пример явно неудачного маршрута. Он содержит тупиковые ответвления, где пешеходу придется возвращаться уже по осмотренной дорожке назад, и самопересечения. В местах пересечений обычно напрасно тратится время на повторный осмотр уже увиденных участков города.
Плохой маршрут собственно был получен генетикой, в которой у фитнес-фунции были отключены пункты 3 и 4 (штрафы за самопересечения и за маленькую площадь)
Нюансы
Во время тестирования всплыли еще некоторые нюансы.
Превышение лимита времени
Во время работы генетики для ускорения длину маршрута мы считаем по прямым линиям между точками. А после того, как мы с помощью генетического алгоритма выбрали объекты для связи, путь между ними мы ищем алгоритмом из прошлой статьи. При этом путь может стать длиннее и вылезти за лимит времени. Ведь в городе часто кратчайший путь по улице может быть в разы длиннее прямой линии.
В среднем разница обычно около 10-20% и мы ее закладываем в фитнес-функцию (т.е. генетика ищет маршрут с запасом по времени, который затем съедается при прокладке детального маршрута). Иногда ее не хватает — приходится пересчитывать маршрут заново. Есть у нас в городах такие вот места, где разница между маршрутами "как птица" и "как пешеход" составляет километры.
Между точками 50 метров по прямой, но полтора километра по тротуарам и переходам в обход.
Впрочем все равно алгоритм иногда превышает заданное пользователем время, но тут уж каждый сам может решить — есть ли у него лишних 10-15 минут или прогулку придется завершить пораньше.
Венеция
Когда алгоритм был готов, я для интереса решил добавить топовые туристические города Европы. Получилось интересно: города везде разные, особенности картографирования в OSM тоже, в итоге постоянно приходилось что-то допиливать.
Конкретно поиск круговых маршрутов сломался на Венеции. Так как это уникальный пример города с несвязанными областями — острова разделены Гранд-каналом, через который нет мостов, переправа возможно только на паромах.
В итоге алгоритм отбирал часть объектов с одной стороны от пролива, часть — с другой, затем не мог найти между ними сухопутного пути и падал. Пришлось добавить проверку на достижимость всех достопримечательностей из стартовой точки.
Иногда все-таки приходится возвращаться той же дорогой
В примере с парком выше есть кусочек маршрута, где придется возвращаться назад той же дорогой — это маленький полуостров, на котором стоит памятник с самолетом. На этот полуостров ведет единственная дорожка, по ней же придется и вернуться. Так что полностью запрещать такие возвраты нельзя. Алгоритм для этого повышает веса всех ребер, которые уже были пройдены, снижая вероятность возврата по ним, но все-таки делает это возможным.
Хотя иногда это все равно плохо работает. Например жалуются на главный кафедральный собор в Калининграде. Он находится на острове посередине реки, через который идет мост. С этого моста один спуск и одна дорожка к собору, видимо алгоритм слишком уж повышает веса этого единственного пути, что делает невыгодным возврат по нему. В итоге в собор он почти никогда маршрут не заводит, хоть это и одна из ключевых достопримечательностей города. Тут еще требуется какая-то доработка.
Результаты
Генетический алгоритм — штука немного непредсказуемая, поэтому иногда он глючит и рисует странные зигзаги. Но в целом результатом я доволен. Что особенно приятно, алгоритм работает не только в туристическом центре (где и так не проблема интересно провести время), но и на окраинах города. Где, зачастую, без подсказок найти что-то интересное очень сложно.
Даже в спальниках юго-запада Санкт-Петербурга можно найти достаточно памятников на двухчасовую прогулку
Попробовать алгоритм самостоятельно в одном из 77 поддерживаемых городов можно на нашем сайте Sight Safari или в нашем Android-приложении (да-да, мы наконец-то его доделали).
Особенно интересно, как будет алгоритм работать в городах со сложным рельефом и перепадами высот. Мы добавили поддержку анализа рельефа к библиотеке поиска путей Graphopper, но проверить как следует не можем — Питер слишком ровный город.
В общем пробуйте, пишите отзывы, правильно ли строятся маршруты. Тут же можно оставить заявку на добавление новых городов.
Комментарии (65)
TheGodfather
06.09.2019 14:18Окей, список достопримечательностей-кандидатов мы собрали.
Я, видимо, что-то пропустил — где собрали-то? Откуда достопримечательности берете? Если ли какое-то ранжирование (условно, мемориальная табличка Шухова и Красная Площадь должны иметь разные приоритеты)? Что делать с людьми, которые уже были на самых «приоритетных» точках, но хотят по задворкам погулять?JediPhilosopher Автор
06.09.2019 14:20В предыдущей статье описан алгоритм сбора достопримечательностей из Open Street Map и эвристический алгоритм ранжирования. С тех пор он, конечно, немного доработался, но идея осталась той же.
Если хочется погулять по задворкам, можно поставить на задворки промежуточную точку чтобы идти через нее (пока есть только в веб-версии, в андроид-приложение еще не включили), либо включить фильтр по типам достопримечательностей.
Vsevo10d
06.09.2019 16:34Может показаться, что я придираюсь, но раз уж взялись за эту тему — нужно хотя бы первично и банально разложить достопримечательности по классам. Иначе от вашего приложения у атеистов будет пригорать с бесконечных рекомендаций хорошо кластеризованных в православных монастырях музеев и храмов. Или например не каждому по душе будет тягучий монументализм Площади Независимости в Минске, а вот по костелам и кирхам он бы пробежался. Для кого-то и 76-мм ПТшка на спущенных шинах в районном сквере — повод сфотографироваться, а некоторым интересны старые кладбища — довольно обособленные и задвинутые между дорогами и промзонами участки земли явно не рекреационного назначения. Я из прошлой статьи понял, что достопримечательности просто ранжируются по баллам, не учитывая «вкус» пользователя. Может ли сам пользователь повлиять на разбалловку, добавляя некоторым тегам или типам пользовательский приоритет?
JediPhilosopher Автор
06.09.2019 17:24Нет, пользовательского рейтинга никакого нет. Есть лишь категории и возможность фильтровать по ним — это в приложении уже сделано. Так что не хотите храмы — отключайте религиозные объекты, не хотите пушки — отключайте объекты военные.
В пользовательский рейтинг я не верю, во всяком случае на нынешнем этапе развития. Даже у Maps.me, которыми пользуется дофига народу, очень редко можно увидеть рейтинги у объектов. Хотя коммьюнити там на порядки больше нашего.
Tiamon
06.09.2019 16:59Интересное приложение, для велопрогулок по городу будет очень хорошо, постоянные маршруты надоедают.
Из минусов:
На карте нельзя поставить промежуточные точки.
Также из минусов, нельзя, скажем выделить зоны, которые не хочется посещать, было бы удобно выделять их на карте.
Нельзя изменить маршрут, типа как в навигаторе.
На сайте круговой маршрут ограничен 2 часами.
Это на сайте, попробую приложение для мобильника )JediPhilosopher Автор
06.09.2019 17:27Промежуточные точки на сайте есть — когда уже выбраны начало и конец кликните правой кнопкой — там в контекстном меню будет пункт с промежуточной.
Про зоны которые не хочется посещать — подумаем. Но если уж делать кастомизацию под себя — придется заводить еще и всякие там аккаунты, куда это будет сохраняться, истории маршрутов и т.п. Это надо, конечно, но работы много выходит.
Ограничение в 2 часа — потому что если сильно увеличивать радиус поиска то оно начинает медленно работать. Я на себя ориентировался, мне двух часов погулять более чем достаточно. Но видимо придется что-то придумывать, есть люди которые и 5-6 часов просят.
tvr
06.09.2019 17:50+1Спасибо, на компе потыкал — весьма интересно (для РнД, по крайней мере).
В выходной потестю, если не забуду, на натуре.
Alf1n
06.09.2019 20:48При построении кругового маршрута на юге Москвы, в районе Олимпийского парка выдает ошибку
JediPhilosopher Автор
06.09.2019 20:48Если вы это из веба делаете то пришлите ссылку пожалуйста из адресной строки браузера.
Судя по логу сервера, там не хватает достопримечательностей поблизости. Попробуйте лимит времени побольше поставить.
TheGodfather
06.09.2019 21:10Кстати, вот в первой версии статьи вы писали «Вот Исакиевский собор ого-го, а к графити на стене никто не пойдет». Так вот, можно как-нибудь включить режим «не хочу на Исакиевский собор, проведите меня по третье- и второсортным достопримечательностям»? Или вообще «стритарт-тур»?
JediPhilosopher Автор
06.09.2019 21:34Сейчас там есть возможность отключать разные категории достопримечательностей. Соборы можно отключить. Стритарт там в категории "произведения искусства". Правда его в OSM не так уж и много.
latonita
07.09.2019 08:35+1Попробовал на андроид. Отключаю парки, театры и церкви. Все равно строит маршрут, состоящий на 70% из парков, театров и церквей (
JediPhilosopher Автор
07.09.2019 10:59Скриншот скиньте пожалуйста и координаты точек. Посмотрю в чем дело
tvr
07.09.2019 14:12Все равно строит маршрут, состоящий на 70% из парков, театров и церквей (
А может в окрестностях больше ничего и нет?
CAJAX
06.09.2019 21:18+1Спасибо, что добавили Париж.
Но вот маршруты весьма спорные.
https://sightsafari.city/?type=straight&from=48.859945,2.333138&to=48.834829,2.331446&ratio=1.5&locale=en&intermediatePoint=
Я примерно понимаю, почему алгоритм выбрал такой путь, но абсолютно не согласен. Как минимум путь должен пролегать через люксембургский сад, а не вдоль его забора по шумной улице. А путь к нему либо более тихими улицами через Pont des arts, и театр Одеон либо хотя бы стандартным для туристов маршрутом через Нотр Дам.CAJAX
06.09.2019 21:35+1Вот ещё пример странного огибания достопримечательности
https://sightsafari.city/?type=straight&from=48.847100,2.352340&to=48.844398,2.365009&ratio=1.5&locale=en&intermediatePoint=
Через арены Лютеции можно пройти насквозь.JediPhilosopher Автор
06.09.2019 21:38+1Спасибо, именно такой фидбек нам и нужен. Погляжу что там и попробую настроить.
Люксембургский сад видимо не отмечен в OSM как собственно сад, поэтому для него действуют другие правила (достаточно пройти рядом и не обязательно заходить внутрь).
Постоянно всплывают такие вот нюансы тегирования OSM, которых везде навалом и под которые надо пилить кастомные правила.
xFFFF
06.09.2019 21:47В некоторых случаях выбор не очень. Например, выбирает не примечательное внешне, но по какой-то причине популярное место. ) в целом штука интересная)
JediPhilosopher Автор
06.09.2019 22:11Алгоритм там эвристический, и его еще требуется отлаживать. Плюс еще все зависит от детальности OSM данных. Приведите примеры таких мест, которые вам кажутся неправильно помеченными, попробую что-то с этим сделать.
kost
06.09.2019 22:26Я работал в стартапе, делали то же самое — планирование туристических маршрутов. Тоже использовали генетический алгоритм, боролись с зигзагами.
Стартап успешно сдох.JediPhilosopher Автор
06.09.2019 22:30Идея витает в воздухе, мне уже несколько человек писали про что-то такое. У всех сдохло, хех.
А можно поподробнее? Почему не выстрелило? Может какие-то идеи есть, которыми не жалко поделиться? Как называлось, можно что-то прочитать про него?
qant
07.09.2019 09:42Мое мнение. те кто хочет посмотреть просто пользуется гугл картами. те кому нужно интересно берет гида тк кроме внешнего осмотра хочется информации. Ну и конечно стартапы дохнут тк не выстреливает монетизация. Что точно восстребовано это рыночки и колоритные бары, гастро туры достаточно популярны. Но не уверен что на картах есть полезная информация для составления маршрута
kost
07.09.2019 00:36Работало несколько лет, продавали white label приложения разным крупным конторам (типа сетей гостиниц, центрам туризма, авиакомпаниям). Ожидалось, что контору купят, но сделка не случилась. Меня уже там не было пару лет к этому моменту.
www.geekwire.com/2019/seattle-travel-planning-startup-utrip-will-shut-critical-deal-falls
www.geekwire.com/2019/happened-utrip-abrupt-end-seattle-travel-startup-blindsides-investors-clientsJediPhilosopher Автор
07.09.2019 01:14+1Интересная штука. Не совсем то что у нас — не навигация, а планирование поездки в целом.
А в чем был интерес у гостиниц и авиакомпаний именно в whitelabel приложении? Я могу еще представить модель монетизации с продажей их рекламы и заведений в трипах пользовательских.
Вообще с монетизацией пока не очень ясно что делать, но у нас есть преимущество — пока мы делаем какую-то науку на базе этого (ну там статейки всякие или прикручивание этой штуки к другим исследованиям пешеходной среды, которые ведет наш институт) деньги нам государство дает.kost
07.09.2019 05:16В whitelabel гостиница или attraction включались в маршрут (например Space Needle или Empire State Building).
Большим клиентам — просто как сервис для клиентов, без прямолинейной монетизации.
vortupin
07.09.2019 07:40Гуляем по городу с умом — 2: ходим по городу кругами
Гмм, у автора данного поста несколько странное определение «ума»… Впрочем, после прочтения данного опуса это становится понятным — Егор всю свою молодую жизнь явно заблуждался касательно значения этого слова (напрашивается бородатый и неприличный анекдот про «оргазм» :)
P.S. Могу дать лишь один совет: не стоит увеличивать энтропию, и загромождать Play store глючными, бесполезными и неработающими приложениями — там и так говна достаточно!
Javian
07.09.2019 09:03Достоверность картографических данных под вопросом. «Потыкал в карту» — маршрут проложен через заборы, пересекает дороги без пешеходных переходов.
Например Евпатория. поставил Настройку на максимум «Интереснее». Курортный город, много чего интересного можно увидеть в архитектуре. Тыкаю от вокзала маршрут на набережную. Перед самым краеведческим музеем маршрут сворачивает, музейный квартал обходит и возвращается обратно. Самое интересное пропустил. Составил другие маршруты в точки рядом — старательно избегает музея, избегает достопримечательности на набережной.
Что-то с данными карты не так.JediPhilosopher Автор
07.09.2019 11:01Погляжу. Хорошо бы получить скрин карты с маршрутом и ошибками на нем.
Часть ошибок вызвана неполнотой osm карты — тогда можно сделать доброе дело и ее дорисовать, что поможет всему картографическом у сообществу. Иногда дело в алгоритме, как выше с Парижем оказалось, это я могу сам поправитьJavian
09.09.2019 12:51Еще раз сгенерировал. Начало от здания жд вокзала 45.199789, 33.355085, конец набережная у памятника архитектуры «Курортная поликлиника» 45.184219, 33.366606.
Настройка «Интереснее». Расстояние: 5459.54 метров (229% от кратчайшего пути).
Довел до мечети, но не дошел до главной достопримечательности — Собора. Рядом масса точек интереса — памятники, архитектура. Игнор.
Затем вернулся обратно по тому же неинтересному пути вместо того, чтобы пройти по набережной. Обошел мимо краеведческого музея (45.187028, 33.369963) к скверу с фонтаном, где смотреть не на что. Хотя там есть очень примечательное здание, памятник архитектуры 45.186234, 33.367276, но до него 50 метров маршрут не дошел.
Исходя из увиденного, рекомендую скачать для каждого города соответствующий официальный документ со списком объектов культурного наследия.
Я, например, при прогулке по Евпатории ориентировался на метки Яндекса и такой документ:
СПИСОК ОБЪЕКТОВ КУЛЬТУРНОГО НАСЛЕДИЯ (ПАМЯТНИКИ АРХИТЕКТУРЫ, ИСТОРИИ, МОНУМЕНТАЛЬНОГО ИСКУССТВА И ВЫЯВЛЕННЫЕ ОБЪЕКТЫ КУЛЬТУРНОГО НАСЛЕДИЯ), РАСПОЛОЖЕННЫХ НА ТЕРРИТОРИИ РЕСПУБЛИКИ КРЫМ (по состоянию на 01.11.2015)
К слову в википедии у достопримечательностей есть координаты — их на местности отображает Google Earth при включении слоя wikipedia. Тоже удобно при изучении местности.JediPhilosopher Автор
09.09.2019 13:32Проблема в том, что как правило все эти данные нельзя автоматически скачать и пропарсить. Все эти списки ОКН как правило лежат где-то в дебрях государственных сайтов в виде нераспознанных пдф файлов. Только у некоторых городов и регионов есть свои открытые ГИС, откуда можно их скачать в векторном виде, причем у каждого региона такая система своя собственная, со своими форматами и костылями.
В итоге требуется большое количество ручной работы, что для нас пока не вариант. Все проекты, известные мне, которые пытались работать с достопримечательностями вручную со временем загнулись — потому что объем работы неподъемен для небольшой команды. Идея нашего проекта — максимальная автоматизация, которая работает может не всегда хорошо, зато легко масштабируется.
Ваш маршрут погляжу, спасибо. Возможно что-то исправим в эвристике оценок.
Javian
09.09.2019 14:14Хотя бы избегайте возвращения по одному и тому же пути, если есть альтернативный путь, например пройти обратно по другой стороне парка.
P.S. К слову снова о Google Earth — у них есть интересный слой сообщества Google Earth.
Наконец слой геотегированных фотографий с Фликра — концентрация фотографий в одном месте указывает, что там что-то интересное есть и стоит проложить маршрут рядом.JediPhilosopher Автор
09.09.2019 15:58Я стараюсь избегать — пройденные ребра графа получают штраф. Однако не всегда это срабатывает если путь в обход слишком длинный. А полностью запрещать возврат по тем же ребрам нельзя — тогда нельзя будет сходить к достопримечательностям с единственным путем к ним (например на острове с единственным мостом), как я в статье писал про собор в Калининграде.
Javian
09.09.2019 16:18В упомянутом маршруте можно было обойти по контуру парка — Мечеть, Собор- Здание в стиле модерн (пансионат Орбита) — Набережная. Плюс взглянув на общий вид маршрута я увидел, что вместо хождения туда обратно по центральным улицам, можно было с вокзала пойти на прямую в Караимские кенассы и от них через Старый город спуститься к парку. Возможно маршрут был бы короче, а впечатлений намного больше.
парк Караева - набережная Терешковой
aulitin
07.09.2019 11:18Работает как волшебство.
Почему Вальдфридхоф (кладбище) в Мюнхене считается парком? В принципе, это правильно, туда даже экскурсии водят, но не понимаю откуда данные. У него в тэгах явно написано, что landuse=cemetery.JediPhilosopher Автор
07.09.2019 12:20Потому что кладбища я запихивают в категорию парков. Тема спорная, не на всех кладбищах приятно гулять, но иногда кроме кладбищ зелёных зон вообще нет поблизости.
brom_portret
07.09.2019 11:59Это одна из вещей, которой мне не хватает в google maps.
Типа это очень странно, что их продакт менеджмент не видит очевидных вещей.
Я бы побробовал решить эту задачу так:
Построил бы индекс все интересных точек мире по:
Регион
Рейтинг
Тип
Координаты
Расстояние до ближайших точек и их тип и рейтинг
Таким образом, на входе скажем мои координаты и сколько времени у меня есть (или расстояние в км которое я хочу гулять), опционально фильтры и опционально координаты точки B куда я хочу придти, на выходе из базы — ребра графа.
А имплментацию решения — сделал бы модулем, чтобы юзер мог выбирать алгоритм [список релевантных алгоритмов для решения задачи коммивояжера включая полный перебор]
VladimirAndreev
07.09.2019 12:11А нет возможности (планов) ограничить зону маршрута?
Например, я хочу 2 часа гулять по парку, парк огромный (Москва, Сокольники)… Но маршрут из него уводит…JediPhilosopher Автор
07.09.2019 12:23Ну задача алгоритма просто показать все интересные места рядом, а уж если человеку что-то конкретное понравилось то он может сам решить там остаться.
По карте невозможно определить интересность парка и пригодность его для бесцельных прогулокVladimirAndreev
09.09.2019 10:10Я имел ввиду, возможность для пользователя в момент создания маршрута нарисовать замкнутый многоугольник, за который маршрут не должен уходить.
JediPhilosopher Автор
09.09.2019 13:33Хм, интересный use-case, не думали о таком. Вряд ли в ближайшее время сделаем, так как потребует заметной переделки логики работы, но на будущее запишем.
zone19
07.09.2019 14:08Вчера погулял немного по городу с круговыми маршрутами. Где-то на середине пути программа упала. Ну это ладно, но вот то, что она после перезапуска не восстановила маршрут было немного грустно. Было бы неплохо иметь в программе список последних нескольких маршрутов на такой случай.
JediPhilosopher Автор
07.09.2019 17:10Да, история маршрутов есть в планах.
Статистику крешей из консоли плеймаркета обработаем и постараемся починить в ближайших версиях.
singeorange
08.09.2019 13:21Спасибо, любопытно. Как в приложении переключить язык?
JediPhilosopher Автор
08.09.2019 13:23Никак, берется системная локаль. Есть либо русская либо английская по умолчанию.
Ge1i0N
08.09.2019 14:43Отличное приложение и идея, оценил и взял в использование.
Будет круто, если добавите Осло, Стокгольм и Мадрид, а то отпуск на носу.
oxff
08.09.2019 15:41+1- Добавьте, пожалуйста, Монреаль.
- В списке "Route Duration" ошибочка: "1 hour и 30 minutes", нужно бы исправить на "and".
- Хорошо бы ещё веломаршруты добавить. Приоритет давать по убыванию: bike paths, bike lanes, shared streets. Для городов с развитой вело-инфраструктурой это очень даже актуально. Берешь байк в аренду на любом углу и погнал.
oxff
08.09.2019 18:20В продолжение темы веломаршрутов.
Например, если у вас есть два часа до поезда или до встречи с друзьями, съездить куда-то далеко вы за это время не успеете, а вот погулять и посмотреть красоты поблизости вполне можно.
Вот этот сценарий реально будет выглядеть иначе в городе с развитой вело/скутер инфраструктурой. Я достаю смартфон, запускаю Uber, нахожу ближайший электробайк/скутер, беру его за рога и лечу куда хочу. При этом я успеваю не просто "пройти мимо" достопримечательности, но и осмотреть всё как следует, потому что на дорогу уходит в разы меньше времени.
Но проблема в том, что далеко не везде можно проехать на велике, где можно пройти пешком. К примеру, в моем городе за езду по тротуару или по парку (если там нет велодороги) штраф $100. Так что нужно использовать только подходящие пути. Ну и с учётом класса дороги, как я уже сказал выше, для повышения безопасности.
Если ваши сайт и приложение — не просто pet project (а даже если и так!), то неплохо было бы ознакомить юзера с правилами дорожного движения в данном конкретном городе, и привести таблицу штрафов. Например, у нас запрещено ездить на велике в наушниках, кроме специальных зон, а для электробайка обязателен шлем, который часто прилагается к арендованному байку.
JediPhilosopher Автор
09.09.2019 00:44Езда на велосипеде это особая тема. Действительно, не везде можно ездить на велосипеде, не везде это комфортно делать — уклоны, крутые повороты для велосипедистов имеют большее значение, чем для пешеходов. Доступность и безбарьеность среды из карты вообще никак не определишь, такие мелочи как пандусы и слишком высокие поребрики не картируются. Так что вряд ли получится что-то разумное.
glycol
09.09.2019 09:18Готов потестить, но Риги нет. Можно добавить? Приложение интересное, я бы пользовался в поездках, а то часто бывает, что не знаешь, что посмотреть в округе в незнакомом городе
JediPhilosopher Автор
09.09.2019 13:54Добавил.
glycol
09.09.2019 14:22Спасибо. Посмотрел, маршрут строиться достаточно странно, например, при построении 2-х часового, он почему-то уводит далеко от центра ради разрушенной синагоги и пары незначительных объектов, но игнорирует самый центр, большую часть старого города и канал, где красоты одна на одной. Логичнее было бы петлять по центру.
Картинка
zone19
09.09.2019 09:301. Еще бы значки метро сделать видимыми на более крупном масштабе. Иначе неудобно ориентироваться.
2. Ну и в поиске станции метро тоже имеет смысл добавить.JediPhilosopher Автор
09.09.2019 13:52Карту мы используем уже готовую, какие тайлы сторонний сервер (Mapbox) отдает те и рисуем. Сами мы их не рендерим.
Поиск — есть планы добавить строку поиска как в обычных картографических приложениях, чтобы искать достопримечательности, но опять же все упирается в нехватку рабочих рук.
amarao
This app is incompatible with all of your devices:
Samsung Galaxy S9
Xiaomi Mi Mix
Прям обидно.
JediPhilosopher Автор
Странно почему это? У нас по идее стоит поддержка андроида начиная с 4.4, так что уж новые смартфоны должны поддерживаться. Нет пока поддержки для планшетов, так как еще не подогнали интерфейс, но это же смартфоны, а не планшеты. Может кто из знатаков андроида подскажет, в чем может быть дело?
amarao
Вот тут есть статья. developer.android.com/guide/practices/compatibility
Вы с экранами не перенакрутили? Если что, оба устройства с high-dpi экранами.
JediPhilosopher Автор
Знать бы еще что там такого можно перенакрутить. Вроде по дефолту (и по ссылке тоже указано) приложение доступно для всех разрешений экрана.
Может дело в регионе? Я сейчас включил все страны, раньше там только РФ стояла.
Плей маркет разве где-нибудь не показывает, что именно ему не понравилось?
amarao
Да, страна — Cyprus. Всё так же (нет совместимых устройств).
Если оно свободное, то загрузили бы в чуть менее фашистское место (f-droid хорошее место, если у вас сырцы открытые).
(Ну или, хотя бы, apk'ку выложили).
JediPhilosopher Автор
Cейчас поставил все страны, но плей маркет чет в последнее время очень долго обновления выкатывает. Через какое-то время должно появиться. Если не появится — выложу апкшку тут.
Сырцы закрытые, хотя в самом приложении полезной логики-то особо нет, все на сервере делается.
Выкладывать во всяких мелких сторах — это времени много тратить, плюс еще искать их, регистрировать, разбираться.
amarao
С закрытыми сырцами, это, да, не нужно.
А f-droid — это не мелкий «стор», это opensource репозиторий.