4장 인공지능 - ② 길 찾기 알고리즘
인공지능(AI, Artificial Intelligence)알고리즘은 게임에서 컴퓨터가 제어하는 오브젝트의 행위를 결정하는 데 사용한다. 4장에서는 3가지의 유용한 AI 게임 테크닉을 다룬다.
💡 4장의 목차
- 상태 기계로 행위 변경하기
- 오브젝트가 세계 주변을 돌아다니도록 경로 계산하기(길 찾기)
- 너비 우선 탐색(BFS)
- 휴리스틱
- 탐욕 최우선 탐색
- \(A^*\) 탐색
- 데이크스트라 알고리즘
- 2인용 턴 기반 게임(미니맥스와 게임 트리)에서 의사결정 내리기
길 찾기 알고리즘
길 찾기 알고리즘은 두 지점의 경로상에 있는 장애물을 피해서 길을 찾는다. 길 찾기의 복잡성은 두 점 사이에는 여러 다양한 경로 집합이 존재할 수 있다는 사실에 있다. 이러한 경로 중 아주 적은 수의 경로만이 최단 경로가 될 수 있다.
그래프
노드의 정의
여기에서는 위의 그래프 자료구조 설명 링크에서 구현했던것과 비슷하게 인접 리스트 방식으로 구현하고자 한다. 하지만, 위의 링크에 있는 그래프 자료구조 구현은 C언어로 구현하였지만, 여기에서는 C++로 그래프를 구현하는 만큼 std::vector를 사용하여 다음과 같이 더욱 간결하게 그래프를 정의한다.
노드의 정의
struct GraphNode
{
// 각 노드는 인접 노드의 포인터들을 가지고 있다.
std::vector<GraphNode*> mAdjacent;
};
struct Graph
{
// 그래프는 노드들을 포함한다.
std::vector<GraphNode*> mNodes;
};
가중 그래프에서의 노드(node)와 에지(edge) 정의
가중 그래프에서 각 노드는 연결된 노드 리스트 대신에 외부로 향하는 에지를 저장한다. 그리고 에지의 '시작'과 '끝'을 참조하면 노드 A에서 B로 향하는 방향성 있는 에지의 지원이 가능하다.
가중 그래프에서 노드의 정의
struct WeightedEdge
{
// 이 에지에 어떤 노드가 연결돼 있는가?
struct WeightedGraphNode* mFrom;
struct WeightedGraphNode* mTo;
// 이 에지의 가중치
float mWeight;
};
struct WeightedGraphNode
{
// 외부로 향하는 에지을 저장
std::vector<WeightedEdge*> mEdges;
}너비 우선 탐색(BFS)
BFS 알고리즘은 가장 가까운 노드에 목표물을 발견할 수 없을때 한 단계 더 먼 노드를 탐색한다. 때문에 모든 에지에 가중치가 없거나 모든 에지가 양의 같은 가중치를 가진다면 BFS 알고리즘으로 최단경로의 이동횟수를 구할 수 있다. 그리고 BFS 알고리즘을 수행하는 동안 몇 가지 데이터를 기록하면 최단경로도 구할 수 있다.
BFS 알고리즘으로 최단경로를 구하기 위해서는 BFS 알고리즘을 수행하는 동안 각 노드는 직전에 방문한 부모노드를 알아야 한다. 부모 노드는 BFS가 완료된 후 경로를 재구성하는 데 도움이 된다. 부모노드는 다음과 같이 정의한다.
부모노드 정의(해쉬맵 이용)
using NodeToParentMap = std::unordered_map<const GraphNode*, const GraphNode*>;BFS의 구현
BFS를 구현하는 가장 간단한 방법은 Qeueue이다.
- 먼저 시작 노드를 큐에 추가하고 루프에 진입한다.
- 각 반복에서 큐로부터 노드를 꺼낸 뒤 해당 노드의 이웃을 큐에 추가한다.
- 이때 부모노드 맵을 확인함으로써 이미 검사한 노드를 큐에 다시 추가하는걸 피할 수 있다.
BFS 함수
bool BFS(const Graph& graph, const GraphNode* start, const GraphNode* goal, NodeToParentMap& outMap)
{
// 경로를 찾았는지를 알 수 있는 플래그
bool pathFound = false;
// 고려해야 될 노드
std:queue<const GraphNode*> q;
// 시작 노드를 큐에 넣는다
q.emplace(start);
while(!q.empty())
{
// 큐에서 노드를 꺼낸다.
const GraphNode* current = q.front();
q.pop();
if(current == goal)
{
pathFound = true;
break;
}
// 큐에는 없는 인접 노드를 꺼낸다
for(const GraphNode* node : current->mAdjacent)
{
// 시작 노드를 제외하고
// 부모가 null이면 큐에 넣지 않은 노드다
const GraphNode* parent = outMap[node];
if(parent == nullptr && node != start)
{
// 이 노드의 부모 노드를 설정하고 큐에 넣는다
outMap[node] = current;
q.emplace(node);
}
}
}
return pathFound;
}BFS 함수를 통해서 경로 찾기에 성공한다면 outMap의 부모 포인터를 사용해서 경로 재구축이 가능하다. 왜냐하면 경로상에서 목표 노드의 상위 노드는 선행 노드를 가리키기 때문이다.
하지만 아쉽게도 outMap을 참조하면 시작지점 → 목표지점이 아니라 목표지점 → 시작지점의 경로가 반환된다. 그래서 결과 값의 반전이 필요한데 이때 stack을 활용할 수도 있지만, 더욱 효과적인 방법은 애초에 탐색을 거꾸로 하는 것이다. 즉, 목표지점 → 시작지점으로 입력을 주면 시작지점 → 목표지점의 결과가 나오게 될 것이다.
BFS의 한계
BFS는 다음 두 가지의 한계를 가진다.
- 에지에 가중치가 없거나 모든 에지가 동일한 양의 가중치를 가질 경우에만 최단 거리를 탐색결과를 보장한다.
- 목표노드의 반대 방향으로도 탐색이 이루어지면서 불필요한 테스트를 진행하게된다.
조금 더 복잡한 알고리즘을 적용하면 위의 문제들흘 해소할 수 있다.
휴리스틱 (heuristic) 함수
휴리스틱 함수는 주어진 노드로부터 목표 노드까지의 예상되는 비용을 추측하는 함수이다. 많은 탐색 알고리즘은 예상되는 결과를 근사하는 휴리스틱 함수에 의존한다.
예를 들어 BFS도 휴리스틱 함수를 사용하면 성능을 개선시킬 수 있다. 휴리스틱을 사용하지 을 경우의 BFS 알고리즘에서는 각 반복마다 다음으로 탐색하려는 노드가 목표로부터 멀어지는 방향에 있다 하더라도 큐에서 해당 노드를 꺼내었다. 하지만 휴리스틱 함수를 여기에 적용하면 특정 노드가 목표에 얼마나 가까운지를 예상할 수 있게 되기 때문에 목표노드와 조금 더 가까운 노드를 우선적으로 살펴 볼 수 있다. 때문에 불필요하게 목표와 더 멀어지는 방향으로의 탐색을 줄여 더 빠르게 탐색을 종료할 수 있다.
휴리스틱 함수는 맨해튼 거리 방식과 유클리드 거리 방식으로 나뉜다.
맨해튼 거리
맨해튼 거리 휴리스틱 함수를 사용기 위해서는 대각선의 이동은 유효하지 않다고 가정해야한다. 그리고 맨해튼 거리는 다음 공식으로 계산한다.
\[h(x) = |start.x - end.x| + |start.y - end.y|\]
유클리드 거리
유클리드 거리는 다음 공식으로 계산한다.
\[h(x) = \sqrt{(start.x - end.x)^2 + (start.y - end.y)^2} \]
맨해튼 휴리스틱은 단순 덧셈 연산인 반면 유클리드 휴리스틱은 제곱근을 사용하므로 유클리드 휴리스틱 함수는 계산에서는 비효율 적이다. 하지만 유클리드 휴리스틱은 거의 모든 상황에서 사용 가능하다. 유클리드 휴리스틱을 사용할 수 없는 경우는 게임이 레벨에 존재하는 두 노드 사이를 텔레포트하는 것과 같은 비유클리드 이동을 허락하는 경우이다.
탐욕 최우선 탐색
탐욕 최우선 탐색(GBFS, Greedy Best First Search)는 다음 탐색 노드를 선정하기 위해서 휴리스틱 함수를 사용한다. GBFS는 아래의 그림 처럼 최단 경로를 보장해주지 않는다. (빨강색 화살표 처럼 불필요한 이동을 한다.)
GBFS가 최단 경로를 보장해주지는 않지만, GBFS를 몇가지만 수정하면 \(A^*\)가 되어서 최단경로를 구할 수 있기 때문에 GBFS를 다루는 것은 중요하다.
BFS의 구현에서는 탐색을 진행하는 동안 큐를 사용했지만 GBFS는 큐 대신에 2개의 집합을 사용한다.
- 열린 집합: 평가 대상이 될 노드를 모두 포함하는 집합
- 닫힌 집합: 평가를 위해 선택된 노드를 포함하는 집합
노드가 닫힌 집합에 있다면 GBFS는 더이상 그 노드를 조사하지 않는다. 열린 집합이나 닫힌 집합에 있는 노드가 경로상에 있을 거란 보장은 없지만, 이 집합들은 불필요한 노드를 쳐내는 데 도움이 된다.
노드가 닫힌 집합인지 열린 집합인지 알기 위해서는 추가 데이터에 이진값을 사용한다. 열린 집합을 관리하기에 적합한 자료구조는 우선순위큐이다. 하지만 여기서는 간결함을 위해 벡터를 사용한다. GBFS 탐색 동안 노드를 위한 추가 데이터가 필요하고, 그 수가 많으므로 이 데이터를 캡슐화한 구조체를 정의한다.
GBFS 탐색을 위한 추가데이터 구조체
struct GBFSScratch
{
const WeightedEdge* mParentEdge = nullptr;
float mHeuristic = 0.0f;
bool mInOpenSet = false;
bool mInClosedSet = false;
}GBFS에서 사용할 맵
using GBFSMap = std::unordered_map<const WeightedGraphNode*, GBFSScratch>;이제 탐욕 최우선 탐색 함수를 구현한다.
- 시작 노드를 평가하기 위해서 닫힌 집합에 담는다
- 현재 노드의 모든 인접노드들에 대해서 다음 반복문을 실행한다.
- 현재 인접 노드가 닫힌 집합에 없다면 인접 노드의 부모 노드를 현재 노드로 한다.
- 그리고 현재 인접노드가 열린 집합에 없다면 이 노드의 휴리스틱을 계산하고 열린 집합에 추가한다.
- 열린집합이 비었다면 시작점에서 목표점 까지의 경로가 존재하지 않음을 뜻하기 때문에 탐색을 종료한다.
- 열린 집합이 비어있지 않다면 열린집합에서 휴리스틱값이 가장 작은 노드를 현재 평가중인 노드(
current)로 설정하고 열린 집합에서 빼내어 닫힌 집합에 넣는다.(다음 경로가 되는 것이다.) - 아직 목표지점에 도달하지 않았다면 2.번부터 반복한다.
GBFS
bool GBFS(const WeightedGraph& g,
const WeightedGraphNode* start,
const WeightedGraphNode* goal,
GBFSMap& outMap)
{
// 열린 집합 벡터
std::vector<const WeightedGraphNode*> openSet;
// 시작 노드를 현재 노드로 설정하고 닫힌 집합에 있다고 마킹한다.
const WeightedGraphNode* current = start;
outMap[current].mInClosedSet = true;
do
{
// 인접 노드를 열린 집합에 추가
for(const WeightedEdge* edge : current->mEdges)
{
// 이 인접 노드의 추가 데이터를 얻는다.
GBFSScratch& data = outMap[edge->mTo];
// 닫힌 집합에 있는 노드가 아니라면 테스트를 진행한다.
if (!data.mInClosedSet)
{
// 인접 노드의 부모를 현재 노드로 설정
data.mParentEdge = edge;
if(!data.mInOpenSet)
{
// 이 노드의 휴리스틱을 계산하고 열린 집합에 추가한다.
data.mHeuristic = ComputeHeuristic(edge->mTo, goal);
data.mInOpenSet = true;
openSet.emplace_back(edge->mTo); // 열린 집합에 추가
}
}
}
// 열린 집합이 비었다는 것은 경로가 존재하지 않는것으로 간주
if(openSet.empty())
{
break; // 루프에서 벗어난다.
}
// 열린 집합에 노드가 있다면 알고리즘을 계속 진행
// 열린 집합에서 가장 비용이 낮은 노드를 찾는다
auto iter = std::min_element(openSet.begin(), openSet.end(),
[&outMap](const WeightedGraphNode* a, const WeightedGraphNode* b)
{
return outMap[a].mHeuristic < outMap[b].mHeuristic;
});
// 현재 노드를 설정하고 이 노드를 열린 집합에서 닫힌 집합으로 이동시킨다.
current = *iter;
openSet.erase(iter);
outMap[current].mInOpenSet = false;
outMap[current].mInClosedSet = true;
}while(current != goal);
// 탐색 성공여부를 반환
return (current == goal) ? true : false;
}위 코드에서 몇 가지만 추가적으로 살펴보자
- 위 코드에서 사용된
ComputeHeuristic()함수를 여기서 별도로 구현하지는 않았지만, 맨하튼 거리 혹은 유클리드 거리 중 필요에 맞는 방식으로 구현할 수 있다. - 이 코드에 중에서
auto iter = std::min_element()부분을 살펴보자.min_element()알고리즘에 대한 설명은 이 링크로 대체한다. - 여기서
min_element()알고리즘의 3번째 인자(두 값을 비교하는 조건자)로 람다식을 활용했다. 결론적으로iter반복자에openSet벡터의 원소들 중에서 휴리스틱 값이 가장 작은 원소의 반복자를 반환하는 문장으로 이해하면 된다.
탐욕 최우선 알고리즘을 그림으로 살펴보면 다음과 같다. 초록색 부분이 닫힌 집합이고 보라색 부분이 열린 집합을 표현한 것이다.
- 첫 번째 그림
- 시작지점을 현재 노드로 설정하여 닫힌 집합에 넣었다.
- 현재 노드의 인접 노드들의 휴리스틱 값을 계산하고 모두 열린 집합에 넣었다.
- 두 번째 그림
- 열린 집합에서 휴리스틱 값이 가장 작은 노드를 닫힌 집합에 넣고, 현재 노드로 설정한다.
- 현재 노드의 인접 노드들의 휴리스틱 값을 계산하여 열린 집합에 넣었다.
\(A^*\) 탐색
GBFS은 최단 경로를 보장하지 않는다. 하지만 GBFS를 약간 수정하면 \(A^*\)탐색으로 변환 가능하며, \(A^*\)탐색은 최단 경로를 보장한다.
\(A^*\)는 시작 노드에서 임의의 노드로의 실제 비용을 뜻하는 경로 비용을 추가로 사용한다. 경로 비용을 계산하는 함수를 g(x)라 한다. g(x)는 출발 정점에서 해당 정점까지의 이동 비용을 뜻한다. GBFS에서 각 노드별 평가 함수를 휴리스틱 함수로 사용했었는데 \(A^*\)에서 평가함수f(x)는 아래의 식과 같이 경로 비용과 휴리스틱 값의 합으로 사용한다.
\[f(x) = h(x) + g(x)\]
GBFS에서는 다음의 현재노드를 설정할 때 휴리스틱 함수 h(x)의 결괏값이 가장 작은 노드로 지정했지만, \(A^*\) 탐색에서는 평가함수 f(x)의 결괏값이 가장 작은 노드를 다음의 현재 노드로 지정한다.
경로 비용 g(x) 산정
\(A^*\)에서는 노드를 열린 집합에 추가할 때 경로 비용 g(x)를 계산해야 한다.
GBFS에서는 인접 노드는 항상 현재 노드를 부모 노드로 설정했지만 \(A^*\)는 그렇지 않다. \(A^*\)에서 노드의 경로 비용 값g(x)는 아래의 그림처럼 부모 노드의 g(x)값에 따라 달라진다. 노드 x의 경로 비용 값은 해당 노드 부모의 경로 비용 값에 부모로부터 노드 x로의 에지를 이동하는데 드는 비용을 더한 값이기 때문이다.
그래서 노드x에 부모를 할당하기 전에 \(A^*\)는 g(x) 값이 더 개선될 수 있을지를 확인해야 한다.
\(A^*\) 구현
\(A^*\)를 구현하기 위해서는 g(x)에 대한 값을 저장하기 위해서 데이터를 추가해야한다. 그래서 GBFSScratch 구조체를 아래와 같이 수정한다.
AstarScratch 구조체
struct AStarScratch
{
const WeightedEdge* mParentEdge = nullptr;
float mHeuristic = 0.0f;
float mActualFromStart = 0.0f; // 경로 비용 g(x) 값
bool mInOpenSet = false;
bool mInClosedSet = false;
};노드 채택을 제외하면 \(A^*\)코드는 GBFS코드와 매우 유사하다. 아래의 코드는 GBFS와 차이가 큰 부분만 작성하였고, 전체 코드는 여기(Search.cpp)에서 확인할 수 있다.
\(A^*\) 탐색에서 인접 노드에 대한 루프
for (const WeightedEdge* edge : current->mEdges)
{
const WeightedGraphNode* neighbor = edge->mTo;
// 이 노드의 추가 데이터를 얻는다
AStarScratch& data = outMap[neighbor];
// 닫힌 집합에 없는지를 확인
if (!data.mInClosedSet)
{
// 인접 노드가 열린 집합에 없다면
if(!data.mInOpenSet)
{
// 부모는노드를 현재 노드로 지정한다.
data.mParentEdge = edge;
// 휴리스틱 값을 계산해서 저장한다.
data.mHeuristic = ComputeHeuristic(neighbor, goal);
// 실제 비용(g(x)) 부모의 실제 비용(g(x)) + 부모에서 자신으로 이동하는 에지의 가중치
data.mActualFromStart = outMap[current].mActualFromStart
+ edge->mWeight;
// 인접노드를 OpenSet에 넣는다.
data.mInOpenSet = true;
openSet.emplace_back(neighbor);
}
else // 열린 집합에 이미 존재하는 인접 노드라면
{
// 현재 노드가 부모 노드가 될지를 판단하고자 새로운 실제 비용을 계산
float newG = outMap[current].mActualFromStart + edge->mWeight;
if( newG < data.mActualFromStart)
{
// 현재 노드가 이 노드의 부모 노드로 채택됨
data.mParentEdge = edge;
data.mActualFromStart = newG;
}
}
}
}데이크스트라 알고리즘
데이크스트라 알고리즘(Dijkstra's algorithm)은 변형이 많다. 데이크스트라 알고리즘은 원래 두 노드 간의 가장 짧은 경로를 찾는 알고리즘이지만, 더 일반적인 변형은 한 노드를 "시작" 노드로 고정하고 그래프의 다른 모든 노드까지의 최단경로를 찾는 알고리즘으로 최단 경로 트리를 만드는 것이다. 우리는 이를 활용해서 시작점에서 목표지점까지 최단거리를 알 수 있게 된다.
데이크스트라 알고리즘은 \(A^*\)알고리즘을 다음과 같이 간단히 수정하여 사용할 수 있다.
- h(x) = 0 으로 두어서 휴리스틱 함수 요소를 제거한다.
- 목표 노드를 제거하고 열린 집합이 빌 때만 루프를 종료하도록 한다.
- 이를 통해서 시작점에서부터 모든 도달 가능한 노드에 대한 경로 비용 g(x)를 계산한다.
이 방식은 원래 데이크스트라 알고리즘의 공식과 조금 다르지만 기능적으로는 동일하다. AI 서적에서는 이러한 접근법을 균일 비용 탐색 이라고 부르기도 한다. 그리고 게임에서는 사실 \(A^*\)같은 경험에 기반을 둔 접근법을 선호한다. 왜냐하면 휴리스틱 기반 접근법이 데이크스트라 알고리즘보다 노드 탐색의 수가 훨씬 적기 때문이다.
길 따라가기
길 찾기 알고리즘이 경로를 생성하면 AI는 그 경로를 따라가야 한다. 우리는 이미 MoveComponent에서 엑터가 전진하도록 구현하였기 때문에 아래의 기능들만 추가 구현하면 된다. 구현 순서는 다음과 같다.
MoveComponent를 상속받는NavComponent만들어 경로를 따라가도록 한다.- 액터는
MoveComponent에 의해서 앞 방향으로 이동한다 - 액터가
mNextPoint에 도달할때 까지 앞 방향으로 이동한다. mNextPoint에 도달했다면 새로운GetNextPoint()함수로 다음mNextPoint를 받아오고 새로운mNextPoint방향을 향해서 회전한다.
전체 구현 코드 NavComponent.h / NavComponent.cpp
기타 그래프 표현
일반적인 게임에서 캐릭터가 격자상의 사각형에서 사각형으로 이동하는 경우는 드물다. 이번 절에서는 그래프로 세계를 표현하는 방법을 다룬다. 그래프로 세계를 표현하는 방법은 크게 두 가지가 있다.
- 경로 노드(Path node). 혹은 웨이포인트(Waypoint) 라고도 부름
- 네비게이션 메시
경로 노드
이 접근 방식에서 디자이너는 게임 세계에서 AI가 이동할 수 있는 위치에 경로 노드를 배치한다. 이 경로 노드는 그래프상의 노드로 직접 변환된다. 일반적으로 경로 노드 사이의 에지는 자동적으로 생성된다. 에지 생성 알고리즘은 다음과 같다.
- 각 노드에서 해당 노드와 해당 노드 근처에 있는 노드 사이에 장애물이 있는지 검사한다.
- 각 노드 사이를 차단하는 장애물이 없다면 에지를 생성한다.
경로 노드 방식은 "AI가 노드 또는 에지의 위치로만 이동할 수 있다."는 단점이 존재한다. 이를 해결하기 위해서는
- AI가 이동에 제약을 받지 않는 공간을 많이 준다.
- AI의 이동을 위해 많은 경로 노드를 제공해야 한다.
하지만 첫번째 방법은 AI가 믿음직스럽지 못한 행동을 할 수 있기 때문에 바람직하지 않다. 두 번째 방법은 노드와 에지가 많아지면 많아질수록 길 찾기 알고리즘 성능이 해답을 찾는데 많은 시간을 소비하기때문에 비효율적이다. 즉, 정확도와 성능 간의 트레이드 오프가 필요함을 의미한다.
네비게이션 메시
또다른 접근 법으로는 네비게이션 메시(Navigation mesh)가 존재한다. 이 접근법에서 그래프상의 각 노드는 볼록 다각형에 해당하며 인접 노드는 인접한 볼록 다각형이다. 이 방식은 다음과 같은 장점이 존재한다.
- 몇 개의 볼록 다각형만으로도 게임 세계의 전체 지역을 나타낼 수 있다.
- 내비게이션 메시를 사용하면 AI는 볼록 다각형 내부의 어떠한 지점도 안전하게 이동할 수 있다.
- 이동의 종류가 다양한 게임에 대해 더욱더 효과적이다.
- 예를 들어 지상 유닛이 이동할 수 있는 곳과 공중 유닛이 이동할 수 있는 곳은 분명 다르다. 네비게이션 메시에의 특정 블록 다각형 지역이 해당 캐릭터에 적합한지 여부를 계산하는 것은 쉬운일이다.
네비게이션 메시 생성
네비게이션 메시의 자동 생성은 디자이너가 AI 경로 지정에 따른 영향을 걱정할 필요없이 레벨을 변경할 수 있기에 유용하다. 하지만 내비게이션 메시 생성 알고리즘은 복잡하다. 보통은 내비게이션 메시 생성을 구현한 오픈소스를 많이 활용한다. 대표적으로는 Recast 라이브러리를 사용할 수 있다.
본 게시글은 에이콘 출판사의 Game Programming in C++ 도서를 학습하며 요약정리한 내용입니다.
