Разделение A * пути многих юнитов на отдельные игровые фреймы

Question

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

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

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

Дополнительная информация: Это A * на прямолинейной сетке, запрограммированная с использованием C # и платформы XNA. Я планирую иметь потенциально до 50-75 единиц, нуждающихся в маршрутизации.

Спасибо.

Answer 1

Масштабируемость

Есть несколько способов оптимизации для этой ситуации. С одной стороны, вам, возможно, не придется делить на несколько игровых кадров. В некоторой степени кажется, что масштабируемость является проблемой. 100 единиц, по крайней мере, в 100 раз дороже, чем 1 единица.

Итак, как мы можем сделать путь более оптимизированным для масштабируемости? Ну, это зависит от вашего игрового дизайна. Я собираюсь (возможно, ошибочно) предположить типичный сценарий RTS. Несколько групп юнитов, каждая из которых находится относительно близко друг к другу. Путь решения для многих единиц в непосредственной близости будет довольно похожим. Модули могут запросить маршрутизацию от какого-либо решателя маршрутизации. Этот решатель маршрутизации может хранить таблицу недавних запросов маршрутизации и их решений и избегать расчета одного и того же вывода из одного и того же ввода несколько раз. Это называется памятка .

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

Многокадровые вычисления

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

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

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

В качестве альтернативы, вы можете спроектировать свои алгоритмы поиска пути так, чтобы они выполнялись дискретно. По истечении n шагов проверьте количество времени, прошедшее с момента запуска алгоритма. Если он превышает определенное количество времени, алгоритм маршрутизации сохраняет свой прогресс и возвращает. Затем вызывающий код может проверить, завершен ли алгоритм или нет. На следующем кадре возобновите алгоритм пути с того места, где он был. Повторите, пока не решено.

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

Использовать частичные решения

При любом из вышеперечисленных подходов вы можете столкнуться с вопросом о единицах, которым приказано пойти куда-нибудь на холостом ходу для нескольких кадров, прежде чем будет иметь полное решение для маршрутизации. Это может быть приемлемым и практически необнаружимым в типичных обстоятельствах. Если это не так, вы можете попытаться использовать неполное решение как есть. Если каждое неполное решение отличается слишком сильно, единицы будут вести себя довольно нерешительно. На практике эта «нерешительность» также может происходить недостаточно часто, чтобы вызывать беспокойство.

Answer 2

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

Я использую алгоритм расстояния в ширину, чтобы отследить отряды.Начните с пункта назначения и отметьте расстояние от него как 0. Любые соседние ячейки равны 1, соседние ячейки равны 2 и т. Д. Не проходите через препятствия и проложите путь по всей доске.Обычно O (A) временная сложность, где A - площадь досок.

Затем, когда вы хотите определить, в каком направлении должен двигаться отряд, вы просто находите квадрат с минимальным расстоянием до пункта назначения.O (1) временная сложность.

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