Алгоритмы нахождения пути - какой тут?
 

Всем привет.

Знаю, тема не раз поднималась..
Делаю игру, нужен оптимальный для АС алгоритм нахождения пути.
Я реализовал волновой, но он тормозит. В моем случае даже минимальные тормоза недопустимы. Задача усложняется тем, что конечная точка пути постоянно меняет положение, тоесть просчитывать путь нужно каждую секунду-две.

Вот мне очень нравится, как тут сделано: http://www.kongregate.com/games/pree...-tower-defense
Кто-нибудь скажет, какой алгоритм тут использован? В этом примере хоть конечная точка и не меняется, зато меняется расположение препятствий..

Ну и, наконец, если у кого-то готов алгоритм не тормозящий на АС, просьба поделиться. Авторства указать не могу, могу подкинуть чуток вебмани.
Имейл flashart (at) flashart (dot) com (dot) ua

Много раз обсуждали:поиск рулит. Этот алгоритм уже не раз писали на разных "языках", возьми и перепиши.

ссылка нерабочая

sinya, ты используешь плиточный мир(пр: pacman) или нет?

Если плиточный мир - это игровое пространство, разбитое на проходимые и непроходимые клетки, то - нет. Но из-за необходимости реализовать поиск пути пришлось переделывать в "плиточный", если я правильно понял этот термин.

2BigDan: Я со страхом ждал этой незамысловатой фразы "поиск рулит".. Я ведь сказал, что ознакомлен с ранними обсуждениями похожих вопросов на форуме. Но вот, допустим, обсуждение алгоритма, реализованного в tower defence (ссылку я выше дал), я на форуме не нашел.

Так кто что думает? =)

Возможно, в твоем случае надо использовать алгоритм Флойда. Если у тебя имеется постоянное множество точек, и конечная и начальная изменяются в пределах этого множества, то как раз с помощью алг-ма Флойда можно просчитать минимальные пути между всеми парами точек. Другое дело, что он более ресурсоемкий чем тот же волновой, но зато не придется пересчитывать каждые несколько секунд значение. Я реализовывал этот алг-м когда-то еще в 6м флеше для расчетов графов, но при большом количестве вершин были хорошие тормоза при расчете. Поэтому мозги выносить на серверные скрипты.

Не, спасибо, мозги на сервере - это не для меня.
Пацаны, в общем, вот пример волнового, который я сделал: http://politball.net.ua/1/ Там недоделано все, но поиск пути работает. Вот каждый раз, когда тормозит, включается пересчет оптимального пути.. Еще предложения будут?

Что-то очень тормозит для матрицы такой размерности.

А откуда вы знаете размерность матрицы?

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

так если плиточный мир, почему бы не взять какой-нибудь усовершенствованный astar? у него хорошая скорость, тормозов за ним не замечал(делал что-то вроде pacman)

народ, а есть какие-нибудь алгоритмы, которые ищут путь, не деля мир на плитки?

Может быть конечно отвечу запоздало, но тема вроде всегда актуальна. ИМХО в примере по ссылке используется не только клеточный алгоритм, но и хитТест :) Вывод сделан по тому, что во время игры пару раз смайлы проскакивали через стену. Глюк обработчика события наверно более реален, чем ошибка в расчете по алгоритму. :quiet: