-맵 길찾기와 유닛 길찾기.

스타크래프트의 경우 길찾기 연산을 두번 합니다. 왜냐하면 모든 거리를 연산하는건 너무나도 비효율이니까요. 맵 끝에서 끝까지 이동하라 명령 한다고, 그걸 다 연산하면 그거 하느라 게임이 뚝뚝 끊깁니다.

그러니까, '어디어디로 이동하여라'라고 명령을 내리면

먼저 지형적으로 탐색 합니다.
유닛이나 그런거 상관 없이 순수 맵데이터를 바탕으로 어느쪽으로 향해야 하는지를 계산합니다.

그리고 짧은 거리를 정교하게 탐색합니다.
짧은 거리는 정교하게 탐색해서 유닛과 건물을 피하도록 탐색합니다.

ex)
테란은 유닛이 지나기지 못하도록 종종 입구를 막습니다.
그리고 그곳을 경과하도록 이동을 명령 내리면, 일단 그 길을 향해 갑니다. 지형적으로 탐색만 하니 건물로 입구가 막힌지를 판단 못하니까요. 건물이 막혔는지에 대한 정밀한 탐색은 현재 유닛의 주위만 하죠. 그러다가 막힌 입구에 도달하면, 지형적으로 뚤렸으되 건물을 고려하는 정교한 탐색으로는 길을 찾을수 없으니 방황 하는 겁니다.

만약, 두갈래 길이 있는데 지름길을 막아버릴 경우, 그럴 경우에도 헤맵니다. 먼길로 돌아가질 않습니다.
왜냐하면 지형적으로 지름길을 찾을때, 유닛이나 건물로 그 길을 막았을 경우는 고려하지 않기 때문이니까요.

(미네랄로 막힌경우도 포함합니다. 그래서 대토네이션의 경우, 여러가지 연산을 해주어야 합니다.)


-A*알고리즘

A*, 에이스타라 발음하는 이 길찾기 알고리즘은, 현존하는 길찾기 AI중 최고입니다. 나온지 50년이나 됀 알고리즘이지만, 더이상 최적화가 불가능하다고 생각될 정도로 좋은 알고리즘이죠. 대부분 이 알고리즘을 사용하며, 스타크래프트도 마찬가지입니다.

이 알고리즘을 파고 드는건 프로그래밍의 영역이므로, 지나치게 복잡합니다. (원하시는 분들이 많다면야 설명 하겠지만.)


-움직이는 유닛은 무시한다.

만약 유닛 뭉쳐있는 유닛 10기를 동시에 이동하라 명령을 내렸다고 합시다.
그때, 단순한 A*알고리즘을 적용시키면 즉시 퍼집니다.

당연한 것입니다. 움직이는 주위의 유닛들을 잠재적인 장애물로 파악하여, 그 유닛들을 돌아가는 지름길을 찾으니까요.

그래서 이동하는 유닛은 '피해 주겠지'라고 잠정적으로 생각하고 길을 찾아야 합니다.
그런데, 그러다가 장애물이 비켜주지 않을 경우가 있습니다.-_- 서로가 교차돼기 때문에 서로가 피해주리라 생각하는-_- 마치 현실과 같은 일이 생깁니다.

그럴때는 일단 잠시 기다립니다. 혹시 조금 있다가는 비켜줄지 모르니까요. 그래도 안비키면, 시계방향으로 돕니다. 마치 두 사람이 서로 마주쳤을때, 한쪽은 오른쪽, 한쪽은 왼쪽으로 비키듯이요.

이것 때문에 병력들이 일렬로 가는 현상이 일어나는 겁니다. 왜냐하면, 특정 지점에서 특정 지점으로 가는 최단로는 하나입니다. 그러므로 모든 유닛들이, 같은 길을 선택하게 되고, 그 길만을 따라 가려 하다보니 자연스레 일렬로 걸어가게 되는 것입니다. 그 최단로를 벗어나지 않으려구요.


-드래군은 왜 방황하는가

아무래도 길찾기 AI는 큰 부하를 주기에 스타의 경우 A*알고리즘을 가끔씩 합니다. 길찾고, 그 길따라 가다가, 다시 길찾고, 그 길따라 가다가, 를 반복하는거죠.

좁은 입구를 지날때 몇몇 드래군이 내려가지 않고 방황하는 경우가 있는데, 그것은 위의 현상과 연관이 됀 것입니다.

입구를 직렬로 내려오면 괜찮은데 내려오다가 서로 길이 약간 엇갈려서 부딪히는  경우가 있습니다. 그 경우 위에서 설명했던 데로 잠시 멈추죠. 그렇게 길을 멈추자 뒤에 있는 드래군은, 멈춰 있는 드래군을 장애물로 인식하고 '입구가 막혔다'라고 판단하게 돼는 겁니다. 그래서 '다른길 찾아봐야지'하고 다른곳으로 가는 거지요.

물론 그러다가 잠깐 멈춘 드래군은 곧 제 갈길을 갑니다. 그런데, 다른길 찾던 뒤에 드래군은, 입구가 뚤린걸 인식하지 않습니다. 왜냐하면 아까 처음에 말한대로, A*알고리즘을 가끔 쓰니까요. 그래서 나중에, 다시 A*알고리즘을 쓸때가 돼어서야 '아 입구가 뚤렸군'하고 알아차리고 원래 길을 가줍니다.

프로게이머들의 경기 화면을 볼때, 유닛에게 입구를 통과하도록 명령 내릴경우, 반복해서 이동을 명령 내리는 경우를 많이 볼수 있는데요, 이것은 버릇이기도 하지만 이동을 명령 내릴때마다 새로 A*알고리즘을 시행하기 때문에, A*알고리즘 지연시간이 사라져 위의 멍청함이 적어지는 것도 하나의 이유 입니다.

(참고로 골리앗, 시즈탱크, 울트라리스크등 큰 유닛은 물론, 마린,저글링 같은 작은 유닛들도 자주 일어나는 현상이지만, 드래군은 특유의 포화 방식(입구를 열고 나서 쏜다)때문에 멈추는 경우가 많아 특히 바보처럼 보입니다.)


* homy님에 의해서 게시물 이동되었습니다 (2004-02-11 15:38)