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

[kelegorm]

Теперь я могу гулять каждый день!

[ov7a]

del

[kaichou]

Руководил разработкой такой штуки в 2008 в рамках проекта gps-навигатора для слепых и инвалидов-колясочников.

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

Готовые прототипы много тестировали со слепыми и инвалидами.
Год спустя тему закрыли в связи с бесперспективностью.

[zzeng]

Полностью доверять построенному таким образом маршруту не стоит.
Зато метод дает отличную оценку расстояния до ближайшей дороги или остановки.
Чем мы и пользуемся.

[dj_raphael]

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

[zzeng]

Мы строим в городах, где очень редко удается построить длинный пешеходный маршрут.
Чтобы пройти пешком пару км в Нске надо уйти в поля, не уверен, что в Москве с ее плотностью застройки это вообще удастся.

[AlexanderG]

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

[dj_raphael]

Студентом в Москве ходил от Ленинградского вокзала до МГУ, приехали в 4 утра и без проводника врядли бы добрались.
А в Питере от главного здания СПбГУ до Балтийского вокзала почти каждую ночь летом.

[Gard]

Решали ли как-нибудь проблему точности GPS? Допустим, я иду по дороге вдоль забора. За забором территория завода, выхода/входа с которой нет. Но из-за ошибки gps, моя позиция определяется за забором. Что произойдёт в этом случае?

[zzeng]

Хуже того, в некоторых местах (возможно из-за переотражения сигналов спутников) есть систематическая ошибка GPS.
Так что даже если прогнозировать маршрут пользователя, это не поможет.
Для автомобилей проще, там мы с учетом азимута притягиваем пользователя к дорожной сети.
А пешеход может быть везде. Но у него остается возможность вмешаться и правильно установить исходную точку.

[Gard]

А «юридическая» доступность территорий есть? Через многие калитки пропускают не всех. Такие территории будут закрытыми?

[zzeng]

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

[h0tkey]

Интересно, насколько лучше или хуже бы себя показало применение visibility graph'а для поиска пути…
Пробовали? Или A* по сетке — первое решение, proof of concept?

[zzeng]

Граф области видимости неудобен для хранения, порождает слишком много связей, на наш взгляд пиксельный вариант дешевле.

[Draku1a]

Всё-таки, в городах лучше ходить по тротуарам и дорогам, чем продираться через каменные джунгли, рискуя наткнуться на «гоп-стоп».
Зато, как алгоритм расчета расстояний — очень полезно. Позволит более точно подбирать автобусные маршруты. А то ранее, например, показывал оптимальный маршрут — пройти через озеро до остановки.

[zzeng]

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

[zzeng]

:) Это очень простая магия. Если точки близко, мы стараемся построить путь напрямую из точки в точку.
В противном случае ищем пеший маршрут до ближайших дорог и дальше ищем путь через дорожную сеть.
В данном случае Вам удалось нащупать пороговое значение.
Отмечу, каков бы ни был порог, кому-то всё равно удастся его нащупать.

[zvirusz]

Нашёл странный маршрут: take.ms/kS68B
2gis.ru/spb/search/%D0%B0%D0%B4%D0%BC%D0%B8%D1%80%D0%B0%D0%BB%D1%82%D0%B5%D0%B9%D1%81%D1%82%D0%B2%D0%BE/routeSearch/center/30.309579%2C59.936717/tab/firms/zoom/17/routeTab/rsType/bus/from/30.320757%2C59.901945%E2%95%8E%D0%A1%D0%B0%D0%BD%D0%BA%D1%82-%D0%9F%D0%B5%D1%82%D0%B5%D1%80%D0%B1%D1%83%D1%80%D0%B3%20%D0%9A%D0%B8%D0%B5%D0%B2%D1%81%D0%BA%D0%B0%D1%8F%203/to/30.309821%2C59.937046%E2%95%8E%D0%91%D1%8E%D1%81%D1%82%20%D0%9C.%D0%AE.%20%D0%9B%D0%B5%D1%80%D0%BC%D0%BE%D0%BD%D1%82%D0%BE%D0%B2%D0%B0

Что-то мне подсказывает, что будет проще и быстрее перейти дорогу по Гороховой :)

[zzeng]

Похоже на ошибку в графе. Будем разбираться, спасибо.

[vlivyur]

Там ещё раньше есть переход у дома 1 на Невском (сейчас ссылка не так ведёт).

[BOOMik]

go.2gis.com/rjjb8 — до входа пешком идти 2.5км
go.2gis.com/prud — на 5 метров дальше от входа надо и уже можно на автобусе ехать
go.2gis.com/t58n — немного перенесем ближе к старту и туда тоже на автобусе предлагает.
Есть таки проблемы с построением маршрутов.
Но идея здравая и полезная. А не думали сделать выбор только пешком или с использованием общественного транспорта?

[zzeng]

Не без проблем, конечно, вычесываем потихонечку.
Только пешком на короткие расстояния можно лишь.

[BOOMik]

Ну тут более чем на 2км пеший маршрут, а так ситуация похожа на жизненную-тоже периодически автобусом, периодически пешком :)
И насущный вопрос: приблизительно когда ждать данную фичу под Android?

[zzeng]

Точно не знаю, скоро.

[BOOMik]

Спасибо, Ждем!