Алгоритм динамического прохождения для игры Tower Defense

Я делаю Tower Defense, и мне нужен хороший алгоритм для этого пути.

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

Я пишу код на C #, если это помогает.

Как правило, вы захотите использовать A *, если вы не ищете что-то важное другое.

Мне нужно было решить аналогичную проблему: поиск пути в большой лабиринтной сетке с постоянно меняющимися «затратами» и барьерами.

Дело в том, что в игре Tower Defense количество сущностей, для которых необходимо решить путь, обычно намного больше, чем количество узлов в графе. * Не самый подходящий алгоритм для обработки этого, потому что вам придется решать его заново каждый раз, когда что-то меняется. Что ж, это уместно, если вам нужно найти только один путь, но в моем случае мне нужно было иметь возможность обрабатывать объекты, которые могут появляться в разных местах, и у каждого есть свой собственный путь.

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

Итак, в начале игры я просто запускаю этот алгоритм на всех моих «целевых» узлах. Затем, всякий раз, когда один узел изменяется (например, становится непроходимым), я просто запускаю его на этом узле, и изменение распространяется на все узлы, которые будут затронуты, а затем останавливается. Таким образом, нет необходимости в глобальном пересчете, и алгоритм полностью независим от числа объектов, которым потребуется поиск пути.

Мой алгоритм был в основном что-то вроде (псевдокод):

update_node method in Node class:
    $old <- $my_score
    find $neighbor node among all neighbors such that
        $neighbor.score + distance_to($neighbor) is minimal
    $my_score <- $neighbor.score + distance_to($neighbor)
    $next_node <- $neighbor
    if ($my_score != $old)
        for each $neighbor
            $neighbor.update_node()

С начальным счетом в зависимости от того, является ли узел целью или каким-то барьером.

Алгоритм маршрута, который я использовал на моем TD, был обратным от обычного A * пути из-за количества объектов, которые я имел в игре. Вместо того чтобы идти от цели к плохим парням, я направлялся от цели к каждой пустой клетке на доске.

Это не займет много времени, вы просто продолжаете итерацию на доске, пока не найдете свои «затраты», и это обеспечивает хорошую обратную связь для заблокированных маршрутов (если вы делаете это). Использование алгоритма Флойда является быстрым и дружественным к кешу по сравнению с A *, так как он не выполняет поиск, зависящий от данных, он просто загружает и обрабатывает данные в потоках.

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

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

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

Поиск пути быстр, и на чем-то похожем на нормальную игру Tower Defense, у вас не будет проблем с полным проходом A * или Dijkstra всякий раз, когда что-то меняется. Мы говорим хорошо за миллисекунду для полного обновления. Любой вид адаптивного поиска пути оказывается ужасно сложным. Просто сделайте это простым способом, если только вы не строите самую большую в мире сетку защиты башни.

Как работает A * pathfinding? может быть хорошим местом для начала :-)

Это может быть излишним для вашего решения, но подумайте о маршрутизации назад, а не вперед.

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

Навигация по путевой точке, вероятно, будет лучшей для игры в формате td, потому что, как правило, в зависимости от уровня, ai следует по прямому пути. По сути, вы устанавливаете свои узлы или путевые точки, затем направляете точку «ai» к путевой точке и идете к ней, как только она приблизится к ней достаточно, чтобы перейти к следующей путевой точке, повернуться лицом к ней и двигаться к ней.

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

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

Простое решение - обмануть.

Разработайте карту заранее, чтобы убедиться в отсутствии тупиков. Затем на каждом перекрестке добавьте триггер, который заставляет персонажа выбирать маршрут (пример: всегда поворачивать налево, всегда поворачивать направо или случайно).