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

Мысля вслух

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Так же, как на плоской поверхности.

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

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

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

астар

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

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

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

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

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

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

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

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

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

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

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

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

А какие они в данной ситуации?

Я про те что с изолиниями

налегке подъем 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 градусов может оказаться непреодолимым без альпинистких кошек.

Я про те что с изолиниями

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

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

Это понятное дело, я про то что функцию всё равно придется подстраивать, поэтому надо всё вокруг сначалв сделать.

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

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.

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

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

движение по участку местности с минимальным модулем градиента.

Но ведь это частный случай движения по изолинии, не?

Нет конечно, даже близко не оно.

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

А что такое «СПВ»? Гугл говорит «свободный порт Владивосток» и этим тегом объединены совершенно кажется не связанные темы на форуме.

Ты не знаешь о специалистах по всему?

Апять дрон разрабатывать помогаем

Ага, который по земле ходи и ориентируется только по карте.

Ты не знаешь о специалистах по всему?

Ах.. Точно! Я не догадался.

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

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

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

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