Astar.cpp

#include "stdafx.h"
#include "Astar.h"

void Astar::init(vector<tile> vTile, bool checkwall)
{
	//노드 초기화
	_startNode = NULL;
	_endNode = NULL;
	_curNode = NULL;
	_vTiles = vTile;
	idleCount = 0;
	//전체노드 초기화
	for (int y = 0; y < MAPTILEY; y++)
	{
		for (int x = 0; x < MAPTILEX; x++)
		{
			//새로운 노드와 렉트위치 설정
			SAFE_DELETE(_totalNode[x][y]);
		}
	}
	for (int y = 0; y < MAPTILEY; y++)
	{
		for (int x = 0; x < MAPTILEX; x++)
		{
			//새로운 노드와 렉트위치 설정
			_totalNode[x][y] = new node(x, y);
			_totalNode[x][y]->rc = _vTiles[y*MAPTILEY + x].rc;
			if (checkwall) {
				if (!_vTiles[y*MAPTILEY + x].canPass) {
					_totalNode[x][y]->nodeState = NODE_WALL;
				}
			}
		}
	}
	
	//리스타트용
	_openList.clear();
	_closeList.clear();
	_finalList.clear();
}

vector<int> Astar::pathFinding(vector<tile> vTile, int startidx, int endidx, bool checkwall, bool checkdiagonal)
{

	this->init(vTile, checkwall);
	earth _map;
	_startNode = _totalNode[_map.GetTileY(startidx)][_map.GetTileX(startidx)];
	_endNode = _totalNode[_map.GetTileY(endidx)][_map.GetTileX(endidx)];

	//길찾기를 해보자
	//검색을 하려면 무조건 오픈리스트에 담는다
	//F와 H값 가장 작은 놈을 찾아서 그놈을 현재노드로 변경한다
	//오픈리스트에서 현재노드는 삭제하고
	//현재노드는 클로즈리스트에 담아둔다
	//길을 다 찾았다면 클로즈리스트 리버스값을 파이널 리스트로 옮긴다

	//1. 시작노드가 있어야 출발이 가능하니
	//시작노드를 오픈리스트에 추가를 해줘야 한다
	_openList.push_back(_startNode);

	//2. 오픈리스트안에 담겨 있는 벡터를 검사해서
	//종료노드에 도착할때까지 무한 루프
	while (_openList.size() > 0)
	{
		_curNode = _openList[0];
		node* _prevNode = _curNode;

		//오픈리스트중 F가 가장 작거나 F가 같다면
		//H가 작은 걸 현재노드로 하고
		//현재노드를 오픈리스트에서 클로즈 리스트로 옮기기
		//비교를 하려고 하면 최소 시작노드에서 주변을 탐색한 이후
		//길찾기가 시작된다

		for (int i = 1; i < _openList.size(); i++)
		{
			if (_openList[i]->F <= _curNode->F && _openList[i]->H < _curNode->H)
			{
				_curNode = _openList[i];
			}
		}

		//클로즈 리스트에 넣어둔다
		for (int i = 0; i < _openList.size(); i++)
		{
			if (_curNode == _openList[i])
			{
				this->delOpenList(i);
				_closeList.push_back(_curNode);
			}
		}
		
		//현재노드가 이전노드와 같냐? (목적지까지 경로가 없다)
		if (_curNode == _prevNode) {
			idleCount++;
			if (idleCount > 10) {
				return _finalList;
			}
		}
		//현재노드가 마지막 노드와 같냐? (길찾았다)
		if (_curNode == _endNode)
		{
			node* endNode = _endNode;
			vector<node*> tempNode;
			//마지막 노드로부터 시작노드까지 부모노드를 벡터에 담는다
			while (endNode != _startNode)
			{
				tempNode.push_back(endNode);
				endNode = endNode->parentNode;
			}

			for (int i = tempNode.size() - 1; i > 0; i--)
			{
				int tileIndex = tempNode[i]->idy*MAPTILEX + tempNode[i]->idx;
				_finalList.push_back(tileIndex);
			}

			//종료하고 빠져 나온다
			return _finalList;
		}

		//상하좌우 (순서는 상관없음 - 어짜피 주변 4개의 노드를 모두 오픈리스트에 담아서 검사할 예정임)
		addOpenList(_curNode->idx, _curNode->idy - 1);	//상
		addOpenList(_curNode->idx, _curNode->idy + 1);	//하
		addOpenList(_curNode->idx - 1, _curNode->idy);	//좌
		addOpenList(_curNode->idx + 1, _curNode->idy);	//우

		if (checkdiagonal) {
			//우상, 좌상, 우하, 좌하
			addOpenList(_curNode->idx + 1, _curNode->idy - 1);	//우상
			addOpenList(_curNode->idx - 1, _curNode->idy - 1);	//좌상
			addOpenList(_curNode->idx + 1, _curNode->idy + 1);	//우하
			addOpenList(_curNode->idx - 1, _curNode->idy + 1);	//좌하
		}
	}
}

void Astar::addOpenList(int idx, int idy)
{
	//예외처리 인덱스 범위안에서 추가할 수 있어야 한다
	if (idx < 0 || idx >= MAX_X || idy < 0 || idy >= MAX_Y) return;

	//벽은 오픈리스트에 담을 수 없다
	if (_totalNode[idx][idy]->nodeState == NODE_WALL) return;

	//클로즈리스트(지나온길)에 있다면 오픈리스트에 담으면 안된다
	for (int i = 0; i < _closeList.size(); i++)
	{
		if (_totalNode[idx][idy] == _closeList[i]) return;
	}

	//여기까지 왔으면 문제가 없으니 이제 오픈리스트에 추가를 하자
	//현재노드의 4방향 노드를 이웃노드라고 하고 직선10, 대각은 14비용을 추가한다
	node* neighborNode = _totalNode[idx][idy];
	int moveCost = _curNode->G + ((_curNode->idx - idx == 0 || _curNode->idy - idy == 0) ? 10 : 14);

	//오픈리스트안에 이웃노드가 있으면 안된다
	for (int i = 0; i < _openList.size(); i++)
	{
		if (_openList[i] == neighborNode) return;
	}

	//마지막으로 오픈리스트에도 없는경우
	//G, H, ParentNode 설정후 오픈리스트에 추가
	//F = G + H
	//G = 시작에서 현재
	//H = 현재에서 종료
	neighborNode->G = moveCost;
	neighborNode->H = (abs(neighborNode->idx - _endNode->idx) + abs(neighborNode->idy - _endNode->idy)) * 10;
	neighborNode->F = neighborNode->G + neighborNode->H;
	neighborNode->parentNode = _curNode;
	_openList.push_back(neighborNode);
}

void Astar::delOpenList(int index)
{
	_openList.erase(_openList.begin() + index);
}