기억창고

회사 동료에게 소개 받은 책으로 (이전 교수님께 들은 얘기론, 세가 = 게임 프로그래머의 학교라는..)

PSP프로그래밍 .... 보다는 3D에 대한 기본 지식을 다시 복습하고 있습니다.

책은 세가에서 신입사원 프로그래머에게 실전 프로그래밍의 복습용으로 제작된 회사 문서를 정리하고 추가해서

펴낸 책이라고 하네요. (옆의 아이폰 터치(아이폰 요금 짜증나서 끊었기에)으로 이 책의 두께를 알 수 있습니다. 약850p)

물론 안은 일어 글씨만 잔뜩 써있는게,..... 마치 API 정복 책을 보는거 같습니다만,

확실히 설명은 잘 되어있네요. 읽다가, "아.. 이런게 있었지" 가 많이 떠오릅니다.

우리나라에서 저 책이 번역이 있으면 대학교에서 게임 프로그래밍 기본 소양으로 배울수 있을꺼 같습니다.

책 내용 레벨은 대충 대학 3학년 정도... 군대 갔다오고 나서 머리 포멧된 상태에서 저걸 정독하면
3D 기본 프로그래밍, C,C++ 기본 소양, DLL 처리 등이 재 입력됩니다 ^^..

한국인 프로그래밍에선 통할지 안통할지.. 잘 모르겠군요
(책 내용중엔 STL 사용을 가급적 배제 하라는 내용이 있습니다. (MAP이면 괜찮지만 하면서요, 메모리 관리 문제등으로..)

혹시나 해서 yes24에서 찾아봤는데..
http://www.yes24.com/24/goods/3362046
...
orz

NPC의 인공지능 프로그래밍에 대해서 간단히 정리합니다. 처음이라 감이 안 오시는 분은 참고하세요. 매우 허전한 아이디어 정도이지만 화이트데이에 수위 정도의 구현이라면 무리가 없을 것입니다. (화이트 데이에서 초기 AI랑 기본 구현만 제가 해서 사실상 이 글 내용 정도밖에는 잘 ...^^ - 주로 수위가 버벅거리는 부분은 저랑 관련 있고, 재미있는 부분은 관련이 없는.. T_T)

1. Introduction

게임에서 인공지능이 적용되는 부분은 많지만 일반적인 게임에서 겉으로 드러나는 부분 중 가장 큰 비중을 가지는 부분은 NPC 의 처리 일 것입니다.
게임에 따라 인공지능의 난이도나 구성은 크게 차이가 나지만 일반적으로 가장 많이 접하는 NPC(특히나 몬스터, 주민들)은 어느 정도 비슷한 패턴을 가지고 있습니다.
NPC 처리를 크게 지능적인 판단을 하는 부분과 기본적인 행동을 하는 부분, 두 분야로 구분할 수 있을 것입니다.
신경망, 퍼지, 유전자 알고리즘 같은 고급 기술을 사용하는 전자의 처리가 인공지능의 핵심이라고 할 수도 있겠지만, 개인적으로는 게임에서의 인공지능은 오히려 후자의 처리가 비중이 더 크고 중요한 부분에 해당된다고 생각됩니다. 그래서 게임의 인공지능을 처리하기 위해선 인공지능의 분야뿐 아니라 일반적인 게임 프로그래밍에도 어느 정도 기본이 있어야  수월하게 적용할 수 있습니다.
이 글에서는 후자에 해당하는 기본적인 NPC의 행동 처리에 대해서 다루어 보도록 하겠습니다.
(중심은 NPC지만 다른 오브젝트들에도 공통적으로 적용할 수 있는 것들입니다.)

2. 행동 (상태, 명령)

- 유한 상태기계 (Finite State Machine)

유한 상태기계는 쉽게 얘기해서 미리 정해진 상태를 일정한 규칙대로 옮겨가는 것입니다. 아주 간단한 예를 들어보면 아래와 같습니다.

매 프레임 위와 같은 처리를 반복한다면 이 오브젝트는 밥 먹고, 오락하고, 잠자기, 밥 먹기, 오락하기, ... 를 반복할 것입니다. 기본적인 행동 패턴은 위와 같이 처리할 수 있습니다. (행동 패턴 말고 switch 를 쓴다는 식의 구현으로의 접근은 아니고... 의미가...)
여기서 핵심은 상태에 맞는 *행동*을 한다는 것이고 *조건*이 되면 다른 상태로 *분기*된 다는 것입니다.

슈팅 게임의 별 볼일 없는 적(소위 자코)이나 미사일같은 오브젝트처럼 단순한 인공지능의 경우에슨 단순히 FSM 으로도 처리가 가능할 것입니다.

- 명령 시퀀스 : 스택 기계 (Command Sequence : Stack Machine)

기본적으로는 FSM 으로도 어느 정도 구현이 가능하지만 확장하려면 손이 많이 갑니다. (특히나 길 찾기 랑 결합되면 이동에 관한 여러 가지 상태를 만들어 처리해야 하기 때문에 코딩량이 많아집니다.) 이 경우에는 명령어를 쌓아 놓고 처리하는 식으로 접근하게 되면 좀 더 유연하게 처리할 수 있습니다.
스택방식을 사용하는 방법을 추천합니다. (GPG에서는 큐 방식이 소개되어 있는 데, 개인적으로 큐 방식은 기능 확장하기엔 부적절한 방식이라고 생각됩니다. 판단은 직접하세요.)

만약 길 찾기 처리를 통해 얻은 이동해야 하는 경로가 A -> B-> C-> D 라고 하면 다음과 같이 명령을 쌓아둡니다. (D, C, B, A 순으로 쌓아둡니다.)

스택의 특성상 명령을 얻게 되면 "이동:A", "이동:B", "이동:C", "이동:D" 의 순으로 들어오게 되므로 정상적으로 처리할 수 있습니다.

그냥 스택 기계만으로 FSM을 구현할 수도 있겠지만 (항상 현재 상태를 맨 위에 Push 해 두는 식으로 처리하면...) 간단하게 확장하기 위해서 상태 중에 COMMAND_SEQUENCE 상태를 두도록 하겠습니다.

이런 식으로 스택 처리 기계를 위치시킵니다. 여기서 앞의 예를 적용해보기로 하고 간단히 스택 명령어 처리를 아래처럼 해보면

명령을 쌓아두는 식으로 오브젝트가 A, B, C 를 거쳐서 D까지 이동함을 예상할 수 있습니다.
이 장점은 NPC가 할 일을 유동적으로 설정할 수 있다는 것입니다. 만약 엘프 같은 파티 오브젝트가 A의 위치로 가서 C를 공격하고 B의 위치로 이동해야 한다면 아래처럼 명령을 쌓아두면 됩니다.

만약 상태기계로만 처리해야 한다면 여러 가지 상태와 변수들을 같이 사용해야 하지만, 명령어를 쌓아두는 방식을 손 쉽게 순차적으로 행동을 지정할 수 있습니다. (이 방식은 큐나 스택이나 쌓는 순서만 다를 뿐 동일합니다.)

명령 시퀀스를 큐(Queue)가 아닌 스택으로 처리하게 되면 몇 가지 추가적인 이점이 생깁니다. 화이트 데이 수위의 초기 명령어 시퀀스는 아래 같은 식입니다.

수위의 순찰 코스는 1 -> 2 -> 3 -> 4 -> 1 -> ... 식으로 반복되게 설정되어 있는 것입니다. 그럼 처음 언급한 것과 차이 점은 무엇일까요 ? 바로 "이동" 명령이 아니라 "길찾기" 명령이라는 것입니다.
수위차 짠 하고 시작하는 시점에서 "길찾기" 명령을 만납니다. 이 때 길 찾기를 이용해서 '위치1' 로 이동하기 위해서 '위치A' -> '위치B' -> '위치C' -> '위치1' 로 이동해야 한다는 정보를 얻어내고 '위치1'로 이동하는 명령을 하게 되면 명령 시퀀스는 아래처럼 됩니다.

이렇게 되면 순차적으로 A, B, C 를 거쳐 '위치1' 에 도착하게 되고 도착한 위치에서 '위치2'로 이동하기 위한 명령 시퀀스를 설정하게 됩니다. 이런 식으로 특별한 장치 없이도 자연스럽게 원하는 결과를 얻을 수 있습니다.
만약 큐로 처리해야 한다면 명령어에 레벨을 두어서 계층적으로 처리해야 할 것입니다. (순찰에 대한 명령 시퀀스와 길찾아 이동하는 것에 대한 명령 시퀀스가 따로 존재해야 되겠죠.)

화이트 데이에서 수위의 명령 시퀀스 중엔 아래와 같은 부분도 있습니다. (자세히 기억은 안나지만...^^) 위치 0에서 시작해서 문 1을 열고 1, 2를 거쳐서 유저가 갈 수 없는 문2를 열고 들어가서 문닫고 30초후에 다시 반복하는 식으로 유저가 갈 수 없는 문 1과 문 2를 열면서 입구만 있고 실제로는 있지도 않은 층계를 넘나들면서 뻔뻔하게 순찰을 하게 됩니다.

누구나 아는 FSM 와 스택 머신을 이용하면 기본적인 NPC의 행동은 큰 무리 없이 표현할 수 있습니다.

3. 판단 (이벤트)

기본적으로 행동을 정의 했지만 좀 더 NPC의 행동을 확장하기 위해서는 여러 가지 판단을 처리해야 합니다. 이 판단을 할 시점이 먼저 중요한 데, 여기에 이벤트 시스템이 사용됩니다.

먼저 1초 마다 A라는 행동을 하기 위해서 접근한다고 생각해보면

식으로 정의해서 OnTimer 를 매프레임 실행하는 방식으로 접근 할 수 있습니다. 이 방식에는 큰 문제가 없지만 AI를 확장하기 위해 스크립트를 도입하게 된다면 약간 조율이 필요합니다. 만약 OnTimer 를 스크립트로 작성한다면 무거운 스크립트 루틴에서 1초 지났는 지를 판단해야 되기 때문입니다. (아무리 최적화된 스크립트 시스템이더라도 매 프레임 호출되는 것은 바람직하지 못합니다.)
이런 상황은 반드시 피하기 위해서 OnTimer 는 그냥 C 루틴으로 작성하고 A 라는 행동을 스크립트로 정의합니다.
OnTimer 루틴에 의해 조건을 체크하는 것은 폴링(Polling) 방식이긴 하지만 실제로 판단에 해당되는 A는 1초가 지난 시점에 한번이기 때문에 A의 관점에서는 이벤트 방식이라고 할 수 있습니다.

이런 관점에서 NPC 인공지능에서 이벤트가 발생하는 것은 능동적인 것과 수동적인 것 두가지로 구분 할 수 있습니다.

- 능동적인 방식

능동적인 방식이란 조건을 적극적으로 오브젝트가 검색하는 것으로 위에 소개한 방식이 여기에 해당됩니다.
화이트데이의 수위의 시야에 유저가 보이는 시점에서 이벤트 스크립트가 호출되는 데, 그 것이 여기에 해당됩니다. 수위의 프로세스에 매 프레임 시야에 유저가 보이는 가를 체크하는 루틴이 있고 (실제로는 몇 프레임에 한번씩 체크합니다만...^^), 발견되는 시점에 이벤트가 생기도록 되어 있습니다. 이때 수위는 호루라기 불고 추적 상태로 전환한 후 쫓아오게 스크립트로 작성되어 있습니다.
공격 상대가 시야에 보일 때 발생하는 이벤트, 일정 시간 간격으로 발생하는 이벤트등 여러 가지가 있습니다.
요점은 앞서 얘기한 것처럼 적극적으로 조건을 체크하되 가장 핵심적인 판단에 대한 것은 이벤트 방식으로 접근해야 한다는 것입니다.

- 수동적인 방식

이것은 어떤 조건이 되면 발생하는 이벤트로, 공격을 받는 다거나, 에너지가 0이 되는 경우가 여기에 해당됩니다.
주로 오브젝트간의 메세지 교환 시에 발생하는 것으로 판단이 필요한 조건에 이벤트가 발생하도록 작성하면 됩니다.
화이트데이의 경우엔 소리를 낼 경우 수위에게 메세지를 보내는 데 수위는 그 소리를 듣고 판단을 하게 됩니다. (수위 근처에서 문을 열어서 소리를 내면 수위의 스크립트가 호출되고, 스크립트에서는 조건에 따라 해당 위치로 정찰을 가도록 되어 있습니다.)

사실상 이벤트가 능동적으로 호출 되는 지, 수동적으로 호출 되는 지는 구현상에서 구분될 뿐이고, 적절한 조건에 이벤트가 발생하는 것이 중요합니다. (게임에서는 가능한 최소의 이벤트가 호출되는 것이 인공지능 처리 속도의 관건입니다.)

이벤트가 발생 했을 때 어떤 식으로 처리할 까에 대한 것은 여기에서는 다루지는 않겠습니다. (게임마다 다르고 사용되는 기술도 다양하기 때문입니다. - 제대로 모르기도 하고... T_T)

기본적으로 확장을 하기 위해서는 스크립트 도입을 고려해 볼 필요가 있습니다. 물론 순수하게 파라메터들을 이용해서 코딩해도 충분히 확장할 수 있고, 괜찮은 방법이 될 수도 있습니다만, 인공지능에 대한 다양한 컨트롤이 필요할 경우에는 스크립트를 사용하는 것이 많이 유리합니다.

그리고 퍼지나 신경망 같은 고급 기술을 사용하면 좀 더 유연하게 풀 수 있습니다.
예를 들어 신경망을 이용해서 학습을 구현한다면 의도하지 못한 재미있는 결과를 얻을 수도 있을 것입니다. (예를 들어 여자 캐릭터에게 자주 공격 당한 NPC는 능력에 상관없이 여자 캐릭터에게 공격 받으면 도망간다거나 하는...)
퍼지를 이용하면 공격을 몇 번 받은 캐릭터 평소보다 쉽게 화를 낸다거나 하는 식의 접근도 가능할 것입니다.
그 밖에도 인공 생명을 이용한 여러 가지 알고리즘등을 활용한다면 게임에서의 NPC의 행동을 더욱 풍부하게 할 수 있을 것입니다.
(M모 게임은 NPC와 사귈 수도 있다고 하던데...)

4. 기타 아이디어

마지막으로 이동과 관련된 나름대로의 몇 가지 아이디어를 적어봅니다.

- 추적

추적의 기본적인 컨셉은 타겟의 위치로 이동입니다.
물론 무조건 타겟 방향으로 이동하는 것만으로도 어느 정도 추적이 되지만 장애물이 막고 있거나 하다면 이상해질 수 있습니다. 이때 단순히 상대방의 위치로 이동하는 식으로 접근하게 되면 웃기게 길을 따라 가게 되어 거리를 좁히기가 쉽지 않습니다. 여기서 제가 제안하는 방법은

A. 타겟이 보이고 이동 가능하면 방향을 타겟 방향으로 하고 이동
B. 아니면 타겟까지 길 찾기해서 찾은 경로의 중간 위치까지 이동

입니다. 대부분 무난하게 괜찮은 결과를 얻을 수 있습니다. (물론 부가적으로 이동 등을 잘 해야 겠습니다만...)

우선 첫번째 경우는 당연히 보면서 타겟이 따라가기 때문에 계속 시야에 있고, 이동 가능하다면 타겟과 만날 수 있습니다.
주로 문제가 되는 것은 보이지 않는 경우입니다. 가장 쉽게 추적하는 방법은 매 프레임 상대방의 위치로 길 찾기하고 그 길방향으로 이동하는 것입니다. 하지만 게임에서는 철저히 피해야 할 방법입니다. 그럼 길 찾기를 적게 하면서 효율적으로 따라가는 방법을 찾아야 하는 데, 가장 쉽게 생각할 수 있는 것은 n 초마다 혹은 m 미터 이동마다 갈 경로를 갱신하는 것입니다. 이 방법도 괜찮긴 한데, 타겟과의 거리에 따라 간격을 조절해야 하기 때문에 좀 까다로워 질 수 있습니다.
여러 가지 테스트 해 본 결과 가장 효과적인 결과를 얻는 방법이 두 번째 방법입니다. (물론 이동 속도에 따라 중간 위치는 조절될 수도 있습니다.) 오브젝트랑 타겟의 길을 만든 후에 서로를 향해 달렸다고 가정했을 때 만나는 위치까지 이동한 후에 다시 그 곳에서 같은 방법으로 경로를 결정하는 것입니다. (상대가 시야에 나타나면 목표지점 무시하고 A번의 방법으로 추적합니다.) 상대가 어떤 경로로 도망가든지 빈틈없이 적은 길 찾기 횟수로 거리를 좁히면서 추적할 수 있을 것입니다.
사실은 보이지 않는 데 길을 따라 간다는 건 사기에 가깝지만 약간의 조건만 두면 (거리가 너무 멀면 포기 같은...) 실제로 상대방의 소리나 인기척을 고려해서 추적하는 거와 거의 비슷한 결과를 얻을 수 있습니다. (게임이니까... ^^)

- 장애물 피하기

길 찾기는 두 가지 타입으로 작성합니다. 정적인 상태의 길 찾기와 동적인 오브젝트를 고려한 것 길 찾기입니다. 일반적인 길 찾기는 static 한 상태로 합니다. 동적인 오브젝트를 고려해서 길 찾기를 한다면 멍쩡한 길을 꼬불 꼬불 돌아서 가는 일이 발생합니다. (길 찾기하는 시점에는 오브젝트가 있던 자리기 때문에...)
정적인 상태의 길로 가다 보면 이동 못하는 지점이 생깁니다. 이때는 그 지점에서 내가 가고자 하는 경로 중에 오브젝트가 없는 적당한 거리로 동적인 오브젝트를 고려해서 길 찾기를 합니다. 그러면 그 지점에서 막고 있는 오브젝트를 피해서 적당한 거리로 이동하고 스택에 의해서 다시 원래의 갈 길을 가게 됩니다.
화이트데이는 복도가 좁아서 사다리가 애매하게 막고 있으면 수위가 길을 못 가는 일이 생기곤 했는데, 어느 날 작업하다 수위가 버벅거리길래 어떻게 하나 생각하고 있는 데, 갑자기 사다리를 방망이로 부셔버리고 이동하는 거 보고 놀란 적이... (인공지능 프로그래밍 하시던 아뇨 아저씨가 충돌시에 발생하는 이벤트 루틴에 충돌한 오브젝트가 사다리면 부셔버리게 만들었다는... ^^)

- 자연스럽게 이동하기

이건 기회가 되면 샘플과 함께 다루었으면 하는 내용입니다만 간단히 얘기해 보겠습니다. 만약 이동하고자 하는 경로가 A -> B 일 경우 A까지 이동한 후에 B를 향해서 돌면서 이동하게 됩니다. 2D 게임의 경우 별로 어색하지 않습니다만 3D 게임의 경우에는 충돌문제 때문에 제자리에서 꺽고 돌아야 하는 경우 엄청 이상하게 됩니다. 이 경우에는 A 까지 이동하는 중간 중간 A 와 B 사이의 적당한 지점이 이동 가능한 지 (장애물 없는 지) 체크해서 만약 이동 가능하다면 A로 이동하는 거 취소하고 그 지점으로 이동하도록 수정합니다. 이런 식으로 계속 반복하면 A 에서 B로 조금씩 적당하게 경로를 수정하면서 자연스럽게 이동하게 됩니다. (베지어 곡선 비슷하게 생각하시면 되겠네요.)

5. Reference

"AI Game Programming Wisdom"
Charles River Media 출판사
Steve Rabin 외
(번역서:정보문화사)

"Game Programming Gems 시리즈"
Charles River Media 출판사
Mark DeLoura 외
(번역서:정보문화사)

"AiWizWiki"
http://aiwiz.2ing.net

"AIwisdom.com"
http://www.aiwisdom.com

"AiStudy.co.kr"
http://www.aistudy.co.kr

"Guru who gears a.i to life"
http://www.gurugail.com

"Generation5"
http://www.generation5.org

 

이글의 출처 : http://gamecode.org/tt/category/programming/general

어쨋든 출처는 http://plusd.itmedia.co.jp/games/articles/0709/18/news006.html

음... 이미지 1장이라고 한다.
구현할수 있을까...?

참고로 위의 그림은 "스즈미야 하루히의 약속"이라는  PSP게임의 모션보이트 효과이며
저 효과에 사용된 그림은 1장이라고 한다.

추가 자료 사이트
http://www.motionportrait.com/about/

기말 턴프로젝트로 만든 게임
성의 없다고 생각할지도 모르겠지만...
나름대로 최선을 다했다고 생각하는 게임입니다.. orz
사용방법은 ppt내에 있고, 핵심 소스 내용도 ppt에 있습니다.

컴파일을 못시키겠다 싶으시면..
ODE(www.ode.org)를 가져오신뒤, sample소스(설치 디렉토리밑에 bulid ->...)
의 아무 샘플 main에다가 copy and phase 하시면 됩니다.
(아.. 마지막 textures 디렉토리 설정은 sample소스의 것을 따라가야 할껍니다.)
사실 천마를 구현한다고 했지만 실제 미사일은 총알처럼 나간다는것...

예전 방공대대 출신으로서... 향수젖는군요.

마지막으로 ppt에 딴지 걸듯한 사람들이 있을꺼 같네요.
음.. 사실 천마로는 미그기 잡기엔 과분한 용도죠 ㅡ_ㅡ..
그냥 그려러니 하세요.
참고로 mig-19기는 북한정도만 쓰고 있습니다. ㅡ_ㅡ.....