몬스터(NPC) AI 적용 및 길찾기 (2)

xvector<Vector> PathFinder::AStar(Vector& Start, Vector& Goal, xmap<Vector, xvector<Vector>>& Edges)
{
	if (!IsRead)
	{
		cout << "레벨 정보 파일 안읽었음" << endl;
		return {};
	}

	xpriorityQueue<Node, xvector<Node>, greater<Node>> open;
	unordered_set<Vector, VectorHash> closed; //폐쇄 리스트

	//유클리드 거리 계산
	Node startNode = { Start,0,sqrt(pow(Goal.x - Start.x,2) + pow(Goal.y - Start.y,2) + pow(Goal.z - Start.z, 2)), nullptr };
	open.push(startNode);

	cout << "A* 실행" << endl;

	while (!open.empty())
	{
		Node current = open.top();
		open.pop();

		if (current.Position == Goal)
		{
			//경로를 역추적해서 반환
			xvector<Vector> path;
			Node* pathNode = &current;
			
			while (pathNode != nullptr)
			{
				path.push_back(pathNode->Position);
				pathNode = pathNode->Parent;
			}

			reverse(path.begin(), path.end());
			cout << "A* 성공" << endl;
			return path;
		}

		closed.insert(current.Position);

		for (const Vector& neighbor : Edges[current.Position])
		{
			if (closed.find(neighbor) != closed.end())
				continue;

			float tempG = current.GCost + sqrt(pow(neighbor.x - current.Position.x, 2) + 
				pow(neighbor.y - current.Position.y, 2) + pow(neighbor.z - current.Position.z, 2));
			float heuristic = sqrt(pow(Goal.x - neighbor.x, 2) + pow(Goal.y - neighbor.y, 2) + pow(Goal.z - neighbor.z, 2));

			Node neighborNode = { neighbor, tempG,heuristic,new Node(current) };

			open.push(neighborNode);
		}
	}

	cout << "A* 실패" << endl;

	return {};
}

 

	shared_ptr<PathFinder> pf = MakeShared<PathFinder>();
	GRoom->DoAsync(&Room::UpdateTick);
	pf->DoAsync(&PathFinder::ReadFile);

	auto start = pf->CreateVec(-9500.f, -9400.f, 0.f);
	auto end = pf->CreateVec(-9100.f, -9200.f, 0.f);
	auto path = pf->AStar(start, end, pf->EdgeMap);

 

 

A* 알고리즘을 구현하고 실행시켜 보았다.

 

 

나름 괜찮게 나오는것 같은데 아직 이대로 적용시키기에는 문제가 많다.

무엇보다 속도가 너무 느리다.

이대로 게임에 적용 시키면 AI가 길 찾기를 요청할 때 마다 게임이 버벅이게 될 것이다.

 

일단 생각나는 해결법으로는 스레드에 일감을 분배 시켜주기?, a* 알고리즘을 손보기?,

클라이언트에서 레벨바운더리를 줄여서 레벨 정보를 조금 줄이기?, c++20 코루틴 만들어서 사용해보기?

등등이 떠오르는데 하나씩 해보면서 괜찮아 지는지 확인해 봐야겠다.