Отслеживание на большой карте

Ответ 1

Так как число карт составляет 10.000 x 10.000, количество узлов равно 100.000.000. Использование простой реализации A * было бы непрактичным и, конечно же, не сделало бы игру масштабируемой в плане отображения.

Я бы порекомендовал вам использовать следующее решение, которое, по сути, вы думали:

HPA * (Иерархический путь A *). Этот метод создает различные иерархии карты. Вы можете автоматизировать процесс, заявив, что каждый блок размером 100x100 пикселей является регионом. Затем для каждого блока нам нужно найти смежные блоки и где записи и выходы для каждого блока. Если соединение между двумя блоками больше, чем node, то мы используем два узла для представления проблемы. Это изображение объясняет новый график, который мы пытаемся построить. (Черный = препятствие и серый соединяют узлы между блоками).

Этот метод обеспечивает хорошие результаты, как видно из исполнения с использованием карт из игры Baldur Gate с каждым блоком 10x10.

Подробнее читайте в этой статье от Натана Стертеванта (он является одним из самых успешных исследователей, занимающихся поиском путей, когда речь идет о играх). https://skatgame.net/mburo/ps/path.pdf

Для объяснения HPA, пожалуйста, проверьте эту лекцию Sturtevant (мин. 43:50 для HPA). https://www.youtube.com/watch?v=BVd5f66U4Rw

Кроме того, если вы хотите увидеть HPA * в действии, проверьте это видео, которое сделал Sturtevant: https://www.youtube.com/watch?v=l7YQ5_Nbifo

Ответ 2

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

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

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

• игрок не слишком быстро перемещается по карте и
• может быть допущена некоторая неточность.

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

Недостатком такого подхода является то, что он потребляет много ресурсов ЦП. Преимуществом является его простота.

Ответ 3

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

Ваша настройка требует уточнений. 10,000x10,000 все хорошо, но это утверждение не:

так как карта составляет 10 000 на 10000, существует 100 000 000 узлов

Почему для каждой единицы системы координат должно быть 1 node? Это не работает node pathfinding, вместо этого узлы должны быть более разреженными, а по их описанию описывают отдельные (разреженные) точки вдоль пути. Между точками node объект обрабатывает движение другими способами. Система отслеживания сетки может в худшем случае (если вообще никаких препятствий) иметь 100 000 000 точек, но поскольку Q упоминает узлы, я предполагаю, что это примерно node первопрохождения.

100 000 000 узлов

100 000 000 узлов - 381 мегабайт памяти, если int32 и 763 mb, если float64. Кроме того, существуют соединения node. Я понятия не имею, как они будут установлены в вашем случае, но для каждого соединения требуется 2 целых числа, скажем, по 2 байта. То есть. если существует столько связей, сколько узлов, требуется еще 381 мб. В общем, мы получаем данные графа ближе к одному терабайту, и я утверждаю, что наверняка что-то не так.

Как решить проблему, если у нас все еще есть огромный график node/огромная область? Я бы, вероятно, упростил, создав более крупные квадранты (как вы упомянули). Однако каждый квадрант будет удерживать узлы только вдоль 4 ребер - все узлы внутри квадранта будут заменены прямыми. Таким образом, можно было бы разрешить точки входа/выхода для каждого квадранта. Это будет отдельный график node для грубого расчета. Затем внутри квадранта всегда будет загружаться внутренний node граф для этого квадранта только во время. Ofc была бы некоторая ошибка invlued, но эй, что reallife, правильно? Если речь идет о человеческом поведении, то тогда он не всегда полностью оптимизирован.

Предварительные вычисления, кеш, скорость, малые данные - это ключевые слова в игровом кодировании.

Ответ 4

Итак, хотя на квадрате n на n может быть n^4 кратчайшие пути. для сохранения всех путей необязательно требуется пространство O(n^4). Идея состоит в том, что, учитывая два разных целевых местоположения на карте и их кратчайшие деревья путей, чем чем ближе эти две точки на карте, тем более общим элементам будут свои кратчайшие деревья путей. Это особенно верно при использовании планарной карты, такой как сетка с препятствиями.

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

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

У меня нет каких-либо серьезных фактов о том, сколько места для хранения требуется для хранения кратчайших деревьев путей и их различий, но это может быть в диапазоне O(n^2 log(n^2)). Загрузка одного и применение различий может иметь только временную сложность O(n^2).

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

Это решение может также содержать использованное кратчайшее дерево путей в памяти и при необходимости применять diff, чтобы получить новое кратчайшее дерево путей. Тогда сложность получения кратчайшего дерева путей не связана размером карты, а зависит от размера применяемых различий. Этот сценарий может действительно хорошо работать для таких игр, как оригинальный Sacred или Diablo.

Ответ 5

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

• Алгоритм, который предварительно обрабатывает сетку в графе, сворачивая большие пустые пространства в один node. Навигационные сетки разбивают проходящую область на выпуклые многоугольники, каждая из которых может быть пройдена за один шаг. L1 path finder объединяет препятствия вместе, сводя их к графику видимости, вычисляет путь по этому пути.

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

Ответ 6

Концепция высокого уровня может заключаться в том, чтобы найти точки начала и конца - например, точку (0,0) и точку (10000, 10000) - и сделать предварительное предположение для пути, идущего от начала до конца (в этом в случае, если он будет выполняться по диагонали по всему пути вверх и вправо). Затем начните проверку, чтобы увидеть, может ли он успешно добраться (если на этом пути есть препятствия). Если тогда программно выбрать аналогичные пути или поочередно найти, где путь терпит неудачу, и начать там, и попытаться выполнить итерацию до тех пор, пока он не будет работать, это может быть не на 100% быстрее, но вы получите намного лучшие результаты, чем найти все возможные способы, затем выведя кратчайший путь из этого.

Реализация

• Метод поиска начального кратчайшего пути
• Выполнить, чтобы увидеть, работает ли он
  • Если это не удается, попробуйте аналогичный путь или начните с отказа

Ответ 7

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