поиск в ширину, поиск в глубину

а не-сетчатые структуры (хотя по сути это тот же граф) пока еще не писал

Граф

Раз вы столько знаете, я удивлён что спрашиваете про NavMesh. Он для вас должен показаться более примитивным

Я не работал с мешами сам по себе
генерация, оптимизация меша, привязка линков к ребрам, вот это все, Best Practice на этот счет

Ну по сути это дополнительные графы, которые дают связь с соседями (и можно настроить, прыгать на них или можно пройти пешком)

То есть персонаж либо покажет анимацию прыжка и туда переместиться или упадёт (в обратную сторону). Или телепортируется, если расстояние большое между двумя link

О вижу собрата кто собрался погрузиться в пучину написания своих навмешей (я в этой пучине как раз).
Увы инфы не так много, из того что я нашел. У меня top-down 2D и небольшие уровни так что я через polypartition просто делаю меш и вырезаю дырки геометрии в нем, а поиск делаю через A* и simple stupid funnel.
Сейчас как раз думаю над алгоритмом для того чтобы вырезать дырки с отступом и мержить геометрию между собой (потому что polypartition не умеет мержить нормально несколько мешей).

Идеально)

Oh, Hello there

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

Реально мержить не обязательно, вам же ничего не мешает сделать между ними link или несколько

> Quality of solution: Satisfactory in most cases.
ыы)

Не оптимизирую. Надо бы, но самому писать это не хочется, а те библиотеки которые пробовал (тот же polypartition), не умеют нормально работать с геометрией с дырками.
У меня могут быть очень длинные треугольники, чтобы это работало +- нормально я добавил шаг в A* который делает raycast условный внутри треугольника чтобы пытаться строить прямой путь когда возможно. Хак но работает очень хорошо.

Ведь там как, если использовать A* то для него у каждой ноды должна быть одна оценка (ну то есть для каждого выпуклого полигона надо выбрать одну точку).
И тут как бы можно выбрать угол, центр грани или центр полигона, но если полигоны растянуты, то каждая из этих точек может находиться не по оптимальному пути.
То есть можно упарываться в построение идеально сбалансированного навмеша, можно упороться в идеальный поиск пути по тому что есть. Я выбрал второй путь, так как хочу иметь возможность перегенерировать навмеши на лету. И да, оба пути - глубокая кроличья нора.

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

Спасибо за информацию

Если что потом потыкаю в личку, если не против

Не против

Эмм, не понял как треугольники могут перекрывать или находится вне пути

Я могу формировать геометрию на лету, хоть в Unity, хоть за еë пределами, создаю собственный формат моделей, пишу экспортер для blender. Импортер для чтения в Unity, Unreal, Godot, Flash, LibGDX и т.д.