Перейти к содержимому


Внимание!

Это форум по извлечению ресурсов из игр: музыки, звуков, текстур, 3D-моделей...
Перед поиском ответов на форуме, рекомендуется ознакомиться с основным сайтом EXTRACTOR.ru!
[ Прочтите внимательно - правила создания тем и ответа в них ]
Все вопросы по запуску игр задавайте в другом месте: Установка и запуск игр.


Фотография

Новые обстоятельства....


  • Авторизуйтесь для ответа в теме
Сообщений в теме: 5

#1 Terminus

Terminus

    Генерал-майор

  • Администраторы
  • 1969 сообщений
  • Пол:Мужчина
  • Город:Санкт-Петербург

Отправлено 14 August 2004 - 00:08

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

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

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

#2 Araton

Araton

    Подполковник

  • Доверенные
  • 449 сообщений
  • Город:Эстония,г Силламяэ

Отправлено 14 August 2004 - 07:44

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

#3 Terminus

Terminus

    Генерал-майор

  • Администраторы
  • 1969 сообщений
  • Пол:Мужчина
  • Город:Санкт-Петербург

Отправлено 14 August 2004 - 11:33

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

#4 Terminus

Terminus

    Генерал-майор

  • Администраторы
  • 1969 сообщений
  • Пол:Мужчина
  • Город:Санкт-Петербург

Отправлено 14 August 2004 - 20:59

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

#5 device

device

    Старший сержант

  • Доверенные
  • 58 сообщений

Отправлено 19 October 2004 - 12:15

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

#6 Terminus

Terminus

    Генерал-майор

  • Администраторы
  • 1969 сообщений
  • Пол:Мужчина
  • Город:Санкт-Петербург

Отправлено 19 October 2004 - 14:33

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