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

sinya · 18.04.2007, 19:46

Всем привет.

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

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

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

BigDan · 18.04.2007, 20:46

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

Терминатор · 19.04.2007, 16:31

Цитата:

Сообщение от BigDan

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

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

Sp1R1t · [+1 31.05.07]

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

sinya · 20.04.2007, 00:32

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

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

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

Sh@man · 20.04.2007, 01:42

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

sinya · 20.04.2007, 03:02

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

Sh@man · 20.04.2007, 16:34

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

sinya · 20.04.2007, 20:24

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

Sh@man · 21.04.2007, 17:36

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