게임인공지능 7주차 - Shortest Path, Dijkstra, A* Algorithm

Edge Relax (에지완화)

알고리즘이 진행되는 동안 시작 노드에서 목적 노드까지 Best Path Found So Far (BFSP)에 대한 정보 수집 및 갱신

Dijkstra's Algorithm

비용기반 방향 그래프 G = (V, E)에서 시작 노드에서 다른 모든 노드까지의 최단 경로를 구할 수 있다.
- SPT(Shortest Path Tree) 관리 : 시작 노드 s로부터의 최종 최단경로 가중치가 이미 결정된 정점들을
관리한다.
- 우선순위 큐(Priority Queue)를 이용한다.
 : 최단 경로 추정 가중치가 가장 작은 정점 u ∈ V – S를 선택
 : u 를 S에 추가
 : u 와 연결된 모든 간선을 완화

https://youtu.be/dhvf9KCAsVg?si=de46BllxT84Xa6pP 

실습 진행

#include "Dijkstra.h"


void Dijkstra::extractMin(point& choicePos)
{
	int min = INT_MAX;
	int width = m_gameMap->getWidth();
	int height = m_gameMap->getHeight();

	int curX, curY;
	list<point>::reverse_iterator curPos;

	for (curPos = m_visitNode.rbegin(); curPos != m_visitNode.rend(); curPos++)
	{
		// 현재 노드를 기준으로 8방향을 스캐닝
		for (int ty = -1; ty <= 1; ty++)
		{
			for (int tx = -1; tx <= 1; tx++)
			{
				curX = curPos->x + tx;
				curY = curPos->y + ty;

				if (curX < 0 || curX > width - 1 || curY < 0 || curY > height - 1 || (tx == 0 && ty == 0))
				{
					continue;
				}

				if (m_gameMap->getMapVal(curX, curY) < min && m_gameMap->getVisitInfo(curX, curY) == false)
				{
					min = m_gameMap->getMapVal(curX, curY);
					choicePos = { curX, curY };
				}
			}
		}
	}
}

bool Dijkstra::findPath(int sx, int sy, int dx, int dy)
{
	m_bFound = false;
	int width = m_gameMap->getWidth();
	int height = m_gameMap->getHeight();

	point** parent;
	parent = new point * [height];

	for (int i = 0; i < height; i++)
	{
		parent[i] = new point[width];
	}

	point choicePos;
	m_gameMap->setMapVal(sx, sy, 0); // 시작 위치의 비용을 0으로 설정
	choicePos = { sx, sy };
	parent[sy][sx] = choicePos;

	for (int i = 0; i < width * height; i++)
	{
		m_gameMap->setVisitInfo(choicePos.x, choicePos.y, true);
		m_visitNode.push_back(choicePos);

		// 목표 노드를 만나면 종료
		if (choicePos.x == dx && choicePos.y == dy)
		{
			m_bFound = true;
			break;
		}

		// 에지완화 알고리즘 적용
		for (int ty = -1; ty <= 1; ty++)
		{
			for (int tx = -1; tx <= 1; tx++)
			{
				int nx = choicePos.x + tx;
				int ny = choicePos.y + ty;
				int dist;

				if (nx < 0 || nx > width - 1 || ny < 0 || ny > height - 1)
				{
					continue;
				}

				if (m_gameMap->getVisitInfo(nx, ny) == false)
				{
					dist = (tx == 0 || ty == 0) ? 10 : 14;
					int tcost = m_gameMap->getMapVal(choicePos.x, choicePos.y) + dist;

					// 에지완화 처리
					if (m_gameMap->getMapVal(nx, ny) > tcost)
					{
						m_gameMap->setMapVal(nx, ny, tcost);
						parent[ny][nx] = choicePos;
					}
				}
			}
		}
		extractMin(choicePos);
		draw();
	}

	if (m_bFound)
	{
		point p;
		p = { dx, dy };

		m_path.push(p);

		while (p.x != sx || p.y != sy) 
		{
			p = parent[p.y][p.x];
			m_path.push(p);
		}
		return true;
	}

	return false;
}

void Dijkstra::draw()
{
	m_gameMap->draw();

	if (m_bFound) 
	{
		point p;

		do 
		{
			p = m_path.top();
			cout << "(" << p.x << "," << p.y << ") ==> ";
			m_path.pop();
		} while (!m_path.empty());
		cout << "최단 경로를 찾았습니다..." << endl;

	}
}

Shortest Path - A* Algorithm

배경 화면 상의 두 지점이 존재할 때, 시작점에서 목표점을 연결하는 가장 효율적인 경로를 찾는 목표 지향성 알고리즘.

현재의 위치에서 이동 가능한 노드로 간 후 목표점까지의 비용으로 길을 결정한다.

둘은 큰 줄기가 같다. dijkstra 알고리즘에서 extractMin만 다른 형태.

 

void AStar::extractMin(point& choicePos, int dx, int dy)
{
	int min = INT_MAX;
	int width = m_gameMap->getWidth();
	int height = m_gameMap->getHeight();

	int curX, curY;
	list<point>::reverse_iterator curPos;

	for (curPos = m_visitNode.rbegin(); curPos != m_visitNode.rend(); curPos++)
	{
		// 현재 노드를 기준으로 8방향을 스캐닝
		for (int ty = -1; ty <= 1; ty++)
		{
			for (int tx = -1; tx <= 1; tx++)
			{
				curX = curPos->x + tx;
				curY = curPos->y + ty;

				if (curX < 0 || curX > width - 1 || curY < 0 || curY > height - 1 || (tx == 0 && ty == 0))
				{
					continue;
				}
				
				// 현재 노드에서 목표노드까지의 추정 거리 계산
				int hx = abs(dx - curX) * 10;				
				int hy = abs(dy - curY) * 10;
				int hdist = hx + hy;
				//hdist = sqrt((dx - curX) * (dx = curX) + (dy - curY) * (dy - curY));

				if (m_gameMap->getMapVal(curX, curY) + hdist < min && m_gameMap->getVisitInfo(curX, curY) == false)
				{
					min = m_gameMap->getMapVal(curX, curY) + hdist;
					choicePos = { curX, curY };
				}
			}
		}
	}
}

 

중간평가 과제

FSM과 A* 알고리즘을 적용하여 팩맨게임을 구현한다.

 

다음의 조건을 만족해야 한다.

- 고스트가 팩맨에게 먹히면 리스폰된다.

- 리스폰된 고스트는 In-Box에서 다시 시작한다.

- 고스트가 Hunter 상태일 때 팩맨이 근처에 있으면 팩맨을 쫒아간다

- 팩맨을 쫒아갈 때에는 최단경로찾기 알고리즘을 적용한다. (A* algorithm)

- 고스트가 Hunter 상태일 때 팩맨이 근처에 없는 경우 배회한다.

- 팩맨이 파워 쿠키를 먹으면 고스트는 Hunted 상태로 바뀌고 팩맨으로부터 도망간다.

- Hunted 상태의 고스트는 일정 시간이 지나면 Hunter 상태로 바뀐다.

- 고스트가 Hunted 상태일 때 팩맨에게 먹히면 리스폰 장소로 되돌아간다.

- 고스트의 FSM은 state pattern으로 구현한다.

 

11월 05일 일요일까지

Source code 1set, 보고서 (pdf)를 lms 과제란에 업로드한다.

- no copy

- no delay

- no engine

- 미완성인 경우에도 미완성 내용을 보고서에 포함하여 code와 함께 제출

- 부분 점수 있음