помощь в стратегической игре: туман войны

Question

Я пытаюсь создать стратегическую игру в реальном времени, такую ​​как Starcraft или Age of Empire. мои карты должны поддерживать до 1500 объектов. Моя проблема возникает из-за того, как создать туман войны, не отставая от игры. Метод, который я сначала попробовал, состоял в том, чтобы просто рассчитывать расстояние до всех окружающих частей юнита каждый раз, когда он перемещался, но, как я и ожидал, это отставало, так как многие юниты будут постоянно двигаться. Если кто-нибудь знает более быстрый алгоритм тумана войны, пожалуйста, помогите. карты будут основаны на тайлах и хранятся в массиве.

Answer 1

Другое решение: биннинг для ваших сущностей.

Вы создаете относительно запасную сетку или даже квад-дерево.При заданных координатах (x,y) он позволяет найти за log(d) шагов все объекты, находящиеся в одной и той же (или соседних) ячейках, где d - это глубина вашего четырехугольного дерева.

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

Чтобы узнать, видна ли данная плитка карты или нет, вам просто нужно запросить в своемquad-tree.

Кроме того, quad-tree может быть полезным для других задач, не связанных с туманом войны.Например, вы можете захотеть найти ближайшего «работника» с указанными координатами (x,y) или хотите нанести некоторый урон по области всем подразделениям в регионе.

Answer 2

Очень простая реализация может быть следующей:

• Видимость задается значением v[i,j] для каждой плитки (i,j).Любое значение ниже определенного порогового значения находится в тумане.

• Значения обновляются с регулярными временными шагами (примечание: для этого не требуется высокая точность или высокая частота, кроме как для очень особенныхслучаи), используя следующие два шага:

  1. размытие текущей карты v[i,j]
  2. для каждого unit увеличение значения v[unit_i, unit_j] на постоянную величину.Вы также можете добавить постоянную сумму , если единица находится на квадрате (независимо от того, сколько их там).

Answer 3

Каждый раз, когда юнит перемещается, вы, вероятно, можете предположить, что он перемещается на соседний тайл, не так ли?В этом случае вы также можете предположить, что видимая область этого устройства также перемещается на одну плитку в том же направлении, поэтому у вас не должно возникнуть проблем с определением или обновлением области, которая должна быть видимой.В зависимости от радиуса обзора единицы, обновление только значений, которые требуют обновления, может, вероятно, сэкономить много ресурсов процессора.

Проблема может быть в области, которая должна быть размытой - может быть больше единиц, видящих одну и ту же плиткуно это можно решить, выполнив то, что предлагает Говард.