обход преград в warcraft е

← →
keal (2005-05-27 14:32) [0]

может кто-то знает какой алгоритм поиска пути и обхода преград используется в warcraft"е, ведь там все юниты имеют не квадратную основу, а круглую и все разных размеров.

← →
miek © (2005-05-27 14:39) [1]

Обычный волновой алгоритм, только перемещаться можно не по 4-м направлениям, а по всем 8-ми (или 6-ти, не помню). Для ускорения - пока юнит не попадет в тупик, волна делается небольшая, потом увеличивается.

← →
keal (2005-05-27 14:48) [2]

юниты не находятся на квадратах карты, они имеют дробные координаты и круглую форму. а если и находятся на квадратах, то многие из них занимают сразу несколько квадратов.

← →
XProger © (2005-05-27 15:08) [3]

keal, ты хочешь сказать что астар и волновик только для квадратных подходят?
ок... а как тогда в CS боты по вейпоинтам дорогу находят? ;)

← →
keal (2005-05-27 15:19) [4]

почему же, астар и волновик подходят для ячейки с 4, 6, 12.. направлениями. почти для любого.
а если координаты измеряються типа (14.77, 51.211).

← →
XProger © (2005-05-27 17:09) [5]

А если понять что ты программист и должен думать абстрактно?

← →
keal (2005-05-27 17:20) [6]

я и думаю абстрактно, или я думаю, что так думаю...

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

выхожу из положения используя волну и некоторые добавления для работы с картой.

можно предварительно обработать карту, но остаются юниты, которые появляются в динамике.

← →
XProger © (2005-05-27 17:28) [7]

Есть карта. Вся делится на квадратики. Квадратик может быть занят и свободен. Есть юниты которые квадратики не занимают, а просто не подпускают к себе никого и ничего ближе чем радиус их БиСферы.
Ищем путь по этив квадратикам (плевать как).
Юнит может находиться в нецелых координатах в квадратике
[trunc(PosX) div Size, trunc(PosY) div Size]
Где Size - размер одного квадартика. Далее игрок идёт к следующему квадратику т.е. поход на (Size, Size) относительно текущей позиции... и т.д. до самого конца.
При этом заметь, что варкрафте толпа двигалась не хаотично, а выстраивалась в определённый ряд чтобы друг-другу не мешать.

← →
keal (2005-05-27 17:39) [8]

они строятся в линию первого поворота или моста.
проведу пару эксперементов в варкрафте, уже больно классная там система перемещения унитов.

← →
OSokin © (2005-05-27 21:42) [9]

Имхо, можно так: вычисляется угол по касательной по прямой, по которой должен следовать чел, если произошел коллижен с каким-либо препятствием, то не пускаем чела дальше препятствия и постоянно вычисляем новый угол. Если старая и новая координаты совпадают, то применяем любой другой подход (можно просто поставить на время случайный угол), а потом снова начинаем вычисления угла. Немного трудоемко, но того стоит :-).

← →
keal (2005-05-28 15:33) [10]

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

сейчас пробую объеденить волну с углом.

← →
П7 (2005-05-28 16:25) [11]

Ну вот вы мне объясните, чем вам вей-поинты не катят?

Можно сделать так: искать путь любым "клеточным" методом - а потом срезать получившиеся "углы" проверкой - пройдет ли юнит по этому пути ничего не задевая. В сети помойму даже лежали примеры таких pf на паскале.

keal (28.05.05 15:33) [10]
Дык если застрянет, то

> применяем любой другой подход (можно просто поставить
> на время случайный угол), а потом снова начинаем
> вычисления угла

обход преград в warcraft е Найти похожие ветки