Сообщений в теме: 5

[Terminus]

В общем так. Добавив монстров, обнаружил очень неприятный артефакт. Если восемь монстров окружают игрока, то девятый (например) просчитывает путь к игроку, и не находит его (разумеется). Суть в том, что путь к точке, которая недостижима, расчитывается очень долго, 21мс. Тоже самое произойдет, если мы попытаемся направится к точке, которая заведомо недостижима. Короче, плохо. Для обхода этого момента я вынужден пойти на следующие ограничения:

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

Впрочем, при некоторых условиях все вышеперечисленное может сойти за фичи

[Araton]

21 милисекунда это разве долго?=)

[Terminus]

Это очень долго. Средний путь на 20-30 клеток считается за 1-1.5мс. Даже это не очень хорошо, ведь ежесекундно надо будет расчитываеть сотни путей, что в результате может обернуться лагами.

[Terminus]

Небольшое уточнение. Ограничение на длину пути как такового не будет. Будет только ограничение на арсстояние до конечной точки расчета пути. Она должны вписываться в квадрат 64x64 вокруг существа. Т.е. примерно в радиусе 32 клеток. Это полная ширина экрана.

[device]

Я немного знаю, что такое поиск пути, правда я алгоритмы писал для графов. А тут все маршруты динамически меняться могут. То есть пересчитывать надо для каждого монстра маршрут после каждого шага. В играх делают упрошенные алгоритмы. Очень часто.
В частности я сейчас играю в DarkEden, там монстры ходят довольно-таки тупо, но эффективно. Они просто прут в сторону врага, по мередохождения до препятствий - пытаются их обходить, часто с приоритетом против часовой стрелки. Непрограммисты не замечают в таком "интелекте" монстров ничего необычного. Но всю траекторию монстра от начала до конца пути монстра комп не считает. Для перса тоже самое примерно. Если препятствие большое и в радиусе зрения нет пути его обхода, то никакого обхода и не будет.
Радиус зрения тоже большим назвать там трудно. Наверное клеток 8 во все стороны (16 на 16).
В каждой локации куча монстров и людей, локаций тоже куча... тут явно упрощение алгоритма требуется.
Ну например монстр доходит до препятствия и упирается в него - срабатывает случайный генератор и он начинает движение вокруг препятствия по часовой стрелке или против часово стрелки. если после нескольких шагов (пусть тоже случайность срабатывает) он не приблизился к цели, то может попробовать другое направление...
-----------------------
В общем я это к чему. Предлагаю обойтись алгоритмом, который не будет считать всю трассу монстра, а только определять направление его движения в двнный момент.

[Terminus]

Не, все таки хочется полный и честный маршрут иметь
В принципе, меня и сейчас маршрутизация не сильно напрягает, но один добрый человек работает сейчас над своей реализацией, основанной на A*, и если результат будет хотя бы в 2-3 раза быстрей, я буду доволен