Реализация ходьбы в играх типа квест
 

Всем привет.
Вопрос такой: по какому принципу чаще всего реализуют передвижение персонажа по сцене в играх типа mechanarium (2д квест). Я имею в виду поиск пути, принцип построения карты и z-сортинг.
То есть что нужно иметь, чтобы персонаж переместился из пункта А в пункт Б по пути соблюдая определенные модели поведения (лесенки, прыжки и т.д.) с учетом того что карта не известна (генерируется динамически перед началом движения)
Я знаком с алгоритмом А* по поиску пути но для этого придется делить карту на дискретные элементы (тайлы по которым можно ходить). а этого не хочется, так как это не гибко.

Добавлено через 4 часа 12 минут
так. вроде понял в какую сторону копать.
не сталкивался никто с примерами пасфаинда в полигонах заданных векторами?

Ну неужели никто не сталкивался с данной проблемой? как блин сделать ходьбу универсальную в квесте? )))
я тут откопал что раньше был SCUMM язык скриптовый там были некие walking boxes но ничего более подробного не нашел (

как и писал A* требует дискретности карты, а графы требуют точек.. токо вот как эти точки получить?

почитай про графы, алгоритмов более чем достаточно

так вроде нашел.
http://algolist.manual.ru/games/smartmove.php - толковая статья
а на счет графов - как бы теперь сделать не прямыми и кривыми путь финальный. тоесть курвами )

Простое решение только одно:
- найти набор координат центров ячеек сетки, котрые входят в путь
- провести через найденные точки плавную кривую
(может http://bezier.ru поможет, хотя оно точно через точки кривые проводит, но этого может хватить)

нет никаких ячеек и сетки - карта векторная и произвольная как в робототехнике алгоритмы без дискретных элементов местности

Если бы Вы соблаговолили воспользоваться поиском по форуму:
http://www.flasher.ru/forum/search.php?searchid=2160628
там бы вы нашли:
http://www.flasher.ru/forum/showthread.php?t=113645

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