Поиск пути (Starcraft) Опции

[Baumanec]

прохождение объекта по "карте" (двумерный массив(булевский)) тру=можно фолс=нельзя.
Идея пришла уже как 2 месяца назад, но внятной реализации придумать не могу, всегда нахожу ситуации где она сорвёться...
Предлагаю обсудить алгоритм прохождения объекта по "карте" (двумерный массив(булевский)).

[Michael_Rybak]

эта задача - одна из классических.

не думаю, что тут есть особо что обсуждать. поищи (в гугле и здесь) "волновой алгоритм", "метод волны", "лабиринт поиск в ширину".

[andriano]

Для пошаговых стратегий - да. Еще советую "алгоритм Дейкстры".
Для реалтаймовых еще советую поискать алгоритм A*.

[Baumanec]

Ну как в старике устроенно это просто, там как бы наложение ландшафта, а потом при столкновении с юнитами уже меньше обсчитывать...

[Baumanec]

Или я вообще ничего не понимаю, но в первом же выпавшем алгоритме ошибка...
Алгоритм
Или я не прав...
А так принцип ясен, я совершенно в другую сторону думал...

[andriano]

Изложена ужасно неоптимальный вариант алгоритма.
До конца не читал, но начало, вроде бы, правдоподобное.

[Baumanec]

Там он волну запускает от старта, и собирает тоже...
А как экономней сделать, это ясно...

Сообщение отредактировано: Baumanec - 16.05.2008 21:43

[andriano]

Почему от старта?
Там конечной точке присваивается 0, а потом ищутся точки, совпадающие со счетчиком, начальное значение которого тоже 0, т.е. ищется, как и положено от конца к началу.

[Baumanec]

Блин действительно, чё-то я не разглядел, 3 раза читал, сам понял как делать, а казалось что тут ошибка, но после пяти раз я уже сам додумал.