Пешком по тайлам



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

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

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

    Принято считать, что такой способ строить маршруты неприемлем, потому что съедает много ресурсов. Под катом — как мы с этим справились.


    Алгоритм


    Изобразим алгоритм построения пешего маршрута.

    1. Растеризуем местность с разрешением 2 × 2 метра. Под растеризацию попадают дома, дороги, заборы, водоёмы, переходы, овраги… В простейшем случае каждый пиксель получает значение — можно или нельзя пройти. Но ничто не мешает градуировать проходимость:
      • можно пройти быстро
      • можно пройти
      • проходится с трудом
      • не пройти
      Важен приоритет. На изначально проходимую местность мы наносим препятствия: дома, непроходимые дороги, заборы, овраги, железные дороги… Затем прорезаем проходимые дороги и пешеходные переходы с железнодорожными переездами в виде кругов диаметром чуть шире дороги.
    2. Рассматриваем карту местности как описание графа с неявно указанными взаимоотношениями между соседними клеточками. Переход только в проходимые, в которых мы ещё не были.
    3. Работаем с графом. Если ищем проход из точки в точку, используем вариант алгоритма А*.
      Если ищем ближайшую дорогу, определяя проход до ближайшего из зарегистрированных объектов, то пускаем волну поиска честным алгоритмом Дейкстры.

    Две вещи пугают в этой схеме: память и память. Оперативная и на диске. И та, и та расходуются слишком быстро. Попробуем решить проблему.

    Боремся за оперативную память


    У каждой точки потенциально 8 пар рёбер — прямое и обратное. На квадратный километр получается: 500 × 500 × 8 = 2 000 000. Если действовать «в лоб», придётся каждое обработать и сохранить…

    Чтобы сэкономить оперативную память, мы делим карту на тайлы по 256 × 256 клеточек или 512 × 512 метров. Будем хранить только периметр волны, проходящий по границам тайлов. Для хранения периметра заведем общую «кучу».

    Тайлы обрабатываем атомарно. При заливке тайла используем его локальную «кучу». Алгоритм такой:

    1. Находим тайл, в который попадает начальная точка, и вносим точку в локальную «кучу» этого тайла.
    2. Пускаем в тайле волну. Если при заливке мы дошли до финиша, то переходим к пункту 7. Если нет, то когда волна зальет весь тайл, на его границах мы получим длины от исходной точки.
    3. Заносим в общую «кучу» периметр этого тайла. Сам тайл нам больше не нужен, его можно освободить.
    4. Берём из общей «кучи» минимальный элемент, смотрим, в какой тайл и на какую его сторону этот элемент смотрит.
    5. Убираем из общей «кучи» все точки из этой стороны этого тайла и запоминаем их.
    6. Загружаем новый тайл. В его локальную кучу с нужной стороны заносим найденные точки. Снова возвращаемся к пункту 2.
    7. После того как путь найден (это фактически список точек на межтайловой решетке), восстанавливаем настоящий путь и внутри тайлов. Делаем это потому, что сами тайлы мы уже давно выгрузили для экономии памяти. Для этого мы идём по нашему пути, загружаем по очереди тайлы и заново строим маршрут, но на этот раз из точки в точку внутри тайла.
    8. Найденный путь выпрямляем, чтобы избавиться от характерной «пилы». Методика хоть и не устраняет все артефакты, но быстро избавляет от наиболее явных.
      Для этого внутри тайла используем алгоритм Брезенхема. Для спрямления кусков пути мы рисуем между кусками линию и по маске препятствий следим, проходима ли эта линия.
      Между тайлами мы также спрямляем путь. Для этого берём предпоследнюю точку предыдущего тайла и вторую текущего. Находим на решетке точку, которую заметает пересекающая их линия. В обоих тайлах Брезенхемом пытаемся пройти напрямую к этой пограничной точке. Если удалось — вуаля! — соединяем напрямую.

    Посмотрим распределение стоимости внутри тайла:

            

            Цветом — от синего к оранжевому — обозначается длина
            пройденного пути. Вышли мы из правого верхнего угла.



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

    Боремся за дисковую память


    Для хранения одного тайла в 256 × 256 точек с разрешением в 1 бит на точку потребуется 8 килобайт. Тогда квадратный километр стоит 32 килобайта, а типичный город с окрестностями — 100 × 100 км уже весит 320 Мб.

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

    Изначально, принимая это во внимание, мы применили адаптивный арифметический кодировщик. Растеризация Новосибирска заняла около четырёх минут. Получилось 4946 непустых тайлов, которые заняли примерно 10 Мб. При этом те же данные в gif’ах занимают всего 6 Мб (что унизительно :-). Выглядит это так:

            

            Несколько произвольных тайлов в виде картинок


    10 или даже 6 Мб для Новосибирска — это больше, чем занимает наш роутинг индекс.

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

    Растеризация «на лету»


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

    Но тогда для растеризации каждого тайла придётся делать 10 пространственных запросов к пространственным индексам с последующим вычитыванием из соответствующих пространственных слоёв.

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

    Попросту говоря, такой вариант слишком дорог. Так что мы сделали своё хранилище данных для растеризации.

    Для хранения геометрий используется Б-дерево с ключом из 3 элементов (или из двух + значение, если угодно):
    1. TileID — идентификатор тайла. Экстент карты разбивается на тайлы, нумерация идёт построчно снизу вверх слева направо.
    2. Attr — атрибут объекта. Используем только 1 младший бит. 0 — объект растеризуем единичками, 1 — нулями.
      При траверзе дерева нули идут вперёд, и мы сначала нарисуем все блокирующие объекты (дома, заборы), а затем поверх нанесём разрешающие объекты (калитки, переезды).
    3. Shp — геометрия, все типы геометрий упакованы вместе.

    Такая организация за один поиск и один траверз находит данные данного тайла. При этом используются преимущественно стековые объекты. Дополнительная память берётся из пула, что заметно гуманнее по отношению к CRT.

    Геометрии на этапе экспорта клипируются по границам тайлов. При записи дерева данные сжимаются. В результате хранение векторной информации втрое компактнее растеризованной, если сравнивать с адаптивным арифметическим кодером, и вдвое экономнее gif.

    Примеры маршрутов


    Идём из точки в точку, проходим через ж.-д. переезд.

            


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

            


    Идём до ближайшей дороги.

            


    Опять до ближайшего ребра.

            

    Что в итоге


    Объём дополнительных данных для Новосибирска — примерно 3 Мб. Столица нашей необъятной Родины — 8Мб. Поиск за 1,5 км на десктопе занимает 90 мсек без разогрева. Это около 20 распакованных и обработанных тайлов. Дополнительной оперативной памяти, как правило, требуется меньше мегабайта.

    Но у подхода есть недостатки. Несмотря на «выпрямление» геометрий, иногда результат довольно странный. Например, за счёт дискретности растеризации время от времени «слипаются» здания.

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

    И всё-таки, это лучше, чем притягиваться напрямую к ближайшим дорогам и шагать по городам и весям, невзирая на преграды. Пешие маршруты уже работают в мобильных приложениях на iOS и Windows Phone и при поиске проезда на общественном транспорте на 2gis.ru.
    2ГИС
    138,00
    Карта города и справочник предприятий
    Поделиться публикацией

    Похожие публикации

    Комментарии 26

      +6
      image

      Теперь я могу гулять каждый день!
        0
        del
          +3
          Руководил разработкой такой штуки в 2008 в рамках проекта gps-навигатора для слепых и инвалидов-колясочников.

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

          Готовые прототипы много тестировали со слепыми и инвалидами.
          Год спустя тему закрыли в связи с бесперспективностью.
            0
            Полностью доверять построенному таким образом маршруту не стоит.
            Зато метод дает отличную оценку расстояния до ближайшей дороги или остановки.
            Чем мы и пользуемся.
            0
            Как то давно здесь была статья про расчет маршрутов в старкрафте, и почему юниты так быстро его находят. Так вот там маршруты между точками крупной сетки рассчитываются при сохранении в хранятся в самой карте и берутся готовые, а короткие примерно как у вас.
            У вас конечно масштаб другой, но можно попробовать собрать статистику расчетов. и для популярных больших маршрутов хранить предрассчитанные.
              0
              Мы строим в городах, где очень редко удается построить длинный пешеходный маршрут.
              Чтобы пройти пешком пару км в Нске надо уйти в поля, не уверен, что в Москве с ее плотностью застройки это вообще удастся.
                0
                Удастся, ходили пешочком от Кремля до Октябрьского поля. И там подобные подсказки крайне пригодились бы — было несколько пересечений железных дорог, которые пришлось преодолевать по техническим галереям мостов, т.к. на картах не было пешеходного пути.
                  0
                  Студентом в Москве ходил от Ленинградского вокзала до МГУ, приехали в 4 утра и без проводника врядли бы добрались.
                  А в Питере от главного здания СПбГУ до Балтийского вокзала почти каждую ночь летом.
                0
                Решали ли как-нибудь проблему точности GPS? Допустим, я иду по дороге вдоль забора. За забором территория завода, выхода/входа с которой нет. Но из-за ошибки gps, моя позиция определяется за забором. Что произойдёт в этом случае?
                  0
                  Хуже того, в некоторых местах (возможно из-за переотражения сигналов спутников) есть систематическая ошибка GPS.
                  Так что даже если прогнозировать маршрут пользователя, это не поможет.
                  Для автомобилей проще, там мы с учетом азимута притягиваем пользователя к дорожной сети.
                  А пешеход может быть везде. Но у него остается возможность вмешаться и правильно установить исходную точку.
                    +1
                    А «юридическая» доступность территорий есть? Через многие калитки пропускают не всех. Такие территории будут закрытыми?
                      0
                      Технически такая возможность есть, практически, если не ошибаюсь, мы проходим через большинство калиток т.к. это порождает наименьшее количество ошибок.
                  0
                  Интересно, насколько лучше или хуже бы себя показало применение visibility graph'а для поиска пути…
                  Пробовали? Или A* по сетке — первое решение, proof of concept?
                    0
                    Граф области видимости неудобен для хранения, порождает слишком много связей, на наш взгляд пиксельный вариант дешевле.
                    +3
                    Всё-таки, в городах лучше ходить по тротуарам и дорогам, чем продираться через каменные джунгли, рискуя наткнуться на «гоп-стоп».
                    Зато, как алгоритм расчета расстояний — очень полезно. Позволит более точно подбирать автобусные маршруты. А то ранее, например, показывал оптимальный маршрут — пройти через озеро до остановки.
                      0
                      Мы так и делаем там где дорожки прорисованы. Но надо отдавать себе отчет, что каждая прорисованная пешая дорожка занимает место. Это выливается в то, что распухает база и растёт трафик у клиентов. Опять же нужно дополнительное время и память на распаковку.
                      Поэтому мы стараемся нащупать баланс.
                      0
                      Магия!
                      image
                      image
                        0
                        :) Это очень простая магия. Если точки близко, мы стараемся построить путь напрямую из точки в точку.
                        В противном случае ищем пеший маршрут до ближайших дорог и дальше ищем путь через дорожную сеть.
                        В данном случае Вам удалось нащупать пороговое значение.
                        Отмечу, каков бы ни был порог, кому-то всё равно удастся его нащупать.
                          +1
                          Похоже на ошибку в графе. Будем разбираться, спасибо.
                            0
                            Там ещё раньше есть переход у дома 1 на Невском (сейчас ссылка не так ведёт).
                            0
                            go.2gis.com/rjjb8 — до входа пешком идти 2.5км
                            go.2gis.com/prud — на 5 метров дальше от входа надо и уже можно на автобусе ехать
                            go.2gis.com/t58n — немного перенесем ближе к старту и туда тоже на автобусе предлагает.
                            Есть таки проблемы с построением маршрутов.
                            Но идея здравая и полезная. А не думали сделать выбор только пешком или с использованием общественного транспорта?
                              +2
                              Не без проблем, конечно, вычесываем потихонечку.
                              Только пешком на короткие расстояния можно лишь.
                                0
                                Ну тут более чем на 2км пеший маршрут, а так ситуация похожа на жизненную-тоже периодически автобусом, периодически пешком :)
                                И насущный вопрос: приблизительно когда ждать данную фичу под Android?
                                  +1
                                  Точно не знаю, скоро.
                                    0
                                    Спасибо, Ждем!

                            Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                            Самое читаемое