PGR21.com
다시봐도 좋은 양질의 글들을 모아놓는 게시판입니다.
Date 2004/02/07 20:03:13
Name 김연우
Subject 스타크래프트 파고들기 1 - 길찾기 AI에 관해
-맵 길찾기와 유닛 길찾기.

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

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

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

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

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

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

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


-A*알고리즘

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

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


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

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

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

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

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

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


-드래군은 왜 방황하는가

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

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

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

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

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

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


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

통합규정 1.3 이용안내 인용

"Pgr은 '명문화된 삭제규정'이 반드시 필요하지 않은 분을 환영합니다.
법 없이도 사는 사람, 남에게 상처를 주지 않으면서 같이 이야기 나눌 수 있는 분이면 좋겠습니다."
대책없음
04/02/07 20:07
수정 아이콘
이 글을 보니 드라군의 두뇌가 제것과 비슷해 지는 기분입니다
04/02/07 20:17
수정 아이콘
너무 어렵다는...파고들기2탄을 기대할께용^^;
04/02/07 20:21
수정 아이콘
재밌네요;
안녕하세요
04/02/07 20:27
수정 아이콘
잼있네요^^
드라군 귀여워요~
지겨울 만큼 계속되는 밸런스 논쟁보다 이런 글이 더 좋다는 것은 저만의 생각일까요?
넌내뒤가어울
04/02/07 20:37
수정 아이콘
아.......머리가 깨질껏 같애(색즉시공 한 대사)
낭만다크
04/02/07 20:44
수정 아이콘
내일 아침에 일어나서 맑은 정신으로 봐야겠습니다 -_-;
BoxeR'fan'
04/02/07 20:47
수정 아이콘
하하 재밌네요...
(나름대로 이해했다고 굳게 믿는 중..)
박대호
04/02/07 21:00
수정 아이콘
대단하십니다
묵향지기
04/02/07 21:18
수정 아이콘
프로그램 짜시는 분같군요 ^^;

좋은글 보고갑니다.
총알이 모자라.
04/02/07 21:49
수정 아이콘
그럼 결국 드래군의 방황을 최소화하는 길은 빠른 손놀림이 필수겠네요. 박정석 선수나 강민 선수가 손이 빠르다는 이야기가 되는군요...
PeculiarDay
04/02/07 22:37
수정 아이콘
프로그래밍적으로 보면 스타크의 유닛 길 찾기는 크게 두 가지라고 합니다. 그 첫 번째는 가장 앞서있는 놈을 뒤의 놈들이 줄줄이 따라가는 식이고, 두 번째는 맵 자체에 이미 유닛들이 다니는 길이 있다는 거라더군요. 실제로 유닛을 특정 지역에 보낼 때 가는 길은 늘 동일합니다. 그 길에 장애물이 길게 늘어서면 출발부터 길을 다르게 가면 유닛이 출발할 때 자신이 갈 길을 검색한다는 의미인데, 장애물이 있어도 일단 가는 길은 동일하다는 거지요.
당시 저사양에서도 원할하게 구동하기 위해 최대한 CPU 를 괴롭히는 행위를 줄인 블리자드의 놀라운 잔머리들이 대단하게 느껴집니다 ^^
04/02/07 22:55
수정 아이콘
흐으으음....제가 컴퓨터 소프트웨어과 안 다녔으면 전혀 무슨소리인지 못알아 들을뻔 했군요^^;;
Mr.쿠우의 절규
04/02/08 00:11
수정 아이콘
첫번째 댓글에 올인 ㅡ.-)=b
"이 글을 보니 드라군의 두뇌가 제것과 비슷해 지는 기분입니다"
무계획자
04/02/08 00:17
수정 아이콘
요즘 프로그래머들이 용량이 남아 돌아서 방만하게 짜서 그렇지
스타가 개발되던 시절만 해도 용량이 딸려서 정말 최적화시켜서 잘 짰었죠.
A* 알고리즘이 뭔지는 모르겠지만 아마 n log n 이겠죠? -_-
04/02/08 00:40
수정 아이콘
다시 보고 싶은 글일 것 같읍니다. 추천계시판에 넣어주시면 감사하겠읍니다.
토마토터틀
04/02/08 01:24
수정 아이콘
..이야 진실로 유용합니다.
그동안 왜 드라군이 저렇게 바보같은; 짓을 할까 싶었는데,
조금은 그에대한 답이 보이는 것도 같군요.
더불어 에이스타.. 라. 멋진 알고리즘이군요 !!
다음편도 기대하겠습니다 ^^
04/02/08 01:33
수정 아이콘
오...멋진 글입니다. 갑자기 드래군이 막 이해될려고 하는 군요. 추게로 보내줍시다에 올인합니다.
본호라이즌
04/02/08 01:38
수정 아이콘
게임 중계시 해설자분들중 최초로 이 알고리즘을 언급하실 분은 누구일까요? 흠흠..
04/02/08 02:02
수정 아이콘
1시간 뒤에 다시 보니, 조금 이해가 되네요.. ^^
저도 다음 편 기대하겠습니다.
04/02/08 03:05
수정 아이콘
밸런스 법칙에 이어 또 다시 좋은글 멋지시네요^^
남자의로망은
04/02/08 04:11
수정 아이콘
스타크 유닛은 (지상유닛에 한해서) 크기가 클수록 길을 잘 찾지 못하죠.가디언이 캐논에 맞거나 리버가 성큰에 맞는것도 이와 비슷한 논리로 알고 있습니다.
시미군★
04/02/08 05:12
수정 아이콘
저글링을 입구에 홀드시켜서 틀어막았을때 scv가 올라가려고 하는데 저글링을 보기도 전에 밑에서 헤메는건 어떤 현상이죠?
04/02/10 13:31
수정 아이콘
좋은 글 감사합니다. 추게에서 또 보고싶어요 :)
Progrssive▷▶
04/02/10 22:38
수정 아이콘
와우!!!멋진 글이에요!!잼있게 잘 읽었습니다~~
04/02/11 20:46
수정 아이콘
아 이해가 잘 가요~~
(대략 뭔지 하나도 모르겟다는;;;)
윤수현
04/02/12 00:48
수정 아이콘
그러니까 결론은 드래곤은 계속 컨트롤해줘야 한다는 얘기....군요
김대선
04/02/12 01:02
수정 아이콘
1.그러니까 유닛끼리 마주쳤을때 상대 유닛의 길을 막으려면 반시계 방향으로 움직여야 한다는 말이군요...
2.제 경험상으로는 여러번 클릭을 하는것이 안그래도 작은 드래군의 뇌에 무리한 부하를 주는 것 같습니다.
전 저그유저인데 저글링러커 로 언덕 올라갈때 부대단위 무빙은 단 한번만 합니다. 안그러면 막힌길로 인식하고 두번쨰 무빙 하는순간 뒤로 물러서더라구요.
3. 그래서 더욱 마이크러 컨트럴 유저들은 컨할때는 드래그로 하나봅니다.
◀玉童子의성
04/02/12 05:50
수정 아이콘
무뇌군... 프토는 이래저래 암움하군요
04/02/13 02:22
수정 아이콘
3번을 읽고 난 다음에야 겨우 이해를..T_T
그래도 드라군의 심정을 조금이나마 이해할 듯 합니다. 그동안 멍청하다고 구박했던 드라군들에게 약간의 미안함을..T_T; 좋은 글 감사합니다^^
제4의종족ㅡ_ㅡ
04/02/13 20:40
수정 아이콘
더 이상 드라군의 태생적 한계를 미워하지 않을 겁니다. ㅜㅜ
진짜 엑스터시
04/02/15 23:32
수정 아이콘
컴퓨터 만지시는 분이신가 보군요 ^^;; 무지 잼게 읽었습니다.
담번엔 스캐럽AI도 좀 분석해 주셨으면 합니다;;
아!! 평소부터 궁금했던건데, 예전에 파나소닉 16강 임요환vs김동수선수의 네오 포비든존에서의 김동수선수의 전략..패스트 아비터요..
거기서 나온 이상한버그.. 마인이 질럿을 따라가다가 아비터가 클로킹해주니깐 마인버로우 후에 다시 질럿을 인식하여 자폭하는현상..
이게 무지 궁금했거든요.. 이게 왜 그런지 좀 알려주셨스면 감사하겠습니다.
목록 삭게로! 맨위로
번호 제목 이름 날짜 조회
3513 [15] 호기심은 목숨을 위험하게 한다. [6] Story1582 22/05/20 1582
3512 [15] 신라호텔 케이크 (부제 : 나의 히어로 아카데미아) [9] Night Watch1661 22/05/18 1661
3511 [15] 1주기 [10] 민머리요정1260 22/05/18 1260
3510 나른한 오후에는 드뷔시 음악을 들어봅시다 [19] Ellun1200 22/05/17 1200
3509 [15] 다음 [3] 쎌라비2399 22/05/17 2399
3508 늬들은 애낳지마라.....진심이다... [280] 런펭5665 22/05/16 5665
3507 착한 사람이 될 기회를 박탈당한 이들이 있는가 [27] 아빠는외계인2514 22/05/13 2514
3506 [15] 꽃으로도 때리지 않겠습니다 [18] 나래를펼쳐라!!1648 22/05/12 1648
3505 러브젤 면도 후기 [47] speechless3105 22/05/12 3105
3504 우리에게는 화형식이 필요하다. 그것도 매우 성대한 [33] 12년째도피중3839 22/05/12 3839
3503 [15] 어느 여자아이의 인형놀이 [19] 파프리카너마저3236 22/05/12 3236
3502 나는 어떻게 문도피구를 우승하였나? [77] 임영웅2994 22/05/10 2994
3501 음식.jpg [42] 이러다가는다죽어2469 22/05/10 2469
3500 [테크 히스토리] 전세계 콘센트 하나로 통일 좀 해줘라 / 전기 플러그 역사 [43] Fig.12509 22/05/09 2509
3499 [15] 아빠 차가 최고에요! [18] 두동동3105 22/05/08 3105
3498 그동안 감사했습니다. [365] 여왕의심복3291 22/05/06 3291
3497 더 이상 찾을 수 없는 그 맛.. [62] 원장1715 22/05/04 1715
3496 [15] 장좌 불와 [32] 일신1449 22/05/03 1449
3495 퇴사를 했습니다 [29] reefer madness2015 22/05/02 2015
3494 집에서 먹는 별거없는 홈술.JPG [23] insane6625 22/04/30 6625
3493 인간 세상은 어떻게해서 지금의 모습이 됐을까 - 3권의 책을 감상하며 [15] 아빠는외계인3682 22/04/29 3682
3492 [테크 히스토리] 인터넷, 위성으로 하는 거 아닌가요? / 해저 케이블의 역사 [32] Fig.12667 22/04/25 2667
3491 소수의 규칙을 증명..하고 싶어!!! [64] 라덱3666 22/04/25 3666
목록 이전 다음
댓글

+ : 최근 6시간내에 달린 댓글
+ : 최근 12시간내에 달린 댓글
맨 위로