Pathfinding На огромной карте

Question

Мне нужен какой-то тип поиска пути, поэтому я искал в Интернете и нашел некоторые алгоритмы.

Кажется, что им тоже нужен какой-то тип карты. Эта карта может быть представлена:

• Сетка
• Узлы

Как моя карта в настоящее время довольно огромный (20,000 х 20,000 пикселей), отображение сетки 1 х 1 РХ плитки приведет до 400.000.000 уникальных точек на сетке, а также лучшего качества, которое я бы подумал. Но то способ много очков для меня, так что я мог либо

• увеличить размер плитки (например, 50 х 50 точек = 160.000 уникальных точек)
• переключатель для Узлов

Как 160.000 уникальных точек также для меня, или, я бы сказал, не качество, которое я хотел бы иметь, поскольку некоторые единицы больше, чем 50 px, я думаю, что Nodes - лучший способ пойти.

Я нашел в Интернете 2D Nodal Pathfinding without a Grid и сделал некоторые расчеты:

local radius = 75        -- this varies for some units so i stick to the biggest value 
local DistanceBetweenNodes = radius * 2   -- to pass tiles diagonaly 
local grids = 166        -- how many col/row 
local MapSize = grids * DistanceBetweenNodes -- around 25.000 
local walkable = 0        -- used later 

local Map = {} 

function even(a) 
    return ((a/radius) % 2 == 0) 
end 

for x = 0, MapSize, radius do 
    Map[x] = {} 
    for y = 0, MapSize, radius do 
     if (even(x) and even(y)) or (not even(x) and not even(y)) then 
      Map[x][y] = walkable 
     end 
    end 
end 

без удаления непроходимым узлов и размер блока 75 я бы в конечном итоге с ~ 55445 уникальных узлов. Узлы резко сократятся, если я удалю недоступные узлы, но поскольку мои юниты имеют разные размеры, мне нужно сделать радиус самой маленькой единицей, которую я получил. Я не знаю, будет ли это работать с более крупными единицами позже.

Так что я снова искал в Интернете и нашел это Nav Meshes. Это уменьшит количество узлов до «нескольких» в моих глазах и будет работать с любым размером блока.

ОБНОВЛЕНИЕ 28.09 Я создал узловую карту всех проходимых областей теперь ~ 30.000 узлов.

Вот совершенно случайно пример карты и точки у меня есть: Example Map

Answer 1

Это требует некоторой оптимизации, а также уменьшить количество узлов у вас есть.

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

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

В конце дня я предлагаю вам сократить количество узлов, просто разместив узлы в организованном пути, где вы знаете, что можно добраться из точки A в B, указав соседей. Тем не менее, вам нужно вручную создать путь к узлу для каждого уровня.Возьмите мой тест в качестве примера (Там нет стен, только путь узла):

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

Который имеет около 50 узлов, по сравнению с сотнями, которые могут иметь сетки.

Это может работать на любом масштабе, так как количество узлов резко сокращается по сравнению с подходом к сетке. Вам нужно будет внести некоторые корректировки, такие как вычисление расстояния между узлами, теперь, когда они не находятся в сетке. Для этого теста я использую алгоритм dijkstra в Corona SDK (Lua), но вы можете попробовать использовать любую другую, такую ​​как A-star (A *), которая используется во многих играх и может быть быстрее.

Я нашел пример единства, который принимает подобный подход с использованием узлов, и вы можете видеть, что этот подход работает в 3D, а также: