Unity3D

길 찾기 알고리즘 중에 유명한 것이 A*(A star)라는 것이 있는데 이것을 간단하게 구현하는 방법을 정리한 것이다. 프로 게임 엔진에선 길 찾기 기능도 제공을 한다. 아마추어용 공짜 게임 엔진에선 제공하지 않는다. 물리적 충돌 현상 시뮬레이션은 공짜 게임 엔진에서도 제공한다. 프로 게임 엔진에서도 인공지능은 제공하지 않는다. 이 부분은 직접 구현 해야 한다. A*에 대한 소개는 다른 글에 있다.(http://blog.daum.net/jty71/15645104)

먼저 기본적으로 공간을 조각으로 나눈다. 보통 삼각형, 육각형, 사각형, 마름모꼴을 이용해서 평면을 잘게 나눈다. 이렇게 공간을 나누고 시간을 나누면 편리한 점이 많다. 공간을 잘게 나누어 바둑판을 만들어 거기에 유닛을 배치한다. 마치 장기와 바둑과 비슷하다. 지도는 M x N 평면 2차원 배열이다. 3차원 이상의 다차원 배열은 사용하지 않는다. 왜냐하면 첨자 계산 시간이 그만큼 소모된다. 고로 M x N 크기는 모두 같지만 다른 이름의 여러 바둑판 배열을 만들어 사용한다. 제일 기본은 지도의 지형을 묘사하기 위한 바둑판 배열이다. 이 배열은 지형 그림의 번호를 저장한다. 그 다음에 나무, 건물, 이동 유닛 등의 배치 정보를 기억하는 배열이다. 그 다음이 전쟁 안개라는 것으로 아직 밝혀지지 않는 지도는 검게 나타나며, 지도는 밝혀 졌지만 유닛이 없어 관찰 할 수 없는 곳은 중간 정도로 어둡게 나타나며, 유닛이 있어 관찰이 가능한 곳은 밝게 정상적으로 나오는 그런 것을 묘사하기 위한 배열이다. 그 다음에 길 찾기에서 사용하는 배열이다. 길 찾기 배열은 Max(최대)/Min(최소)을 찾기 위한 1차원 배열도 함께 사용한다.

유닛을 배치하는 배열을 사용하는 장점은 이렇다. 화면에 표시되는 지역의 유닛만 찾으려고 할 때 이 배열을 사용한다. 유닛이 이동 중에 자신과 충돌할 것 같은 다른 유닛을 찾을 때 이 배열을 사용한다. 즉, 유닛이 수백 개가 지도에서 활동 중이라도 모두 충돌 검사를 할 필요가 없다. 지금 보이는 영역의 유닛만 그리면 되고, 지금 이동 중인 유닛 근처의 유닛만 거리 계산에 이용하면 된다. 유명한 실시간 전략 시뮬레이션을 보면 수백 개의 유닛이 등장한다. 나무, 건물, 이동 유닛들을 모두 합하면 수백 개는 된다. 이런 것을 실시간으로 처리하려면 공간을 나누어 배치해야 유리하다.

타일 하나에 유닛이 4개나 9개가 들어갈 수 있도록 되어 있다. 유닛의 크기가 다양한데 가장 큰 유닛이 타일 하나에 배치 된다. 고로 그보다 작은 유닛들은 여럿이 타일 하나에 배치될 수 있다. 고로 유닛 배치용 바둑판 배열은 3차원 배열이 되어야 한다. 한 타일 안의 유닛의 위치는 비교적 자유롭다. 그 유닛의 중심이 그 타일 안에 있으면 그 타일 소속이 된다. 허나 유닛의 위치가 그 안에서 자유롭기 때문에 매우 자연스럽게 배치 되어 보인다. 하지만 이는 눈속임이고 유닛의 크기와 위치를 수학적으로 계산하면 최대 4개(또는 9개) 이상 들어가지 못하게 되어 있다. 왜냐하면 유닛의 크기를 타일 안에 4개, 9개만 들어가도록 결정했기 때문이다.

길 찾기 알고리즘인 A*는 다른 글에서 설명을 했다. 길 찾기를 하려면 지도 타일과 같은 형태의 2차원 배열과 최적의 길을 선택하기 위해서 Max/Min 값을 찾을 수 있는 1차원 배열이 필요하다. 2차원 배열에선 가상의 유닛이 이미 갔던 길을 표시하고, 그 길의 평가 결과를 기록한다. 즉, 이 타일에 오기 전에 어디에서 왔으며, 이 타일에 도달하기까지 필요한 비용은 얼마이며, 이 타일에서 목표까지 직선 거리는 얼마이며, 그래서 최종 평가 결과(지나 온 길의 비용 + 목표까지 직선 거리)는 얼마인지 기록을 한다. 선택할 타일 후보자들 중에 어떤 것이 가장 짧은 길인지 결정을 해야 한다. 그래서 후보자 타일을 기록하고 최소 비용을 찾아 주는 1차원 배열이 필요하다. 이 1차원 배열에는 항상 다음에 선택할 타일들이 들어 있다. A*에선 장애물을 만나기 전까지는 직진을 한다. 그러다 장애물을 만나면 둥글게 확장하며 길을 찾는다. 돌아갈 틈이 발견 되면 거기서 또 직진을 하여 최소 비용의 길을 결정하게 된다. 이 때 둥글게 확장할 때 가장 밖의 얇은 껍질들이 선택해야 할 후보 타일이 되는데 이것들은 1차원 배열에서 기록하고 관리한다.

복잡한 A*를 구현하기 전에 먼저 길이 있는지 없는지 판단부터 해야 한다. A*는 타일에서 8방향으로 확장하면서 계산을 하기 때문에 시간이 많이 걸리고 장애물을 만나서 둥글게 확장하는 부분에선 시간 소모가 많다. 이것을 좀 더 짧게 끝내려면 약간 다른 지능적인 방법을 추가로 사용해야 한다. 먼저 일단 길이 있는지 없는지 판단해야 한다. 먼저 출발점과 목적지를 직선으로 달려 본다. 직선을 긋는 것과 같다. 이 직선에선 타일 중심을 따라 갈 필요는 없다. 그러면 중간에 장애물을 만날 것이다. 이 장애물의 특성에 따라서 길이 없던가, 길이 양쪽으로 돌아갈 수 있거나, 어느 한 방향으로만 돌아가야 한다. A Type 지형에선 길이 없다. 장애물을 만났을 때 그 장애물의 표면을 따라 가 보면 지도의 경계선에 도달한다. 양방향으로 가도 경계선에 도달했다면 막힌 길이다. 고로 길 찾기를 계산할 필요가 없다. 이런 것을 벽 타기라고 한다. 보통 이런 계산은 지도가 완성될 때 해 두면 좋다. 즉, 장애물에 특성이 표시되어 있는데 그 장애물의 특성을 보니 A형 장애물이라면 더 계산해 볼 것도 없다. B형 장애물도 목표에 도달할 수 없다. B Type 장애물의 표면을 따라 이동해 보니 다시 제자리로 왔다면 이것은 성벽처럼 목표를 감싸고 있는 것이다. 이것도 지도를 제작할 때 미리 계산해서 장애물에 식별표시를 붙이면 된다. B형 장애물이면 답이 없는 것이다. C형 장애물의 경우는 어느 한 쪽에 통로가 있다. 고로 이런 것은 어느 방향으로 꺾으면 된다는 정보를 미리 계산해서 장애물에 부여하면 된다. D Type 장애물의 경우는 양쪽으로 돌아갈 수 있다. 이런 장애물의 표면을 따라 돌면 역시 제자리가 되는데 장애물 특성으로 보면 B와 D는 같은 형태다. 목표물이 어디에 있는지가 차이가 있다. 이 경우 B와 D 경우를 구분해야 하는데 이는 목표물이 위치한 영역의 특성을 보면 된다. 지도를 제작할 때 영역들이 단절 되어 있는지 확인해서 영역 ID를 부여할 수 있다. 만약 시작점과 목표점의 영역 ID가 같다면 이것은 이어져 있다는 뜻이 된다. 영역 ID가 다르면 이 둘은 장벽에 의해 갈라진 것이다. 이렇게 미리 계산을 해 놓고 영역과 장애물에 어떤 정보를 부여하면 무식하게 A*를 항상 계산할 필요가 없다. 목표지점에 가장 가까운 곳을 새로운 목표로 정해야 한다.

A*의 계산법을 이용하지 않는 다른 종류의 길 찾기 방법이다. 먼저 시작 지점에서 목표 지점까지 직선으로 달려 본다. 장애물을 만나면 장애물과 대화하여 어떤 종류인지 돌아갈 코너는 있는지 확인한다. 장애물과 대화가 불가능한 게임이라면 장애물의 표면을 따라 벽 타기를 한다. 충돌 지점에서 시작해서 좌측이나 우측으로 돌아 보면 직선으로 연결할 수 있는 코너 지점이란 것을 발견할 수 있다. 이 코너 지점이 많이 발견되면 돌아가는 길이 복잡하다는 말이 된다. 반면에 목표 지점에서 시작 지점으로 역으로 길을 추적해 보니 이런 코너 지점의 수가 더 적어진다면 일단 그 길을 택한다. 가장 적은 코너 지점을 가진 길을 택한 후에 마지막 코너 지점을 시작 지점이나 목표 지점에 직접 직선으로 연결하면 최적화 된 길을 얻을 수 있다. 이 방법의 원리는 장애물 돌출부 주변에 생기는 코너 지점은 서로 직선으로 연결할 수 있다는 점이다. 즉, 코너 지점을 발견하여 연결하면 그 중간은 직선으로 연결되기 때문에 따로 복잡하게 계산할 필요가 없다는 것이다. 장애물에 충돌하는 지점(입사 지점)과 장애물 충돌에서 벗어나는 지점(출사 지점) 이 둘을 우회하여 연결하는 코너 지점들을 먼저 발견한 후에 양쪽 끝의 코너 지점을 직접 시작 지점과 목표 지점에 연결이 되는지 확인하면 최적의 길을 얻게 된다. 즉, 장애물 발견, 장애물 우회하면서 코너 발견, 마지막 코너를 직접 연결해 보기, 이런 식으로 일을 진행한다. A*보다는 간단하다.

A* 방법은 아니지만 이동 비용이 0 아니면 무한대인 간단한 형태의 지형에선 A* 대신 이용할 수 있는 방법이다. 즉, 갈 수 있거나 갈 수 없는 2가지 경우뿐이다. A*는 이동 비용이 0 ~ 무한대까지 다양한 지형에 적용하는 것이 더 좋다. 먼저 직선 달리기를 해서 입사 지점과 출사 지점을 구한다. 입사 지점과 출사 지점을 벽을 타고 돌아서 연결하면 장애물의 특징이 나온다. 입사 지점과 출사 지점이 만나야 길이 있는 것이다. 만나지 못 하면 길이 없는 것이다. 우회로가 2가지인 경우와 1 가지인 경우가 있을 것이다. 우회로가 2가지인 경우는 2개의 경로 중에 짧은 것을 선택하는 문제가 있다. 일단 입사~출사 벽 타기 경로를 구한다. 이 경로를 구하는 중에 코너 지점을 찾게 된다. 코너 지점을 찾으면 코너 지점 사이의 경로는 직선으로 대체할 수 있기 때문에 길을 묘사하기 쉬워진다. 즉, 어디서 어디까지는 직선으로 가라는 식으로 간단하게 길을 묘사하게 된다. 양 끝의 코너 지점을 직접 출발지와 도착지에 연결해 본다. 장애물이 없다면 직접 연결이 되고, 그 길이 더 짧아지면 그 경로를 선택한다. 그 다음에도 중간 코너와 출발지와 도착지를 직접 연결해 보고 장애물이 없이 직접 연결되며 경로가 더 짧다면 그 경로를 취한다. 코너 지점을 시작점과 목표점에 연결하는 중에 또 다른 종류의 장애물이 나타난다면 그 구간에 대해서 길 찾기를 다시 한다. 우회하려던 장애물과 다른 장애물이 나타났다는 말은 처음에는 없던 장애물이 생겼다는 뜻이다. 이것은 길을 단축하는 과정에서 만난 것이다. 고로 그 구간에서 길 찾기를 하여 연결하면 전체적으로 가장 짧은 길을 구할 수 있다. A*보다는 훨씬 빠를 것이다. 또는 이 방법과 A*의 이동 비용 평가 방법을 함께 사용하는 경우도 있을 수 있으나 결국 총 계산 시간은 같을 것이다. 어차피 모든 길을 미리 다녀 보고 가장 짧은 길을 선택하는 것이기 때문에 총 계산 시간은 같다. 게임 엔진을 이용하는 경우에는 이런 길 찾기를 구현할 필요가 없을 것이다.

또 다른 방법이 있다. 처음에 길이 있는지 확인하는 방법은 위와 같이 우회로를 통해 입사 지점과 출사 지점을 연결할 수 있는지 보는 것이다. 일단 길이 있다면 무조건 목표를 향해 직선 전진을 한다. 장애물을 만나면 우회를 하지만 장애물을 벗어 났다고 판단되면 또 직진을 한다. 즉, 출사 지점으로 가는 것이 아니라 바로 목표로 향한다. 마치 목표물에 중력이 있어 그쪽으로 물이 흐르는 것처럼 그렇게 직진한다. 이런 식으로 길을 찾은 후에 반대로 목표 지점에서 출발 지점으로 같은 방식으로 길을 찾는다. 그러면 양 방향 길이 겹치는 구간이 있고, 서로 갈라지지만 같은 곳으로 도달하는 길이 있다. 겹친 구간은 유일한 통로이기 때문에 그대로 사용하고, 갈라진 구간에선 어느 쪽이 더 짧은지 선택한다. 그렇게 해서 최종적으로 길을 결정한다. 이 길은 가장 짧은 길은 아니지만 비교적 짧은 길이다. 이 길을 A*로 찾으려면 상당히 넓은 지역을 계산해야 하지만 이 방법은 길쭉한 길 몇 개만 계산하면 바로 나온다. 그래서 계산 시간이 짧다. 그런데 문제가 있다. 길을 표시할 때 어디에서 왔는지 정보가 필요한데 그런 정보가 2개 이상일 수 있다. 즉, 여기까지 도달하는 경로가 1개가 아니라 2개 이상이기 때문에 타일에 2개 이상의 정보를 기록할 수 있어야 한다. A*의 경우는 항상 하나의 경로를 통해서 그 지점에 도달하기 때문에 자신이 어디서 왔는지 1개의 정보만 기억하면 된다. 그런데 이 방법에선 2개 이상의 경로를 통해 한 곳에 도달할 수 있기 때문에 왔던 길을 기억하는 것이 좀 복잡하다. A*의 경우는 나무 가지가 퍼지는 듯한 연결 상황을 표시하기 때문에 모든 길은 자신의 부모 길만 기억하면 된다. 두 가지가 합쳐지는 일이 없다. 즉, 2개의 경로가 중간에 다시 합쳐지는 경우가 없다. 그런데 이 방법에선 2개의 경로가 합쳐지기 때문에 약간 골치 아프다. 요점은 입사 지점과 출사 지점을 거치지 않고 바로 코너에 연결하는 경로를 찾으면 되는 것이다. 그러면 A*와 유사한 결과를 만들어낸다.

지금까지 방법을 모두 종합해서 결론적인 방법을 정리하면 이렇다. 무조건 목표를 향해 직진한다. 길이 있는지 없는지 미리 판단할 필요 없다. 장애물이 나타나면 우회를 한다. 벽을 타며 장애물을 회피한다. 장애물을 벗어나는 순간 (회전 각도를 참고하여 원래 회전 각도가 나오면) 또 목표를 향해 직진한다. 그렇게 가다 보면 여러 갈래로 길이 갈라지는데 중간에 다시 모이는 지점이 있게 된다. 중간에 모이는 지점에선 어느 길로 오는 것이 더 짧은지 판단하여 긴 쪽 길을 버린다. 즉, 모든 지점은 자신이 어디서 왔는지 한 방향만 기억할 수 있다. 고로 두 길이 합쳐지는 곳에선 어느 한 길을 버려야 한다. 이런 식으로 목표까지 길을 찾는다. 목표에 도달하지 못 하는 경우는 위에서 본 바와 같이 2가지 경우뿐이다. 둥근 장벽에 둘러 싸여 있거나, 긴 장벽이 갈라 놓은 경우이다. 어느 경우라도 더 이상 길을 추가할 수 없는 경우가 나오는데 그러면 길이 없는 것이다. 일단 목표 근처나 목표에 도달했으면 길을 역으로 거슬러 올라오면서 입사 지점을 생략하는 길 단축 과정을 밟는다. 길 단축 과정에서도 장애물이 새로 나타나는 경우가 있을 것이다. 그러면 같은 방법으로 구간의 새로운 경로를 찾는다. 시작 점까지 도달했다면 다시 시작 점에서 목표 지점으로 길을 따라 내려가면서 다시 입사 지점 제거 작업을 한다. 입사 지점이 모두 제거될 때까지 왔다 갔다 반복을 하면 가장 짧은 길을 찾게 된다. 이 방법은 A*를 대신할 수 있다.

A*와 지금까지 방법을 혼용한 경우이다. A*는 여러 길이 합치는 곳에선 그 지점까지 도달할 수 있는 최단 거리 경로를 취하고 나머지는 연결이 되지 못 하게 한다. 고로 모든 길은 하나의 부모 길만 기억하기 때문에 목표 지점에서 시작 지점으로 역추적을 하면 단일 경로로 연결이 된다. 장애물을 만났을 때는 둥글게 확장하며 탐색을 하는데 여기선 장벽을 따라 이동하면서 그 지점까지 가장 가까운 직선을 찾는 것으로 대신한다. 장벽을 넘을 수 있는 지점이 나오면 이런 직선 탐색은 하지 않는다. 장벽을 만나서 길이 양쪽으로 갈라지면 어느 방향으로 나갈 것인지 결정해야 하는데 여기서 A*의 평가 방식을 사용한다. 이런 방식을 계속 반복하면 A*와 유사한 방식으로 탐색하는 것이 된다. A*에선 그 지점까지 도달 거리와 목표까지의 직선 거리의 합으로 다음 경로를 선택한다. 마찬가지로 여기서도 장벽을 따라갈 때 그 지점까지 가장 짧은 직선과 목표까지 직선을 평가 기준으로 사용할 수 있다. 이 과정에서 중간에 새로운 장애물을 만나면 코너 지점을 추가하여 코너 지점이 최단거리 직선으로 연결 되도록 계속 길을 찾아 가는 방식이다. 최종적으로 얻어진 길은 코너 지점을 직선으로 연결한 형태가 된다. 8방향 타일 탐색 대신 직선 길이를 사용할 뿐이며 A*의 평가 알고리즘을 사용하는 것이다. 직선 이동을 할 때는 수평 수직 타일의 간격 중에 가장 작은 간격을 사용한다. 이렇게 하면 직선 경로 중의 모든 타일에 속한 객체와 충돌을 검사할 수 있다.

갑자기 산지와 평지의 이동 비용을 알고 싶어서 검색을 해 보았다. 산을 넘는 시간을 계산하기 위해서 63빌딩 계단 오르기 기록을 살펴 보았다. 산에는 계단이 없어서 더 힘들 것이나 참고할 수 있을 것 같다. 달리기 기록이나 마라톤 기록과 비교한다. 내려올 때는 올라갈 때보다 쉬우니 평지의 달리기 속도와 같다고 하자. 이렇게 계산을 해 보니 산의 이동 비용은 평지의 이동 비용의 5배이다. 현실 세계에서 보통 평지 행군 속도가 4km/h ~ 6km/h 이기 때문에 산에선 평균 1km/h 정도로 행군한다는 말이 된다. 어디까지나 게임 속의 이동 비용이고 현실 세계에선 많이 다르다. 산의 높이보다는 산의 경사도가 더 결정적이다. 같은 높이를 오를 때 절벽을 기어 오르는 것과 계단을 오르는 것은 차이가 많다.