🔓알고리즘/휴리스틱

A* 길찾기 알고리즘 (쉽고 친절한 설명)

Mawile 2021. 11. 21.
728x90

🔥 소개

안녕하세요~!

이번에는 길찾기알고리즘하면 제일 먼저 떠올리는 A* 알고리즘에 관하여

이론과 실제 프로그래밍 코드로 실습을 진행하겠습니다.

 

사실 아시는분은 아시겠지만, 예전에 A* 알고리즘에 관하여 포스팅을 올려놨었는데요..

일단 그 글은 현재 지웠습니다.

설명이 아예없기때문에.. 지금 봐보니까 진짜 불친절하더라구요...ㅠㅠ

이번 포스팅에서는 매우 자세하고 친절하게 알려드리고 있습니다!

 

Image from GeeksforGeeks

 

🔥 참고

기본적인 알고리즘의 원리는 GeeksforGeeks 를 참고했습니다.

 

 

🔥 A* 알고리즘 필수 단어

A* 알고리즘: 출발 꼭짓점에서부터 목표 꼭짓점까지 가는 최단 경로를 찾아내는(다시 말해 주어진 목표 꼭짓점까지 가는 최단 경로임을 판단할 수 있는 테스트를 통과하는) 휴리스틱기반의 그래프 탐색 알고리즘.

열린목록: 아직 방문하지 않은 노드의 집합.

닫힌목록: 이미 방문했거나 갈수없는 노드의 집합.

부모노드: 전에 방문했던 노드.

노드: 그래프상에서의 현재의 위치또는 정점.

 

 

🔥 A* 알고리즘의 원리

 A* 알고리즘의 작동방식은 휴리스틱기반의 계산방식에 있습니다.

 

탐색하는 방법
순서 행위
1 그래프상에서의 모든 정점의 부모노드를 -1로 초기화하고, 비용은 INF(무한대)값으로 설정한다.
2 시작노드의 비용을 0으로 초기화하고, 시작노드의 부모노드는 시작노드를 가리킨다.
3 현재노드를 기준으로 모든방향의 노드에 대한 비용을 계산한다.
4 비용이 계산된 노드들중 최소비용을 가지는 노드가 다음노드가 된다.
5 다음노드의 부모노드는 현재노드를 가리킨다.
6 3~5을 반복한다.
7 만약 다음노드가 도착노드라면, 탐색을 중지하고 최적의 경로를 계산한다.

 

최적의 경로를 계산하는 방법
순서 행위
1 도착노드를 스택에 푸쉬(push)한다. (현재 가리키고있는 노드는 부모노드이다.)
2 현재 가리키고있는 노드의 부모노드를 스택에 푸쉬(push)한다.
3 2를 반복한다.
4 만약 현재 가리키고있는 노드와 부모노드가 같다면(시작노드라면) 3을 중지한다.
5 그러면 이 스택은 최적의 경로에 대한 정보를 담고 있게된다.

 

 

🔥 휴리스틱 기법

 우선 탐색하는방법에서 소개했던 "비용을 계산한다." 이 부분에 대한 계산방법을 담고있습니다.

비용을 계산하는 방법은

비용(f) = 다음노드에서 도착노드까지와의 거리(h) + 다음노드 방향에 대한 비용(g)

입니다.

 

더보기

(모바일의 경우 수학공식이 이상하게 표기되니, 되도록이면 데스크탑환경에서 읽어주시기 바랍니다.)

다음노드에서 도착노드까지와의 거리

우선 다음노드의 절대좌표\( (x_{a}, y_{a}) \) 라고 가정하고,

도착노드의 절대좌표\( (x_{b}, y_{b}) \) 라고 가정하겠습니다.

 

이랬을때, "다음노드에서 도착노드까지와의 거리"는 다음과 같습니다.

cost = \( \sqrt{(x_{a} - x_{b})^{2} + (y_{a} - y_{b})^{2}} \)

 

다음노드 방향에 대한 비용

우선 직선방향은 1.000 이 됩니다.

그 이유를 알기위해서 다음과 같은 직각삼각형이 있다고 가정해봅시다.

 

우리가 앞으로 다뤄야할 가상의 노드(정점)들은 모두 위의 직각삼각형과 같이 일정한 거리를 두고있습니다.

말그대로 현재노드를 A라고 다음노드를 B라고 했을때 이 A와 B사이의 상대적 거리 쉽게말해서

현재노드와 다음노드사이의 상대적 거리 를 간단하게 1.000 로 두겠다는 의미입니다.

 

대각선방향에서 달라지는 점은 다음노드가 C가 된다는것 이외에는 달라지지않습니다.

똑같이 다음노드가 C이기 때문에 그 이동비용은 1.414(\( \sqrt{2} \)) 가 됩니다.

 

 

🔮 A* 길찾기 알고리즘을 직접 설계해보자!

A* 길찾기 알고리즘을 만들기 전에 저는 개발환경을 구성하고자합니다.

저의 개발환경입니다.

 

🕹️ 개발환경

혹시 개발환경이 맞지않아 작동이 안되는 상황도 있기때문에 이 점을 감안해주시기 바랍니다.

통합개발환경 Visual Studio 2022 Current (v143)
컴파일러 MSVC
프로그래밍 언어 C++20
운영체제 Windows 11 home
작성일자 2021-11-21
파일 기본 인코딩 UTF-8
윈도우 패키지 x64

 

🕹️ 프레임워크

이번에 구현할 A* 길찾기 알고리즘의 프레임워크 설계도입니다.

이런식으로 프레임워크를 설계한이유는 쉽게 접근하는데 용이하고,

소스코드가 간결해지며 코드의 가독성이 증가하게됩니다.

 

FileClass는 맵정보가 담긴 파일을 관리합니다.

HeuristicClass는 맵정보를 기반으로 최적의 경로탐색을 수행합니다.

AstarClass는 FileClass와 HeuristicClass를 적절히 사용하여 A* 길찾기 알고리즘을 수행합니다.

 

🕹️ 프로젝트 시작하기

우선 저는 "빈 프로젝트"를 선택하고 다음(N)을 클릭하겠습니다.

 

그다음, 적절한 프로젝트의 이름을 설정하고 만들기(C)를 클릭하겠습니다.

 

그다음, 솔루션을 마우스우클릭한후 속성(R)을 클릭하겠습니다.

 

속성 페이지창이 뜨면 다음과 같이 설정해준후, 적용(A)을 누르고, 확인을 누릅니다.

 

🕹️ 솔루션 정렬

저는 다음과 같은방식으로 프로젝트의 솔루션을 정렬했습니다.

 

 

🔮 A* 길찾기 알고리즘를 직접 만들어보자!

TypeDecl.h

우선 본격적인 A* 길찾기 알고리즘을 수행하기전에 몇가지의 구조체및 선언을 만들어야합니다.

 TypeDecl.h 헤더파일은 앞으로 사용할 모든 헤더파일에 포함될것입니다.

/* < TypeDecl.h > */

#pragma once

#include <vector>
#include <string>

#include <conio.h>

constexpr float INF = (987654321.0000f);
#define BLOCK int _ = _getch()

using Vec2Map = std::vector<std::vector<std::string>>;

/* Vec2MapInfo: 맵정보, 맵의 최대크기, 맵의 출발지점, 맵의 도착지점 */
struct Vec2MapInfo {
	Vec2Map mapInfo;

	int map_col;
	int map_row;

	int beg_x;
	int beg_y;

	int dest_x;
	int dest_y;
};

/* CostCoord: 한 정점의 좌표와 비용 */
struct CostCoord {
	float cost;
	int x, y;
};

/* Coord: 한 정점의 좌표 */
struct Coord {
	int x, y;
};

/* CellDetails: 비용과 부모노드 */
struct CellDetails {
	float f, g, h;
	int parent_x, parent_y;
};

/* PointDecl: 맵에 표기 되어있는 문자의 역할 */
struct PointDecl {
	std::string BeginPoint, DestinationPoint, Void, Wall, TracedPath;
};

 

이제 텍스트파일을 기반으로 맵에 대한 정보를 불러오는 기능을 만들어보도록 하겠습니다.

 

FileClass.h

FileClass 클래스의 선언입니다.

우선 RoadMap함수는 두번째 파라미터로 맵정보를 불러올 맵의 텍스트파일경로를 넣어주면 됩니다.

그리고 외부에서 그 맵정보를 불러오고싶을때,

GetVec2Map함수를 수행하면 해당 맵에 대한 정보를 불러올 수 있습니다.

 

/* < FileClass.h > */

#pragma once

#include "TypeDecl.h"

#include <vector>
#include <string>
#include <fstream>

class FileClass {
public:
	FileClass();
	FileClass(const FileClass&);
	~FileClass();

	bool RoadMap(PointDecl, const char*);
	Vec2MapInfo GetVec2Map();

 

FileClass 클래스는 멤버변수로 Vec2MapInfo라는 구조체를 가집니다.

이 구조체는 외부에서 맵정보를 가져오고싶을때, GetVec2Map함수를 통해 가져올 수 있습니다.

private:
	Vec2MapInfo m_MapInfo;

};

 

FileClass.cpp

이거는 FileClass 클래스의 정의입니다.

우선 맵정보를 가지고있는 멤버변수 m_MapInfo라는 구조체를 초기화합니다.

/* < FileClass.cpp > */

#include "FileClass.h"

FileClass::FileClass() {
	memset(&this->m_MapInfo, 0x00, sizeof(Vec2MapInfo));

	return;
}

FileClass::FileClass(const FileClass&) {
	return;
}

FileClass::~FileClass() {
	return;
}

 

그다음 본격적으로 RoadMap이라는 함수를 정의합니다.

이 함수는 우선 읽기모드(std::ifstream)로 텍스트파일을 열게됩니다.

이제 열었으니, 멤버변수 fail()과 is_open()으로 이 텍스트파일이 정상적으로 존재하는 파일인지 확인합니다.

bool FileClass::RoadMap(PointDecl ptDecl, const char* mapFileName) {
	std::ifstream mapFile(mapFileName);

	if (mapFile.fail()) {
		return false;
	}

	if (!mapFile.is_open()) {
		return false;
	}

 

우선 맵의 가로길이를 mapInfo.map_col라는 변수에 저장하고,

맵의 세로길이를 mapInfo.map_row라는 변수에 저장합니다.

이제 제네릭타입이 std::stringMap이라는 2차원벡터에 세로길이가 mapInfo.map_row,

가로길이가 mapInfo.map_col만큼 빈 데이터공간을 생성합니다.

 

빈공간을 생성하게되면 이제 본격적으로 파일에서 맵정보를 읽어와야합니다.

여기서 중요한점이 있는데,

만약 그 점이 시작지점이거나 도착지점이면 반드시 빈 공간(Void)으로 바꿔주어야 한다는겁니다.

그 이유는 밑에서 HeuristicClass를 다루게되면 아시게될것입니다.

Vec2MapInfo mapInfo;
	mapFile >> mapInfo.map_col >> mapInfo.map_row;

	Vec2Map Map(mapInfo.map_row, std::vector<std::string>(mapInfo.map_col));
	for (int y = 0; y < mapInfo.map_row; ++y) {
		for (int x = 0; x < mapInfo.map_col; ++x) {
			mapFile >> Map[y][x];

			if (Map[y][x] == ptDecl.BeginPoint) {
				mapInfo.beg_x = x;
				mapInfo.beg_y = y;

				Map[y][x] = ptDecl.Void;
			}

			if (Map[y][x] == ptDecl.DestinationPoint) {
				mapInfo.dest_x = x;
				mapInfo.dest_y = y;

				Map[y][x] = ptDecl.Void;
			}
		}
	}

	mapInfo.mapInfo.clear();
	mapInfo.mapInfo = Map;
	this->m_MapInfo = mapInfo;

	return true;
}

Vec2MapInfo FileClass::GetVec2Map() {
	return (this->m_MapInfo);
}

 

HeuristicClass.h

이 HeuristicClass 클래스가 우리가 만들 A* 길찾기 알고리즘의 핵심이 될 부분입니다.

HeuristicClass 클래스는 그래프의 탐색을 하거나,

탐색이 끝난 그래프를 외부에서 가져오기 쉽게 가공하는 역할을 합니다.

 

우선 우리는 열린목록에 대한 자료구조를 set으로 하게될겁니다.

그 이유는

1. set은 중복된 원소를 가지지않는다.

2. 사용자가 직접 정렬방식을 정할 수 있다.

때문입니다.

 

less구조체의 역할은 나중에 열린목록에서

제네릭타입이 CostCoord set을 비용이 적은순으로 정렬할것이기 때문에 추가로 오버로딩했습니다.

/* < HeuristicClass.h > */

#pragma once

#include "TypeDecl.h"

#include <vector>
#include <stack>
#include <set>
#include <queue>
#include <cmath>

class HeuristicClass {
private:
	struct less {
		constexpr bool operator()(const CostCoord& _Left, const CostCoord& _Right) const {
			return _Left.cost < _Right.cost;
		}
	};

public:
	HeuristicClass();
	HeuristicClass(const HeuristicClass&);
	~HeuristicClass();

	bool BeginSearch(PointDecl, Vec2MapInfo);
	std::queue<Coord> GetQueue();

 

이제 아래 4개의 멤버함수는 외부에서 접근할 수 없도록, 내부에서만 사용할것이기때문에 private으로 설정했습니다.

멤버변수 m_TrackedPath는 그래프상에서 최적의 경로를 담고있는 큐입니다.

이 멤버변수는 GetQueue함수로 외부에서 가져갈 수 있습니다.

private:
	bool isUnBlockedNode(PointDecl, Vec2Map, int, int);
	bool isDestinationNode(int, int, int, int);
	bool isInGround(int, int, int, int);
	void TraceMinimumPath(std::vector<std::vector<CellDetails>>, Coord);

private:
	const int m_dx1[4] = { 0, 0, 1, -1 };
	const int m_dy1[4] = { -1, 1, 0, 0 };

	const int m_dx2[4] = { 1, -1, -1, 1 };
	const int m_dy2[4] = { -1, 1, -1, 1 };

	std::queue<Coord> m_TrackedPath;

};

 

HeuristicClass.cpp

먼저 생성자와 소멸자는 아무 역할을 하지않고 기본적인 선언과 정의만 해두었습니다.

BeginSearch함수는 이제 그래프를 탐색하면서 모든 노드들에 대한 최적의 경로를 만들어냅니다.

 

우선 탐색전에 이미 출발지점과 도착지점이 같은지,

출발지점이나 도착지점이 그래프내에 존재하는지,

도착지점이나 출발지점이 벽으로 막혀져있는지 확인해야합니다.

/* < HeuristicClass.cpp > */

#include "HeuristicClass.h"

HeuristicClass::HeuristicClass() {
	return;
}

HeuristicClass::HeuristicClass(const HeuristicClass&) {
	return;
}

HeuristicClass::~HeuristicClass() {
	return;
}

bool HeuristicClass::BeginSearch(PointDecl ptDecl, Vec2MapInfo mapInfo) {
	if (this->isDestinationNode(mapInfo.dest_x, mapInfo.dest_y, mapInfo.beg_x, mapInfo.beg_y)) {
		return true;
	}

	if (!this->isUnBlockedNode(ptDecl, mapInfo.mapInfo, mapInfo.beg_x, mapInfo.beg_y) ||
		!this->isUnBlockedNode(ptDecl, mapInfo.mapInfo, mapInfo.dest_x, mapInfo.dest_y)) {
		return false;
	}

	if (!this->isInGround(mapInfo.map_col, mapInfo.map_row, mapInfo.beg_x, mapInfo.beg_y) ||
		!this->isInGround(mapInfo.map_col, mapInfo.map_row, mapInfo.dest_x, mapInfo.dest_y)) {
		return false;
	}

 

이제 초기화를 해야합니다.

CellDetails는 노드의 비용과 부모노드에 대한 정보를 담고있습니다.

부모노드는 모두 -1로 초기화하고, 비용은 모두 INF(무한대)로 해줍시다.

그다음 출발지점의 비용을 0.0f로하고 출발지점의 부모노드는 출발노드를 가리키게됩니다.

 

이제 닫힌목록과 열린목록을 생성하고, 열린목록에는 출발노드를 집어넣습니다.

	int st_x = mapInfo.beg_x;
	int st_y = mapInfo.beg_y;

	std::vector<std::vector<CellDetails>> cell(mapInfo.map_row, std::vector<CellDetails>(mapInfo.map_col));
	for (int y = 0; y < mapInfo.map_row; ++y) {
		for (int x = 0; x < mapInfo.map_col; ++x) {
			cell[y][x].f = cell[y][x].g = cell[y][x].h = INF;
			cell[y][x].parent_x = cell[y][x].parent_y = -1;
		}
	}

	cell[st_y][st_x].f = cell[st_y][st_x].g = cell[st_y][st_x].h = 0.0f;
	cell[st_y][st_x].parent_x = st_x;
	cell[st_y][st_x].parent_y = st_y;

	std::vector<std::vector<bool>> closedList(mapInfo.map_row, std::vector<bool>(mapInfo.map_col));

	CostCoord bVertex;
	bVertex.cost = 0.0f;
	bVertex.x = st_x;
	bVertex.y = st_y;
	
	std::set<CostCoord, less> openList;
	openList.insert(bVertex);

 

여기는 bfs와 매우 유사합니다.

openList는 항상 제일 적은 비용의 노드를 첫번째주소로 가리키게 됩니다(전에 선언한 less구조체에 의해).

먼저 닫힌목록의 현재노드를 방문처리해주고, 이제 직선방향에 대한 탐색과 대각선방향에 대한 탐색을 시작합니다.

 

직선방향탐색과 대각선방향탐색의 다른점은 g를 업데이트할때말고는 전부 똑같습니다.

 

일단 다음노드가 그래프내부에 있다면 2개의 분기로 나눠집니다.

1. 다음노드가 도착노드인가?

2. 다음노드가 닫힌목록에 존재하지않은 노드인 동시에, 벽으로 막혀져있지않은가?

 

우리는 만약 1번분기로 간다면 다음노드의 부모노드는 현재노드가되고, 그래프의 최적화경로를 탐색하기 시작합니다.

2번분기로 간다면 n, g, f를 각각 업데이트하고, 다음노드의 f가 한번도 업데이트되지않았거나, 새로 업데이트될 f(nf)보다 기존의 f(f)가 크다면 cellDetails를 업데이트하고, 열린목록에 다음노드를 삽입합니다.

	while (!openList.empty()) {
		CostCoord current = *openList.begin();
		openList.erase(openList.begin());

		int cur_x = current.x;
		int cur_y = current.y;

		closedList[cur_y][cur_x] = true;

		float nf, ng, nh;

		for (int i = 0; i < 4; ++i) {
			int new_x = cur_x + this->m_dx1[i];
			int new_y = cur_y + this->m_dy1[i];

			if (this->isInGround(mapInfo.map_col, mapInfo.map_row, new_x, new_y)) {
				if (this->isDestinationNode(mapInfo.dest_x, mapInfo.dest_y, new_x, new_y)) {
					cell[new_y][new_x].parent_x = cur_x;
					cell[new_y][new_x].parent_y = cur_y;

					this->TraceMinimumPath(cell, { mapInfo.dest_x, mapInfo.dest_y });

					return true;
				}
				else if (!closedList[new_y][new_x] &&
					this->isUnBlockedNode(ptDecl, mapInfo.mapInfo, new_x, new_y)) {
					ng = cell[cur_y][cur_x].g + 1.000f;
					nh = ((float)std::sqrt((float)std::pow(new_x - mapInfo.dest_x, 2)
						+ (float)std::pow(new_y - mapInfo.dest_y, 2)));
					nf = ng + nh;

					if (cell[new_y][new_x].f == INF || cell[new_y][new_x].f > nf) {
						cell[new_y][new_x].g = ng;
						cell[new_y][new_x].h = nh;
						cell[new_y][new_x].f = nf;

						cell[new_y][new_x].parent_x = cur_x;
						cell[new_y][new_x].parent_y = cur_y;

						CostCoord bVertex;
						bVertex.cost = nf;
						bVertex.x = new_x;
						bVertex.y = new_y;

						openList.insert(bVertex);
					}
				}
			}
		}

		for (int i = 0; i < 4; ++i) {
			int new_x = cur_x + this->m_dx2[i];
			int new_y = cur_y + this->m_dy2[i];

			if (this->isInGround(mapInfo.map_col, mapInfo.map_row, new_x, new_y)) {
				if (this->isDestinationNode(mapInfo.dest_x, mapInfo.dest_y, new_x, new_y)) {
					cell[new_y][new_x].parent_x = cur_x;
					cell[new_y][new_x].parent_y = cur_y;

					this->TraceMinimumPath(cell, { mapInfo.dest_x, mapInfo.dest_y });

					return true;
				}
				else if (!closedList[new_y][new_x] &&
					this->isUnBlockedNode(ptDecl, mapInfo.mapInfo, new_x, new_y)) {
					ng = cell[cur_y][cur_x].g + 1.414f;
					nh = ((float)std::sqrt((float)std::pow(new_x - mapInfo.dest_x, 2)
						+ (float)std::pow(new_y - mapInfo.dest_y, 2)));
					nf = ng + nh;

					if (cell[new_y][new_x].f == INF || cell[new_y][new_x].f > nf) {
						cell[new_y][new_x].g = ng;
						cell[new_y][new_x].h = nh;
						cell[new_y][new_x].f = nf;

						cell[new_y][new_x].parent_x = cur_x;
						cell[new_y][new_x].parent_y = cur_y;

						CostCoord bVertex;
						bVertex.cost = nf;
						bVertex.x = new_x;
						bVertex.y = new_y;

						openList.insert(bVertex);
					}
				}
			}
		}
	}


	return false;
}

 

이제 그래프에서 탐색된 내용(cell)을 기반으로 최적화된 경로를 만들어 내어야 합니다.

우선 처음 스택에는 도착노드의 좌표를 삽입합니다.

 

그후, 현재노드의 부모노드가 현재노드와 같아질때(출발노드가 이에 해당)까지

스택에 현재노드의 부모노드를 삽입합니다.

 

굳이 큐는 사용하지않아도 되지만 외부에서 가져갈때 좀더 사용하기 쉽도록 큐로 옮겼습니다.

void HeuristicClass::TraceMinimumPath(std::vector<std::vector<CellDetails>> cell, Coord dest) {
	std::stack<Coord> TrackingStack;
	std::queue<Coord> TrackingQueue;
	int cur_x, cur_y;

	cur_x = dest.x;
	cur_y = dest.y;

	TrackingStack.push({ cur_x, cur_y });

	while (!(cell[cur_y][cur_x].parent_x == cur_x &&
		cell[cur_y][cur_x].parent_y == cur_y)) {
		int temp_x = cell[cur_y][cur_x].parent_x;
		int temp_y = cell[cur_y][cur_x].parent_y;

		cur_x = temp_x;
		cur_y = temp_y;

		TrackingStack.push({ cur_x, cur_y });
	}

	while (!TrackingStack.empty()) {
		TrackingQueue.push(TrackingStack.top());
		TrackingStack.pop();
	}

	this->m_TrackedPath = TrackingQueue;

	return;
}

std::queue<Coord> HeuristicClass::GetQueue() {
	return (this->m_TrackedPath);
}

bool HeuristicClass::isUnBlockedNode(PointDecl ptDecl, Vec2Map Map, int cur_x, int cur_y) {
	return (Map[cur_y][cur_x] == ptDecl.Void);
}

bool HeuristicClass::isDestinationNode(int dest_x, int dest_y, int cur_x, int cur_y) {
	return ((dest_x == cur_x) && (dest_y == cur_y));
}

bool HeuristicClass::isInGround(int map_col, int map_row, int cur_x, int cur_y) {
	return (((0 <= cur_x) && (cur_x < map_col)) && ((0 <= cur_y) && (cur_y < map_row)));
}

 

AstarClass.h

AstarClass 클래스는 FileClass 클래스와 HeuristicClass 클래스를 적절히 이용해서 메인함수에서 사용하기 쉽게 브릿지역할을 하게됩니다.

/* < AstarClass.h > */

#pragma once

#include "FileClass.h"
#include "HeuristicClass.h"
#include "TypeDecl.h"

#include <iostream>

class AstarClass {
public:
	AstarClass();
	AstarClass(const AstarClass&);
	~AstarClass();

	bool Initialize(PointDecl, const char*);
	void Shutdown();

	void Run();

 

멤버변수 m_PtDecl은 그래프에서의 문자열에 따라 그에 맞는 역할을 수행하도록 도와주는 구조체입니다.

private:
	FileClass* m_file_class;
	HeuristicClass* m_heuristic_class;

	PointDecl m_PtDecl;

};

 

AstarClass.cpp

생성자가 호출되면 FileClass 클래스와 HeuristicClass 클래스를 가리키는 포인터들을 모두 0으로 초기화합니다.

Initialize함수는 이 포인터들에게 메모리공간을 모두 나눠주고, 각각에 맞는 역할을 수행하도록하는 역할입니다.

Shutdown함수는 이 포인터들의 메모리공간을 다시 반납하고 0으로 초기화하는 역할입니다.

/* < AstarClass.cpp > */

#include "AstarClass.h"

AstarClass::AstarClass() {
	this->m_file_class = 0;
	this->m_heuristic_class = 0;
}

AstarClass::AstarClass(const AstarClass&) {
	return;
}

AstarClass::~AstarClass() {
	return;
}

bool AstarClass::Initialize(PointDecl ptDecl, const char* mapFileName) {
	this->m_PtDecl = ptDecl;

	bool result;

	this->m_file_class = new FileClass;
	if (!this->m_file_class) {
		return false;
	}

	result = this->m_file_class->RoadMap(ptDecl, mapFileName);
	if (!result) {
		return false;
	}

	this->m_heuristic_class = new HeuristicClass;
	if (!this->m_heuristic_class) {
		return false;
	}

	return true;
}

void AstarClass::Shutdown() {
	if (this->m_file_class) {
		delete this->m_file_class;
		this->m_file_class = 0;
	}

	if (this->m_heuristic_class) {
		delete this->m_heuristic_class;
		this->m_heuristic_class = 0;
	}

	return;
}

 

Run함수에서는 먼저 FileClass 클래스의 멤버함수인 GetVec2Map함수를 호출하여 맵정보를 불러옵니다.

그다음 HeuristicClass 클래스에서 해당맵정보를 바탕으로 그래프탐색을 시작합니다.

그래프탐색이 끝나면,

그래프에서 최적의 경로에 대한 정보를 가지고있는 큐를 GetQueue함수를 이용해 얻을 수 있습니다.

void AstarClass::Run() {
	std::queue<Coord> queue;
	bool result;

	Vec2MapInfo mapInfo = this->m_file_class->GetVec2Map();
	if (mapInfo.mapInfo.empty()) {
		return;
	}

	result = this->m_heuristic_class->BeginSearch(this->m_PtDecl, mapInfo);
	
	switch (result) {
	case false:
		std::cout << "올바른 맵의 정보가 아닙니다." << std::endl;
		break;

	case true:
		queue = this->m_heuristic_class->GetQueue();
		break;

	}

 

만약 그래프탐색이 성공적으로 끝난다면(result == true)기존에불러왔던 맵의 그래프에다가 최적의 경로를 순서대로 덮어씌우고, 맵의 그래프를 콘솔창으로 출력합니다.

	if (result) {
		while (!queue.empty()) {
			Coord coord = queue.front();
			queue.pop();
			mapInfo.mapInfo[coord.y][coord.x] = this->m_PtDecl.TracedPath;
		}

		for (int y = 0; y < mapInfo.map_row; ++y) {
			for (int x = 0; x < mapInfo.map_col; ++x) {
				std::cout << mapInfo.mapInfo[y][x] << ' ';
			}
			std::cout << std::endl;
		}
	}

	return;
}

 

main.cpp

메인함수가 포함된 이 소스에서는 그래프의 문자열이 의미하는 바를 정의하고, AstarClass 클래스를 동작시킵니다.

"BLOCK;"은 그냥 빌드에서 실행하면 결과값이 안보이기 때문에 콘솔창을 한번 멈추는 역할을 합니다.

/* < main.cpp > */

#include "AstarClass.h"

int main(int argc, char** argv) {
	AstarClass* astar_class = new AstarClass;

	PointDecl pDecl;
	pDecl.BeginPoint = "@";
	pDecl.DestinationPoint = "$";
	pDecl.TracedPath = "*";
	pDecl.Void = "+";
	pDecl.Wall = "#";

	if (astar_class->Initialize(pDecl, "sample_map.txt")) {
		astar_class->Run();
	}
	
	astar_class->Shutdown();
	delete astar_class;
	astar_class = 0;

	BLOCK;

	return 0;
}

 

 

🧼 실제로 실행을 시켜보자!

우선 실행을 시키기 전에 맵의 그래프정보가 담긴 텍스트파일이 필요합니다.

간단하게 만들어보겠습니다.

 

sample_map.txt
10 5
# @ # + # + # + # #
# + # + + + + + + +
# + # + # # # + # +
# + # + # $ # # # +
# + + + # + + + + +

 

10맵의 가로길이, 5맵의 세로길이를 의미합니다.

밑에는 맵에 대한 정보입니다.

맵에 대한 그래프의 제네릭타입을 std::string으로 했기때문에 한 블럭을 문자열로 하셔도 상관없습니다.

 

이제 실행시켜보겠습니다!

실행화면

다음과 같이 너무 잘 작동합니다~

와우~!!!

꾸웃!

 

 

🧼 마치며...

그대로 복붙만 하는것보다는 이해를 하시면서 공부하는것을 추천드립니다..

이렇게 추천드리는 이유는 "이해한다는것""따라한다는것"은 여러 상황에 대한 유연성과 프로그래밍적인 사고력을 길러준다는 측면에 매우 다릅니다.

 

이해가 안가시는분은 고민하지마시고 댓글로 질문부탁드립니다.

확인하는대로 답변드리겠습니다!

 

그럼 안녕~!!

 


728x90

댓글