게임인공지능 6주차 - Graph, Path Finding, Shortest Path, Dijkstra
What is a Graph?
그래프 : 현상이나 사물을 정점(vertex)와 간선(edge)로 표현한 것
Graph G = (V, E), where V is a set of vertex and E is a set of edges
인접(Adjacent) : 두 정점이 간선으로 연결되어 있는 것
경로(Path) : 하나의 정점 v에서 시작해서 또 하나의 정점 v로 가기 위한 일련의 에지
지하철 노선도, 네비게이션과 같은 경우도 일종의 그래프.
그래프의 유형
- 가중치 그래프(Weighted Graph) : edge에 가중치 값이 할당된 그래프
- 방향 그래프 (Directed Graph, Di-Graph) : 방향이 존재하는 그래프
- 무방향 그래프 (Undirected Graph) : edge의 방향성이 없는 그래프
- 연결 그래프 (Connected Graph) : 모든 정점들 간에 갈 수 있는 경로 존재
- 절단 그래프 (Disconnected Graph) : 한 개의 정점이라도 서로 갈 수 있는 길이 없는 그래프
- 완전 그래프 (Complete Graph) : 모든 정점들 사이에 직접 연결된 간선이 존재하는 그래프
N X N 행렬
- 원소 (i, j) = 1 : 정점 i와 정점 j 사이에 간선이 있음
- 원소 (i, j) = 0 : 정점 i와 정점 j 사이에 간선이 없음
유향 그래프의 경우
- 원소 (i, j) = 1 : 정점 i로부터 정점 j로 연결되는 간선을 나타냄
가중치 그래프
- 원소 (i, j)는 1 대신에 가중치를 가짐
인접 리스트
- N개의 연결 리스트로 표현
- i번째 리스트 : 정점 i에 인접한 정점들을 리스트로 연결
- 가중치 그래프인 경우 : 리스트에 가중치도 보관
인접 행렬 vs 인접 리스트
두 노드가 인접해 있는지 판단 : 인접 행렬이 유리
전점 i에 인접한 모든 노드 찾기 : 인접 리스트가 유리
공간
- 인접 행렬 : V^2
- 인접 리스트 : 2E
게임에서의 그래프
- Navigation Graph (항해 그래프)
- Dependency Graph (종속 그래프)
- State Graph (상태 그래프)
Path Finding
- Depth First Search
- Breadth First Search
- Minimum Spanning Tree
Dijkstra 알고리즘과 Astar 알고리즘을 배울 예정
깊이우선탐색 (Depth First Search, DFS)
그래프를 가능한 깊게 이동하여 탐색하는 방식.
Stack을 이용하여 방문한 노드를 저장하고, 막다른 곳에 도달하면 Backtracking 처리한다.
#include <iostream>
#include <stack>
using namespace std;
const int MAXN = 100; // 노드의 최대 개수
int adj[MAXN][MAXN]; // 인접 행렬
bool visited[MAXN]; // 방문 여부 저장 배열
int edges[10][2] = {
{0, 1},
{1, 2},
{2, 3},
{3, 1},
{1, 4},
{4, 5},
{4, 6},
{0, 6},
{6, 7},
{8, 7}
};
void dfs(int start, int dest, int n) {
stack<int> st; // 스택 생성
st.push(start); // 시작 노드를 스택에 넣음
visited[start] = true; // 시작 노드를 방문
bool isFind = false;
while (!st.empty() && !isFind) {
int cur = st.top(); // 스택의 맨 위 노드를 가져옴
// 현재 노드와 연결된 모든 노드에 대해
bool isNext = false;
for(int next=0; next<n; next++){
if(adj[cur][next] && !visited[next]){ // 방문하지 않은 노드에 대해
st.push(next);
visited[next] = true;
isNext = true;
break;
}
}
if(isNext == false) // 이웃 노드를 모두 방문했으면 backtracking
st.pop();
if (dest == st.top())
isFind = true;
}
if(isFind){
while(!st.empty()){
int cur = st.top();
cout << cur << " ";
st.pop();
}
}
else {
cout << "Not Found" << endl;
}
}
int main() {
int nodeNum = 9 ; // n: 노드의 개수
int edgeNum = 10;
// 에지 정보 초기화
for(int i=0; i<nodeNum; i++){
for(int j=0; j<nodeNum; j++){
adj[i][j] = 0;
}
}
// 에지 정보 설정
for (int i = 0; i < edgeNum; i++) {
int u, v;
u = edges[i][0];
v = edges[i][1];
adj[u][v] = 1;
}
// DFS 실행
int start = 0;
int dest = 5;
dfs(start, dest, nodeNum);
return 0;
}#include <iostream>
#include <vector>
#include <stack>
using namespace std;
const int MAXN = 100; // 노드의 최대 개수
vector<int> adj[MAXN+1]; // 인접 리스트
bool visited[MAXN+1]; // 방문 여부 저장 배열
void dfs(int start, int dest) {
stack<int> st; // 스택 생성
st.push(start); // 시작 노드를 스택에 넣음
visited[start] = true;
bool isFind = false;
while (!st.empty() && !isFind) { // 스택이 빌 때까지 반복
int cur = st.top(); // 스택의 맨 위 노드를 가져옴
// 현재 노드와 연결된 모든 노드에 대해
bool isNext = false;
for (int v : adj[cur]) {
if (!visited[v]) { // 아직 방문하지 않은 노드인 경우
st.push(v); // 해당 노드를 스택에 넣음
visited[v] = true; // 해당 노드를 방문
isNext = true;
break;
}
}
if(isNext == false) // 이웃 노드를 모두 방문했으면 backtracking
st.pop();
if (dest == st.top())
isFind = true;
}
if(isFind){
while(!st.empty()){
int cur = st.top();
cout << cur << " ";
st.pop();
}
}
else {
cout << "Not Found" << endl;
}
}
int edges[10][2] = {
{0, 1},
{1, 2},
{2, 3},
{3, 1},
{1, 4},
{4, 5},
{4, 6},
{0, 6},
{6, 7},
{8, 7}
};
int main() {
int nodeNum = 9; // 노드의 개수
int edgeNum = 10; // 간선의 개수
// 간선 정보 입력받기
for (int i = 0; i < edgeNum; i++) {
int u = edges[i][0];
int v = edges[i][1];
adj[u].push_back(v);
}
// DFS 실행
int start = 0;
int dest = 5;
dfs(start, dest);
return 0;
}#include <iostream>
#include <vector>
using namespace std;
const int MAXN = 100; // 노드의 최대 개수
int graph[MAXN+1][MAXN+1]; // 그래프 정보 저장 배열
bool visited[MAXN+1]; // 방문 여부 저장 배열
void dfs(int u, int n) {
visited[u] = true; // 현재 노드 방문 처리
cout << u << " "; // 현재 노드 출력
// 현재 노드와 연결된 모든 노드에 대해
for (int v = 1; v <= n; v++) {
if (graph[u][v] && !visited[v]) { // 아직 방문하지 않은 노드인 경우
dfs(v, n); // 해당 노드로 이동하여 재귀호출
}
}
}#include <iostream>
#include <stack>
#include <vector>
using namespace std;
const int MAX = 100;
int graph[MAX][MAX];
bool visited[MAX][MAX];
int dy[] = {0, 0, 1, -1}; // 우, 좌, 하, 상
int dx[] = {1, -1, 0, 0};
void dfs(int sx, int sy, int tx, int ty) {
// 스택에 현재 정점 push
stack<pair<int, int>> s;
s.push({sy, sx});
visited[sy][sx] = true;
bool isFind = false;
while (!s.empty() && !isFind) {
// 스택의 top에 있는 정점 get
int cy = s.top().first;
int cx = s.top().second;
// (cx, cy)에 인접한 4방향 정점 중 방문하지 않은 정점을 스택에 push
bool isNext = false;
for (int i = 0; i < 4; i++) {
int nx = cx + dx[i];
int ny = cy + dy[i];
if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue; // 배열 범위 체크
if (graph[ny][nx] == 0 || visited[ny][nx]) continue; // 벽이거나 이미 방문한 정점인 경우
s.push({ny, nx});
visited[ny][nx] = true;
isNext = true;
break;
}
if(isNext == false) // 이웃 노드를 모두 방문했으면 backtracking
s.pop();
if (ty == s.top().first && tx == s.top().second)
isFind = true;
}
if(isFind){
while(!s.empty()){
cout << "( " << s.top().first << " , " << s.top().second << " )" << endl;
}
}
}너비우선탐색(Breadth First Search, BFS)
- 폭을 우선적으로 탐색
- DFS는 최적 경로 탐색을 보장하지 않음
- BFS는 목표 노드를 찾는 경로가 가능한 가장 적은 에지를 포함하도록 보장
- FIFO 큐 사용
#include <iostream>
#include <queue>
using namespace std;
const int MAXN = 100; // 노드의 최대 개수
int adj[MAXN][MAXN]; // 인접 행렬
bool visited[MAXN]; // 방문 여부 저장 배열
int parent[MAXN];
int edges[10][2] = {
{0, 1},
{1, 2},
{2, 3},
{3, 1},
{1, 4},
{4, 5},
{4, 6},
{0, 6},
{6, 7},
{8, 7}
};
void bfs(int start, int dest, int n) {
queue<int> q; // 큐 생성
q.push(start); // 시작 노드를 큐에 넣음
visited[start] = true; // 시작 노드 방문 처리
bool isFind = false;
while (!q.empty() && !isFind) { // 큐가 비거나 목적지를 찾지 못하는 경우
int cur = q.front(); // 큐의 맨 앞 노드를 가져옴
q.pop(); // 해당 노드를 큐에서 제거
// 현재 노드와 연결된 모든 노드에 대해
for (int i = 0; i < n; i++) {
if (adj[cur][i] && !visited[i]) { // 인접한 노드 중에서 아직 방문하지 않은 노드인 경우
q.push(i); // 해당 노드를 큐에 넣음
visited[i] = true; // 해당 노드 방문 처리
parent[i] = cur; // 해당 노드의 parent를 cur 노드로 설정
if (i == dest){
isFind = true;
break;
}
}
}
}
if(isFind){
int cur = dest;
cout << cur << " ";
while(true){
cur = parent[cur];
cout << cur << " ";
if(cur == start)
break;
}
}
}
int main() {
int nodeNum = 9 ; // 노드의 개수
int edgeNum = 10; // 긴산의 개수
// 에지 정보 초기화
for(int i=0; i<nodeNum; i++){
for(int j=0; j<nodeNum; j++){
adj[i][j] = 0;
}
}
// 에지 정보 설정
for (int i = 0; i < edgeNum; i++) {
int u, v;
u = edges[i][0];
v = edges[i][1];
adj[u][v] = 1;
}
// DFS 실행
int start = 0;
int dest = 5;
bfs(start, dest, nodeNum);
return 0;
}#include <iostream>
#include <queue>
using namespace std;
const int MAXN = 100; // 노드의 최대 개수
int adj[MAXN][MAXN]; // 인접 행렬
bool visited[MAXN]; // 방문 여부 저장 배열
int parent[MAXN];
int edges[10][2] = {
{0, 1},
{1, 2},
{2, 3},
{3, 1},
{1, 4},
{4, 5},
{4, 6},
{0, 6},
{6, 7},
{8, 7}
};
void bfs(int start, int dest, int n) {
queue<int> q; // 큐 생성
q.push(start); // 시작 노드를 큐에 넣음
visited[start] = true; // 시작 노드 방문 처리
bool isFind = false;
while (!q.empty() && !isFind) { // 큐가 비거나 목적지를 찾지 못하는 경우
int cur = q.front(); // 큐의 맨 앞 노드를 가져옴
q.pop(); // 해당 노드를 큐에서 제거
// 현재 노드와 연결된 모든 노드에 대해
for (int i = 0; i < n; i++) {
if (adj[cur][i] && !visited[i]) { // 인접한 노드 중에서 아직 방문하지 않은 노드인 경우
q.push(i); // 해당 노드를 큐에 넣음
visited[i] = true; // 해당 노드 방문 처리
parent[i] = cur; // 해당 노드의 parent를 cur 노드로 설정
if (i == dest){
isFind = true;
break;
}
}
}
}
if(isFind){
int cur = dest;
cout << cur << " ";
while(true){
cur = parent[cur];
cout << cur << " ";
if(cur == start)
break;
}
}
}
int main() {
int nodeNum = 9 ; // 노드의 개수
int edgeNum = 10; // 긴산의 개수
// 에지 정보 초기화
for(int i=0; i<nodeNum; i++){
for(int j=0; j<nodeNum; j++){
adj[i][j] = 0;
}
}
// 에지 정보 설정
for (int i = 0; i < edgeNum; i++) {
int u, v;
u = edges[i][0];
v = edges[i][1];
adj[u][v] = 1;
}
// DFS 실행
int start = 0;
int dest = 5;
bfs(start, dest, nodeNum);
return 0;
}최소신장트리(Minimum Spanning Tree)
트리 : 사이클이 없는 연결 그래프
신장트리 : 주어진 그래프에서 모든 정점들과 간선으로 구성된 트리 (그래프에서 사이클을 제거한, 절단된 그래프)
최소신장트리 : 신장트리들 중 간선의 합이 최소인 트리 (엣지의 가중치를 전부 재봤더니 가장 작더라)
그래프에서 스패닝 트리는 여러개 나올 수 있다.
그래프 알고리즘의 중요한 개념. 과거에는 유용하게 쓰였으나, 현재는 사용되지 않는 경향.
통신에서는 유용하게 사용한다. 게임에서는 거의 사용하지 않는 경향.
AStar 알고리즘보다 효율이 좋은 경우가 사실상 나오지 않음.
1. 정렬함
2. 쭉 돌면서 선 연결함
3. 선 연결하다가 잉? 이거 사이클인디? 하면 선 삭제함
4. 반복
5. 예시의 경우 9-11-13 라인은 13을 그리지 않음, 만약 13이 10이여서 9-11-10일 경우 11을 그리지 않음
Shortest Path
조건
- 간선 가중치가 있는 유향 그래프
- 무향 그래프 : 양방향 유향 그래프로 가정
두 정점 사이의 최단 경로
- 두 정점 사이의 경로들 중 간선의 가중치 합이 최소인 경로
단일 시작점 최단 경로
- 단일 시작점으롭터 각 정점에 이르는 최단 경로
- Dijkstra's Algorithm
목표지향 최단 경로
- A* Algorithm
모든 쌍 최단 경로
- 모든 정점 쌍 사이의 최단 경로를 모두 구한다
- 플로이드-워샬 알고리즘
Shortest Path - Edge Relax (엣지 완화 알고리즘)
알고리즘이 진행되는 동안 시작 노드에서 목적 노드까지 Best Path Found So Far (BFSP)/에 대한 정보 수집 및 갱신
사이클이 생기면 안 되기 때문에 가중치를 비교 한 다음 짧은것을 택한다.
if(TotalCostToThisNode[t] > TotalCostToThisNode[n] + EdgeCost(n-to-t))
{
TotalCostToThisNode[t] = TotalCostToThisNode[n] + EdgeCost(n-to-t));
Parent(t) = n;
}Shortest Path - Dijkstra's algorithm
- 비용기반 방향 그래프 G = (V, E)에서 시작 노드부터 다른 노드까지의 최단 경로를 구할 수 있다
- SPT(Shortest Path Tree) 관리 : 시작 노드 s로부터의 최종 최단경로 가중치가 이미 결정된 정점들을 관리
- 우선순위 큐(Priority Queue)를 이용
: 최단 경로 추정 가중치가 가장 작은 정점을 선택
: u를 S에 추가
: u와 연결된 모든 간선을 완화
영상 시청 - Dijkstra's Algorithm (UNITY3D)
https://youtu.be/dhvf9KCAsVg?si=zEjZlXJl6MPVGmHT