Поиск пути без использования сетки
 

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

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

WERt, можно же просто сгладить путь

Да,спасибо, я думал об обоих этих вариантах,и решил,что буду думать,как сгладить)

Добавлено через 7 минут
Спасибо)

Вообще тот же astar обладает настройкой, в ширину расти или в глубину. Там можно заюзать стек или очередь, от этого он в в ширину или в глубину поползёт. Ещё можно добавить возможность хождения по диагоналям, но это от графики зависит.
http://service.crazypanda.ru/v/clip2...z2MK44ZyXz.png

Вообще А* не обязательно работает с сеткой, он работает с любым графом.
Есть еще один классный способ, я читал о нем в презентации Valve. Суть примерно такая:
Вложение 31051
То есть тот же самый A*, но не по клеточкам, а по "навигационной сетке". Те участки карты, где ничего нет (или нет непроходимых препятствий) мы пересекаем по прямой, в те же где что-то нам мешает мы просто не заходим (препятствие занимает всю клетку, отведенную ему). Довольно просто на самом деле. Главное научиться разбивать свою карту при добавлении на нее объектов.

PS
Если нужен тот самый pdf с презентацией, погуглите по запросу "the ai systems of left 4 dead"

всем спасибо,скорее всего,буду отказываться от изометрической сцены)буду смотреть в сторону презентации left 4 dead, но она,правда,не особо подробно расписана:)

Для сетки Valve, предположу что подойдет алгоритм kD деревьев.

Как связана изометрическая сцена и презентация left 4 dead? это способ подходит для любой сегментированнной сцены, в том числе и для изометрической клеточной. 2д у тебя или 3д? если 2д то тебе нужно будет делать больше направлений у персонажа, иначе он боком будет ходить.

Меши и для 2д можно применять, причем это иногда даже предпочтительнее спрайтовой анимации, если камер (направлений) более чем одна. Да даже если одна. Помню анимацию, занимающую 2к атлас тупо стоящего персонажа.