인공지능 - 길찾기 BFS

 

길 찾기 알고리즘은 두 지점의 경로상에 있는 장애물을 피해서 길을 찾는다.

이 길 찾기의 복잡성은 두 점 사이에는 여러 다양한 경로 집합이 존재할 수 있다는 사실에 있다.

하지만 이러한 경로 중 아주 적은 수의 경로만이 최단 경로이다.

장애물의 표면을 따라 이동하는 AI는 지능적으로 보이지 않는다.

그래서 최단 경로를 찾기 위해서 모든 가능한 경로를 효율적으로 탐색하기 위한 방법이 필요하다.

 

그래프

 

길 찾기 문제를 풀기 전에 먼저 AI가 통과할 수 있는 게임 세계의 부분을 표현하는 방법이 필요하다.

일반적으로는 그래프 데이터 구조를 많이 선택한다.

그래프는 일련의 노드를 포함한다. 이 노드는 에지를 통해서 서로 연결된다.

 

이 에지는 방향성이 없는 경우가 있는데

방향성이 없다는 것은 양방향으로 이동할 수 있다는 걸 의미한다.

 

반면 방향성이 있다는 것은,

에지가 오직 한 방향으로만 이동할 수 있다는 걸 뜻한다.

AI가 플랫폼에서 뛰어 내릴 수는 있지만,

다시 뛰어 올라갈 수는 없는 경우 방향성 있는 에지를 사용하면 된다.

이 연결은 플랫폼에서 땅으로의 방향성 있는 에지로 나타낼 수 있다.

 

에지는 선택적으로 에지와 관련된 가중치를 가질 수 있는데,

가중치는 에지를 이동하는 데 드는 비용을 나타낸다.

게임에서 가중치는 노드 사이의 최소한의 거리를 뜻한다.

그러나 이 가중치는 에지를 이동하는 것이

얼마나 어려운지를 나타내는 뜻으로 수정해서 사용할 수 있다.

 

예를 들어 에지가 게임 세계에서 모래더미를 지나간다면

콘크리트를 이동하는 같은 길이의 에지보다는 더 큰 가중치를 가져야 할 것이다.

에지에 가중치가 없는 그래프(균일 그래프)는 모든 에지의 가중치가 항상 일정한 그래프다.

 

메모리상에 그래프를 나타내는 데는 여러 가지 방법이 있으나

이 글에서는 인접 리스트를 사용한다.

이 표현에서 각 노드는 std::vector를 사용해서 인접 노드 컬렉션을 가진다.

그리고 그래프는 그런 노드의 단순한 집합이다.

 

위 내용을 종합하여 코드를 작성하면 다음과 같다.

struct GraphNode
{
	// 각 노드는 인접 노드의 포인터들을 가지고 있다.
	std::vector<GraphNode*> mAdjacent;
};

struct Graph
{
	// 그래프는 노드들을 포함한다.
	std::vector<GraphNode*> mNodes;
};

// 즉 Grahp는 vector<vecor<<Node>>; 의 형태랑 비슷하다.

struct WeightedEdge
{
	// 이 에지에 어떤 노드가 연결돼 있는가?
	struct WeightedGraphNode* mFrom;
	struct WeightedGraphNode* mTo;
	// 이 에지의 가중치
	float mWeight;
};

struct WeightedGraphNode
{
	// 외부로 향하는 에지를 저장한다.
	std::vector<WeightedEdge*> mEdges;
};

// (가중 그래프는 WeightedGraphNode를 가진다.)
// 가중 그래프에서 각 노드는 연결된 노드 리스트 대신 외부로 향하는 에지를 저장한다.
struct WeightedGraph
{
	std::vector<WeightedGraphNode*> mNodes;
};

 

 

에지의 '시작'과 '끝'을 참조하면 노드 A에서 B로 향하는 방향성 있는 에지의 지원이 가능하다.

이 경우에는 노드 B의 mEdges 벡터가 아니라 노드 A의 mEdges 벡터에 에지를 추가해야 한다.

 

방향성이 없는 에지를 원하면 간단히 각 방향별로 하나씩 2개의 방향성 있는 에지를 추가하면 된다.

 

여러 게임은 여러 가지 방식을 사용해서 그래프를 통해 게임 세계를 나타낸다.

세계를 격자 형태의 사각졍으로 분할하는 것은 일반적인 접근법이다.

이 접근법은 문명이나 격자 형태의 사각형으로 분할하는 것은 일반적인 접근이다.

(타일맵도 이러한 개념과 흡사하다.)

 

하지만 다른 유형의 게임에서는 이 방법을 사용하는 것이 실현 가능하지 않을 수도 있다.

일단 해당 게시글에서는 사각형으로 분할된 형태로 보겠다.

 

너비 우선 탐색 (Breadth-First Search)

게임이 사각형 격자로 설계된 미로에서 일어난다고 가정하자.

게임은 오직 4개의 기본적인 방향으로의 이동만 가능하다.

미로에서 각각의 길이가 일정하므로 가중치 없는 그래프로 이 미로를 표현할 수 있다.

 

BFS 알고리즘은 에지에 가중치가 없거나

모든 에지가 같은 양의 가중치를 가질 경우 최단 경로를 찾는 것을 보장한다.

 

BFS 알고리즘을 수행하는

동안 몇 가지 데이터를 기록하면 최소한의 이동 횟수로 경로를 재구성할 수 있다.

경로가 계산되면 AI 캐릭터는 이 경로를 따라 이동할 수 있게 된다.

 

BFS 동안에 각 노드는 직전에 방문한 노드를 알아야 한다.

부모 노드라 불리는 해당 노드는 BFS가 완료된 후 경로를 재구성하는 데 도움이 된다.

이 데이터를 GraphNode 구조체에 추가할 수 있지만,

GraphNode는 부모 노드에 의해 데이터가 변경되지 않도록 분리하는 것이 좋다.

부모 노드는 시작 노드와 목표 노드에 따라 변하기 때문이다.

 

또한 데이터를 분리하면 멀티 스레드를 통해 

동시에 몇 개의 통로를 계산할 경우 각 탐색이 서로 간에 간섭하지 않는 것을 보장할 수 있다.

 

BFS를 구현하는 가장 간단한 방법은 큐의 사용이다.

큐는 노드를 추가하거나 제거할 때 선입선출 행동을 한다는 것을 떠올리자.

enqueue 연산을 통해 노를 큐에 추가할 수 있고,

dequeue를 통해 노드를 제거할 수 있다.

 

using NodeToParentMap =
std::unordered_map<const GraphNode*, const GraphNode*>;

해당 맵을 사용해서,

키 값이 이미 맵에 존재한다면 검사 된 노드이므로 추가하지 않는다.

 

이러한 과정을 반복하다가

시작 노드와 목표 노드 사이에 어떤 경로도 존재하지 않는다면

루프는 종료할 것이다.

 

위 설명을 코드화 하게되면 다음과 같다.

 

//헤더

struct GraphNode
{
	//각 노드는 인접 노드의 포인터들을 가지고 있다.
    std::vector<GraphNode*> mAdjacent;
}

struct Graph
{
	// 그래프는 노드들을 포함한다.
    std::vector<GraphNode*> mNodes;
};

struct WeightedEdge
{
	// 이 에지에 어떤 노드가 연결돼 있는가?
    struct WeightedGraphNode* mFrom;
    struct WeightedGraphNode* mTo;
    float mWeight;
};

struct WeightedGraphNode
{
	//외부로 향하는 에지를 저장
    std::vector<WeightedEdge*> mEdges;
}

// 따로 두는 것이 멀티스레딩 사용 시 각 길찾기에 영향을 주지 않음.
// (가중 그래프는 WeightedGraphNode를 가진다)
// 가중 그래프에서 각 노든느 연결된 노드 리스트 대신 외부로 향하는 에지를 저장
struct WeightedGraph
{
	std::vector<WeightedGrapNode*> mNodes;
}

// CPP

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->mAdhacent)
        {
        	// 부모가 null이면 큐에 넣지 않은 노드이다.
            // (시작노드 재외)
            const GraphNode* parent = outMap[node];
            if (parent == nulptr && node != start)
            {
            	// 이 노드와 부모 노드를 설정하고 큐에 넣는다.
                outMap[node] = current;
                q.emplace(node);
            }
        }
    }
    return pathFound;
}