A* Algorithm -2

https://youtu.be/icZj67PTFhc?si=qGwdtC5PYNqeaHSr

 

이분의 영상 자료와 C++ 콘솔로 그래픽 엔진을 제공해줘서 이분의 코드를 분석해볼 예정이다.

(이 분이 제작하신 콘솔 게임 엔진에 대한 코드 리뷰도 따로 진행할 예정)

 

코드 분석을 위한 간단한 양식을 생각해봤다.

 

코드의 목적

코드의 구조 파악

핵심 로직 분석

함수, 클래스 계층 구조 파악

성능구조 및 리팩토링

부족한 문서화 보충

 

이런식으로 진행할 예정이다.

 

 

코드의 목적

-> A* 알고리즘을 가시적으로 보이게 하고, 그 원리를 이해할 수 있도록 구현.

 

코드의 구조 파악

클래스 PathFinding -> 콘솔 게임 엔진 헤더 상속받음

 

virtual로 상속받은 UserCreate 와 UserUpdate 안에서 배경 및 UI, 그래픽 구현

 

Solve_AStar 라는 함수가 메인 로직 함수이며, A* 연산 및 알고리즘 구현

 

그래서 main 에는

int main()
{
	PathFinding game;
	game.ConstructConsole(160, 160, 6, 6);
	game.Start();
}

 

이게 전부임.

콘솔 게임엔진의 양식에 맞게 구현이 되는편.

 

 

일단 PathFinding 클래스 멤버 변수 확인해보자

#include <iostream>
#include <vector>
#include "olcConsoleGameEngine.h"

using namespace std;

class PathFinding : public olcConsoleGameEngine
{
public:
	PathFinding()
	{
		m_sAppName = L"Path Finding";
	}
private:
	// make node 
	struct Node
	{
		bool bObstacle = false;
		bool bVisited = false;
		float fGlobalGoal;
		float fLocalGoal;
		int _x;
		int _y;
		vector<Node*> vecNeighbours;
		Node* parent;
	};

	Node* nodeStart = nullptr;
	Node* nodeEnd = nullptr;

	// make grid
	Node* nodes = nullptr;
	int nMapWidth = 10;
	int nMapHeight = 10;

console 그래픽 엔진의 헤더를 상속받고, class PathFinding을 만든다.

 

 

먼저 콘솔상에서 그리드를 만들어서 시각적으로 보여야 한다. 

그럴려면 그리드를 이루는 노드를 먼저 생성해야 하고,

노드가 가지고 있는 정보들을 표시해줘야 한다.

그래서 노드의 구조체는

 

노드의 좌표 x,y

그리고 노드가 장애물인지 판단하는 bObstacle

노드가 방문했던 곳인지 판단하는 bVisited

A* 에서 중요한, 시작 노드부터 현재 노드까지의 거리 = fLocalGoal

현재 노드에서부터 도착 노드까지의 거리 = fGlobalGoal

vector<Node*> vecNeighbours 는 현재 노드 주변에 있는 노드들을 의미한다.

 

노드는 시작점과 도착 노드가 있기에 nodeStart와 nodeEnd 가 있다. 

그리고 이 노드들로 그리드 (맵)을 만들어야 해서 nodes를 만들고 맵의 크기를 정하는 높이, 넓이를 구한다.

 

정리하자면, 지금까지는 게임엔진에 필요한 정보들과, 그리드를 구성하는 노드에 대해서 정의했다.

노드는 위치, 장애물 여부, 지나온곳 여부, 현재까지의 거리 , 목적지까지의 거리, 현재 노드에 대한 주변 노드들 정도의 데이터를 담을 수 있는 상태이다.

 

protected:
	virtual bool OnUserCreate()
	{
	nodes = new Node[nMapWidth * nMapHeight];

	for (int x = 0; x < nMapWidth; x++)
	{
		for (int y = 0; y < nMapHeight; y++)
		{
			// index 공식
			//세로 * 맵 길이 + 가로 -> 세로는 픽셀의 세로 줄이고, 가로는 1 픽셀이라고 생각하면 됨
			int index = y * nMapWidth + x;
			nodes[index]._x = x;
			nodes[index]._y = y;
			nodes[index].bObstacle = false;
			nodes[index].parent = nullptr;
			nodes[index].bVisited = false;
		}
	}
	// Create connections 
	for (int x = 0; x < nMapWidth; x++)
	{
		for (int y = 0; y < nMapHeight; y++)
		{
			if (y > 0)
			{
				nodes[y * nMapWidth + x].vecNeighbours.push_back(&nodes[(y - 1) * nMapWidth + (x + 0)]);
			}
			if (y < nMapWidth - 1)
			{
				nodes[y * nMapWidth + x].vecNeighbours.push_back(&nodes[(y + 1) * nMapWidth + (x + 0)]);
			}
			if (x > 0)
			{
				nodes[y * nMapWidth + x].vecNeighbours.push_back(&nodes[(y + 0) * nMapWidth + (x - 1)]);
			}
			if (x < nMapWidth - 1)
			{
				nodes[y * nMapWidth + x].vecNeighbours.push_back(&nodes[(y + 0) * nMapWidth + (x + 1)]);
			}
	}
	nodeStart = &nodes[(nMapHeight / 2) * nMapWidth + 1];
	nodeEnd = &nodes[(nMapHeight / 2) * nMapWidth + nMapWidth - 2];


	return true;
	}

 

OnUserCreate() 는 순수 가상함수이고, 엔진쪽을 살펴보면

public:
	// User MUST OVERRIDE THESE!!
	virtual bool OnUserCreate()	= 0;
		}
	virtual bool OnUserUpdate(float fElapsedTime) = 0;	

	// Optional for clean up 
	virtual bool OnUserDestroy(){ return true; }

이렇게 되어있다. 자세한건 엔진 분석쪽에서 더 할꺼라 여기까지만 들어와봤다.

 

그래서 OnUserCreate() 을 재정의해보면,

생성자 느낌이라, 그리드 생성을 세팅해주면 될거 같다.

 

노드를 새로 할당하는데, 그 크기를 맵의 높이와 넓이를 곱해서 생성해준다.

	nodes = new Node[nMapWidth * nMapHeight];

 

 

이 모든 노드를 초기화 해줘야 하는데,  반복문을 통해서 초기화 해줄 예정이다.

for (int x = 0; x < nMapWidth; x++)
{
	for (int y = 0; y < nMapHeight; y++)
	{
		// index 공식
		//세로 * 맵 길이 + 가로 -> 세로는 픽셀의 세로 줄이고, 가로는 1 픽셀이라고 생각하면 됨
		int index = y * nMapWidth + x;
		nodes[index]._x = x;
		nodes[index]._y = y;
		nodes[index].bObstacle = false;
		nodes[index].parent = nullptr;
		nodes[index].bVisited = false;
	}
}

 

여기서 가장 헷갈렸던게 index 부분인데, 이부분에 대한 이해는 예전에 그래픽스 공부할때 적어놓은게 있었다.

height 가 현재 y라고 하고, x가 width, nMapWidth가 10이라고 가정하면

인덱스 (0,10)을 현재 수식으로 표현하고자 한다면  y * nMapWidth+ x 인데 . ( 0 * 10 + 10)일 것이다. 

인덱스 (10,10) 이라면 ( 10 * 10 + 10)  일것이다. 

 

이런식으로 전체 화면의 노드를 해당 위치에 맞게 초기화 하고, 장애물 및 방문하는 bool 형태의 데이터들은 false로 저장해둔다.

 

이렇게 되면 100개의 노드를 가진 그리드가 생성된다.

 

다음은 노드끼리 길을 이어지게 해야한다.

// Create connections 
// 각각의 vecNeigbor에 현재 노드와 연결되어 있는 노드들을 추가
for (int x = 0; x < nMapWidth; x++)
{
	for (int y = 0; y < nMapHeight; y++)
	{
		if (y > 0)
		{
			// 이웃 노드에 맨 윗줄은 제외 하고 나머지
			nodes[y * nMapWidth + x].vecNeighbours.push_back(&nodes[(y - 1) * nMapWidth + (x + 0)]);
		}
		if (y < nMapHeight - 1)
		{
			// 이웃 노드에 맨 아랫줄은 제외하고 나머지
			nodes[y * nMapWidth + x].vecNeighbours.push_back(&nodes[(y + 1) * nMapWidth + (x + 0)]);
		}
		if (x > 0)
		{
			// 이웃 노드에 맨 왼쪽줄은 제외하고 나머지
			nodes[y * nMapWidth + x].vecNeighbours.push_back(&nodes[(y + 0) * nMapWidth + (x - 1)]);
		}
		if (x < nMapWidth - 1)
		{
			// 이웃 노드에 맨 오른쪽줄은 제외하고 나머지
			nodes[y * nMapWidth + x].vecNeighbours.push_back(&nodes[(y + 0) * nMapWidth + (x + 1)]);
		}
    ...

 

다시 한번 모든 노드들을 훑으면서 각 노드가 가지고 있는 vecNeighbours에 다른 노드들을 추가해야 하는데, 문제는 10 * 10 범위를 벗어나는 범위에서는 길이 이어지면 안되니까 0~ nMapWidth 0 ~nMapHeight 범위까지만 길을 잇도록 하는 코드이다. 

 

그 이후

		nodeStart = &nodes[(nMapHeight / 2) * nMapWidth + 1];
		nodeEnd = &nodes[(nMapHeight / 2) * nMapWidth + nMapWidth - 2];

		return true;

 

노드의 시작과 끝을 임의로 정해주면 초기 생성자는 끝이 나게 된다.

초기 세팅이기에 아직 아무런 화면은 안보이지만 다음 포스트에서 화면에 보이도록 세팅할 예정이다.