길 찾기 거대한지도에서

Question

나는 길 찾기를해야하기 때문에 인터넷을 검색하여 일부 알고리즘을 발견했습니다.

그들은 모두지도의 유형을 필요로하는 것처럼 보입니다. 이 맵으로 표현 될 수있다 :

• 그리드
• 노드 내지도 (20,000 X 20,000 픽셀), 이어질 것 1 개 1 픽셀 타일의 격자지도는 현재 매우 큰이므로

400.000.000 유일한 그리드 포인트와 최고의 품질이라고 생각합니다. 그러나 나를 위해 많은 포인트 그게 방법은 그래서 나도

• (예 : 50 × 50 픽셀 = 160.000 독특한 점)
• 스위치 노드에 타일 크기를 늘릴 수있는 160.000 독특한 점으로

나에게 많은 도움이된다. 또는 내가 말하고자하는 것은, 내가 갖고 싶은 품질이 아니라, 어떤 유닛이 50 px만큼 크다. 나는 노드가 더 좋은 방법이라고 생각한다. unpassable 노드와 내가 ~ 55,445 고유의 노드로 끝날 것 (75)의 단위 크기를 제거하지 않고

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 

:

은 좀 계산을 인터넷 2D Nodal Pathfinding without a Grid에이를 발견했다. 내가 비파괴적인 노드를 제거하면 노드가 급격하게 줄어들지 만, 다른 유닛의 크기가 다르기 때문에 반경을 최소 단위로해야합니다. 나는 이것이 나중에 더 큰 단위들과 함께 작동하는지 안다.

그래서 인터넷을 다시 검색 한 결과 Nav Meshes입니다. 이렇게하면 노드가 "약간"으로 줄어들고 모든 단위 크기에서 작동합니다. 지금은 모든 무난 지역 ~ 30.000 노드의 노드 맵을 만들었 28.09

UPDATE.

여기지도의 완전히 무작위 예이며, 포인트는 내가 가지고 : Example Map

Answer 1

이 몇 가지 최적화를 호출하고, 당신이 가지고있는 노드의 양을 줄일 수 있습니다.

거의 모든 길 찾기 알고리즘은 그리드가 아닌 노드 목록을 사용할 수 있습니다. 하지만 노드 사이의 거리를 조정해야합니다.

그리드 크기를 늘려 사각형이 많지 않게 할 수도 있습니다. 당신은 어떤 종류의 방법으로 작고 좁은 길을 보상해야 할 것입니다.

결국 노드를 배열 된 경로에 배치하여 노드 수를 줄이는 것이 좋습니다.이 노드에서는 지점 A에서 B까지 이웃을 지정하는 것이 가능하다는 것을 알고 있습니다. 하지만 모든 레벨에 대해 수동으로 노드 경로를 만들어야합니다.예를 들어 내 시험을 (더 벽이 없다, 단지 노드 경로) :

: 당신 제공하는지도 들어

, 당신이 유사한 경로 노드로 끝날 것

그리드가 가질 수있는 수백 개의 노드와 비교하여 약 50 개의 노드가 있습니다.

그리드 방식에 비해 노드 수가 대폭 줄어들 기 때문에 모든 규모에서 작동 할 수 있습니다. 노드 사이의 거리를 계산하는 것과 같이 그리드에 있지 않도록 조정해야합니다. 이 테스트를 위해 나는 코로나 SDK (루아)에서 dijkstra 알고리즘을 사용하고 있지만 많은 게임에서 사용되는 A-star (A *)와 같은 다른 것을 사용해 볼 수 있으며 빠를 수 있습니다.

나는 노드를 사용하여 유사한 접근 방식을 취하고 유니티 예를 발견하고는 접근뿐만 아니라 3D로 작동하는지 볼 수 있습니다