게임 AI를 만드는 방법: 초보자를 위한 가이드

게임 속 인공지능에 관한 흥미로운 자료를 접했습니다. AI에 대한 기본적인 내용을 간단한 예시를 통해 설명하고 있으며, 내부에는 편리한 개발과 설계를 위한 유용한 도구와 방법이 많이 담겨 있습니다. 언제, 어디서, 어떻게 사용해야 하는지도 나와 있습니다.

대부분의 예제는 의사 코드로 작성되었으므로 고급 프로그래밍 지식이 필요하지 않습니다. 컷 아래에는 사진과 GIF가 포함된 35장의 텍스트가 있으므로 준비하세요.

UPD. 사과드립니다. 하지만 저는 이미 Habré에 관한 이 기사를 직접 번역했습니다. 페이션트제로. 그의 버전을 읽을 수 있습니다 여기에, 그러나 어떤 이유로 기사가 나를 지나쳤습니다 (검색을 사용했지만 문제가 발생했습니다). 그리고 저는 게임 개발 전용 블로그에 글을 쓰고 있기 때문에 구독자를 위해 제 번역 버전을 남기기로 결정했습니다. (어떤 점은 형식이 다르고 일부는 개발자의 조언에 따라 의도적으로 생략되었습니다.)

AI 란?

게임 AI는 개체가 위치한 조건에 따라 개체가 수행해야 하는 작업에 중점을 둡니다. 이를 일반적으로 "지능형 에이전트" 관리라고 하며 여기서 에이전트는 플레이어 캐릭터, 차량, 봇이거나 때로는 더 추상적인 것(전체 개체 그룹 또는 문명)입니다. 각각의 경우에는 환경을 보고 그에 따라 결정을 내리고 그에 따라 행동해야 하는 것입니다. 이것을 감지/생각/행동 주기라고 합니다.

• 감각: 에이전트는 자신의 행동에 영향을 미칠 수 있는 환경 내 사물(근처의 위협, 수집할 항목, 탐색할 흥미로운 장소)에 대한 정보를 찾거나 받습니다.
• 생각하세요: 에이전트가 어떻게 반응할지 결정합니다(아이템을 수집할 만큼 안전한지 또는 먼저 싸우거나 숨어야 하는지 고려).
• 행동(Act): 에이전트가 이전 결정을 실행하기 위한 행동을 수행합니다(적이나 물체를 향해 움직이기 시작합니다).
• ...이제 캐릭터의 행동으로 인해 상황이 바뀌었고, 새로운 데이터로 주기가 반복됩니다.

AI는 루프의 감지 부분에 집중하는 경향이 있습니다. 예를 들어, 자율주행 자동차는 도로 사진을 촬영하고 이를 레이더 및 라이더 데이터와 결합하여 해석합니다. 이는 일반적으로 들어오는 데이터를 처리하고 의미를 부여하는 기계 학습을 통해 수행되며, "20야드 앞에 다른 차가 있습니다."와 같은 의미 정보를 추출합니다. 이것이 소위 분류 문제입니다.

대부분의 데이터가 이미 게임의 필수 부분이기 때문에 게임에서는 정보를 추출하기 위해 복잡한 시스템이 필요하지 않습니다. 앞에 적이 있는지 판단하기 위해 이미지 인식 알고리즘을 실행할 필요가 없습니다. 게임은 이미 알고 있으며 의사 결정 프로세스에 직접 정보를 제공합니다. 따라서 주기의 감각 부분은 생각과 행동 부분보다 훨씬 단순한 경우가 많습니다.

게임 AI의 한계

AI에는 준수해야 할 여러 가지 제한 사항이 있습니다.

• AI는 마치 머신러닝 알고리즘처럼 미리 학습할 필요가 없습니다. 수만 명의 플레이어를 모니터링하고 그들과 대결하는 최선의 방법을 배우기 위해 개발 중에 신경망을 작성하는 것은 의미가 없습니다. 왜? 아직 게임이 출시되지 않았고 플레이어도 없기 때문입니다.
• 게임은 재미있고 도전적이어야 하므로 에이전트는 사람들을 상대로 최선의 접근 방식을 찾아서는 안 됩니다.
• 에이전트는 플레이어가 실제 사람을 상대로 플레이하는 것처럼 느끼도록 현실적으로 보여야 합니다. AlphaGo 프로그램은 인간을 능가했지만 선택한 단계는 게임에 대한 전통적인 이해와는 거리가 멀었습니다. 게임이 인간 상대를 시뮬레이션하는 경우 이러한 느낌이 존재해서는 안 됩니다. 이상적인 결정이 아닌 그럴듯한 결정을 내릴 수 있도록 알고리즘을 변경해야 합니다.
• AI는 실시간으로 작동해야 합니다. 이는 알고리즘이 결정을 내리기 위해 오랜 시간 동안 CPU 사용량을 독점할 수 없음을 의미합니다. 대부분의 게임에서는 모든 처리를 수행하고 다음 그래픽 프레임으로 이동하는 데 10~16밀리초만 필요하기 때문에 33밀리초도 너무 깁니다.
• 이상적으로는 시스템의 적어도 일부가 데이터 기반이어야 합니다. 그래야 코더가 아닌 사람도 변경하고 조정을 더 빠르게 수행할 수 있습니다.

전체 Sense/Think/Act 주기를 포괄하는 AI 접근 방식을 살펴보겠습니다.

기본 결정 내리기

가장 간단한 게임인 탁구부터 시작해 보겠습니다. 목표: 공이 공을 지나쳐 날아가는 대신 튕겨 나가도록 패들을 움직입니다. 공을 치지 않으면 패배하는 테니스와 같습니다. 여기서 AI는 플랫폼을 어느 방향으로 움직일지 결정하는 비교적 쉬운 작업을 수행합니다.

조건문

Pong의 AI에 있어서 가장 확실한 해결책은 항상 플랫폼을 공 아래에 위치시키려고 노력하는 것입니다.

의사 코드로 작성된 간단한 알고리즘은 다음과 같습니다.

게임이 실행되는 동안 모든 프레임/업데이트:
공이 패들의 왼쪽에 있는 경우:
패들을 왼쪽으로 이동
그렇지 않으면 공이 패들의 오른쪽에 있는 경우:
패들을 오른쪽으로 움직여

플랫폼이 공의 속도로 움직인다면 이는 Pong의 AI에 이상적인 알고리즘입니다. 데이터가 많지 않고 에이전트에 가능한 작업이 없다면 아무것도 복잡하게 만들 필요가 없습니다.

이 접근 방식은 너무 간단해서 전체 감지/생각/행동 주기가 거의 눈에 띄지 않습니다. 그러나 그것은 거기에 있습니다:

• Sense 부분은 두 개의 if 문으로 구성됩니다. 게임은 공이 어디에 있고 플랫폼이 어디에 있는지 알고 있으므로 AI는 해당 정보를 찾습니다.
• Think 부분은 두 개의 if 문에도 포함되어 있습니다. 이는 두 가지 솔루션을 구현하는데, 이 경우에는 상호 배타적입니다. 결과적으로 세 가지 작업 중 하나가 선택됩니다. 플랫폼을 왼쪽으로 이동하거나, 오른쪽으로 이동하거나, 이미 올바르게 배치된 경우 아무 작업도 수행하지 않습니다.
• Act 부분은 Move Paddle Left 및 Move Paddle Right 문에 있습니다. 게임 디자인에 따라 플랫폼을 즉시 또는 특정 속도로 이동할 수 있습니다.

이러한 접근 방식을 반응형이라고 합니다. 현재 세계 상태에 반응하고 조치를 취하는 간단한 규칙 세트(이 경우 코드의 if 문)가 있습니다.

의사결정나무

Pong 예제는 실제로 의사결정 트리라고 불리는 공식적인 AI 개념과 동일합니다. 알고리즘은 이를 거쳐 어떤 조치를 취할지에 대한 결정인 "리프"에 도달합니다.

우리 플랫폼의 알고리즘에 대한 의사 결정 트리의 블록 다이어그램을 만들어 보겠습니다.

트리의 각 부분을 노드라고 합니다. AI는 그래프 이론을 사용하여 이러한 구조를 설명합니다. 노드에는 두 가지 유형이 있습니다.

• 결정 노드: 일부 조건 테스트를 기반으로 두 가지 대안 중에서 선택합니다. 여기서 각 대안은 별도의 노드로 표시됩니다.
• 끝 노드: 최종 결정을 나타내는 수행할 작업입니다.

알고리즘은 첫 번째 노드(트리의 "루트")에서 시작됩니다. 어느 하위 노드로 이동할지 결정하거나 노드에 저장된 작업을 실행하고 종료합니다.

의사결정 트리가 이전 섹션의 if 문과 동일한 작업을 수행하면 어떤 이점이 있나요? 여기에는 각 결정에 하나의 조건과 두 개의 가능한 결과만 있는 일반 시스템이 있습니다. 이를 통해 개발자는 하드 코딩할 필요 없이 트리의 결정을 나타내는 데이터에서 AI를 생성할 수 있습니다. 이를 표 형태로 표현해 보겠습니다.

코드 측면에서는 문자열을 읽는 시스템을 얻을 수 있습니다. 각각에 대한 노드를 생성하고, 두 번째 열을 기반으로 결정 논리를 연결하고, 세 번째 및 네 번째 열을 기반으로 하위 노드를 연결합니다. 여전히 조건과 동작을 프로그래밍해야 하지만 이제 게임 구조는 더욱 복잡해집니다. 여기에서 추가 결정과 작업을 추가한 다음 트리 정의 텍스트 파일을 편집하여 전체 AI를 사용자 정의할 수 있습니다. 다음으로 게임을 다시 컴파일하거나 코드를 변경하지 않고도 동작을 변경할 수 있는 게임 디자이너에게 파일을 전송합니다.

의사결정 트리는 대규모 예제 세트(예: ID3 알고리즘 사용)에서 자동으로 구축될 때 매우 유용합니다. 이를 통해 얻은 데이터를 기반으로 상황을 분류하는 효과적이고 고성능 도구가 됩니다. 그러나 우리는 에이전트가 작업을 선택하는 단순한 시스템 이상의 기능을 제공합니다.

시나리오

우리는 사전에 생성된 조건과 조치를 사용한 의사결정 트리 시스템을 분석했습니다. AI를 설계하는 사람은 자신이 원하는 대로 트리를 구성할 수 있지만 여전히 모든 것을 프로그래밍한 코더에게 의존해야 합니다. 디자이너에게 자신만의 조건이나 작업을 만들 수 있는 도구를 제공할 수 있다면 어떨까요?

프로그래머가 Is Ball Left Of Paddle 및 Is Ball Right Of Paddle 조건에 대한 코드를 작성할 필요가 없도록 디자이너가 이러한 값을 확인하기 위한 조건을 작성하는 시스템을 만들 수 있습니다. 그러면 의사결정 트리 데이터는 다음과 같습니다.

이는 기본적으로 첫 번째 표와 동일하지만 솔루션 자체에는 if 문의 조건부 부분과 약간 유사한 자체 코드가 있습니다. 코드 측면에서 이는 결정 노드의 두 번째 열에서 읽히지만 실행할 특정 조건(Is Ball Left Of Paddle)을 찾는 대신 조건식을 평가하고 그에 따라 true 또는 false를 반환합니다. 이는 Lua 또는 Angelscript 스크립팅 언어를 사용하여 수행됩니다. 이를 사용하여 개발자는 게임에서 개체(공 및 패들)를 가져와 스크립트에서 사용할 수 있는 변수(ball.position)를 만들 수 있습니다. 또한 스크립팅 언어는 C++보다 간단합니다. 전체 컴파일 단계가 필요하지 않으므로 게임 로직을 빠르게 조정하는 데 이상적이며 "비코더"가 필요한 기능을 직접 만들 수 있습니다.

위의 예에서 스크립팅 언어는 조건식을 평가하는 데에만 사용되지만 작업에도 사용할 수 있습니다. 예를 들어 Move Paddle Right 데이터는 스크립트 문(ball.position.x += 10)이 될 수 있습니다. Move Paddle Right를 프로그래밍할 필요 없이 동작도 스크립트에 정의됩니다.

더 나아가 전체 의사결정 트리를 스크립팅 언어로 작성할 수도 있습니다. 이는 하드코딩된 조건문 형식의 코드이지만 외부 스크립트 파일에 위치합니다. 즉, 전체 프로그램을 다시 컴파일하지 않고도 변경할 수 있습니다. 게임플레이 중에 스크립트 파일을 편집하여 다양한 AI 반응을 빠르게 테스트할 수 있는 경우가 많습니다.

이벤트 응답

위의 예는 Pong에 적합합니다. 그들은 지속적으로 감지/생각/행동 주기를 실행하고 세계의 최신 상태에 따라 행동합니다. 그러나 더 복잡한 게임에서는 개별 이벤트에 반응해야 하며 모든 것을 한 번에 평가해서는 안 됩니다. 이 경우 Pong은 이미 나쁜 예입니다. 다른 것을 선택해 봅시다.

적들이 플레이어를 감지할 때까지 움직이지 않고 "전문화"에 따라 행동하는 슈팅 게임을 상상해 보십시오. 누군가는 "돌진"하러 달려갈 것이고, 누군가는 멀리서 공격할 것입니다. 이는 여전히 기본적인 반응 시스템("플레이어가 발견되면 무언가를 수행")이지만 논리적으로 Player Seen 이벤트와 반응(응답 선택 및 실행)으로 나눌 수 있습니다.

이는 우리를 감각/생각/행동 주기로 다시 돌아오게 합니다. AI가 플레이어를 보는지 매 프레임마다 확인하는 Sense 부분을 코딩할 수 있습니다. 그렇지 않은 경우 아무 일도 일어나지 않지만, 발견되면 Player Seen 이벤트가 생성됩니다. 코드에는 "Player Seen 이벤트가 발생할 때 수행하십시오"라는 별도의 섹션이 있으며 여기서 Think 및 Act 부분을 해결하는 데 필요한 응답이 있습니다. 따라서 Player Seen 이벤트에 대한 반응을 설정합니다. 즉, "돌진" 캐릭터에 대해서는 ChargeAndAttack, 저격수에 대해서는 HideAndSnipe를 설정합니다. 이러한 관계는 다시 컴파일할 필요 없이 빠르게 편집할 수 있도록 데이터 파일에 생성될 수 있습니다. 여기서도 스크립팅 언어를 사용할 수 있습니다.

어려운 결정을 내리다

단순한 반응 시스템은 매우 강력하지만 그것만으로는 충분하지 않은 상황이 많이 있습니다. 에이전트가 현재 무엇을 하고 있는지에 따라 다른 결정을 내려야 할 때도 있는데, 이를 조건으로 상상하기는 어렵습니다. 때로는 의사결정 트리나 스크립트에서 조건을 효과적으로 표현하기에는 조건이 너무 많습니다. 때로는 다음 단계를 결정하기 전에 상황이 어떻게 변할지 미리 평가해야 할 때도 있습니다. 이러한 문제를 해결하려면 보다 정교한 접근 방식이 필요합니다.

유한 상태 기계

유한 상태 기계 또는 FSM(유한 상태 기계)은 에이전트가 현재 여러 가능한 상태 중 하나에 있으며 한 상태에서 다른 상태로 전환할 수 있음을 나타내는 방법입니다. 그러한 상태가 특정 수 있으므로 이름이 붙었습니다. 인생의 가장 좋은 예는 신호등입니다. 장소마다 다른 순서의 조명이 있지만 원리는 동일합니다. 각 상태는 무언가(정지, 걷기 등)를 나타냅니다. 신호등은 주어진 시간에 한 가지 상태에만 있으며 간단한 규칙에 따라 한 상태에서 다른 상태로 이동합니다.

게임 속 NPC와 비슷한 이야기입니다. 예를 들어 다음과 같은 상태의 가드를 생각해 보겠습니다.

• 순찰.
• 공격.
• 도주.

상태를 변경하기 위한 조건은 다음과 같습니다.

• 경비병이 적을 보면 공격합니다.
• 경비원이 공격했지만 더 이상 적을 볼 수 없으면 순찰로 돌아갑니다.
• 경비원이 공격했지만 심각한 부상을 입으면 도망칩니다.

가디언 상태 변수와 다양한 검사(근처에 적이 있는지, NPC의 건강 수준 등)를 사용하여 if 문을 작성할 수도 있습니다. 몇 가지 상태를 더 추가해 보겠습니다.

• 유휴 - 순찰 사이.
• 수색 중 - 발견한 적이 사라졌을 때.
• 도움 찾기 - 적을 발견했지만 혼자서 싸울 수 없을 정도로 강할 때.

각각에 대한 선택은 제한되어 있습니다. 예를 들어 경비원은 체력이 낮으면 숨겨진 적을 찾지 않을 것입니다.

결국, "ifs"에 대한 거대한 목록이 있습니다. , 저것 "는 너무 번거로울 수 있으므로 상태와 상태 간 전환을 염두에 둘 수 있는 방법을 공식화해야 합니다. 이를 위해 우리는 모든 상태를 고려하고 각 상태 아래에 필요한 조건과 함께 다른 상태로의 모든 전환을 목록에 기록합니다.

이것은 FSM을 표현하는 포괄적인 방법인 상태 전이 테이블입니다. 다이어그램을 그리고 NPC 행동이 어떻게 변화하는지에 대한 전체 개요를 살펴보겠습니다.

다이어그램은 현재 상황에 따라 이 에이전트에 대한 의사 결정의 본질을 반영합니다. 또한 각 화살표는 옆에 있는 조건이 true인 경우 상태 간 전환을 보여줍니다.

업데이트할 때마다 에이전트의 현재 상태를 확인하고 전환 목록을 살펴보고 전환 조건이 충족되면 새 상태를 수락합니다. 예를 들어, 각 프레임은 10초 타이머가 만료되었는지 확인하고, 만료된 경우 가드는 유휴 상태에서 순찰 상태로 전환됩니다. 같은 방식으로 공격 중 상태는 에이전트의 체력을 확인합니다. 체력이 낮으면 도망 중 상태로 전환됩니다.

이는 상태 간의 전환을 처리하는 것입니다. 하지만 상태 자체와 관련된 동작은 어떻습니까? 특정 상태에 대한 실제 동작을 구현하는 측면에서 일반적으로 FSM에 작업을 할당하는 두 가지 유형의 "후크"가 있습니다.

• 현재 상태에 대해 주기적으로 수행하는 작업입니다.
• 한 상태에서 다른 상태로 전환할 때 취하는 조치입니다.

첫 번째 유형의 예. 순찰 상태는 각 프레임마다 순찰 경로를 따라 에이전트를 이동시킵니다. 공격 상태는 매 프레임마다 공격을 시작하거나 이것이 가능한 상태로 전환하려고 시도합니다.

두 번째 유형의 경우 "적이 보이고 적이 너무 강하면 도움 찾기 상태로 이동하는 전환을 고려하십시오. 상담원은 도움을 받을 곳을 선택하고 도움말 찾기 상태가 어디로 가야 할지 알 수 있도록 이 정보를 저장해야 합니다. 도움이 발견되면 에이전트는 공격 상태로 돌아갑니다. 이 시점에서 그는 동맹국에게 위협에 대해 알리고 싶어하므로 NotifyFriendOfThreat 작업이 발생할 수 있습니다.

다시 한번, 우리는 감각/생각/행동 주기의 렌즈를 통해 이 시스템을 볼 수 있습니다. 감지는 전환 논리에 사용되는 데이터에 구현됩니다. 생각 - 각 상태에서 전환이 가능합니다. 그리고 행위는 상태 내에서 주기적으로 수행되거나 상태 간 전환 시 수행되는 작업에 의해 수행됩니다.

때로는 지속적으로 폴링 전환 조건을 수행하는 데 비용이 많이 들 수 있습니다. 예를 들어, 각 에이전트가 매 프레임마다 복잡한 계산을 수행하여 적을 볼 수 있는지 여부를 결정하고 순찰 상태에서 공격 상태로 전환할 수 있는지 여부를 파악한다면 CPU 시간이 많이 소요됩니다.

세계 상태의 중요한 변화는 발생하는 대로 처리되는 사건으로 생각할 수 있습니다. FSM이 프레임마다 "에이전트가 플레이어를 볼 수 있습니까?"라는 전환 조건을 확인하는 대신, 확인 빈도를 낮추도록(예: 초당 5회) 별도의 시스템을 구성할 수 있습니다. 그리고 결과는 검사가 통과되면 Player Seen을 발행하는 것입니다.

이는 FSM으로 전달되며, 이제 FSM은 Player Seen 이벤트 수신 조건으로 이동하여 그에 따라 응답해야 합니다. 응답하기 전에 거의 눈에 띄지 않는 지연이 발생한다는 점을 제외하면 결과 동작은 동일합니다. 하지만 Sense 부분을 프로그램의 별도 부분으로 분리한 결과 성능이 향상되었습니다.

계층적 유한 상태 머신

그러나 대규모 FSM으로 작업하는 것이 항상 편리한 것은 아닙니다. MeleeAttacking과 RangedAttacking을 분리하기 위해 공격 상태를 확장하려면 공격 상태(현재 및 미래)로 이어지는 다른 모든 상태의 전환을 변경해야 합니다.

우리 예에서 중복된 전환이 많이 있다는 것을 눈치챘을 것입니다. 유휴 상태의 전환 대부분은 순찰 상태의 전환과 동일합니다. 반복하지 않는 것이 좋을 것입니다. 특히 유사한 상태를 더 추가하는 경우에는 더욱 그렇습니다. 공회전 및 순찰을 "비전투"라는 일반 레이블로 그룹화하는 것이 합리적입니다. 여기서는 전투 상태로의 전환에 대한 공통 세트가 하나만 있습니다. 이 레이블을 상태로 생각하면 유휴 및 순찰이 하위 상태가 됩니다. 새로운 비전투 하위 상태에 대해 별도의 전환 테이블을 사용하는 예:

주요 상태:


전투 중 상태:


그리고 다이어그램 형식으로:

동일한 시스템이지만 유휴 및 순찰을 포함하는 새로운 비전투 상태가 있습니다. 하위 상태가 있는 FSM을 포함하는 각 상태(그리고 이러한 하위 상태는 자체 FSM을 포함하며 필요한 만큼 계속 유지됨)를 사용하여 계층적 유한 상태 머신 또는 HFSM(계층적 유한 상태 머신)을 얻습니다. 비전투 상태를 그룹화하여 여러 개의 중복된 전환을 제거했습니다. 공통 전환이 있는 새로운 상태에 대해서도 동일한 작업을 수행할 수 있습니다. 예를 들어, 미래에 공격 상태를 MeleeAttacking 및 MissileAttacking 상태로 확장하면 적과의 거리와 탄약 가용성에 따라 서로 전환되는 하위 상태가 됩니다. 결과적으로 복잡한 동작과 하위 동작을 최소한의 중복 전환으로 표현할 수 있습니다.

행동 트리

HFSM을 사용하면 복잡한 행동 조합이 간단한 방법으로 생성됩니다. 그러나 전환규칙 형태의 의사결정이 현 상황과 밀접하게 연관되어 있다는 점에서 약간의 어려움이 있다. 그리고 많은 게임에서 이것이 바로 필요한 것입니다. 그리고 상태 계층 구조를 주의 깊게 사용하면 전환 반복 횟수를 줄일 수 있습니다. 그러나 때로는 어떤 주에 있든 적용되거나 거의 모든 주에 적용되는 규칙이 필요할 수 있습니다. 예를 들어 에이전트의 체력이 25%로 떨어지면 그가 전투 중인지, 유휴 상태인지, 대화 중인지에 관계없이 도망가도록 해야 합니다. 각 상태에 이 조건을 추가해야 합니다. 그리고 나중에 디자이너가 낮은 상태 임계값을 25%에서 10%로 변경하려는 경우 이 작업을 다시 수행해야 합니다.

이상적으로 이 상황에는 전환 조건을 건드리지 않고 한 곳에서만 변경을 수행하기 위해 "어떤 상태에 있을 것인지"에 대한 결정이 상태 자체 외부에 있는 시스템이 필요합니다. 행동 트리가 여기에 나타납니다.

이를 구현하는 방법에는 여러 가지가 있지만 본질은 모두 거의 동일하며 결정 트리와 유사합니다. 알고리즘은 "루트" 노드로 시작하고 트리에는 결정이나 작업을 나타내는 노드가 포함됩니다. 하지만 몇 가지 주요 차이점이 있습니다.

• 이제 노드는 성공(작업이 완료된 경우), 실패(작업을 시작할 수 없는 경우) 또는 실행 중(아직 실행 중이고 최종 결과가 없는 경우)의 세 가지 값 중 하나를 반환합니다.
• 두 가지 대안 중에서 선택할 수 있는 결정 노드가 더 이상 없습니다. 대신 하나의 하위 노드가 있는 데코레이터 노드입니다. 성공하면 유일한 하위 노드를 실행합니다.
• 작업을 수행하는 노드는 수행 중인 작업을 나타내는 Running 값을 반환합니다.

이 작은 노드 세트를 결합하여 수많은 복잡한 동작을 생성할 수 있습니다. 이전 예의 HFSM 가드를 동작 트리로 상상해 보겠습니다.

이 구조를 사용하면 유휴/순찰 상태에서 공격 중 또는 기타 상태로의 명확한 전환이 없어야 합니다. 적이 보이고 캐릭터의 체력이 낮은 경우 이전에 실행했던 노드(순찰, 유휴, 공격 등)에 관계없이 Fleeing 노드에서 실행이 중지됩니다.

비헤이비어 트리는 복잡합니다. 이를 구성하는 방법은 다양하며 데코레이터와 복합 노드의 올바른 조합을 찾는 것이 어려울 수 있습니다. 트리를 얼마나 자주 확인해야 하는지에 대한 질문도 있습니다. 트리의 모든 부분을 확인하고 싶은가요, 아니면 조건 중 하나가 변경된 경우에만 확인하고 싶은가요? 노드와 관련된 상태를 어떻게 저장합니까? 10초 동안 유휴 상태였는지 어떻게 알 수 있습니까? 또는 시퀀스를 올바르게 처리할 수 있도록 마지막으로 어떤 노드가 실행 중이었는지 어떻게 알 수 있습니까?

이것이 바로 구현이 많은 이유입니다. 예를 들어 일부 시스템에서는 데코레이터 노드를 인라인 데코레이터로 대체했습니다. 데코레이터 조건이 변경되면 트리를 재평가하고, 노드 가입을 돕고, 정기적인 업데이트를 제공합니다.

유틸리티 기반 시스템

일부 게임에는 다양한 메커니즘이 있습니다. 단순하고 일반적인 전환 규칙의 모든 이점을 받는 것이 바람직하지만 반드시 완전한 동작 트리의 형태로 제공되는 것은 아닙니다. 명확한 선택 항목이나 가능한 작업 트리를 갖는 대신 모든 작업을 검토하고 현재 가장 적절한 작업을 선택하는 것이 더 쉽습니다.

유틸리티 기반 시스템이 바로 이 작업에 도움이 될 것입니다. 이는 에이전트가 다양한 작업을 수행하고 각 작업의 상대적 유용성에 따라 수행할 작업을 선택하는 시스템입니다. 유용성은 에이전트가 이 작업을 수행하는 것이 얼마나 중요하거나 바람직한지에 대한 임의의 척도입니다.

현재 상태와 환경을 기반으로 계산된 작업의 효용성을 에이전트는 언제든지 가장 적합한 다른 상태를 확인하고 선택할 수 있습니다. 이는 현재 상태를 포함하여 각 잠재적 상태에 대한 추정에 의해 전환이 결정된다는 점을 제외하면 FSM과 유사합니다. 계속 진행하려면(또는 이미 완료한 경우 유지하려면) 가장 유용한 작업을 선택합니다. 다양성을 더 높이려면 작은 목록에서 균형 있게 무작위로 선택할 수도 있습니다.

시스템은 임의의 범위의 효용 값을 할당합니다(예: 0(완전히 바람직하지 않음)에서 100(완전히 바람직함)). 각 작업에는 이 값의 계산에 영향을 미치는 여러 매개변수가 있습니다. 보호자의 예로 돌아가서:

작업 간의 전환은 모호합니다. 모든 상태가 다른 상태를 따를 수 있습니다. 작업 우선순위는 반환된 유틸리티 값에서 찾을 수 있습니다. 적이 보이고 해당 적이 강하고 캐릭터의 체력이 낮은 경우 Fleeing 및 FindingHelp 모두 50이 아닌 높은 값을 반환합니다. 이 경우 FindingHelp는 항상 더 높습니다. 마찬가지로 비전투 활동은 XNUMX 이상을 반환하지 않으므로 항상 전투 활동보다 낮습니다. 액션을 생성하고 그 효용성을 계산할 때 이 점을 고려해야 합니다.

이 예에서 작업은 고정된 상수 값이나 두 개의 고정 값 중 하나를 반환합니다. 보다 현실적인 시스템은 연속적인 값 범위에서 추정치를 반환합니다. 예를 들어 Fleeing 액션은 에이전트의 체력이 낮을 경우 더 높은 유틸리티 값을 반환하고, Attacking 액션은 적이 너무 강할 경우 더 낮은 유틸리티 값을 반환합니다. 이 때문에 에이전트가 적을 물리칠 만큼 체력이 충분하지 않다고 느끼는 상황에서는 도망치는 행동이 공격하는 것보다 우선합니다. 이를 통해 다양한 기준에 따라 작업의 우선 순위를 지정할 수 있으므로 이 접근 방식은 동작 트리나 FSM보다 더 유연하고 가변적입니다.

각 동작에는 프로그램 계산을 위한 많은 조건이 있습니다. 이는 스크립팅 언어로 작성되거나 일련의 수학 공식으로 작성될 수 있습니다. 캐릭터의 일상을 시뮬레이션하는 The Sims에는 추가 계산 계층이 추가됩니다. 에이전트는 유틸리티 등급에 영향을 미치는 일련의 "동기 부여"를 받습니다. 캐릭터가 배가 고프면 시간이 지남에 따라 더욱 배가 고파지며, 캐릭터가 이를 수행할 때까지 EatFood 작업의 유틸리티 값이 증가하여 배고픔 수준이 감소하고 EatFood 값이 XNUMX으로 돌아갑니다.

등급 시스템을 기반으로 행동을 선택한다는 아이디어는 매우 간단하므로 유틸리티 기반 시스템은 AI 의사 결정 프로세스를 완전히 대체하기보다는 AI 의사 결정 프로세스의 일부로 사용할 수 있습니다. 의사결정 트리는 두 하위 노드의 효용 등급을 요청하고 더 높은 노드를 선택할 수 있습니다. 마찬가지로, 행동 트리에는 실행할 하위 항목을 결정하기 위해 작업의 유용성을 평가하는 복합 유틸리티 노드가 있을 수 있습니다.

이동 및 탐색

이전 예에서는 왼쪽이나 오른쪽으로 움직이는 플랫폼과 순찰하거나 공격하는 경비원이 있었습니다. 하지만 일정 기간 동안 에이전트 이동을 정확히 어떻게 처리합니까? 속도를 어떻게 설정하고, 장애물을 어떻게 피하며, 직선으로 이동하는 것보다 목적지에 도달하는 것이 더 어려울 때 경로를 어떻게 계획합니까? 이것을 살펴보자.

거버넌스

초기 단계에서는 각 에이전트가 이동 속도와 방향을 포함하는 속도 값을 가지고 있다고 가정합니다. 초당 미터, 시간당 킬로미터, 초당 픽셀 등으로 측정할 수 있습니다. Sense/Think/Act 루프를 떠올려 보면 Think 부분이 속도를 선택하고 Act 부분이 해당 속도를 에이전트에 적용한다고 상상할 수 있습니다. 일반적으로 게임에는 이 작업을 수행하고 각 개체의 속도 값을 학습하고 조정하는 물리 시스템이 있습니다. 따라서 에이전트가 가져야 할 속도를 결정하는 하나의 작업으로 AI를 떠날 수 있습니다. 에이전트가 어디에 있어야 하는지 알고 있다면 설정된 속도로 올바른 방향으로 움직여야 합니다. 매우 사소한 방정식:

Desired_travel = 목적지_위치 – 에이전트_위치

2D 세계를 상상해 보세요. 에이전트는 지점 (-2,-2)에 있고 목적지는 북동쪽 지점 (30, 20)에 있으며 에이전트가 해당 지점에 도달하는 데 필요한 경로는 (32, 22)입니다. 이러한 위치가 미터 단위로 측정된다고 가정해 보겠습니다. 에이전트의 속도를 초당 5미터로 설정하면 변위 벡터의 크기를 조정하고 대략 (4.12, 2.83)의 속도를 얻습니다. 이러한 매개변수를 사용하면 에이전트는 거의 8초 안에 목적지에 도착합니다.

언제든지 값을 다시 계산할 수 있습니다. 에이전트가 목표까지 중간에 있었다면 이동 길이는 절반이 되지만 에이전트의 최대 속도는 5m/s(위에서 결정함)이므로 속도는 동일합니다. 이는 움직이는 대상에도 적용되므로 에이전트가 이동하면서 작은 변경을 할 수 있습니다.

그러나 우리는 더 많은 변형을 원합니다. 예를 들어 서 있는 상태에서 달리는 캐릭터를 시뮬레이션하기 위해 속도를 천천히 높이는 등의 작업이 필요합니다. 중지하기 전에 마지막에도 동일한 작업을 수행할 수 있습니다. 이러한 기능은 조향 동작으로 알려져 있으며 각 동작에는 탐색, 도주, 도착 등의 특정 이름이 있습니다. 에이전트의 위치와 현재 속도를 목적지와 비교하여 에이전트의 속도에 가속력을 적용할 수 있다는 아이디어입니다. 목표를 향해 나아가기 위해 다양한 방법을 사용하기 위해서입니다.

각 동작에는 약간 다른 목적이 있습니다. 탐색 및 도착은 에이전트를 목적지로 이동시키는 방법입니다. 장애물 회피 및 분리는 목표를 향해 가는 도중에 장애물을 피할 수 있도록 에이전트의 움직임을 조정합니다. 정렬과 응집력은 에이전트를 계속 함께 움직이게 합니다. 다양한 조향 동작을 합산하여 모든 요소를 ​​고려한 단일 경로 벡터를 생성할 수 있습니다. 벽이나 다른 에이전트로부터 멀리 떨어져 있기 위해 도착, 분리, 장애물 회피 동작을 사용하는 에이전트입니다. 이 접근 방식은 불필요한 세부 사항 없이 개방된 위치에서 잘 작동합니다.

더 어려운 조건에서는 다양한 동작을 추가하는 것이 더 나쁘게 작동합니다. 예를 들어 도착과 장애물 회피 간의 충돌로 인해 에이전트가 벽에 갇힐 수 있습니다. 따라서 단순히 모든 값을 추가하는 것보다 더 복잡한 옵션을 고려해야 합니다. 방법은 다음과 같습니다. 각 행동의 결과를 합산하는 대신 다양한 방향으로의 움직임을 고려하고 최상의 옵션을 선택할 수 있습니다.

그러나 막다른 골목과 갈 길에 대한 선택이 있는 복잡한 환경에서는 더욱 발전된 것이 필요합니다.

길 찾기

조향 동작은 A에서 B로 이동하는 것이 장애물 주위를 약간만 우회하는 직선 경로인 개방된 공간(축구장 또는 경기장)에서 간단한 이동에 적합합니다. 복잡한 경로의 경우 세계를 탐색하고 이를 통과하는 경로를 결정하는 방법인 길 찾기가 필요합니다.

가장 간단한 방법은 에이전트 옆에 있는 각 사각형에 그리드를 적용하고 어느 사각형이 움직일 수 있는지 평가하는 것입니다. 그 중 하나가 목적지라면 시작 지점에 도달할 때까지 각 광장에서 이전 광장까지 경로를 따라가세요. 이것이 경로입니다. 그렇지 않으면 목적지를 찾거나 사각형이 부족할 때까지(가능한 경로가 없음을 의미) 근처의 다른 사각형에서 이 과정을 반복하세요. 이것이 공식적으로 Breadth-First Search 또는 BFS(Breadth-First Search Algorithm)로 알려진 것입니다. 모든 단계에서 그는 모든 방향(따라서 너비, "너비")을 봅니다. 검색 공간은 원하는 위치에 도달할 때까지 이동하는 파면과 같습니다. 검색 공간은 끝점이 포함될 때까지 각 단계에서 확장되며, 그 이후에는 처음으로 다시 추적될 수 있습니다.

결과적으로 원하는 경로가 컴파일된 사각형 목록을 받게 됩니다. 이것이 경로(따라서 경로 찾기)입니다. 에이전트가 목적지를 따라가는 동안 방문할 장소의 목록입니다.

우리가 전 세계 모든 사각형의 위치를 ​​알고 있다는 점을 고려하면 스티어링 동작을 사용하여 경로를 따라 이동할 수 있습니다(노드 1에서 노드 2로, 그런 다음 노드 2에서 노드 3으로 등). 가장 간단한 옵션은 다음 사각형의 중앙을 향해 가는 것이지만, 더 좋은 옵션은 현재 사각형과 다음 사각형 사이의 가장자리 중간에 멈추는 것입니다. 이로 인해 에이전트는 급회전 시 코너를 통과할 수 있습니다.

BFS 알고리즘에는 단점도 있습니다. 즉, "올바른" 방향만큼 "잘못된" 방향에서도 많은 사각형을 탐색합니다. 여기서 A*(A star)라고 하는 더 복잡한 알고리즘이 작동합니다. 동일한 방식으로 작동하지만 이웃 사각형(이웃의 이웃, 이웃의 이웃의 이웃 등)을 맹목적으로 검사하는 대신 노드를 목록으로 수집하고 검사된 다음 노드가 항상 노드가 되도록 정렬합니다. 최단 경로로 연결되는 경로입니다. 노드는 원하는 광장까지의 가상 경로의 "비용"(여행 비용 포함)과 해당 광장이 목적지에서 얼마나 멀리 떨어져 있는지에 대한 추정치(검색 편향)라는 두 가지를 고려하는 경험적 방법을 기반으로 정렬됩니다. 바른 길).

이 예는 에이전트가 한 번에 하나의 사각형을 탐색하고 매번 가장 유망한 인접한 사각형을 선택한다는 것을 보여줍니다. 결과 경로는 BFS와 동일하지만 그 과정에서 고려되는 사각형이 적어서 게임 성능에 큰 영향을 미칩니다.

그리드 없는 움직임

그러나 대부분의 게임은 그리드에 배치되어 있지 않으며 현실성을 희생하지 않고서는 그렇게 하는 것이 불가능한 경우가 많습니다. 타협이 필요합니다. 정사각형의 크기는 얼마여야 합니까? 너무 크면 작은 복도나 회전을 올바르게 표현할 수 없고, 너무 작으면 검색할 사각형이 너무 많아 결국 시간이 많이 걸립니다.

가장 먼저 이해해야 할 것은 메시가 연결된 노드의 그래프를 제공한다는 것입니다. A* 및 BFS 알고리즘은 실제로 그래프에서 작동하며 메시에는 전혀 신경 쓰지 않습니다. 우리는 게임 세계의 어느 곳에나 노드를 배치할 수 있습니다. 연결된 두 노드 사이는 물론 시작점과 끝점, 그리고 적어도 하나의 노드 사이에 연결이 있는 한 알고리즘은 이전과 마찬가지로 잘 작동합니다. 각 노드는 수많은 가상 경로의 일부가 될 수 있는 세계의 중요한 위치를 나타내기 때문에 이를 흔히 웨이포인트 시스템이라고 합니다.

예 1: 각 사각형에 매듭이 있습니다. 검색은 에이전트가 위치한 노드에서 시작하여 원하는 사각형의 노드에서 끝납니다.

예 2: 더 작은 노드 세트(경유지). 검색은 에이전트의 광장에서 시작하여 필요한 수의 노드를 거쳐 목적지까지 계속됩니다.

이는 완전히 유연하고 강력한 시스템입니다. 그러나 웨이포인트를 배치할 위치와 방법을 결정할 때는 약간의 주의가 필요합니다. 그렇지 않으면 에이전트가 가장 가까운 지점을 볼 수 없고 경로를 시작할 수 없게 됩니다. 세계의 기하학적 구조를 기반으로 웨이포인트를 자동으로 배치할 수 있다면 더 쉬울 것입니다.

여기에 탐색 메시 또는 navmesh(탐색 메시)가 표시됩니다. 이는 일반적으로 에이전트가 걸을 수 있는 모든 곳의 세계 형상 위에 겹쳐지는 삼각형의 2D 메시입니다. 메쉬의 각 삼각형은 그래프의 노드가 되고, 그래프의 인접한 노드가 되는 인접한 삼각형은 최대 XNUMX개까지 있습니다.

이 그림은 Unity 엔진의 예입니다. 이는 세계의 형상을 분석하고 내비메시를 생성했습니다(스크린샷에서 연한 파란색). 내비메시의 각 다각형은 에이전트가 한 다각형에서 다른 다각형으로 서거나 이동할 수 있는 영역입니다. 이 예에서 다각형은 해당 다각형이 위치한 바닥보다 작습니다. 이는 공칭 위치 이상으로 확장되는 에이전트의 크기를 고려하기 위해 수행됩니다.

A* 알고리즘을 사용하여 이 메시를 통해 경로를 검색할 수 있습니다. 이를 통해 우리는 모든 기하학을 고려하고 불필요한 노드와 웨이포인트 생성이 필요하지 않은 세계에서 거의 완벽한 경로를 제공할 것입니다.

길 찾기는 기사의 한 섹션만으로는 충분하지 않을 만큼 너무 광범위한 주제입니다. 더 자세히 공부하고 싶다면 도움이 될 것입니다 아미트 파텔 홈페이지.

계획

우리는 때때로 방향을 선택하고 이동하는 것만으로는 충분하지 않다는 것을 길 찾기를 통해 배웠습니다. 원하는 목적지에 도달하려면 경로를 선택하고 몇 차례 회전해야 합니다. 우리는 이 아이디어를 일반화할 수 있습니다. 목표 달성은 단지 다음 단계가 아니라 때로는 첫 번째 단계가 무엇인지 알아내기 위해 여러 단계를 미리 살펴봐야 하는 전체 시퀀스입니다. 이것을 계획이라고 합니다. 길찾기는 계획의 여러 확장 중 하나로 생각할 수 있습니다. Sense/Think/Act 주기의 관점에서 보면 Think 부분이 미래를 위해 여러 Act 부분을 계획하는 곳입니다.

보드게임 매직: 더 개더링(Magic: The Gathering)의 예를 살펴보겠습니다. 먼저 다음 카드 세트를 손에 쥐고 진행합니다.

• 늪 - 1개의 흑색 마나(대지 카드)를 제공합니다.
• 숲 - 녹색 마나 1개(대지 카드)를 제공합니다.
• 도망자 마법사 - 소환하려면 청색 마나가 1개 필요합니다.
• Elvish Mystic - 소환하려면 녹색 마나가 1개 필요합니다.

더 쉽게 하기 위해 나머지 세 장의 카드는 무시합니다. 규칙에 따르면 플레이어는 턴당 대지 카드 1장을 사용할 수 있으며, 이 카드를 "탭"하여 마나를 추출한 다음 마나 양에 따라 주문(생물 소환 포함)을 시전할 수 있습니다. 이 상황에서 인간 플레이어는 숲을 플레이하고 녹색 마나 1개를 탭한 다음 Elvish Mystic을 소환하는 방법을 알고 있습니다. 그런데 게임 AI가 이를 어떻게 알아낼 수 있을까요?

쉬운 계획

간단한 접근 방식은 적합한 작업이 더 이상 남지 않을 때까지 각 작업을 차례로 시도하는 것입니다. AI는 카드를 보고 Swamp가 어떤 플레이를 할 수 있는지 파악합니다. 그리고 그는 그것을 연주합니다. 이번 턴에 다른 행동이 남아 있나요? Elvish Mystic이나 Fugitive Wizard는 각각 녹색 마나와 파란색 마나가 필요한 반면 Swamp는 흑색 마나만 제공하므로 소환할 수 없습니다. 그리고 그는 이미 Swamp를 플레이했기 때문에 더 이상 Forest를 플레이할 수 없습니다. 따라서 게임 AI는 규칙을 따랐지만 제대로 수행하지 못했습니다. 개선될 수 있습니다.

계획을 통해 게임을 원하는 상태로 만드는 작업 목록을 찾을 수 있습니다. 경로의 모든 사각형에 이웃이 있는 것처럼(경로 찾기에서) 계획의 모든 작업에도 이웃 또는 후속 항목이 있습니다. 원하는 상태에 도달할 때까지 이러한 작업과 후속 작업을 찾을 수 있습니다.

이 예에서 원하는 결과는 "가능한 경우 생물을 소환"하는 것입니다. 턴이 시작될 때 게임 규칙에 따라 허용되는 두 가지 가능한 행동만 볼 수 있습니다.

1. Swamp 플레이(결과: 게임 내 Swamp)
2. 숲 플레이(결과: 게임 내 숲)

취해진 각 조치는 게임 규칙에 따라 추가 조치로 이어질 수 있으며 다시 다른 조치를 종료할 수 있습니다. 우리가 Swamp를 플레이했다고 상상해 보세요. 이렇게 하면 다음 단계에서 Swamp가 제거되고(우리는 이미 플레이했습니다) Forest도 제거됩니다(규칙에 따라 턴당 하나의 대지 카드를 사용할 수 있기 때문입니다). 이후 AI는 다른 옵션이 없기 때문에 다음 단계로 흑색 마나 1개를 얻는 것을 추가합니다. 그가 계속해서 Tap the Swamp를 선택하면 그는 흑색 마나 1유닛을 받게 되며 그것으로 아무 것도 할 수 없게 됩니다.

1. Swamp 플레이(결과: 게임 내 Swamp)
1.1 "탭" 늪(결과: 늪 "탭", +1 흑색 마나 단위)
사용할 수 있는 작업이 없습니다. - 종료
2. 숲 플레이(결과: 게임 내 숲)

작업 목록이 짧아서 막다른 골목에 도달했습니다. 다음 단계를 위해 프로세스를 반복합니다. 우리는 Forest를 플레이하고 "1개의 녹색 마나 얻기" 액션을 시작합니다. 그러면 세 번째 액션인 Elvish Mystic을 소환하게 됩니다.

1. Swamp 플레이(결과: 게임 내 Swamp)
1.1 "탭" 늪(결과: 늪 "탭", +1 흑색 마나 단위)
사용할 수 있는 작업이 없습니다. - 종료
2. 숲 플레이(결과: 게임 내 숲)
2.1 "탭" 숲(결과: 숲이 "탭"됨, 녹색 마나 +1 단위)
2.1.1 Elvish Mystic 소환(결과: Elvish Mystic in play, -1 녹색 마나)
사용할 수 있는 작업이 없습니다. - 종료

마지막으로 우리는 가능한 모든 행동을 탐색하고 생물을 소환하는 계획을 찾았습니다.

이것은 매우 간단한 예입니다. 어떤 기준에 맞는 계획을 세우기보다는 가능한 최선의 계획을 선택하는 것이 좋습니다. 일반적으로 구현의 결과나 전반적인 이점을 기반으로 잠재적인 계획을 평가하는 것이 가능합니다. 대지 카드를 사용하면 1점, 생물을 소환하면 3점을 얻을 수 있습니다. Swamp를 플레이하는 것은 1점 계획이 될 것입니다. 그리고 숲 → 숲 탭 → Elvish Mystic 소환을 플레이하면 즉시 4점을 얻습니다.

이것이 매직: 더 개더링에서 계획이 작동하는 방식이지만, 다른 상황에도 동일한 논리가 적용됩니다. 예를 들어, 체스에서 비숍이 움직일 수 있는 공간을 만들기 위해 폰을 움직이는 것입니다. 아니면 벽 뒤에 숨어 이렇게 XCOM에서 안전하게 촬영할 수도 있습니다. 일반적으로 아이디어를 얻습니다.

향상된 계획

때로는 가능한 모든 옵션을 고려하기에는 잠재적인 조치가 너무 많습니다. Magic: The Gathering의 예로 돌아가서 게임과 손에 여러 대지 카드와 생물 카드가 있다고 가정해 보겠습니다. 가능한 이동 조합 수는 수십 개가 될 수 있습니다. 문제에 대한 몇 가지 해결책이 있습니다.

첫 번째 방법은 역방향 연결입니다. 모든 조합을 시도하기보다는 최종 결과부터 시작하여 직접적인 경로를 찾는 것이 좋습니다. 나무의 뿌리에서 특정 잎사귀로 가는 대신, 우리는 반대 방향, 즉 잎에서 뿌리로 움직입니다. 이 방법이 더 쉽고 빠릅니다.

적의 체력이 1이라면 "1개 이상의 피해를 줍니다" 계획을 찾을 수 있습니다. 이를 달성하려면 다음과 같은 여러 조건이 충족되어야 합니다.

1. 주문으로 인해 피해가 발생할 수 있습니다. 주문이 손에 있어야 합니다.
2. 주문을 발동하려면 마나가 필요합니다.
3. 마나를 얻으려면 대지 카드를 사용해야 합니다.
4. 대지 카드를 사용하려면 해당 카드를 손에 들고 있어야 합니다.

또 다른 방법은 최선 우선 검색입니다. 모든 경로를 시도하는 대신 가장 적합한 경로를 선택합니다. 대부분의 경우 이 방법은 불필요한 검색 비용 없이 최적의 계획을 제공합니다. A*는 가장 유망한 경로를 처음부터 검사하여 다른 옵션을 확인할 필요 없이 이미 최적의 경로를 찾을 수 있는 최선의 우선 검색 형식입니다.

흥미롭고 점점 더 인기를 얻고 있는 최고 우선 검색 옵션은 몬테카를로 트리 검색(Monte Carlo Tree Search)입니다. 각 후속 조치를 선택할 때 어떤 계획이 다른 계획보다 더 나은지 추측하는 대신 알고리즘은 끝에 도달할 때까지(계획이 승리 또는 패배하는 경우) 각 단계에서 무작위 후속 조치를 선택합니다. 최종 결과는 이전 옵션의 가중치를 늘리거나 줄이는 데 사용됩니다. 이 프로세스를 연속해서 여러 번 반복함으로써 알고리즘은 상황이 바뀌더라도(적이 플레이어를 방해하는 조치를 취하는 경우) 최상의 다음 움직임이 무엇인지에 대한 좋은 추정치를 제공합니다.

목표 지향 행동 계획 또는 GOAP(목표 지향 행동 계획) 없이는 게임 계획에 관한 이야기가 완성되지 않습니다. 이는 널리 사용되고 논의되는 방법이지만, 몇 가지 구별되는 세부 사항을 제외하면 본질적으로 앞서 이야기한 역방향 연결 방법입니다. 목표가 "플레이어를 파괴"하는 것이었고 플레이어가 엄폐물 뒤에 있는 경우 계획은 수류탄으로 파괴 → 획득 → 던지는 것입니다.

일반적으로 여러 가지 목표가 있으며 각각 고유한 우선순위가 있습니다. 우선 순위가 가장 높은 목표를 완료할 수 없는 경우(플레이어가 보이지 않기 때문에 어떤 작업 조합으로도 "플레이어 죽이기" 계획이 생성되지 않음) AI는 우선 순위가 낮은 목표로 돌아갑니다.

훈련과 적응

게임 AI는 실시간으로 에이전트를 관리하는 데 적합하지 않기 때문에 일반적으로 머신러닝을 사용하지 않는다고 이미 말씀드렸습니다. 하지만 이것이 이 지역에서 무언가를 빌릴 수 없다는 의미는 아닙니다. 우리는 슈팅 게임에서 뭔가를 배울 수 있는 상대를 원합니다. 예를 들어, 지도에서 가장 좋은 위치를 알아보세요. 또는 플레이어가 자주 사용하는 콤보 동작을 차단하여 다른 동작을 사용하도록 동기를 부여하는 격투 게임의 상대입니다. 따라서 머신러닝은 이러한 상황에서 매우 유용할 수 있습니다.

통계와 확률

복잡한 예를 살펴보기 전에 몇 가지 간단한 측정을 수행하고 이를 사용하여 결정을 내려 얼마나 멀리 갈 수 있는지 살펴보겠습니다. 예를 들어, 실시간 전략 - 플레이어가 게임 시작 후 몇 분 안에 공격을 시작할 수 있는지 여부와 이에 대비할 수비를 어떻게 결정합니까? 우리는 플레이어의 과거 경험을 연구하여 미래의 반응이 무엇인지 이해할 수 있습니다. 우선, 우리는 그러한 원시 데이터를 가지고 있지 않지만 이를 수집할 수 있습니다. AI가 인간과 대결할 때마다 첫 번째 공격 시간을 기록할 수 있습니다. 몇 번의 세션 후에 플레이어가 앞으로 공격하는 데 걸리는 평균 시간을 얻을 수 있습니다.

평균 값에도 문제가 있습니다. 플레이어가 20번 돌진하고 20번 천천히 플레이했다면 필요한 값은 중간 어딘가에 있을 것이며 이는 우리에게 유용한 것을 전혀 제공하지 않습니다. 한 가지 해결책은 입력 데이터를 제한하는 것입니다. 마지막 20개를 고려할 수 있습니다.

플레이어의 과거 선호도가 미래에도 동일할 것이라고 가정하여 특정 행동의 가능성을 추정할 때 유사한 접근 방식이 사용됩니다. 플레이어가 파이어볼로 다섯 번, 번개로 두 번, 근접 공격으로 한 번 공격한다면, 그 플레이어는 파이어볼을 선호하는 것이 분명합니다. 다양한 무기를 사용할 확률을 추정하여 살펴보겠습니다: 불덩어리=62,5%, 번개=25%, 근접=12,5%. 우리 게임 AI는 화재로부터 자신을 보호할 준비가 되어 있어야 합니다.

또 다른 흥미로운 방법은 Naive Bayes Classifier를 사용하여 대량의 입력 데이터를 연구하고 상황을 분류하여 AI가 원하는 방식으로 반응하도록 하는 것입니다. 베이지안 분류기는 이메일 스팸 필터에 사용되는 것으로 가장 잘 알려져 있습니다. 그곳에서 그들은 단어를 조사하고 해당 단어가 이전에 나타난 위치(스팸인지 아닌지)와 비교하고 수신 이메일에 대한 결론을 도출합니다. 더 적은 수의 입력으로도 동일한 작업을 수행할 수 있습니다. AI가 보는 모든 유용한 정보(예: 적 유닛이 어떤 유닛이 생성되는지, 어떤 주문을 사용하는지, 어떤 기술을 연구하는지 등)와 최종 결과(전쟁 또는 평화, 돌진 또는 방어 등)를 기반으로 - 원하는 AI 동작을 선택하겠습니다.

이 모든 훈련 방법은 충분하지만 테스트 데이터를 기반으로 사용하는 것이 좋습니다. AI는 플레이 테스터가 사용한 다양한 전략에 적응하는 방법을 학습합니다. 출시 후 플레이어에 적응하는 AI는 너무 예측 가능하거나 패배하기가 너무 어려울 수 있습니다.

가치 기반 적응

게임 세계의 콘텐츠와 규칙을 고려하면 단순히 입력 데이터를 사용하는 것이 아니라 의사 결정에 영향을 미치는 값 집합을 변경할 수 있습니다. 우리는 이렇게 합니다:

• AI가 게임 중 세계 상태와 주요 이벤트에 대한 데이터를 수집하도록 합니다(위와 같음).
• 이 데이터를 기반으로 몇 가지 중요한 값을 변경해 보겠습니다.
• 우리는 이러한 가치를 처리하거나 평가하여 결정을 내립니다.

예를 들어 에이전트에는 XNUMX인칭 슈팅 게임 맵에서 선택할 수 있는 여러 방이 있습니다. 각 객실에는 방문하는 것이 얼마나 바람직한지를 결정하는 고유한 가치가 있습니다. AI는 값에 따라 어느 방으로 갈지 무작위로 선택합니다. 그런 다음 에이전트는 그가 어느 방에서 죽었는지 기억하고 그 가치(그가 그곳으로 돌아올 확률)를 줄입니다. 반대 상황도 마찬가지입니다. 에이전트가 많은 상대를 파괴하면 방의 가치가 높아집니다.

마르코프 모델

수집된 데이터를 사용하여 예측을 한다면 어떨까요? 특정 기간 동안 플레이어가 있는 모든 방을 기억하면 플레이어가 어느 방으로 갈지 예측할 수 있습니다. 방 전체에서 플레이어의 움직임(값)을 추적하고 기록함으로써 이를 예측할 수 있습니다.

빨간색, 녹색, 파란색의 세 개의 방을 선택하겠습니다. 또한 게임 세션을 보면서 기록한 관찰 내용은 다음과 같습니다.

각 방의 관찰 횟수는 거의 동일합니다. 우리는 매복을 위한 좋은 장소를 어디에서 만들어야 할지 아직 모릅니다. 맵 전체에 고르게 나타나는 플레이어의 리스폰으로 인해 통계 수집도 복잡해집니다. 하지만 지도에 표시된 후 그들이 들어가는 다음 방에 대한 데이터는 이미 유용합니다.

녹색 방이 플레이어에게 적합한 것을 볼 수 있습니다. 대부분의 사람들은 빨간색 방에서 빨간색 방으로 이동하고 그 중 50%는 더 멀리 남아 있습니다. 반면에 블루룸은 인기가 없어서 가는 사람이 거의 없고, 간다고 해도 오래 머물지 않는다.

하지만 데이터는 더 중요한 사실을 알려줍니다. 플레이어가 파란색 방에 있을 때 우리가 볼 수 있는 다음 방은 녹색이 아닌 빨간색일 것입니다. 녹색 방이 빨간색 방보다 인기가 높음에도 불구하고 플레이어가 파란색 방에 있으면 상황이 달라집니다. 다음 상태(즉, 플레이어가 갈 방)는 이전 상태(즉, 플레이어가 현재 있는 방)에 따라 달라집니다. 종속성을 탐색하기 때문에 단순히 관찰값을 독립적으로 계산하는 것보다 더 정확한 예측을 할 수 있습니다.

과거 상태의 데이터를 기반으로 미래 상태를 예측하는 것을 마르코프 모델(Markov model)이라고 하며, 이러한 예시(방 포함)를 마르코프 체인(Markov chain)이라고 합니다. 패턴은 연속적인 상태 간의 변경 확률을 나타내므로 각 전환 주변의 확률과 함께 FSM으로 시각적으로 표시됩니다. 이전에는 FSM을 사용하여 에이전트의 동작 상태를 나타내었지만 이 개념은 에이전트와 연결되어 있는지 여부에 관계없이 모든 상태로 확장됩니다. 이 경우 상태는 에이전트가 차지하는 공간을 나타냅니다.

이는 상태 변경의 상대적 가능성을 나타내는 간단한 방법으로, AI가 다음 상태를 예측할 수 있는 능력을 제공합니다. 앞으로 몇 단계를 예상할 수 있습니다.

플레이어가 대기실에 있으면 다음에 관찰될 때 그 플레이어가 대기실에 남아 있을 확률은 50%입니다. 하지만 그 이후에도 그가 여전히 그 자리에 있을 가능성은 얼마나 될까요? 두 번의 관찰 후에도 플레이어가 대기실에 남아 있을 가능성이 있을 뿐만 아니라, 떠났다가 돌아올 가능성도 있습니다. 다음은 새 데이터를 고려한 새 테이블입니다.

두 번의 관찰 후 녹색 방에서 플레이어를 볼 확률은 51% - 빨간색 방에서 올 확률은 21%, 플레이어가 두 관찰 사이에 있는 파란색 방을 방문할 확률은 5%, 플레이어가 대기실을 떠나지 않을 확률이 25%입니다.

테이블은 단순히 시각적 도구입니다. 절차에서는 각 단계의 확률을 곱하기만 하면 됩니다. 이는 한 가지 주의 사항으로 먼 미래를 내다볼 수 있다는 것을 의미합니다. 방에 들어갈 가능성은 전적으로 현재 방에 달려 있다고 가정합니다. 이것을 마르코프 속성(Markov Property)이라고 합니다. 미래 상태는 현재에만 의존합니다. 그러나 이것이 XNUMX% 정확한 것은 아닙니다. 플레이어는 체력 수준이나 탄약 양 등 다른 요인에 따라 결정을 변경할 수 있습니다. 이러한 값을 기록하지 않기 때문에 예측의 정확성이 떨어집니다.

N-그램

격투 게임의 예와 플레이어의 콤보 동작을 예측하는 경우는 어떻습니까? 똑같다! 그러나 하나의 상태나 이벤트 대신 콤보 공격을 구성하는 전체 시퀀스를 살펴보겠습니다.

이를 수행하는 한 가지 방법은 각 입력(예: Kick, Punch 또는 Block)을 버퍼에 저장하고 전체 버퍼를 이벤트로 쓰는 것입니다. 따라서 플레이어는 SuperDeathFist 공격을 사용하기 위해 Kick, Kick, Punch를 반복적으로 누르면 AI 시스템은 모든 입력을 버퍼에 저장하고 각 단계에서 사용된 마지막 XNUMX개를 기억합니다.

(굵은 선은 플레이어가 SuperDeathFist 공격을 시작할 때입니다.)

AI는 플레이어가 Kick을 선택한 후 또 다른 Kick을 선택하면 모든 옵션을 확인한 후 다음 입력이 항상 Punch임을 알 수 있습니다. 이를 통해 에이전트는 SuperDeathFist의 콤보 이동을 예측하고 가능하면 이를 차단할 수 있습니다.

이러한 일련의 이벤트를 N-그램이라고 하며, 여기서 N은 저장된 요소의 수입니다. 이전 예에서는 3그램(트라이그램)이었습니다. 즉, 처음 두 항목이 세 번째 항목을 예측하는 데 사용됩니다. 따라서 5그램에서는 처음 XNUMX개의 항목이 XNUMX번째 항목을 예측하는 식입니다.

디자이너는 N-그램의 크기를 신중하게 선택해야 합니다. N이 작을수록 더 적은 메모리가 필요하지만 더 적은 기록을 저장합니다. 예를 들어 2그램(바이그램)은 Kick, Kick 또는 Kick, Punch를 기록하지만 Kick, Kick, Punch를 저장할 수 없으므로 AI는 SuperDeathFist 콤보에 응답하지 않습니다.

반면, 숫자가 클수록 더 많은 메모리가 필요하고 가능한 옵션이 더 많아 AI를 훈련시키기가 더 어려워집니다. Kick, Punch 또는 Block의 세 가지 가능한 입력이 있고 10그램을 사용했다면 약 60만 가지의 다른 옵션이 있을 것입니다.

바이그램 모델은 간단한 마르코프 체인입니다. 각 과거 상태/현재 상태 쌍은 바이그램이며 첫 번째 상태를 기반으로 두 번째 상태를 예측할 수 있습니다. 3-그램 이상의 N-그램은 모든 요소(N-그램의 마지막 요소 제외)가 함께 첫 번째 상태를 형성하고 마지막 요소가 두 번째 상태를 형성하는 마르코프 체인으로 간주될 수도 있습니다. 격투 게임 예에서는 Kick and Kick 상태에서 Kick and Punch 상태로 전환될 가능성을 보여줍니다. 여러 입력 기록 항목을 단일 단위로 처리함으로써 본질적으로 입력 시퀀스를 전체 상태의 일부로 변환합니다. 이는 Markov 체인을 사용하여 다음 입력을 예측하고 다음에 어떤 콤보 이동이 있을지 추측할 수 있는 Markov 속성을 제공합니다.

결론

우리는 인공지능 개발에 있어 가장 일반적인 도구와 접근 방식에 대해 이야기했습니다. 또한 사용해야 하는 상황과 특히 유용한 상황도 살펴보았습니다.

이는 게임 AI의 기본을 이해하기에 충분할 것입니다. 그러나 물론 이것이 모든 방법은 아닙니다. 덜 인기가 있지만 덜 효과적인 것은 다음과 같습니다.

• 언덕 등반, 경사 하강 및 유전 알고리즘을 포함한 최적화 알고리즘
• 적대적 검색/스케줄링 알고리즘(minimax 및 알파-베타 가지치기)
• 분류 방법(퍼셉트론, 신경망 및 지원 벡터 머신)
• 처리 에이전트의 인식 및 기억 시스템
• AI에 대한 아키텍처 접근 방식(하이브리드 시스템, 하위 집합 아키텍처 및 AI 시스템을 오버레이하는 기타 방법)
• 애니메이션 도구(계획 및 모션 조정)
• 성능 요인(세부 수준, 언제든지 및 타임슬라이싱 알고리즘)

관련 자료 :

1. GameDev.net에는 AI에 관한 기사와 튜토리얼이 포함된 섹션과 форум.
2. AiGameDev.com 게임 AI 개발과 관련된 광범위한 주제에 대한 많은 프레젠테이션과 기사가 포함되어 있습니다.
3. GDC 금고 GDC AI Summit의 주제가 포함되어 있으며 그 중 대부분은 무료로 제공됩니다.
4. 홈페이지에서도 유용한 자료를 보실 수 있습니다. AI 게임 프로그래머 길드.
5. AI 연구원이자 게임 개발자인 Tommy Thompson은 YouTube에서 동영상을 만듭니다. AI와 게임 상용게임 속 AI에 대한 설명과 연구로

주제에 관한 책:

1. Game AI Pro 도서 시리즈는 특정 기능을 구현하는 방법이나 특정 문제를 해결하는 방법을 설명하는 짧은 기사 모음입니다.

게임 AI 프로: 게임 AI 전문가들의 지혜를 모아보자
게임 AI 프로 2: 게임 AI 전문가들의 지혜를 모아보자
게임 AI 프로 3: 게임 AI 전문가들의 지혜를 모아보자

2. AI 게임 프로그래밍 위즈덤(Wisdom) 시리즈는 게임 AI 프로(Game AI Pro) 시리즈의 전신이다. 여기에는 오래된 방법이 포함되어 있지만 거의 모든 방법이 오늘날에도 관련이 있습니다.

AI게임프로그래밍 지혜 1
AI게임프로그래밍 지혜 2
AI게임프로그래밍 지혜 3
AI게임프로그래밍 지혜 4

3. 인공 지능: 현대적인 접근 방식 인공지능의 일반적인 분야를 이해하고 싶은 모든 사람을 위한 기본 교재 중 하나입니다. 이 책은 게임 개발에 관한 책이 아닙니다. AI의 기초를 가르치는 책입니다.

출처 : habr.com