안녕하세요, Badump입니다.
제가 1~2달 전에 올리기로 약속했던 길찾기 말인데... 드디어 올리게 되었네요.
1. 소개, 목표와 문제
2. 전통적인 해결 방법과의 비교
3. 첫 시도
4. 적용
5. 갑작스러운 문제
6. 최적화
7. 2차 시도
8. 아이디어
9. 우리가 유지한 것
10. 갑작스러운 문제가 해결된 방법
11. 진형
12. 목표
13. 적용
14. 문제
15. 장애물 회피(길찾기가 바뀐 이유)
16. 유닛 움직임
17. 목표
18. 적용
19. 대역너비 고려
20. 군집
21. 3개 중 2개의 시나리오 채택
22. 전체적인 최적화, 문제가 발생한 곳
23. 조직화
소개, 목표와 문제
이제 모두가 아시겠지만, 생츄어리는 수천에서 수만 단위의 유닛들을 조종하는 스케일에서 게임을 플레이할 수 있는 것을 목표로 하고 있습니다. 유닛들이 맵 끝에서 끝까지 한 줄로 늘어서는 명령을 내려도 성능 문제 없이 잘 돌아가는 게임을 만드는 것이죠. 그래서 이것을 어떻게 해야 할까요? 일정한 규칙 없이 단순히 하나로 뭉쳐 움직이게 만드는 것은 비효율적이었습니다.
만약 포병대가 전차 유닛보다 빠른 경우, 적한테 먼저 돌진했다가 죽는 일이 발생하지 않도록 적어도 최소한의 조직화가 필요했죠. 그래서, 이 부분은 대부분이 진형 코드에 의해서 다루어지게 되었습니다.
유닛들이 어떻게 움직이냐를 다룰 때, 종류 별로 고려해야만 하는 특징이 많습니다. 물 위를 지나다닐 수 있는 호버 탱크들부터, 급강하 폭격기, 뭐 그런 것들 말이죠. 솔직히 말해서 상당히 많은 편입니다.
게다가 길찾기 코드는 수천 수만의 유닛들과 대형 맵들을 감당할 수 있어야만 합니다. 가장 큰 문제는, 위에서 나열한 조건들이 모두 동시에 이루어져야 한다는 것이었습니다. 길찾기와 다른 두 요소들이 동시에 작동해야 한다는 것은 이 분야에서의 도전을 더 어렵게 만들었고요.
그리고 이 마지막 이유가 바로 우리가 단순히 기존에 존재하는 해결 방법을 가져와서 끼워넣을 수 없는 이유였습니다.
전통적인 해결 방법과의 비교
길찾기에서 가장 먼저 떠오르는 건 무엇인가요? A*? Flowfield?
캐슬 스토리의 개발자들이 올린 단계적 길찾기(HPA)에 관한 정리글https://www.gdcvault.com/play/1025320/Hierarchical-Dynamic-Pathfinding-for-Large ?
어떻든 간에, 가장 먼저 떠오르는 것은 적어도 A와 B 사이의 길은 장애물을 피해야 한다는 것일 겁니다. 그리고 보통 그 일에 쓰이는 가장 인기가 좋은 알고리즘이 A*고요. 충분히 효율적인 물건이지만, 애석하게도 맵의 넓이에 비례해서 성능이 떨어지는 고약한 단점이 있습니다. 예를 들어서 맵 크기가 5x5라고 했을 때 성능 저하가 25 정도라면, 맵 크기가 40x40까지 갔을 때 성능 저하는 1600에 달하는 식입니다.
이 성능 저하는 프레임에 반비례하는 가상의 유닛으로 측정된 것입니다
문제는 그것뿐만이 아니었습니다. 맵의 크기가 커질수록 유닛들의 숫자도 대개 늘어나게 된다는 것이었죠. 5x5의 맵에서 두 명의 플레이어가 각각 50개씩 유닛을 조작한다고 했을 때의 결과는 2 곱하기 50 곱하기 25 = 2500이었습니다. 그리고 40x40의 맵에서 16명의 플레이어가 각각 500유닛씩 조작한다고 했을 때의 결과는 1600 곱하기 10 곱하기 500 = 8000000이었죠. 즉, 스케일이 커질수록 랙 또한 기하급수적으로 증가합니다.
이제 우리가 이 문제를 어떻게 해결할 수 있을지 알아봅시다. 비교적 쉬운 해결책은 3가지입니다:
각각의 연산에 드는 비용을 감소시킨다(= 모든 걸 10배정도 빠르게 만든다)
유닛 또는/혹은 플레이어의 수를 줄인다
지도의 크기를 줄인다
이제 각각의 해결책을 한 번 살펴보도록 합시다.
첫 번째 방안의 문제는 우리가 성능 저하를 10분의 1로 줄인다고 한들, 연산 비용이 여전히 너무 크다는 것이었습니다. 첫 번째 예시와 동등한 성능을 뽑아내려면 적어도 100배는 더 빠르게 만들 필요가 있었죠.
두 번째 해결책은 생츄어리의 컨셉 자체에 반하는 것이었습니다. 우리가 게임의 스케일을 가장 중요시하는 것은 아니지만, 지나치게 마이크로 컨트롤에 치중하는 게임도 원하지 않았으니까요.
세 번째 해결책의 문제는 해결책 자체가 성능 문제의 주된 원동력이었다는 것이었습니다. 맵 크기를 줄이는 것이 성능적으로 가장 크게 개선은 되겠지만, 좁은 맵에서 많은 유닛들을 넣을 수는 없으니까요. 우리의 상황에는 적절한 해결책이 아니었죠.
그렇기에, 우리는 2번과 3번 방안의 장점들을 합치면서도 단점을 가지지 않는 해결책이 필요했습니다. 그렇다먼 그것을 어떻게 해야 할까요?
앞서 언급한 Flowfield들이 무엇인지, 그것들이 어떻게 문제 해결에 도움을 줄 수 있을지에 대한 설명부터 시작해봅시다.
이름에서도 알 수 있듯이, 이들은 맵 전체에 걸친 일종의 영역입니다(field).
이미지에서 나온 것처럼, 이 영역은 당신이 어느 위치에 있던 상관 없이 목표 지점으로 향하는 가장 적절한 길을 가리키는 화살표를 형성합니다. 예를 들어서 미궁이 등장하는 게임에 당신이 플레이어로 있고 Flowfield가 보인다고 가정했을 때, 이 화살표들을 따라가기만 하면 목적지에 도달할 수 있게 되는 것이죠.
목적지로 향하는 길 자체가 없어서 화살표가 나타나지 않는 경우를 제외한다면요.
이제 이 방식이 어떤 식으로 작동하는지 대략적으로 이해하셨을 겁니다. 남은 문제는 이게 성능에 어떤 식으로 도움을 주냐는 것이겠죠? 음, 앞서 예시에서 설명했듯이, 원래는 각각의 유닛들은 목표 지점까지 알아서 길을 찾아야 합니다. 하지만 Flowfield가 있다면 더는 아니죠. 이젠 유닛들이 Flowfield에서의 현재 위치를 보는 것만으로도 길을 찾을 수 있으니, 유닛이 얼마나 많던 간에 상관 없이 길찾기로 인한 성능 저하가 거의 나타나지 않습니다.
정말 좋아보이지만, 아직은 좀 이릅니다. 제가 Flowfield에 대해서 아직 설명 안 한 게 있어요. 필요한 연산의 양을 바꿀 수도 있는 변수죠. 원래의 연산이 전체 유닛 수 곱하기 맵의 넓이라는 점을 기억해봅시다.
여기서 질문을 하나 하겠습니다: 각각의 유닛이 어디로 가게 될까요? 그 유닛들의 목표 지점은 어디일까요? 앞서 제가 Flowfield들이 하나의 위치를 향해 이어진다고 이야기한 것을 기억하실 겁니다. 그렇다면, 두 개의 유닛들에게 서로 다른 목적지를 주면 무슨 일이 일어날까요? 이런 상황에서, Flowfield는 A*에 비해 별로 나을 것도 없는 방식이, 아니, 더 안 좋은 방식이 되어버립니다. 단일 유닛의 경우에는 오히려 A*보다 연산이 느리니까요.
현실적으로 우리가 계산을 위해서 실질적인 유닛의 개수를 줄이긴 했지만 1은 아니고, 무시할 정도로 작지도 않습니다. 특히 AI가 100000 APM으로 개입할 때는 말이죠. 어찌되었든 이 이상 개개의 유닛별 연산을 줄이는 건 불가능하니, 다른 접근법을 택해보도록 합시다.
그리고 두 해결책 모두 목표물에 대한 접근 여부를 가늠하는 것에는 좋은 방법이 아닙니다. 유닛이 목표 지점에 도달할 수 없더라도 시간을 낭비하게 될 테니까요. 섬의 경우를 한번 상상해봅시다.
단계적 길찾기 (한번 읽어보시는 것을 추천드립니다!)를 끝내고 다시 돌아오겠습니다.
간단하게 요약하자면:
Hpa*의 목표는 엄청나게 큰 월드, 너무 커서 1 유닛 이상으로 길찾기를 걱정할 시간도 없는 월드들과, 지속적으로 바뀌는 지형을 감당하기 위한 것입니다.
앞서 설명한 방법들이 바뀌는 지형, 그러니까 벽이나 공장을 세워 길을 가로막는 등의 변화를 감당할 수 있을 리가 없으니, 여기서 Hpa* 가 등장합니다.
맵이 전처리되는 방식 때문에 우리는 오직 맵의 변화된 부분만 업데이트가 가능하고, 매번 길찾기를 조회할 때마다 우리는 그에 맞게 업데이트된 진로를 설정받게 됩니다. A*와 비교했을 때 이는 큰 변화인데, 이제 맵 전체를 염두에 두고 진로를 만드는 대신 작은 부분들만 설정해 목적지에 도달할 수 있기 때문입니다.
불운하게도, 이게 연산을 훨씬 줄이긴 하지만, 우리 게임에서 수행하는 연산은 훨씬 더 많은 처리량을 필요로 하고, 그렇기에 Hpa*는 대형 맵에서만 제대로 효과를 발휘합니다. 맵이 작아질수록 성능도 저하되죠. 그리고 연산 비용은 유닛이 길을 찾는 동안 계속 일정하게 유지되는데, 썩 나쁘다고는 할 수 없지만 썩 좋은 점도 아닌 특징입니다. 그럼에도, 수만 수천 개의 유닛들에게 길을 찾아주는 건 연산을 많이 필요로 할 수밖에 없습니다. 일단, 제가 길찾기를 처음 시도한 과정을 한번 보도록 하죠.
1차 시도
적용
우리가 첫 번째로 해야 하는 것은 navmesh를 설정하는 것입니다. 앞서 설명했던 것처럼, 여기에는 일정한 위계가 존재하고요. 이걸 어떻게 코딩하냐고요? 우선 맨 아래에서부터 시작해봅시다. 첫 단계는 단순히 지형을 가져다 노드로 만드는 것입니다. 그리고 각각의 4x4 사각형을 또다른 윗 단계로 묶고, 이 과정을 반복하는 것이죠.
(1)
4의 크기는 상대적이니, 얼마든지 바뀔 수 있습니다. (지금은요. 나중에는 이것도 중요해질 겁니다)
이제 몇 개의 장애물을 추가해줍시다.
(2)
이제, 각각의 노드들이 어떻게 하면 첫 단계에 지어질 수 있을지 찾아야 합니다.
(3)
각각의 색깔은 서로 다른 영역을 나타냅니다. 서로 다른 색의 영역으로 넘어갈 수는 없고요. 하지만 이건 어디까지나 1단계에 불과하고, 좌측과 우측 셀 사이에는 장애물이 없습니다. 그러니 다음 단계로 넘어가봅시다.
(4)
간단하게 요약해서, 우리는 현재의 위치와 목적지가 같은 색깔인지만 보면 됩니다.
여기서부터는 조금 더 기술적인 설명입니다. 첫 단계의 각각의 셀에서, 우리는 이웃한 셀의 리스트를 만듭니다. 그러니 가장 작은 칸은 위, 아래, 좌, 우로 오직 4개나 그 이하의 이웃만을 가지게 되죠. 사실 나중에 보면 되기 때문에 굳이 목록을 만들 필요는 없지만, 일단 리스트가 있다고 가정해둡시다. 더 큰 노드들의 경우에는 이런 식으로 넘길 수는 없습니다. 그리고 사각형이 막혀있는 경우에는 이웃이 아닙니다. 다만, 이웃이 없는 노드들도 존재할 수 있습니다. 가장 높은 단계의 노드부터 그럴 테니까요.
다음으로, 우리는 말하자면 사각형을 ‘채우는’ 작업을 하게 됩니다. 그리고 채워진 노드들을 통해 새로운, 윗 단계의 노드를 만드는 것이죠, 사진에서, 모든 녹색, 적색 사각형들은 새로운 윗 단계의 노드를 형성하게 됩니다. 이제 이 노드들은 오직 같은 기반 노드의 사각형들만 포함할 수 있게 됩니다.
자, 이제 한번 요약해서 정리해봅시다:
기반 노드: 사각형 전체입니다. 아랫 단계의, 그리고 같은 단계의 여러 노드들을 포함하고 있습니다.
노드: 적색 또는 녹색으로 칠해진 영역입니다. 예를 들어서, 3번 사진에서 2단계 노드는 녹색과 적색 영역 전체입니다. 3단계 노드는 4번 사진의 녹색과 적색 영역 전체를 포함합니다. 4번 사진에는 모두 합쳐서 2개의 3단계 노드, 3번 사진에는 3개의 2단계 노드가 존재하죠.
‘이웃’은 모든 같은 단계의 노드들로, 아이들의 이웃들의 부모라고 할 수 있습니다.
조금 더 쉽게 설명하자면: 내 친구들은 내 아이들의 친구들의 부모라고 할 수 있죠 (친구들이 전부 또래라는 가정 하에서요). 즉 내가 아이들과 직접 친구인 것은 아니고, 아이들도 마찬가지입니다. 아이들의 부모는 각각 하나씩이죠. 아니면 그건 버그니까요.
계속해서, 당신이 1단계 노드로 2단계 노드들을 만들었을 때, 당신은 한 단계 위로 올라갑니다. 이제 가능한 최대 단계의 노드에 도달할 때까지 그 과정을 반복하게 되죠. 그 한계는 시작 시에 미리 정해진 상태입니다. 이제 이 방식이 a에서 b까지 길을 찾을 때 어떻게 적용되는지 알아봅시다. 답은 단순합니다: 같은 ‘부모’가 발견될 때까지 계속해서 부모 노드를 확인하는 것이죠. 찾는다면 길이 존재하는 것이고, 아니라면 가능한 길이 없는 것입니다. 이 과정은 단계 처리를 거의 즉발적인 과정으로 바꿉니다. 뭐, 적어도 로그와 거듭제곱의 차이 정도로는요. 맵이 5000 유닛 크기라고 했을 때, 노드 크기가 4개라면, Hpa*는 400만배 더 빠른 처리 속도를 자랑합니다. 맵의 크기가 10배 증가하고, 노드가 8개라면, 이제 50만배 정도 더 빠른 수준으로 변하죠. 단, 이 처리 과정은 어디까지나 길이 존재하는지의 여부를 알아내는 데 필요한 것이지, 순회 자체의 과정은 아닙니다.
이제 진짜 길을 찾는 과정에 대해서 알아봅시다. 우선 시작하기 위해서, 우리는 가장 가까운 위치에 있는 공동의 부모 노드를 찾아야 합니다. 그 다음에, 우리는 그 노드의 자식 노드로부터, 우리가 가기를 원하는 부모 노드까지 통하는 길을 찾아야 하죠. 크기가 4나 그 이상인 대신 2라면 이 과정은 조금 쉬워지는데, 길을 실제로 찾는 대신 위/아래/좌/우 중 하나를 선택하기만 하면 되니까요. 사실 길을 찾는다 하더라도 그리 어렵지는 않은데, 각각의 단계마다 작은 그리드에서 길을 찾는 것이기 때문입니다. 그렇기 때문에 노드의 크기와 순회에 필요한 시간에 어느 정도 균형을 맞추는 것이 필요하고요.
예를 들어서, 1024x1024 사이즈 맵의 경우 log2(1024) = 10 단계가 필요합니다. 하지만 노드 크기가 4일 때는 log4(1024)로 5단계만 필요하죠. 노드 크기를 16으로 늘린다면 2.5단계면 충분하겠지만, 0.5단계를 만드는 건 불가능하기 때문에 반올림해 3단계를 거치게 됩니다.
애석하게도, 순회 단계에 연산이 많이 소모되는 것은 아니지만 그렇게 가볍지도 않습니다. 제 컴퓨터에서도 해당 접근법을 사용했을 때 20000개의 유닛 이상부터는 성능 저하가 발생하기 시작했죠. 최적화를 하면 좀 더 끌어올릴 수도 있지만, 여전히 부족했고 다른 문제도 있었습니다.
갑작스러운 문제들.
문제들 중 하나는 이 방식이 단계적인 구조를 형성하지만 다음 단계의 큰 노드만 인식하기 때문에, 좀 더 정확한 해결 방식이 필요할 때는 문제로 다가온다는 것입니다. 여기 예시를 들어서 설명하자면, 녹색에서 적색으로 가는 길이 필요하다고 합시다. 가장 위쪽의 단계에서, 그 길은 이렇게 나타나게 됩니다.
보시다시피 검은색의 길이 산출되지만, 실제로는 보라색이 더 정확하죠. 이게 아직 2단계의 진로고, 그렇기에 3단계 부모 노드 안에 있는 2단계 노드들 사이의 길이라는 점을 고려하면, 이 길을 다듬는 건 꽤나 골치아플 겁니다. 일반적인 상황이 아니니까요.
그리고, 또다른 문제도 있습니다. 여기 예시를 보여드리죠.
검은색의 진로는 우리가 통상적으로 가게 되는 길입니다. 우측으로 가라는 명령을 받았으니, 가장 가까운 길이 바로 오른쪽에 있으니까요.
보라색은 대신 우측 아래의 노드(여전히 같은 부모 노드 안에 포함된)으로 가라고 명령을 내렸을 경우의 길입니다.
그리고 주황색은 우리가 그 길을 다듬었을 경우고요.
왜 우리가 검은색 길을 다듬지 않았냐고요? 음, 문제는 우리가 검은색 길의 실행된 첫 부분만을 인지하고 있다는 겁니다. 그러니까 저 회색 선을 넘기 전까지는, 어디로 갈지 우리도 모르는 거죠. 미리 계산을 해두는 식으로 그 문제를 해결할 수도 있겠지만, 더 멀리 나갈수록 필요한 계산의 횟수도 많아집니다. 캐싱을 통해 어느 정도 해결할 수는 있지만, 더 많이 사전 계산을 할수록 길이 바뀔 때 문제가 생길 가능성이 높아지죠. 벽을 지을 때처럼 말입니다. 그러니 사전 계산은 최소한으로만 하는 것이 좋습니다. 길이 길어지기 시작하면 먹히지도 않고요. 길을 가로막는 벽이나 우회로가 생긴다면 제대로 된 진로를 선택하는 게 불가능해지는 것처럼 말입니다.
최적화
알고리즘에 필요한 연산값은 대략 log(맵의 크기) 곱하기 유닛의 수와 같습니다. 앞서 말했던 것처럼, 그렇게 작지는 않죠. 100 단위의 유닛들로 돌아가는 상대적으로 작은 스케일의 게임들에서는 유리하겠지만, 1000 단위로 넘어가면 병목 현상을 일으키는 주범이 됩니다. 그래도 A*에 비교하면 장족의 발전이고, flowfield 방식처럼 갑작스러운 랙을 유발하지는 않습니다. 특히 여러 유닛들에게 여러 목표 지점을 지정해줄 때는 말입니다.
2차 시도
음...아무래도 커다란 맵에서도 잘 작동하고 유닛 당 잡아먹는 사양도 작거나 없는 길찾기 알고리즘이 필요할지도... 그래요. 우물은 목마른 사람이 파야겠죠.
아이디어
눈 감고도 맞추셨겠지만, 우리의 아이디어는 flowfield와 단계적 구조룰 결합하는 것이었습니다. 단계적 구조에서는 유닛별로 즉각적인 계산이 가능해주는 부분을 따와, 거기에 flowfield를 적용해 모든 유닛이 같은 진로를 공유할 수 있도록 할 것입니다. 비록 만들다 보니 단계 구조의 중요한 부분을 완전 엉망으로 만들어버리긴 했지만...맵 크기를 지구 전체 수준으로 끌어올리지 않는 이상에야, 잘 작동할 겁니다. 만약 그런 상황이 생긴다면, 그때 좀 더 생각해봐야겠죠.
물론 이 두 방식이 서로 잘 조화되냐면, 그건 아니었습니다. 그렇기에 다음 단계는 필요한 것과 불필요한 것을 구분하는 것이었죠. 우리의 알고리즘이 안 해도 되는 일을 쳐낼수록, 더 최적화가 잘 된 알고리즘이 탄생하는 것이나 다름없으니까요. 그러면, 어떤 방식으로 이걸 적용하면서도 중요한 과정은 손상시키지 않을 수 있을까요?
우선 두 아이디어를 섞는 과정부터 시작해봅시다. 한 가지 방식은 셀 크기를 키우고 A* 대신 flowfield를 적용해 그것을 캐싱하는 것입니다. 나쁜 해결책은 아니고, 기존의 연산 과정을 여럿 재활용할 수 있지만, 여전히 맵 대부분에 영역을 생성해야 한다는 문제가 있었죠. 최악의 경우를 가정했을 때는, 맵의 경계를 둘러싼 유닛들에게 명령을 내려 중앙으로 모이도록 할 때인데, 이러면 영역이 맵 전체를 뒤덮어버리게 됩니다. 즉, 그만큼 더 많은 레이어가 생기고, 오히려 단순히 flowfield만 적용할 때보다도 사양을 많이 잡아먹게 되는 것이죠. 못 쓰는 수준까지는 아니겠지만, 이것보다 나은 방식을 구상해낼 수는 있을 겁니다.
특정 부분을 캐싱하거나 사전 계산하면 어떨까요?
이미 단계 구조에서 이뤄지는 것이긴 하지만, 우리는 여기서 더 나아가보고 싶었습니다. 런타임 값이 0이라면 참 좋을 테니까요. 하지만 단계 구조 관점에서 보는 건 별다른 도움이 되지 않았고, 대신 좀 더 flowfield 중심의 접근법을 시도해보기로 했죠.
flowfield를 단계 구조에 더하는 대신, 단계 구조를 flowfield에 더한 것입니다.
flowfield는 캐싱이 불가능하지 않냐고요? 음, 내려진 모든 명령을 보관해둘 수는 있겠지만, 수백에서 수천번은 해야 쓸모가 있어지기 시작할 겁니다. 512*512의 지도는 260k로, 이것보다 더 크다면 명령을 캐싱하는 게 불가능해지고요. 게다가 이 과정은 RAM을 과부하시키기 때문에, 테이프(여러분이 생각하시는 자기 테이프가 맞습니다)를 사용해 캐싱을 진행해야 할 겁니다. 그러니 모든 명령을 전부 다 캐싱하는 건 불가능하죠. 그렇다면 일부분만 캐싱해서 나중에 사용하는 건 어떨까요?
그러면, 우리는 정확하게 어떤 명령을 캐싱해야 할까요?
음, 단계 구조를 조정해서 flowfield를 만들려면 어떤 방법을 쓰는 게 좋을까요? 흠... 잠시 돌아가봅시다. 우리는 이미 단계적 길찾기가 만들어낸 일종의 navmesh를 가지고 있군요. 노드, 기반 노드 등등을 포함하고 있으니 사용이 가능할 겁니다.
우리가 유지한 것
그래서, 우리는 navmesh를 사용하기로 결정했지만, 길찾기 알고리즘 자체가 버려진 건 아니었습니다. 이제 결과물이 flowfield처럼 보이는 다른 방식의 길찾기를 구성해야 했죠.
어디 어떻게 그 방법을 사용할 수 있을지 알아봅시다:
중심부가 서로 가까운 flowfield들은 멀리서 봤을 때 사실상 하나의 영역이나 다름없습니다.
여기 이미지를 보시면 이해가 가실 겁니다. 4개 전부가 서로 다른 영역이죠.
(flowfield 방식을 실험해보고 싶으신 분들이 있다면, 이 이미지를 만들기 위해 사용한 프로그램의 소스 코드를 패트론에 올려두었습니다.)
아래와 측면 부분이 대체로 동일하게 남아있는 게 보이시나요?
평균적으로 밝기가 살짝 다르거나, 다리의 시작이 다르게 보일지도 모르지만, 결과적으로는 사실상 동일한 결과물이 나오게 됩니다.
즉, flowfield를 매번 계산하는 건 낭비라는 거죠. 목표 지점을 약간 옮기는 것처럼, flowfield를 새로 생성하는 것은 99% 동일하지만 새로운 결과를 초래하게 됩니다.
이걸 고치는 데는 몇 가지 방법이 있지만, 그 전에 다른 특징 하나를 염두해두어야 합니다. 지형이 바뀌어서 원래는 길을 낼 수 있었던 지역이 더는 길이 아니게 될 수도 있다는 것이죠.
명령을 내릴 때마다 계산을 다시 하는 건 최적화에 굉장히 나쁜 결과를 초래할 테니, 우리가 원하는 바가 아닙니다.
그러니 우리가 flowfield를 최적화하고 캐싱하더라도, 벽이 무너지거나 하는 일이 생기면 여전히 역부족일 겁니다. 하지만 여기서 단계적 절차가 마법을 부릴 수 있게 되죠.
우리는 기존의 레이어를 사용하지만, 사실 첫 두 단계만 있어도 충분합니다. 이제 지형을 모든 ‘이웃;들이 인식하는 일정 크기로 분할하고... 이웃들 간의 flowfield를 계산합니다. 그리고 다음 단계에서, 우리는 다시 flowfield를 계산하지만, 이번에는 영역 자체가 작게 줄어들었죠. 32 크기의 노드를 가진 512x512의 맵은 256개의 노드를 가진 16x16의 맵으로 바뀔 테니까요. 이 과정에서 처음 잡아먹는 사양의 경우 맵 전체에 걸친 8개 정도의 문제를 연산하는 것과 비슷합니다. 나쁘진 않지만, 엄청 좋지도 않죠.
물론, 이 접근법은 여러 난점을 만들고, 연결된 flowfield들 간의 연산은 약간 복잡합니다. 특히 유닛들이 움직이는 방식과 진형까지 고려 가능한 범위에 넣는다면요. 이 두 요소들은 길찾기를 많이 복잡하게 만듭니다.
이것은 여러 단계의 노드를 포함한 최종적인 flowfield들의 모습입니다.
노드가 작을수록 더 정확해지지만, 가장 균형잡힌 건 16에서 32 사이더군요.
문제
몇 번의 초기 시험은 이 새로운 길찾기 방식이 비교적 잘 작동한다는 걸 밝혀냈지만, 몇몇 문제가 있었습니다.
유닛들이 지나치게 벽에 달라붙는 현상과 같이, 유닛 그룹이 너무 커지면 알고리즘이 잘 작동하지 않았죠.
그리고, 벽 사이에 뚫린 구멍의 경우도 존재했습니다. ‘기술적으로는’ 유닛들이 지나다닐 수 있는 통로였지만 실제로 시험해본 결과는 처참했죠. 그리고 navmesh 자체가 생성되는 과정에서도 길찾기 과정을 크게 개선할 수 있는 여러 조정이 필요했습니다. 유닛들이 이리저리 흔들리거나 헤매는 것을 막기 위해서 길찾기 과정에 지나치게 큰 변화가 일어나지 않도록 막을 필요도 있었고, flowfield 자체를 더 유닛 친화적으로 만들기 위해 어느 정도 개조를 팔 필요도 있었고요.
다음 주에 이어서 설명할 예정이니, 기대해 주세요.