[게임 개발 이론] 캐릭터 메커니즘

[게임 개발 이론] 캐릭터 메커니즘

"유니티로 만드는 게임 개발 총론(2013, 페니 드 빌, 박기성 옮김)에서"

NPC의 의사결정에 쓰이는 AI의 종류

가시선

NPC의 시야로 NPC가 플레이어를 보았는지 판별

플레이어에게 직선적으로 접근, NPC가 위협적이고 나쁜 의도를 가지고 있음을 곧장 깨닫게 해줌

NPC의 시야 : 바라보는 방향, 위치, 가시 범위, 가시각으로 결정

direction = player.position - NPC.position;

바라보는 방향 벡터와 방향 벡터가 이루는 각도(direction)가 가시각보다 작고

방향 벡터(direction) 크기가 가시 범위보다 작으면 플레이어 감지

그래프 이론

그래프 : 노드(정점)와 엣지(간선)의 집합

노드 : 좌표, 혹은 물리적 위치가 의미가 없는 상징적인 상태로 사용 가능

엣지 : 노드 간의 거리, 액션을 완료하는데 소요되는 시간

경유지

맵에서 기억된 위치, 직선 경로로 연결됨

경로를 따라 움직이는 NPC가 장애물에 충돌되지 않도록 경로와 경유지 연결 => 그래프를 이룸

한 경유지에서 다른 경유지로 이동 : 모든 노드 검색 및 탐색해서 연결 상태 파악하는 알고리즘 필요 (BFS, DFS)

물리적 구조(노드의 위치, 노드들 사이 거리)는 꼭 반영할 필요는 없다

NPC가 경유지들을 최단 경로를 통해 이동하게 하려면?

최단 경로

게임에서의 최단 경로의 계산 = 각 경유지를 이동하는 데 소요되는 시간을 기준으로 계산

기하학적 최단 거리를 가진 경로와 최단 경로는 다를 수 있다

강을 곧바로 가로지르는 경로(최단 거리)의 소요 시간 = 다리로 이동하여 강을 건너는 경로의 소요 시간 * 2 일 경우...

NPC가 거리보다 시간에 효용 utility을 높이 둔다면 다리로 이동하여 강을 건너는 경로를 선택

그래프에서 효용 가치 = 엣지에 대한 가중치

경로를 효율적으로 구현하려면 경유지를 검색해서 최적의 경로를 찾는 효율적인 방법이 필요

경유지 탐색

DFS, BFS, A*

https://achro98.tistory.com/8

A* 알고리즘

가장 유망해 보이는 노드를 찾는 정점 탐색 알고리즘

시작 노드에서 모든 인접 노드의 추정 비용 계산, 최적의 노드가 경로상 다음 노드를 선택

경로가 적당하지 않으면 대기 중인 다음 최적 후보로 되돌아가서 다른 경로 검색

Dijkstra 알고리즘과 다른 점 : 목적지를 설정할 수 있음

// 이 소스 코드의 그래프는 인접 리스트 방식으로 그래프를 표현하였다. using ii = pair; priority_queue, vector > pq; /// N_VER은 그래프의 정점의 개수를 의미한다. int dist[N_VER], cost[N_VER][N_VER]; /// dist[i]는 i번째 정점까지 가는 최단 거리를 의미한다. vector edges[N_VER]; /// edges[i]는 i와 연결된 정점과 가중치를 묶어 저장하는 벡터이다. int minDist(int src, int dst) { pq.push({0, src}); bool success = false; while (!pq.empty()) { int v = pq.top(); pq.pop(); if (v == dst) { success = true; break; } for (ii adj: edges[v]) { if (dist[adj.first] < g(v) + adj.second + h(adj.first)) { dist[adj.first] = g(v) + adj.second + h(adj.first); // 이완 (relaxation) pq.push({dist[adj], adj}); // 다음 정점 후보에 탐색하고 있는 정점을 넣는다. } } } if (!success) return -1; else return dist[dst]; }

출처 : https://ko.wikipedia.org/wiki/A*_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

유한 상태 기계 finite state machines : FSM

방향성 그래프의 형식 (노드 : 상태, 엣지 : 상태 전환)

상태 : NPC의 현재 행동 혹은 심리 상태

상태 전환 : 한 상태에서 다른 상태에 도달하는 방법

예시) 상태 S = {WANDER, ATACK, PURSUE}, 상태 변화 T = {out of sight, sighted, out of range, in range, dead}

out of sight sighted out of range in range dead WANDER WANDER PURSUE PURSUE WANDER PURSUE ATTACK ATTACK PURSUE ATTACK WANDER

FSM 코드 : NPC에게 현재 행동을 나타내는 상태 값(+ 이벤트 값)을 제공

이벤트 값 : NPC가 상태 돌입 여부, 상태 돌입 경과 시간

군집

하늘의 세 때 무리처럼 공통의 목적지를 향해 이동하지만 모두가 완전히 똑같은 경로는 아닌 상태

Craig Reynolds가 군집 행동을 만들기 위해 개발한 알고리즘의 3가지 규칙

그룹의 평균 위치를 향해 이동한다. 그룹의 평균 방향으로 방향을 맞춘다. 다른 그룹 구성원과 붙는 것을 피한다.

한 개체만 목적지로 향하게 하고 나머지 개체는 군집을 이뤄 따르게 만들면 성능 최적화 가능

결정 트리 Decision tree

복잡한 불 함수를 구조화하고 활용해서 상황을 추론하는 계층적 그래프

추론되는 상황을 기술하는 속성들의 집합

노드 : 결정 경로 상에 존재하는 하나의 불 결정

결정 경로 : 트리 말단 또는 잎 노드까지 이어짐

프로그램 실행 중에도 NPC 행동 개선할 수 있는 신규 정보 통합 업데이트가 가능

자동 자원 수집

퍼지 로직 Fuzzy Logic

모호하고 불완전한 정보를 기반으로 의사 결정

집합론을 적용, 모호한 용어에 존재하는 값의 범위를 기술

퍼지집합에서는 값들이 여러 개의 집합에 중첩될 수 있음

if x가 A

then y는 B

언어 변수(x, y) : 측정되는 특징들 (온도, 속도, 높이)

언어 값(A, B) : 퍼지 카테고리 (뜨겁다, 빠르다, 높다)

퍼지 규칙 집합과 입력 값 => 퍼지 추론 fuzzy inferencing으로 출력 값 추정

맘다니 스타일 Mamdani

퍼지화 fuzzification : 불연속적인 값의 입력을 받아 모호하게 만듦 (소속도로 만듦) 규칙 평가 rule evaluation : 소속도를 주어진 규칙으로 대체 통합 aggregation : 퍼지 집합을 잘라내어 통합하고 새로운 퍼지 집합 생성 역퍼지화 defuzzification : 최종 통합된 퍼지 집합을 퍼지 출력 값이 될 단일 값으로 변환

유전자 알고리즘

진화 컴퓨팅 Evolutionary computing : 환경 적응과 생존을 통해 지능을 연구

선택, 번식, 돌연변이 같은 개념을 구현해 자연적 진화 과정을 계산적으로 흉내내어 재현해 봄

집단 생성, 적성 결정 ㅣ 염색체 길이와 집단 규모 지정, 각 개체의 과제 수행도로 적자 the fittest 결정 적자 개체 교배 : 적응도 기준 정렬 후 상위 개체 교배, 새로운 개체 생성, 이 중 유전자 뒤집어 돌연변이 생성 가능 새로운 집단 유입 : 이전 세대 절멸, 새로운 집단의 적응도 판별 후 정렬과 교배

셀룰러 오토마타

연관 값을 가진 셀들로 이루어진 격자

각 셀의 값이 이웃한 셀의 값에 따라 끊임없이 갱신

<문명 6>에서 특수지구 인접 보너스, 매력도가 주변 타일의 상태에 의해 갱신되는 것

from http://achro98.tistory.com/17 by ccl(A) rewrite - 2021-08-16 23:00:34