LINUX.ORG.RU

Алгоритмы для поиска пути по карте высот

 , ,


0

2

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

★★★★★

Последнее исправление: ya-betmen (всего исправлений: 1)

Мысля вслух

А сымысла нет кажется кривизну вообще учитывать, она тебе ничего не даст на небольшие участке полигоны могут давать TBN веером во все стороны, перепад небольшой, а кривизна резкая, но по высоте будут отличаться пренебрежительно мало. Наверное надо просто пройтись по всем высотам, всё что выше X пометить как игнорируемое, всё что с разницей Y пометить как одинаковое, записать данные в текстуру, всё что X имеет цвет 0 всё это нужно обходить, всё остальное будет цветом 255 путями для поиска пути в обход X черноты. Искать пути в картинке строя по ней путь, а затем масштабировать полученные пути уже на 3d сетку.

LINUX-ORG-RU ★★★★★
()

Понятно, что можно всё поле сеточкой покрыть

Зачем? У вас уже есть карта высот.

Берите точки А и В, делайте A* с приоритетом наименьшей разницы высоты с соседней нодой по арбитрарному порогу, не нашли - увеличиваем порог, повторяем до успеха. Дайте вес дорогам и тропам, всё.

Bfgeshka ★★★★★
()
Ответ на: комментарий от LINUX-ORG-RU

В самом тупом варианте пройденный путь в гору/под гору больше чем по ровной поверхности ибо гипотенуза.

ya-betmen ★★★★★
() автор топика
Последнее исправление: ya-betmen (всего исправлений: 1)
Ответ на: комментарий от Bfgeshka

Блин, ты про карту высот как ч/б пиксели. Точно я не подумал. Но а-стар же будет пипец долго считать тогда.

ya-betmen ★★★★★
() автор топика
Последнее исправление: ya-betmen (всего исправлений: 1)

Ну для начала надо придумать целевую функцию для пути которая будет учитывать набор/сброс высоту? В туризме емнип ко времени на линейное перемещение (типа скорость 5км/ч) тупо добавлялось время на набор (300м/ч) и сброс (600м/ч) высоты.

А дальше интересно, я не спец по таким алгоритмам, но можно либо адаптировать существующий, либо че то свое свелосипедить, скажем на основе оптики или метода марша.

AntonI ★★★★★
()
Ответ на: комментарий от AntonI

надо придумать целевую функцию

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

Просто даже на 1024х1024 астар это слоупок. Если только разбивать и группировать участки, но там надо какой-то мутантский граф строить.

ya-betmen ★★★★★
() автор топика
Ответ на: комментарий от ya-betmen

Вообще то в любых задачах оптимизации это первичный момент - какую целевую ф-ю задать то и получишь.

Если речь о маршруте в реальной жизни, то гипотенуза точно не вариант - набор высоты гораздо дороже чем горизонтальное перемещение.

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

Какие вообще требования по производительности?

AntonI ★★★★★
()
Ответ на: комментарий от AntonI

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

какую целевую ф-ю задать то и получишь.

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

астар

А*, так и называется

ya-betmen ★★★★★
() автор топика
Последнее исправление: ya-betmen (всего исправлений: 3)
Ответ на: комментарий от ya-betmen

Но а-стар же будет пипец долго считать тогда.

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

Блин, ты про карту высот как ч/б пиксели.

Я лично работал с картами высот в виде tiff грейскейлов. А какие они в данной ситуации?

Bfgeshka ★★★★★
()
Ответ на: комментарий от ya-betmen

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

делать выбор в пользу меньшего времени или меньших затрат сил.

При движении по пересеченной местности время=силы.

AntonI ★★★★★
()
Ответ на: комментарий от AntonI

Это все на смартфоне должно крутится?

Пока хз, пока концепт, вдруг станет ясно что мне без суперкомпа не обойтись, значит приехали.

При движении по пересеченной местности время=силы

В общем смысле да, но налегке подъем 45% можно срезать ради 30 минут, а с 20 кг рюкзаком уже не факт.

ya-betmen ★★★★★
() автор топика
Ответ на: комментарий от ya-betmen

налегке подъем 45% можно срезать ради 30 минут, а с 20 кг рюкзаком уже не факт.

О_О… у Вас какие то очень странные представления о движении по пересеченной местности. Эскалатор в метро имеет уклон в 30 градусов. По лестнице с уклоном 45 градусов двигаться можно, но для среднестатистического человека недолго и вызовет большой дискомфорт.

В. И. Прокаев [6, с. 13] привел следующую шкалу крутизны склонов: 0,5-1° – ровные, близкие к горизонтальным; 1-3° – очень пологие; 3-5° – пологие; 5-8° – покатые; 8-12° – сильно покатые; 12-16° – умеренно крутые; 16-20° – крутые; 20-30° – очень крутые; 30-45° – обрывистые; больше 45° – обрывы.
Склоны круче 60° воспринимаются как отвесные, а с 75° до 80° — как имеющие отрицательную крутизну, поскольку при движении по такому склону человек вынужден отклоняться от вертикали в сторону падения склона (с) Алексеев.

И есть огромная разница при движении по тропе и вне тропы (если мы про природу). В дождь травяной склон крутизной более 30 градусов может оказаться непреодолимым без альпинистких кошек.

AntonI ★★★★★
()
Ответ на: комментарий от Bfgeshka

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

ya-betmen ★★★★★
() автор топика

https://pypi.org/project/pathfinding3d/

Currently there are 8 path-finders bundled in this library, namely:

  • A*: Versatile and most widely used algorithm.
  • Dijkstra: A* without heuristic.
  • Best-First
  • Bi-directional A*: Efficient for large graphs with a known goal.
  • Breadth First Search (BFS)
  • Iterative Deeping A* (IDA*): Memory efficient algorithm for large graphs.
  • Minimum Spanning Tree (MSP)
  • Theta*: Almost A* with path smoothing.

Dijkstra, A* and Bi-directional A* take the weight of the fields on the map into account. Theta* is a variant of A* but with any angle of movement allowed.

dataman ★★★★★
()
Ответ на: комментарий от ya-betmen

Очевидно что нет, хотя бы потому что оптимальным (если смотреть на то как проложены тропы в горах) зачастую является движение по дну лощины/гребню морены, т.е. это скорее движение по участку местности с минимальным модулем градиента.

Движение по изолии оптимальным является очень редко, например если идти на Эльбрус с юга по классике то это т.н. «косая» полка.

AntonI ★★★★★
()
Последнее исправление: AntonI (всего исправлений: 1)

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

visitor
()

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

Если решать алгоритмами теории графов, то в конечном счете так оно и получится – ты преобразуешь карту в граф, а веса ставишь в соотв. со сложностью перехода на соседнюю клетку/полигон, попутно выкидывая ребра по которым пройти нельзя, а дальше обычными алгоритмами (А* я бы применял в последнюю очередь, т.к. он нужен только тогда когда одновременно нужна почти линейная скорость, и ты очень хорошо понимаешь карту, чтобы подобрать правильную эвристическую функцию).

soomrack ★★★★★
()
Ответ на: комментарий от ya-betmen

Кстати вертолет в горах учитывает при планировании полета предполагаемый набор высоты - на это тоже уходит время и топливо, причем довольно много.

М.б. действительно начать с программы для дрона летающего по пересеченной местности?

AntonI ★★★★★
()