[GPG 1 글 3.3] A* 알고리즘에서 길찾기.

GPG 시리즈 관련 질답, 논의 공간.

Moderator: 류광

심 형근
Posts: 526
Joined: 2002-08-19 23:30

A* 알고리즘에서 길찾기.

Post by 심 형근 »

A* 알고리즘은 기본적으로 2D 타일기반에서 동작하며,
갈수없는곳을 블럭으로 지정해서 움직입니다.

스타크래프트를 예로 들자면, 건물/미네랄/가스/절벽 같은 지형은
A* 타일에서 못가는 지역으로 설정될 것입니다.

한가지 궁금한점이 있다면,
마린이나 탱크같은 유닛도 A* 타일에서 못가는 지역으로 설정되는것인가? 입니다.

Image

서플라이 디팟으로 오른쪽과 아래쪽을 막고, 마린으로 입구를 막은다음에,
SCV 를 왼쪽에 클릭하면 알아서 최단거리로 이동합니다.
(마린몸뚱이에 버벅거리다가 이동하는것이 아닌.. 아예 처음부터 못가는걸로 간주하고
최단거리로 이동합니다.)

그 반대의 경우도 마찬가지 입니다.

Image

개인적으로는 이런 행동을 봤을때, A* 알고리즘에서 유닛도 건물이나 미네랄처럼
A* 타일에서 못가는 "타일로서" 작동하는것 같은데,

다른분들의 의견은 어떤지 알고 싶습니다.
비회원

타일정보에..

Post by 비회원 »

타일 정보에 넣지 않고 길을 찾는다면 유닛을 모두 돌아야 하므로 부담이 가니 타일정보에 유닛 정보를 넣어야겠죠.

탱크다 마린이다 이런 정보가 아닌 해당 위치에 오브젝트가 위치했다 안했다 형식으로요.
비회원

자료구조

Post by 비회원 »

A*를 이용해서 휴리스틱 검사를 할 때 참고할 테이블이 2개면 되겠죠. (블리자드 특성상 비트플래그로 했을 듯)
기본적으로 변하지 않는 지형 데이터가 있고 동적인 지형 데이터에 각 오브젝트의 위치를 넣어주면 되겠네요. 아마도 지형 먼저 검사 안하고 동적인 지형 먼저 검사하고 정적인 지형 검사할 것으로 보입니다. 왜냐하면 오브젝트가 그곳에 있다면 우선 클릭해서 이동할 때 해당 좌표에 이동이 가능했었다라고 알 수 있었을 테니까요.

물론 동적인 지형 데이터로 갈 수 있다고 하더라도 (공중 유닛), 현재 검사하고 있는 주체가 걸어다는 종류에 두번째 정적인 지형을 검사했을 때 걸어갈 수 없는 지역이다. 라고 하면 대충 근사치까지 움직이다가 말겠죠. 실제로 스타크래프트도 갈 수 없는 지역 클릭했다고 해서 아예 안가는건 아니거든요.
비회원

Post by 비회원 »

질문 올린사람은 아닙니다만

그 오브젝트들을 어떤식으로 A*에 적용시키죠??

유닛들이 타일의 중앙에 있을수도 있고 두개의 타일에 걸칠 수 도 있는데요

어떤식으로 A*에 적용을 시키는지 궁금하군요

참고로 유닛들 사이에 틈이 있더라도 자신의 바운딩박스보다 작다면

처음부터 지나가지 못하는 걸로 인식합니다
비회원

Re: 자료구조

Post by 비회원 »

비회원 wrote:A*를 이용해서 휴리스틱 검사를 할 때 참고할 테이블이 2개면 되겠죠. (블리자드 특성상 비트플래그로 했을 듯)
기본적으로 변하지 않는 지형 데이터가 있고 동적인 지형 데이터에 각 오브젝트의 위치를 넣어주면 되겠네요. 아마도 지형 먼저 검사 안하고 동적인 지형 먼저 검사하고 정적인 지형 검사할 것으로 보입니다. 왜냐하면 오브젝트가 그곳에 있다면 우선 클릭해서 이동할 때 해당 좌표에 이동이 가능했었다라고 알 수 있었을 테니까요.

물론 동적인 지형 데이터로 갈 수 있다고 하더라도 (공중 유닛), 현재 검사하고 있는 주체가 걸어다는 종류에 두번째 정적인 지형을 검사했을 때 걸어갈 수 없는 지역이다. 라고 하면 대충 근사치까지 움직이다가 말겠죠. 실제로 스타크래프트도 갈 수 없는 지역 클릭했다고 해서 아예 안가는건 아니거든요.
지형 서치가 먼저입니다.. 지형 서치를 해서 이동한후 좁은 범위의 동적 오브젝트를 서치하는 방식이죠..

예 먼곳을 클릭하면 쭉 이동하다 미네랄 혹은 건물등.. 동적 오브젝트에 의해 걸려서 왔다 갔다 하는 상황이 많지요.
chkino
Posts: 8
Joined: 2006-08-21 12:57

Post by chkino »

http://blog.naver.com/topgunmagic?Redir ... 0024678963

참고가 되실지 모르겠는데 탑건매직님 블로그에 좋은 글이 있네요
비회원

Post by 비회원 »

예전에 워3와 거의(ㅡ0ㅡ) 똑같은 3D RTS Project를 진행했던 적이 있었습니다. 3D 관련된 프로그래밍 보다는 다른 쪽을 해보고 싶어서, AI를 맡았는데 그때 스타크래프트의 길찾기를 꽤나 많이 연구하고 거의 동일한 반응성을 얻도록 구현하여 프로젝트를 완수 하였습니다. 스타와 워3의 길찾기는 큰 차이가 없습니다.

본래 대부분의 타일맵 기반의 길찾기에서는 계층구조의 맵을 사용합니다. 주로 평면 지형에서 많이 사용하는 Quad Tree와 같은 개념입니다. 스타에서 이와같은 트리를 썼는지 않썼는지 몇단계 인지보다는 결론적으로 말하면 스타는 크게 두단계 이상의 맵 자료구조를 가지고 있습니다. 하나는 변하지 않는 지형타일 셑에 의해 결정되는 지형정보이고 다른 하나는 유닛들의 충돌을 처리할 수 있는 지형타일셑보다 훨씬 작은 크기의 맵입니다. 이후에는 임의대로 디테일맵(Detail Map)이라고 부르겠습니다.
맵을 생성하고 로드하게 되면, 지형정보는 자동적으로 작은 타일로 된 디테일 맵에 그정보가 올라가게 됩니다. 이정보들은 변경되지 않는 정보들입니다. 그리고 이 바탕위에 공중유닛처럼 타일을 점유하지 않는 유닛을 제외한 유닛들이 크기별로 올라가게 됩니다. 유닛의 크기는 디테일 맵의 최소 타일 입자 단위의 정수배가 될 수 밖에 없습니다. 물론 유닛의 크기도 floating형태로 지정해도 별로 상관은 없습니다.

자 이제 중요한 이야기는 다 나왔습니다. A*만 적용하면 됩니다. A*는 그래프 탐색 알고리즘으로 비용은 크지만 최단경로를 보장하고 경로의 유무를 확인할 수 있습니다. 문제는 스타 256*256타일 사이즈에 그것보다 훨씬 작은 Detail Map사이즈 타일 2048*2048정도 된다고 해보죠, 이것에 유닛 한 부대만 찍어서 머얼리 어택땅을 찍었다고 합시다. 아마도 이 한번의 명령으로 이 함수가 호출되는 순간 리턴값을 기다리기 위해 아마도 한 몇분간 혹은 10분이상 유저는 전체적인 전술을 연습장을 펴놓고 그림을 그려가며 고민할 수 있을 겁니다. 초당 30프레임은 꿈에서나 이야기 해야 겠지요.
국내에 출간된 거의 유일한 RTS책에 나온 내용을 보면 대부분의 RTS게임은 물론 모든 RealTime System이 그렇겠지만 철저한 Update Mgr가 필요합니다. 각 해당 유닛별로 update count를 관리하고 전체 유닛과 장면 갱신에 할당될 CPU자원에 대한 관리가 필요합니다. A*를 적용하여 길찾기를 할때도 node탐색 횟수에 제한이 있어야 되겠지요. 예를 들어 한번의 길찾기 요청에 A-star Step에 제한을 100으로 둔다고 합시다. Detail Map으로 100번의 Update를 하게 되면 중요한 문제가 발생할 수 있습니다. 지형의 구조에 따라 이전 길찾기 Path나 A* 탐색정보를 저장하지 않는다면 커다란 움푹진 지형에서 유닛은 절대로 빠져나오지 못할 것입니다. 또 일단 유닛의 높은 반응성을 위해서 유닛은 이동명령 직후에 바로 움직일 수 있어야 합니다. 100번의 스텝으로 여러번의 길찾기를 반복하면서 경로를 찾는 과정에서도 유닛은 계속 발견된 최적의 경로를 따라 움직이고 있는 상태입니다. 이것은 유닛이 이동하면서 실제 최적화 경로를 무효화 할 수 있다는 뜻입니다. 따라서 간단하게는 유닛이 충돌했거나 해서 새로운 길찾기 요청이 있을때 마다 매번 현재 위치부터 새로 길찾기를 해야 합니다. 그렇지 않고 무난하게 진행하고 있다면 현재 저장된 길찾기 정보를 계속 확장해 나갈 수 있습니다.
자 말이 길어지니 또 결론적으로 이야기 합시다. 일단은 큰 지형타일 기반에서 A* 스텝 제한을 50으로 하고, 디테일맵 기반에서 자신의 유닛크기별 노드타입을 정의(적용)해서 Step을 50적용합니다. 큰 지형타일 기반의 길찾기는 유닛에게 목적 경로에 대한 높은 반응성과 정확한 방향성을 제시 할 것입니다. 디테일맵은 실제 유닛의 충돌하지 않는 영리한 길찾기 경로를 찾아 줄 것입니다.
갑자기 버럭 화가 나는 기억이 떠오르네요. 스타 길찾기에 대한 자료들을 찾다가 어떤 분이 움직이는 물체는 충돌(타일점유)에 포함시키지 않는다고 하셨는데, 잘못된 정보입니다. 이 경우 심각한 문제가 두가지 발생합니다. 하나는 움직이는 물체끼리 장애물 회피를 적용하기가 쉽지 않다는 것이고,(심심하면 간단한 우회법으로는 데드락이죠 머) 정지해야 할 경우 여러개 유닛이 하나의 디테일맵 타일에 걸치게 될 수 있다는 것입니다. 또한 잦은 충돌도 문제가 됩니다. 이 문제때문에 결국 전체 코드를 뒤집고 다시 재작성하였습니다. 일단 유닛은 타일을 차지하고 있어야 합니다. 물론 SCV가 건물 지을때처럼 유닛이 타일을 차지하지 않다가 다시 차지하게 되는 등의 인터페이스는 있어야 합니다. 자원을 캐거나 유닛이 생산이나 다른 상황으로 겹치게 되었을때 풀어줄 수 있는 방법이 필요합니다.
이동하는 유닛의 처리는 선점하는 방식을 사용했습니다. 스타에서도 이런 방식을 사용하였으리라 생각합니다. 유닛은 이동하기 전에 다음 해당 타일을 선점하고 못가는 타일로 변경한 후 자신의 이동속도에 맞추어 이동합니다. 만일 유닛이 확보한 경로로 이동중에 다른 유닛과 충돌하게 되면, (이것은 인접한 유닛들에 대해서 간단한 사각형 충돌을 계산합니다.) 반드시 이동중인 유닛과 충돌하게 된 케이스임으로 무조건 기다립니다. 현재 위에서 설명한 길찾기의 전략에서 확보된 짧은 경로로는 무조건 이동할 수 있다고 보는 것입니다.

자 다 나왔습니다. 적절한 Update Count와 지형 디자인, 타일 구조의 Hierachy Level등은 설계하기 나름입니다. A*를 적용할 그래프 구조나 노드, 에지 등도 자기 마음입니다. 최적화의 방법은 무수하게 찾을 수 있습니다.
지형정보를 만들때 부터 지형마다 이동비용이나 우선순위값(가중치)을 정의할 수도 있고, 미리계산된 길찾기 해법을 심어놓을 수도 있습니다.
스타에서 뒤 유닛이 앞 유닛을 따라가는 것은 최적화가 아닙니다. 스타에서는 모든 유닛이 각자 길찾기를 합니다. 모든 유닛들이 같은 길찾기를 수행하거나 특정 위치에서 특정 위치로의 최적의 해가 발견된 것이 있으면 그것을 함께 참조하기 때문에 비슷한 경로를 따라 이동하려는 것이고, 그 결과 충돌이 발생하고, 이동하는 유닛끼리의 충돌에서는 일단 기다리는 것이 정책이기때문에 시간이 지날수록 먼거리를 가다보면 어느새 일렬로 달리고 있는 것입니다. 느린 머린 뒤에서 빠른 벌쳐가 질질질 천천히 뒤쫓아 가는 것도 위와 같은 현상으로 설명할 수 있습니다. 속도차가 현격하거나 충돌이 발생하지 않거나 아예 장애물로 인식되는 케이스가 오면 벌쳐는 자연스럽게 머린을 추월할 것입니다.
만일 이동할 수 없는 곳을 이동하라고 하면 어떻게 해야 할까요. 위와 같은 설계라면 어떻게 되리라고 생각하시나요? 목표로의 해를 발견하기 위해 무한히 일정 스텝마다 혹은 조건마다 길찾기를 반복하게 될겁니다. 주변에서 빙빙 돌게 되겠지요. 지형으로는 갈 수 있지만 유닛들로 막힌 지형같은 경우도 설명됩니다. 가다가 디테일맵 서치에서 막히면 그때 또 디테일 단위로 목표 지형타일 단위로의 이동가능 경로를 찾는 등의 경로 수정이 필요하겠죠. 경로 수정이 필요한 경우, 수정과 접합, 재탐색 등등 할 수 있는 일은 많습니다. A* 서치를 한번이라도 줄이는 방법을 찾는게 바로 최적화 입니다.

길찾기를 작성하다 보면 성능과 사소한 이동 문제들, 메모리 관리문제, 충돌문제, 회피문제, 메모리 오류 등이 끝도없이 괴롭히게 될 것입니다. 다양한 상황에서 테스트 해야 하고, 문제를 재현해야 하고, 게임이 다 그렇지만 리얼타임 특유의 짱나는 디버깅이 뒤따름니다. 또 유닛이 한둘이어야 말이죠. @~@ 어떻게 최적화하느냐는 만드는 사람마음입니다. 적당히 좋은 장치들을 삽입하고 기획과 설계자가 함께 논의하는 것이 좋습니다. 우리는 유닛 크기가 단일하다! 이러는 순간 문제는 정말 많이 단순해 집니다. 우리는 지형단위로만 길찾기 하고 다음에는 장애물 회피법만 쓴다. 우리는 'ㄷ'자 지형같은건 안쓴다. 등등.... 복잡하게 생각하면 또 끝도 없습니다. 물, 불은 피해가자, 충돌예측, 높이 고려 등등.....

자신의 게임의 특성에 맞게 디자인하고 설계하고 최적화 하는 것이 정답입니다. 누가 Pentium 50 좀 무린가, Pentium 100에서 8명의 Player가 유닛 제한 200을 놓고 멀티 플레이를 실시간으로 한다고 누가 생각했을까요. 길찾기만 하나요? 스타는 지금보면 별것 아니지만 지금 다시 봐도 명품임에는 확실합니다. 스타2가 곧 나온다니 간절히 기다려 봅니다.
회사에서 짬짬이 쓰다보니 성의가 없지만 이해해 주시기 바랍니다. 지금은 게임 회사가 아닙니다. ㅠ.ㅠ
liteplayer
Posts: 43
Joined: 2003-10-30 16:00
Contact:

이벤트 기반으로 하여...

Post by liteplayer »

안녕하세요?

저는 플레이어가 콘트롤이 가능한 일반 유닛들도 이벤트 기반으로 하여
타일맵의 인덱스에 접근해서 비트플래그를 바꿔줄것같습니다.
크리쳐들이나(클릭하면 노락색으로 활성화 서클이 표시되는...) 공중에 띄어진
건물들을 제외한 모든 오브젝트들이 저것에 적용될거라 생각합니다...
(에.. 또 있을까요? 스타 했던지가 좀 오래되서 --;)
유닛끼리의 충돌객체와는 별개로 말이죠.

지금은 어떠한지 잘 모르겠지만, 일꾼 콘트롤 할 때 미네랄 클릭을
계속적으로 해서 gathering명령을 계속 내리게하여 한곳으로 모은다음
적에게 대항하는 전략이 있었던것으로 기억합니다.
기본적으로 일꾼들은 gathering을 하면서 서로의 충돌체크를 하지 않아서,
채집을 원활히 하게끔 하므로 일꾼간의 충돌은 없는걸로 보아 저런 생각을 하게 됐습니다.
chkino
Posts: 8
Joined: 2006-08-21 12:57

Post by chkino »

유닛의 크기는 디테일 맵의 최소 타일 입자 단위의 정수배가 될 수 밖에 없습니다.
여기에 해답이 있었군요

졸업작품으로 RTS를 제작중 입니다

길찾기 때문에 골머리를 앓아 왔는데

정말 막혔던게 뻥 뚫리는 기분이네요

좋은 글 올려주셔서 감사합니다
Post Reply