AI Game Programming Wisdom2
http://icdia.egloos.com/v/1319479
1. A*길찾기(PathFinding)
길찾기에서 절대 최소비용 경로를 찾는 가장 빠른 알고리즘이라 할 수 있다. 모든 이동의 비용이 동일한 경우, 최소비용 겅로(Cheapest Path)는 최단 경로 (shortest path)라고 할 수 있다.
Example)
A*는 속도에 대해 최적화할 수 있다. 보다 자연스러운 형태의 경로를 위해서 미학적으로 최적화 할수 도 있고, 길 찾기 이외의 다른 과제들에게도 사용할 수 있다.
2. 명령 계통구조(Command Hierarchy)
명령 계통구조는 서로 다른 수준들을 따라, 예를 들면 사령관에서 보병까지 단계적으로 내려가면서 일어나는 AI의사 결정을 다루기 위한 하나의 전략이다.
군 명령 계통에서 사령관은 전장 전반에 대한 고수준의 전략을 지시하는 반면, 보병은 개별 전투에 집중한다. 그 사이 수준의 단위들은 다양한 종류의 부대, 분대들 사이의 협력을 처리한다.
이러한 명령 계통구조의 장점은, 의사 결정들이 각 수준에서 개별적으로 일어나며, 따라서 각 의사결정이 좀더 직관적이고 다른 수준들로부터 추상화 된다는 점이다.
Example)
실시간 전략 게임, 밀리터리 게임.
RTS에서는 전반적인 전략, 분대 전술, 개별 전투라는 세 단계의 의사결정 수준들은 흔히 볼 수 있다.
3. 추측항법 (Dead Reckoning)
추측항법은 플레이어의 현재 위치, 속도, 가속에 근거해서 플레이어의 다음 위치를 예측하는 한 방법이다. 간단한 형태이긴 하지만 상당히 유용하다. 왜냐하면 대부분의 경우 물체는 짧은 시간 동안 직선으로 움직이기 때문이다. 좀더 진보된 형태의 추측항법은 물체가 이전 프레임의 위치에서 얼마나 멀리 움직일 수 있는지에 대한 지침도 제공할 수 있다.
Example)
FPS에서 게임의 난이도를 조정하는 한가지 효과적인 한 방법은 컴퓨터의 예측 사격의 정확도를 다르게 하는 것이다. 대부분의 무기들이 목표에 도달하기 위해서는 일정 시간 동안을 날아 갸야 하므로 컴퓨터는 목표의 이후 위치를 계산하고 예측위치를 겨냥해야 한다.
비슷한 예로 스포츠 게임에서는 컴퓨터가 다른 플레이어들의 이후 위치를 예측해서 공을 패스하거나 가로챈다.
4. 창발적 행동 (Emergent Behavior)
명시적으로 프로그래밍 되어 있는 것이 아닌 여러 가지 단순한 행동들로부터 창발되어 나오는 행동을 가리킨다.
일반적으로 게임에서의 창발적 행동은 저수준의 규칙들이 서로 상호작용해서 좀더 흥미롭고 복잡한 행동을 만들어내는 형태로 쓰인다.
따로 떼어놓고 보면 별로 흥미로울 것도 없는 규칙들이지만, 그걱들이 상호 작용함으로써 예기치 못한 개별 또는 집단 행도잉 나타나게 된다.
Eample)
가장 전형적인 예는 무리짓기 (Flocking)이다.
5. 대형 (Formation, 또는 진형)
집단이동 기법의 하나로 군대 대형을 흉내내는 데 쓰인다.
Example)
RTS(AOE, C&C)등에서의 자동 진형 기법. 그라나도 에스파다, 던전시즈에서의 대형 기법
6. 영향력 분포도 (Influence Map)
게임 세계 안의 세력 분포를 보여주는 수단. 일반적으로 영향력 분포도는 지형 위에 겹쳐지는 2차원 격자이다. 격자의 각 칸에 대해 칸에 있는 유닛들의 개수를 합한 것을 그 칸에 대한 영향력으로 간주한다. 또한 그 영향력은 선형적으로 또는 지수적으로 감소 되면서 주변 칸들에게도 전파된다. 그 결과로 2차원 격자에는 여러 세력들의 위치와 영향력을 나타내는 숫자들로 채워진다.
Example)
배틀 필드(FPS)에서 병사의 배치 세력에 따라서 컴퓨터(적, 아군)의 진행 방향이 결정 된다.
Sim City에서 주변에 위치한 경찰서 혹은 소방서의 영향력을 보여주는 실시간 지도를 제공함으로써 플레이어가 전략적 선택을 할 수 있다.
7. 세부수준 AI
세부수준(Level Of Detail)은 3차원 그래픽에서 뿐만 아니라, AI 기법으로도 사용 될 수 잇다. 즉 플레이어가 인지하고 중요시 여길 만한 부분에 대해서는 AI계산을 상세히 수행하고 그렇지 않은 부분은 생략하거나 간단한 계산을 사용하는 것이다.
Example)
플레이어와 에이전트와의 거리, 시야에 따라 에이전트의 갱신주기를 동적으로 결정하는 것
Starcraft 에서 컴퓨터를 일꾼과 본진만 남긴 후 Observer로 보고 있으면 아무런 일도 하지 않는다.
8. 관리자 과제 부여
각 에이전트가 자신의 임무를 결정하는 것 보다 하나의 관리자가 과제의 목록을 두고 과제에 가장 적합한 개체를 선택하는 방식. 이는 과제를 중심으로 고려하고 그것을 우선순위 부여의 근거로 삼는다는 이야기임, 관리자가 개체들의 목록을 훑으면서 각각에게 과제를 부여한다는 의미가 아님
Example)
야구에서 야수에게 가장 중요한 것은
1, 타구 잡기
2, 1루 커버 하는 것
3, 타구 잡는 야수를 백업하는 것
4, 2루를 커버하는 것
이 때 관리자는 이 임무를 가장 잘 수행할 수 있는 야수를 선택한다.
타구가 1,2루 사이에 있는 땅볼이라면 관리자는 1루수로 하여금 공을 잡게 하고 유격수로는 2루를 커버 하게 할 것이다.
9. 장애물 회피
다른 플레이어, 각종 Object를 피해서 이동해야 하는 경우
Example)
RPG에서 몬스터의 전방 10M 앞에 플레이어가 있고 그 사이에 강물이 있거나 큰 건물이 있어서 가로 막고 있다면 근처의 다리를 건너가거나 건물을 돌아 가야 함
4명의 몬스터가 다리를 건널 경우 다리에서 가장 가까운 몬스터는 자연스럽게 건너가고 2,3번째 몬스터는 다행이 다리가 2명이 같이 설 수 있는 폭이 되어서 같이 가지만 4번째 몬스터는 앞의 둘과 충돌 하며 돌아갈 곳도 없으므로 앞지르려 하지 않고 적당히 이동 속도를 늦춘다.
10. 스크립팅 (Scripting)
최근 많이 사용되는 기법(Python, Lua). 게임의 자료나 로직을 게임의 원본 코드 외부에서 지정하는 기법.
[장점]
– 코드를 다시 컴파일 하지 않고 스크립트 안의 게임 로직을 변경하거나 테스트 할 수 있다.
– 프로그래머 자원을 낭비하지 않으면서 디자이너에게 게임 변경 능력을 부여 할 수 있다.
– 플레이어에게 스크립트 기능을 제공함으로써 플레이어로 하여금 직접 게임을 다듬고 확장하게 할 수 있다.
[단점]
– 디버깅이 힘들다
– 비 프로그래머들도 프로그래밍을 해야 한다.
– 스크립팅 언어의 구현이나 도입, 그리고 보조 디버깅 도구들의 개발에 시간을 들여야 한다.
11. 상태기계 (State Machine)
유한 상태 기계 (Finite State machine, FSM)은 널리 쓰이는 소프트웨어 설계 패턴의 하나로, 이제는 게임 AI의 초석으로 자리 잡았다.
FSM의 상태들과 전이들의 유한한 집합으로 정의하며, 주어진 시점에서 오직 하나의 상태만 활성화 된다.
Example)
PatrolRoute상태에서 시야에 있는 적을 주기적으로 점검해서 적이 보이면 AttackEnemy상태로 전이된다.
12. 스택 기반 상태기계 (Stack Based State machine)
푸시다운 자동자 (Puch Down Automata)라고도 한다 전통적인 상태기계는 이전 상태를 기억하지 못하는데 스택 기반 상태기계는 이전의 상태에서는 이전의 행동을 기억해서 저장한다.
이러한 스택 개념은 이전 상태로 돌아가거나 전체 상태기계를 기억하는 데 쓰일 수 있다.
Example)
MMORPG 원더링 하다가, 적을 만나고 전투 후 상황이 해결되면 본래의 자리로 돌아 가는 것.
RTS에서 일꾼이 자원을 채취하다가 적을 만나면 전투를 한 후 상황 종료시 다시 자원을 채취하는 것
13. 포섭 아키텍처 (Subsumption Architecture)
한 캐릭터의 행동을 병렬적으로 수행하는 FSM계층들로 깨끗하게 분리 한다. 아래쪽 계층들은 장애물 회피 같은 원초적인 행동을 처리하며, 위쪽 계층들은 목표 결정이나 목표물 탐색 같은 좀더 정교한 행동을 처리한다. 낮은 계층들의 우선순위가 더 높기 때문에 시스템은 안정성을 유지 하면서 높은 계층이 낮은 계층들에 영향을 미치기 전에 낮은 계층의 요구 사항들이 만족될 수 있도록 보상한다.
Example)
Oddword, Jedi Knight : Dark Forces2, Helo : Combat Evolved 등
포섭 아키텍처는 캐릭터의 움직임과 환경 감지가 의사결정 및 고수준 목표들과 반드시 공존하는 캐릭터 기반 게임들에 이상적이다.
14. 지형 분석 (Terrain Analysis)
자원, 병목 지점, 매복 지점 같은 전략적 장소를 식별하기 위해 게임 세계의 지형을 분석하는 활동 전반을 가리키는 광범위한 용어이다.
RTS에서 방어벽 건설 지점, FPS에서는 스나이퍼 위치, 엄호 위치, 수류탄 투척 목표등을 결정하는데 유용하다.
지형 분석을 레벨 안의 주요 지점들을 “하드코딩”으로 지정하는 것의 대안으로 볼 수도 있다.
15. 트리거 시스템 (Trigger System)
단순한 if/then 규칙들을 게임 객체나 세계 자체에 내장 시킬 수 있도록 하는 고도로 특화된 스크립팅 시스템이다.
Example)
Starcraft에서 미션 정의 기능
RPG에서 바닥의 돌을 밟을 경우 몬스터가 다량 스폰 되는 경우
16. 베이즈망 (Baysian Networks)
불확실한 상황에서 AI로 하여금 사람처럼 복잡한 추론을 수행하도록 만드는 데 쓰인다.
하나의 베이즈망에서 변수는 게임 세계 안의 특정 상태나 특징 사건에 연관 된다. 베이즈 망은 하나의 그래프로 그래프의 노드는 변수를 나타내며 호(간선)는 변수들 사이의 인과관계를 나타낸다. 이러한 그래프에 대해 확률론적 추론을 수행해서 미지 변수의 값을 추론하거나 또는 다른 형태의 추론을 이끌어낸다
Example)
AI가 자신에게 주어진 정보에 근거해서 인간 플레이어에 대해 무언가를 믿게 만드는 것이다. RTS를 예로 들자면AI는 지금까지의 관찰 결과에 근거해서 플레이어 건물의 존재 여부를 추론한다. 이전에는 치팅을 통해서 이루어 졌지만. 베이즈망 추론을 통해서 구현한다면, 예를 들어 사람이 고의로 잘못된 정보를 흘려서 AI를 속이는 새로운 게임 플레이 및 전략이 가능하다.
17. 칠판 아키텍처 (Blackboard Architecture)
하나의 복잡한 문제를 공통의 의사소통 공간인 “칠판”과 그에 참여하는 여러 전문가 객체들을 통해서 해결한다. 칠판에 쓰인 문제들에 대해 전문가 객체들이 나름의 해결책을 칠판에 적고, 시스템은 각 해결책에 적합도 점수를 매겨서 점수가 가장 높은 해를 택해 적용한다. 이를 문제가 해결될 때까지 반복한다.
Example)
공성의 문제가 주어졌을 때 개별 유닛들이 전투에서의 자신의 역할을 칠판에 제안하면 그 제안들에 점수를 매겨서 가장 적합한 것을 선택하는 식
또는 개별 에이전트들이 협동을 조정할 수 있도록 칠판을 의사소통 공간으로만 엄격히 사용 할 수 도 있다. 예를 들어 건물에 경보가 울리고 적 유닛들이 플레이어에게 몰려온다고 가정할 시 적 유닛들은 각자 자신이 들어갈 문을 칠판에 적거나 칠판에 있는 정보를 보고 다른 문을 선택하게 된다. 이 방법을 이용해서 FPS의 여러 협동 문제를 해결할 수 있다.
18. 의사결정 트리 학습 (Decision Tree)
Black & White에서 크리처가 학습을 통해 “의견”을 형성하는 부분을 예로 들 수 있음
플레이어가 크리쳐를 쓰다듬거나 때림으로써 크리처에게 긍정적인 또는 부정적인 피드백을 제공한다. 이 피드백에 의해 크리쳐가 경험으로부터 배운 것을 반영하는 의사결정 트리가 만들어진다.
또한 의사 결정 트리를 통해 자신의 배고픔을 해결하는데 사용될 수 있는지 판단한다.
19. 플레이어 모형화 (Player Modeling)
플레이어 행동의 모형을 만들고 그것에 게임을 적응시킨다. 이 경우 플레이 도중 플레이어의 행동에 관련된 통계 수치들을 계속 축적하면서 플레이어의 프로파일을 개선해 나가게 된다. 프로파일이 어느 정도 뚜렷해지면, 게임은 그 프로파일에 담긴 정보를 이용해서 플레이어의 특정한 버릇이나 특징에 AI를 적응시킬 수 있다.
Example)
FPS에서 플레이어에 대한 관찰을 통해서 플레이어가 특정 무기를 잘 다루지 못하던지. 탄창을 교체한 후 5초 후에 사격을 한다 던지 하는 정부를 축적한 후 이 약점을 이용해서 게임의 난이도를 조정한다.
20. 명성 시스템 (Reputation System)
게임 세계 안에서 플레이어의 명성이 플레이어의 행동에 기반해서 발전, 변화하는 방식을 모형화 하는 수단.
Example)
삼국지 명성 시스템, MMORPG의 카오 시스템, 엘더스크롤4 – 오블리비언
