PGR21.com


Date 2010/02/28 12:26:26
Name 김연우
Subject 스타2의 길찾기 AI

스타2의 유닛 이동에 있어 스타1, 워3과 구별되는 주요한 특징은 길찾기 AI가 매우 다르다는 점인거 같습니다.

개발자가 어떻게 개발하느냐에 따라 다르지만, RTS의 게임내 길찾기 AI는 맵 Level과 유닛 Level로 구분됩니다. 사람으로 치자면 '신촌가야 하니까 사당가면 되겠네~'하는 식의 전체적인 길을 잡는 것이 맵Level이라면, 지하철 내에서 이동하던 중에 앞에 사람이 있으면 비켜간다던가 하는 것이 유닛 Level이지요.

맵 Level의 길찾기에 대해서는 딱히 변화한거 같지 않습니다만, 유닛 Level에서는 전혀 다른 형태로 변화한 것 같습니다.


스타1나 워크3, 그 외 대부분의 RTS게임에서 유닛 Level의 길찾기는

1. 장애물 파악 (건물 및 유닛)
2. 목적지로 이동하기 위한 길을 그림
3. 2번에서 그린 길을 따라 이동

이상 세가지 공식을 따릅니다 .


이러한 길찾기는 매우 정확한 길찾기가 가능합니다만, 한가지 문제가 있습니다. 2번, 즉 목적지로 이동하기 위한 길을 찾는 연산이 너무 느리다는 것이지요. 사람은 대충 보고 알지만, 컴퓨터는 앞으로 갔을 경우, 뒤로 갔을 경우, 다시 앞으로 갔는데 옆으로 갔을 경우 등등을 모두 따져보고 그중에 제일 빨리목적지에 도달하는 것을 찾는식이라 그렇습니다.

그래서 여러가지 꽁수가 들어가지요. 꽁수 중에 하나가 유닛 수 제한입니다. 그러면 동시에 길을 찾아야 하는 유닛이 12기로 제한되니까요.

하지만 스타2는 다릅니다. 동시에 몇기의 유닛이든 한꺼번에 움직일 수 있지요. 확인하진 않았지만 거의 무한대였습니다. 이것이 가능해진 이유는 길찾기 연산의 비용을 거의 없애버렸기 때문입니다. 즉 스타2는 사실상 유닛 Level의 길찾기를 하지 않습니다.


유닛 level의 길찾기를 하지 않는다?
스타2의 유닛 Level길찾기는 다음과 같다고 추측됩니다.

1. 그냥 목적지를 향해 이동
2. 주변 유닛과 충돌
3. 충돌한 유닛은 옆으로 비켜준다.

즉 내가 피해간다기 보다, 상대방을 밀치는 쪽이 더 가깝습니다. 물론 홀드를 눌러주면 3번, 즉 밀쳐져도 이동하지 않지만, 대부분은 이런 방식으로 수행합니다. 마치 공중유닛과 비슷하지요.
그래서 각각의 유닛들은 '내 옆에 누가 있나'만 생각해서 옆으로 비켜주면 됩니다. 길찾기 연산이 없습니다. 그래서 수백기의 유닛이 동시에 이동해도 문제가 없습니다.



하지만 이런 식으로 이동하는 만큼 게임성이 좀 다르지요. 스타1나 워3와는 다르게 스타2의 유닛들은 굉장히 둥글둥글하게 잘 뭉칩니다. 이것도 이러한 길찾기AI의 특성 때문입니다. 또한 교전중에 뒤에서 우왕좌왕하는 유닛도 스타1보다는 다소 많은것 같습니다.
(물론 예전식의 길찾기, 즉 유닛 Level의 길찾기를 아예 안하는 것은 아닙니다만, 그 비중이 매우 작은것 같습니다.


통합규정 1.3 이용안내 인용

"Pgr은 '명문화된 삭제규정'이 반드시 필요하지 않은 분을 환영합니다.
법 없이도 사는 사람, 남에게 상처를 주지 않으면서 같이 이야기 나눌 수 있는 분이면 좋겠습니다."
허느님맙소사
10/02/28 13:20
수정 아이콘
아무래도 마인같은 리콜대비에 적합한 요소가 없으니

뭉치기 쉬운만큼 모선의 리콜이 엄청나게 크게 작용하겠네요
Summerlight
10/02/28 13:29
수정 아이콘
실제 구현은 생각하신 내용과 꽤 다르지 않을까 싶습니다. 아군 유닛 소수만 있는 경우라면 저런 길 찾기 전략이 성립할 수 있습니다만, 그렇지 않은 예외 상황이 무척 많습니다. 스타2의 깔끔한 집단 단위 이동은 저렇게 간단하게는 구현이 어렵죠. 이를테면 저글링 여럿이 m신공 쓰는 것 마냥 광전사를 빠르고 촘촘하게 둘러싸는 것은 저런 간단한 전략만으론 안 됩니다. 제 생각엔 실제로 적용된 많은 길찾기 전략 중 하나가 비켜주기 액션이라고 봐야 하지 않나 싶군요. (헌데 비켜주기로 인해 연산량이 적어지는가는 좀 의문이 듭니다.)

디테일한 레벨의 길 찾기 횟수 및 부하를 최대한 줄이면서도 그럴 듯 하게 보이는 것이 전략 게임에서 길찾기의 목표입니다만, 이를 아예 하지 않기는 어렵습니다. (이걸 안 하면 스타2의 모든 유닛들이 드래군화될겁니다 아마) 스타2는 12년 만에 나온 신작이고, 그 사이에 연산 능력이 수백배 가량 상승한 상황이기 때문에 굳이 스타1보다 길찾기 부담을 줄일 필요도 없고요.
김연우
10/02/28 13:57
수정 아이콘
비켜주기 연산이 있느냐 없느냐의 차이는 장애물 유닛이 막느냐 적으냐의 차이가 됩니다.

스타1의 장애물 유닛은 '움직이는 아군 유닛 제외한 전부'로 보입니다. 서있는 아군 유닛, 적군 유닛은 장애물로 판단하여 이동하고 이동하는 아군 유닛은 '가로막지 않을 것이다, 또는 가로막더라도 금방 비켜줄 것이다'라는 기대를 갖고 긍정적으로 길을 찾지요. 그러다가 부딪히면 움직이는 아군 유닛도 장애물로 인식하구요.

스타2의 장애물은 '홀드한 아군 유닛'과 '적군 유닛'입니다. 즉 가만히 서 있는 아군 유닛은 장애물로 인식되지 않지요. 그런데 사실 길찾기를 할때 제일 많이 영향을 끼치는 것이 '가만히 서있는 아군유닛'입니다. 교전시간을 제외한 대부분의 유닛이 그러니까요.
따라서 장애물로 인식되는 유닛은 거의 교전중인 적 유닛 밖에 없게되지요.



장애물이 적어지면 단 한번만에 정답을 찾아낼 가능성이 매우 높습니다. 그냥 알고리즘에 따라 휴리스틱하게 A*로 그으면 바로 정답이 나올테니까요. 주변에 장애물 유닛이 없다면 아예 길을 긋는 연산을 무시할 수도 있습니다.

물론 조금 더 자세히 말하면 유닛 충돌 크기에 대한 차이, 유닛 충돌을 확인하기 위한 블록의 크기, 밀어치기 자체에 대한 적용 방법 등에서 차이가 많이 나오겠지만,

게임하는 입장에서 '마치 공중유닛처럼 미끌어지는 지상 유닛'이 전투나 유닛 배치에 많은 영향을 주 때문에 거기에 집중해서 이야기 한 것입니다. 제가 설명을 잘 못했네요.
10/02/28 14:12
수정 아이콘
한번에 선택할 수 있는 유닛수 제한이 길찾기 연산과 관련이 있었군요...흥미로운 사실이네요.
부엉이
10/02/28 16:33
수정 아이콘
유닛비비기가 더힘들어진다라는 의미일까요?
10/02/28 17:59
수정 아이콘
컴퓨터공학부 다닐때에 다른 친구들 몇명이 스타만든다고 방학내내 프로그래밍 하는 모습을 보았는데, 친구들 말로는 스타에서 중요한 부분중 하나가 길찾기라고 하더군요. 위에 나온 알고리즘 A*등등은 인공지능 시간에 들었던 내용인데 여기서 들으니 감회가 새롭군요^^. 스타1과 2에서 어떠한 알고리즘을 썼는지는 모르지만, 많은 노력이 들어가 있지 않을까 하는 생각이 드는데요, 윗분들은 로봇공학 하시는 분들인가요? 너무 어려운 이야기들을 하시네요.웁쓰.
목록 삭게로! 맨위로
번호 제목 이름 날짜 조회
92 초보가 보는 테란의 문제점...; [12] 마빠이3607 10/03/03 3607
91 [알림] 스타2 ... Crack 관련 게시글 [1] 메딕아빠4278 10/03/03 4278
90 토르를 어떻게 생각하십니까 [18] 김연우4445 10/03/02 4445
89 [스타크래프트2]Protoss(프로토스) 유닛 및 마법, 건물 리뷰. [4] 똑똑한드라군4361 10/03/02 4361
88 저그유저분들 거신 어떻게 상대하시나요 [12] steellord3738 10/03/02 3738
87 테란하다보니 스나이퍼 된거 같네요 [14] 김연우4407 10/03/02 4407
86 스타2 간단리뷰...;;; [19] 마빠이3994 10/03/02 3994
85 감염충좀 만져보니.... [8] 하나4445 10/03/02 4445
84 10시간 전쯤 스타2 버그 발견했습니다. [3] 탈퇴한 회원4304 10/03/01 4304
81 스타2 싱글 플레이 후기 [10] 카스4142 10/03/01 4142
80 드론님의 AI 저그대 토스.. [6] 하나3839 10/03/01 3839
79 길찾기를 하지 않는다고한 이유 [3] 김연우4718 10/03/01 4718
76 프로토스 기본 빌드(+파일런의 활용) [7] 허느님맙소사5211 10/02/28 5211
75 스타2의 길찾기 AI [10] 김연우8100 10/02/28 8100
74 중저음이 사라진 이펙트 사운드에 대한 아쉬움.... [6] 민트줄립3707 10/02/28 3707
72 [질문]넥서스 스킬말이죠..(이름이 기억이...) [4] RookieKid4022 10/02/28 4022
71 캐리어 질문 리틀몽크2847 10/02/28 2847
70 테란 플토 대공 능력이 이슈군요.. [13] sinfire4451 10/02/27 4451
69 관문과 차원관문에 대해.. [8] 하나3818 10/02/27 3818
68 현재의 밸런스 이슈. [14] 루루4401 10/02/27 4401
67 요번 패치로 테란 좀 쓸만하네요. [15] 김연우4270 10/02/27 4270
66 김동수님의 밸런스 평가 [11] 루루5399 10/02/27 5399
64 패치정보 (버전 0.4.0.14133) [13] 엔뚜루3702 10/02/27 3702
목록 이전 다음
댓글

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