Длинная история путеводителя — как я 5 лет писал сервис для умных пешеходных маршрутов

У многих есть один или несколько своих домашних проектов. Это бывают небольшие утилиты, экспериментальные штуки, пробы новых технологий, “убийцы” фейсбуков и много что ещё. Заметно реже такими проектами занимаются долгое время.

В статье я поделюсь своим опытом и расскажу как в течении 5 лет эпизодически занимался разработкой умного путеводителя по Санкт-Петербургу, как мне удавалось не забросить это дело, как менялось отношение к проекту и что в итоге вышло.

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

Идея

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

Поэтому пришла идея построения умных маршрутов. Пользователь выбирает точки A и B и получает не классический кратчайший маршрут, а что-то близкое к нему, но проходящее через расположенные рядом достопримечательности.

Аудитория такого путеводителя — не только туристы, но и местные жители, которые хотят разнообразить свои типичные маршруты до дома/работы/магазина (и такие отзывы в итоге на приложение были!) или просто лучше узнать город.

TL;DR
Итог — Android приложение Wander, которое сейчас работает только для Санкт-Петербурга.

Акт 1: Прототип

Идея пришла ещё в университете в 2014-м году, не уверен даже что идея была изначально моя, на каком-то курсе нужно было разбиться на группы, придумать проекты и выполнить их как курсовую работу. Разбились и сгенерировали идею проекта, а затем название к нему — TravelPath и понеслось.

Это должен был быть веб-сервис, я умел немного на PHP, поэтому выбрали PHP.
Нужно было решить несколько задач:

1. База достопримечательностей
Тут мы познакомились с Open Street Map, оказалось что это крутейший проект, который нам отлично подходит. OSM — некоммерческий проект по созданию силами сообщества карты мира. Как Википедия, только про карты.
Скачиваем карту в xml формате Санкт-Петербурга — тут есть список ресурсов, где это можно сделать.
На тот момент, помню, файлы карт весили больше 1 GB, поэтому пишется потоковый парсер, который выделяет объекты выбранных заранее категорий — памятники, парки, церкви, музеи.
У OSM есть обширная документация по тегам, атрибутам и всему что нужно тут, благодаря ей не составит труда разобраться как достать из карт нужные вам данные.

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

Если я правильно раскопал свой старый код, то я использовал следующие теги для выборки объектов:

• building со значением cathedral, chapel, church стало категорией church
• amenity со значениями fountain попадает в monument
• tourism со значениями artwork и viewpoint идёт в monument, zoo и museum в museum, а theme_park в park
• historic со значениями boundary_stone, castle, memorial, monument уходит в категорию monument
• leisure со значением в park закономерно попадает в park

Складываем все полученные объекты в базу данных с координатами и радуемся! Вышло более 1200 точек по Санкт-Петербургу.

2. Построение маршрута
Не подразумевалось реализовывать сложные системы в рамках курсовой, да и технические знания на тот момент были скудны, поэтому построение маршрута решили разбить на две части: выбор объектов в маршрут и само построение маршрута. Отчасти это определило дальнейшую судьбу, потому что позже менять эту схему уже не хотелось.

Построение маршрута между выбранными точками отдали API гугл карт, который вполне неплохо строил автомобильные маршруты, но на тот момент ещё не умел пешеходные, по крайней мере в России.

Выбор же объектов нужно было реализовать самому. Получилось такая схема работы приложения:

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

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

Не очень чёткая формулировка задачи, таким же вышел и алгоритм, чем-то похожий на A* (wiki): считается что из каждой точки есть переходы в каждую. При этом в A* цена перехода в вершину n при поиске A-B маршрута обычно выражается так: f(n) = g(A-n) + h(n-B), где g(x,y) — длина пути от x до y, а h(x,y) — эвристическая оценка расстояния от x к y. У меня же цена такая — f(n) = h(x,n) + h(n,y) * q, где q — константа, меньшая 1. Меняя значение q, можно влиять на количество точек в маршруте.

Реализуем алгоритм и, ура, всё работает, прикручиваем интерфейс, покупаем домен, выкладываем на хостинг, пишем отчёты и прочую бюрократию и радуемся зачёту! Примерно так это выглядело (и особо не менялось после):

Итого: получился прототип классной идеи, познакомились с OSM, Google API, поработали в команде, получили зачёт в универе, да ещё и было интересно.

Акт 2: Первая полноценная web версия

Мне очень понравилась идея и я решил развивать её дальше, но уже один. И было сразу ясно что нужно в первую очередь: на тот момент Google Maps ещё не умел строить пешеходные маршруты, строились только автомобильные. А вся идея приложения в первую очередь про пешеходные прогулки — значит нужно уметь строить маршруты по тенистым аллеям парков, пешеходным дорожкам, мостам и многому другому.

Дело было в 2015-м году и я продолжил работать над TravelPath, взялся за исправление этого фатального недостатка — стал строить пути самостоятельно.

Технологии при этом я не изменил, PHP + MySQL. Конечно, я сразу осознавал что это не самый лучший технический стек для подобной задачи (строить маршруты на PHP? серьёзно?).
Но я был ограничен во времени и не готов был переходить на более разумный стек, а во-вторых до сих пор проект писался "в стол" — пользоваться таким приложением хочется с мобильного устройства, а в те годы это означало только нативную разработку. То есть была очевидна его неприменимость в виде веб версии, даже несмотря на какие-то попытки делать адаптивный интерфейс.

Встали следующие задачи:

1. Получение графа города
Тут нас спасает всё тот же OSM. Снова скачиваем граф в xml формате, парсим его, выбирая только нужные типы дорог и удивляемся количеству данных — на тот момент вышло более 3млн вершин и 500к рёбер. Первая же идея — граф может быть несвязанным.
Всякие внутренние дворы, закрытые территории, непонятные штуки не очень интересуют для построения маршрута, поэтому выбираем какую-то точку, из неё обходим весь граф, помечая пройденные вершины и получаем связанную часть графа.
Итого вышло более 600к вершин и 150к рёбер.
Сохранили полученное в базу и оставили до лучших времён.

2. Построение маршрута
Данные есть, дело осталось за малым: по ним строить маршруты. Тут ничего нового придумывать не пришлось — вспоминаем курс алгоритмов, внимательно читаем статьи о работе с графами, берём алгоритм A*, реализуем его на PHP и радуемся расстраиваемся от того, как медленно всё работает.

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

(красная рамка = ~такой граф был прочитан для построения пути)

Тоже самое и с точками-кандидатами в маршрут — учитываем не все, а только те что между начальной и конечной + небольшое значение.
Подобрав размер этого прямоугольника (константу, на которую его увеличиваем), пытаемся гарантировать что читаем минимальный необходимый размер данных.
Была ещё идея побить город на квадраты, строить маршрут сначала по квадратам, а затем читать уже граф внутри этих квадратов и искать путь только по нему. А ещё можно заранее посчитать пути между всеми соседними квадратами. Или даже больше — посчитать и сохранить пути между всеми достопримечательностями. Тогда на лету останется строить только пути от начальной до первого объекта, и от последнего объекта до финиша.
Но до реализации таких велосипедов руки не дошли.

3. Построение маршрута за разумное время
Сразу стало понятно, что узкое место это хранение и работа с данными — сам алгоритм поиска особо не ускоришь. Да и бенчмарки на коленке подтверждают, что основное время тратится на чтение из БД и подобные манипуляции.
Что в таких случаях нужно делать? Не хранить так граф. Но у меня особый путь, MySQL и ничего более, а проблему нужно решать.

1. Самое первое — данные были нормализованы, что удобно было при парсинге, но читать десятки тысяч записей да ещё и из двух таблиц — больно. Очевидное решение — из двух таблиц (для вершин и рёбер) делаем одну, только для рёбер, в которой в каждой записи координаты обоих вершин и их id.
2. Считаем заранее ближайшие вершины графа к достопримечательностям, а не делаем это на лету каждый раз.
3. Существенное время занимает поиск точки графа, ближайшей к заданной пользователю. Чтобы ускорить это, я разбил весь граф на небольшие сектора, с помощью формулы по координате можно моментально получить id сектора, а далее выбирать вершину уже только внутри сектора, а не во всём графе, что гораздо быстрее.

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

Итого: ещё лучше познакомился с данными OSM, на практике порешал графовые задачи (тот случай, когда наконец в деле пригодились графовые алгоритмы), написал свои первые бенчмарки.

Акт 3: Первая нормальная web версия

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

1. Было сразу очевидно, что строить маршруты так, как я сделал в прошлом пункте — неправильно.
2. Путеводитель в браузере мало кому может быть удобен — хочется гулять по городу, заглядывая в удобное приложение, где можно почитать что особенного вокруг и прочее прочее. Короче говоря как минимум — нужна крутой адаптивный интерфейс, а по-хорошему мобильное приложение.

Но на данном этапе я решил заняться только первым пунктом. Изучаем интернеты на эту тему и тут снова выручает OSM, точнее проект, который родился благодаря им — OSRM.
Open Source Routing Machine по картографическим данным из OSM умеет строить разнообразные маршруты за хорошее время. Да ещё и проект с открытым исходным кодом и хорошей документацией, который можно установить себе на сервер и использовать.
Как бонус, ещё и имеет довольно удобный API.
И об OSRM уже даже писал antaresm на хабре, что мне помогло на тот момент. Правда, воды утекло много и статья устарела. Но большое спасибо автору! Актуальная и довольно хорошая документация тут.
После успешной установки выкидываем, почти без сожаления, весь свой код про маршруты и начинаем ходить за маршрутами в api OSRM, а итоговая схема выходит такой:

Клиентскую часть даже не трогаем — с её стороны API нашего сервиса никак не меняется.

Итого: задумался о реальном использовании приложения другими, получилась нормальная архитектура и неплохие маршруты. Веб версия всё ещё доступна, хоть и не изменилась с тех пор. https://travelpath.ru/

Акт 4: Android приложение

Несмотря на решение прошлой проблемы, всё равно понятно что проект до сих пор бесполезен для всех, кроме меня. Потому что нужен нормальный интерфейс и, главное, мобильное приложение, а не браузерная версия. Сейчас технологии ушли вперёд и, возможно, уже получится сделать хорошо работающее браузерное приложение такого вида для мобильных клиентов, но в 2015-2016х годах нет. Что означало очень узкую возможность использования проекта в виде веб версии — посидеть дома, повыбирать интересные места для посещения заранее. Поэтому, если мы говорим о нормальном продукте, необходимо мобильное приложение с хорошим интерфейсом.

Тогда к 2016 году я начал писать на Java (но бекенд) и подумал что под Android ведь тоже на Java пишут. Почему бы и не попробовать разработку приложения, это должен быть интересный опыт.
Вторая проблема — я не умею в дизайн и хороший интерфейс сам не сделаю. Я пришёл навестить своё первое место работы (небольшую студию Le-Dantu) и предложил коллеге burovk поучаствовать в проекте. Как ни странно, он согласился, за что большое спасибо :)

Первые макеты и прототип
Первым делом мы пытаемся придумать новое название, потому что TravelPath — не очень, да и слишком говорящая аббревиатура. И так стараниями Кирилла появляется “Wander” со смешным логотипом:

У меня он прочно ассоциировался с усатым мужиком, но в целом нравится.

Затем появляются первые макеты будущего приложения:

Ещё думаем, обсуждаем, появляется второй вариант, который и становится первой версией приложения:

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

Из проблем и задач, которые запомнились:

• Для android есть ProGuard — утилита, сжимающая при сборке исходный код, выпиливает неиспользуемое, меняет имена и прочее прочее. Разумно что она есть, но когда ты только входишь в разработку и делаешь это сам — не очевидно что там идут переименование полей и это может повлиять на поведение. И что всё происходит только в prod сборке. В результате релиз, всё круто, а статистики почему-то нет. Начинаешь дебажить со стороны бекенда — а клиент присылает какую-то чушь, вместо нормальных имён полей — a, b, c и т.д. Костылишь чтобы API умело и такое парсить, а потом узнаёшь что ProGuard постарался и нужно указать нужные классы как исключение в его конфиге. Ничего в целом необычного, но часы отладки улетели.
• Интересной задачей было обновление данных приложения. Основная база данных поставляется вместе с apk файлом и перед каждым релизом я её обновляю. Но ещё нужно поддержать обновление по сети, чтобы у клиентов всегда были свежие данные, если были какие-то изменения.
  В первой версии я решил просто ориентироваться на время последнего обновления. Приложение хранит время самого свежего объекта, при каждом запуске спрашивает бекенд с этим временем не появилось ли что нового. Ему присылают обновления, клиент запоминает снова время самого нового из полученных объектов (но не время самого обновления, это важно).
  Оказалось, придумал я плохо — потому что годом позже появилась пятая категория — здания. И при обновлении со старую на новую версию возникает проблема. Пришлось немного поменять и клиент шлёт время по каждой категории, а не общее. Но схема всё равно не идеальна — при добавлении новых полей в объекты, возникают проблемы которые так не решить. Есть идеи как сделать лучше, но руки не дошли и в целом задача не очень приоритетна. Мораль — стоит внимательнее подходить к таким вопросам и думать немного наперёд.

А ещё хочу сказать то, что и так все знают — Stack Overflow невероятно крут и особенно это заметно когда ты влетаешь в разработку чего-то постороннего так, как это сделал я — сразу пишешь приложение, а не плавно с курсов, гайдов, демо примеров. И когда некого спросить знакомого. Но помимо него, помогали ещё и чаты про android разработку — там можно спрашивать более абстрактные вопросы и просить советов как лучше что-то сделать.

5 декабря 2016 года приложение попадает в Google Play
У него были только базовые функции — прокладывание маршрута, просмотр информации о точках. Но даже это казалось успехом! Успехом, конечно, только в своих собственных глазах. Было понимание что приложение всё ещё сырое и требует доработки.

Первая полноценная версия и СМИ
Поэтому полноценной версией и первым запуском я считаю следующий релиз.
В первую очередь мы пересмотрели и дизайн, и логотип — он теперь стал таким:

И добавили важного для путеводителя функционала — избранное, просмотр точек на самой карте, список достопримечательностей с поиском. Обновлённое приложение выглядело так:

Ещё появилась идея — связаться с Ночью Музеев и сделать отдельный режим для события в Питере.
Ночь музеев — ежегодный международный праздник, где музеи открыты ночью часто со специальными программами. Действует единый билет и многие стараются обойти много музеев сразу. В тоже время нет навигатора/карты для мобильных — только кое-какой функционал на официальном сайте мероприятия.
Звучит как то, что идеально ложится на идею Wander и является ещё и востребованным. Я связался с организаторами события, но идею, к сожалению, не оценили и она осталась лежать в уме до лучших времён.

В конце концов вышло классно и наконец приложением можно было полноценно пользоваться. 2 июня 2018 вышел релиз и его мы решили попробовать показать миру — закупили немного рекламы в ВКонтакте и Instagram. Но главное — написали в пару СМИ. Бумага написала заметку о запуске приложения, после неё веером написали или перепечатали ещё ряд Петербургских изданий — The Village, Собака и другие. И наконец появился трафик! Установки пиком рванули вверх, графики активности внутри приложения тоже. Радоваться, конечно, долго не пришлось — но мы получили первых пользователей, полезный фидбек и вообще это очень замотивировало. Ещё тем же летом был заметен трафик из поиска по Google Play, что очень радовало, но позже результат воспроизвести не удалось.
Всё вместе это дало довольно сильную мотивацию и помогло продолжать работу над приложением.

Что делать дальше? Ночь Музеев, злой Google, круговые маршруты

Сезон прошёл, активность в приложении сильно упала и было ясно что просто пилить фичи не очень полезно — их никто не увидит, бюджета на маркетинг нет. Нужно было что-то придумать и тогда мы ещё раз вернулись к отложенной идеей с Ночью Музеев.
Но снова не удалось договориться о партнёрстве, тем не менее на этот раз мы решили не откладывать идею, а сделать всё своими силами. Получился ряд полезных фич в отдельном режиме путеводителя: музеи на карте, маршруты только по участникам, краткая информация, избранное.

Помимо этого режима, ещё из беклога достали сохранении маршрута и главное — фичу о круговых маршрутах.

Круговые маршруты были всегда важнее маршрутов A-B, но упорно игнорировались. Всё же люди чаще гуляют вокруг метро/дома/работы/гостиницы, чем целенаправленно из А в B. Наконец дошли до них руки и я придумал простую эвристику:
Получаем все точки внутри заданного радиуса. Радиус — ограничитель длины маршрута. Выбираем какую-то точку первой (условно случайную). Все остальные от неё сортируем в порядке возрастания угла между ней, центром и заданной точкой. Добавляем в маршрут точку только если она не сильно ближе/дальше к центру, чем предыдущая.

Этот метод позволяет влиять на размер маршрута, выбирая первую точку дальше или ближе от центра и меняя длину радиуса.

Несмотря на некоторую её странность, работает отлично, вот примеры маршрутов:

Что в этом алгоритме, что в предыдущем, для маршрута между точками А и Б, не используется информация о достопримечательностях, кроме типа, хотя очень бы хотелось. Но непонятно как использовать — ценных данных, по которым можно было бы оценивать и сравнивать точки, нет.

Ещё на этом этапе я решил попробовать Kotlin и сделать это, конечно, сразу на Wander. В целом классно, но заметно труднее читать код. Наверное это с непривычки, но всё же. По сей день новый код стараюсь писать на котлине, но старые классы с java не переписываю — не вижу смысла тратить на это время.

В сумме получилось большое обновление, выпустили его, дали рекламу, написали в СМИ. На этот раз со СМИ так сильно не повезло — заметку выпустила только The Village. Но в сумме с рекламой это дало кое-какие плоды и за ночь пользователи построили больше 1000 маршрутов, а сохранили более 1400 музеев в избранное. Кстати, самыми популярными музеями по версии Wander стали Ленфильм, Анненкирхе, Планетарий, Большой зал филармонии имени Шостаковича и Кунскамера. Список похож и на официальную статистику.

Отдельно хочется упомянуть Google недобрым словом. Приложение работает на их картах и это оказался очень неудачный выбор — в 2018м году они сильно изменили тарифные планы, значительно увеличив цену и уменьшив бесплатные лимиты в API. Это стрельнуло даже в моём небольшом приложении — один из пиков активности после публикации СМИ летом 2018-ого года привел к превышению количества запросов к Places API и его выключению. Я был бы не против даже заплатить за API, но не тут-то было — в России это возможно только для юридических лиц. То есть платёжный аккаунт для физлица не создать.

Годом позже они добавили ещё немного проблем — изменили Places API, потребовав у всех разработчиков поменять и приложение в определённый срок. Это дополнительная работа для меня на ровном месте, при очень ограниченным временем на приложение. Проще говоря, если вы выбираете какие карты использовать у себя — не используйте Google Maps, есть много хороших альтернатив. А я надеюсь что дойдут руки переписать карты на другой сервис.

Итого: запилил android приложение с нуля и до выкладки в Google Play, не умея предварительно ничего в этой области. Нашёл помощи у burovk, благодаря чему над Wander теперь работаю не один, а в приложении удобный и классный интерфейс.

Ты теперь не только разработчик

Один из важных моментов, которые нужно понимать, когда начинаешь заниматься своим проектом для пользователей, а не в стол — то что разработка это не самое важное. Можно сколько угодно думать про архитектуру, упарываться алгоритмами, выбирать самые новые технологии, экономить биты и такты процессора — это всё ничего не значит. Это классно делать, если цель — самообразование, а сам проект пишется в стол. В ином же случае, ваших стараний никто никогда не увидит и не оценит, а время будет потрачено зря.

• Потому что какую бы прорывную идею вы не придумали и как бы круто её не реализовали — никто об этом не узнает сам по себе после git tag v1.0.5.
• Потому что проблема, которую решает приложение, должна быть настоящей, а не придуманной вами.
• Потому что пользователям сначала нужно чтобы приложение хоть как-то решало их проблему, а уже только потом чтобы решало хорошо.
• Потому что чем меньше у вас времени и чем больше проект — тем важнее внятно осознавать что важно, а где на качество/красоту/etc можно забить ради релиза не через бесконечность.

Я пришёл к этому с началом разработки Android версии приложения. И в уме с этого момента, постепенно, технические детали становились всё менее важными, и всё больше времени тратилось на остальное.

Работа над своим проектом для других — в первую очередь работа над продуктом, а затем уже разработка.

Планы

Захватить мир! Если серьёзно, то не очень понятно что делать дальше. По функционалу, фичам, улучшениям есть куча идей, но всё так же непонятно как эти результаты доносить до пользователей, а не писать приложение в стол, не имея бюджета.
Из более крупных планов список такой:

1. Охватить и другие города — Москва? Какой-нибудь крупный европейский город?
2. Полноценная английская версия. Интерфейс уже переведён, остаётся самое сложное — перевод всего контента.
3. Версия под IOS
4. Веб версия

Но не всё это реалистично. Скажем, версию под IOS я сам вряд ли смогу написать, только если найдётся энтузиаст.

Если хотите следить за проектом — группа в ВК. А приложение есть в Google Play.

Выводы

• Заниматься своим проектом в свободное время, параллельно работая — тяжело. Нужно находить время на сам проект, чтобы это не было в ущерб работы и остальной жизни. Нужно учиться концентрироваться на самом главном и выбирать наименее трудоёмкие пути. Наверное, это самый необходимый навык в такой работе.
• Свой проект — классный вызов, особенно когда он не полностью профильный. Я был backend разработчиком, а благодаря ему я занимался и вебом, и вник в android разработку и Kotlin, решал продуктовые проблемы, анализировал конкурентов, думал над рекламой и продвижением. Получаешь крутые и полезные навыки, которые трудно получить иным способом.
• Находить мотивацию на такую работу — трудно. Ты тратишь много времени на какую-то работу, у которой даже не видишь особо больших перспектив в ближайшем времени. Легко на каком-то этапе всё бросить. Поэтому крутая идея, которая тебя захватывает — это очень важно.

Буду рад комментариям и предложениям. А если вдруг вы захотите сделать версию под IOS (но это вряд ли) — буду очень рад!

P.S.
Не могу не упомянуть статью о похожем проекте — https://habr.com/post/414433/. Именно эта статья натолкнула меня на мысль написать свою. Забавно, что мы пишем очень похожие сервисы (и оба изначально о Санкт-Петербурге!), но только с акцентом на разных частях.