[C++ 자/알 Note] Prim 알고리즘 적용 (미로 생성)

주의사항

미로 맵을 생성하는 경우에

Prim 알고리즘을 사용하면 쉽게 맵을 생성할 수 있다

 

코드에 앞서

기본적으로 타일은 WALL(빨강)과 EMPTY(초록)로 구분되어 있다

Prim 알고리즘을 적용하기 전에

y와 x의 2의 배수 위치에는 모두 WALL로 처리한다

이렇게 하면 아래와 같이 된다

 

먼저 간선정보를 저장할 edges를 만들어준다

그리고 랜덤맵을 만들기 위해서

edges의 가중치를 랜덤으로 등록해서 만들어준다

 

그리고 다익스트라처럼 아래와 같은 세팅이 필요하다

우선순위큐, 

해당 정점이 포함되었는지를 체크하는 added, 

해당 정점이 누구에게 발견되었는지를 위한 parent, 

해당 정점에 닿는 최소 간선만을 기록하는 best

 

이렇게 모든 준비가 끝나면

먼저 첫 번째 임의의 정점을 시작점으로 하며

우선순위 큐에 넣으며 세팅값을 넣어준다

 

그리고 우선순위큐가 빌 때까지 반복문을 돌며

해당 정점으로 가는 길을 뚫어주고 해당 정점의 연결 간선들 중

이미 추가된 경우와 best가 아닌 경우들은 스킵하며

우선순위큐에 push 해주면 된다

 

코드 구현

void Board::GenerateMap_Prim()
{
	struct CostEdge
	{
		int cost;
		Pos vtx;

		bool operator<(const CostEdge& other) const
		{
			return cost < other.cost;
		}
	};

	for (int32 y = 0; y < _size; y++)
	{
		for (int32 x = 0; x < _size; x++)
		{
			if (x % 2 == 0 || y % 2 == 0)
				_tile[y][x] = TileType::WALL;
			else
				_tile[y][x] = TileType::EMPTY;
		}
	}

	// edges[u]: u 정점과 연결된 간선 목록
	map<Pos, vector<CostEdge>> edges;

	// edges 후보를 랜덤으로 등록
	for (int32 y = 0; y < _size; y++)
	{
		for (int32 x = 0; x < _size; x++)
		{
			if (x % 2 == 0 || y % 2 == 0)
				continue;

			// 우측 연결 간선 후보
			if (x < _size - 2)
			{
				const int32 randValue = ::rand() % 100;
				Pos u = Pos{ y, x };
				Pos v = Pos{ y, x + 2 };
				edges[u].push_back(CostEdge{ randValue, v });
				edges[v].push_back(CostEdge{ randValue, u });
			}

			// 아래 연결 간선 후보
			if (y < _size - 2)
			{
				const int32 randValue = ::rand() % 100;
				Pos u = Pos{ y, x };
				Pos v = Pos{ y + 2, x };
				edges[u].push_back(CostEdge{ randValue, v });
				edges[v].push_back(CostEdge{ randValue, u });
			}
		}
	}

	// 해당 정점의 트리 포함여부
	map<Pos, bool> added;
	// 해당 정점이 누구에 의해 연결 되었는지
	map<Pos, Pos> parent;
	// 해당 정점에 닿는 최소 간선의 정보
	map<Pos, int32> best;

	for (int32 y = 0; y < _size; y++)
	{
		for (int32 x = 0; x < _size; x++)
		{
			best[Pos{ y, x }] = INT32_MAX;
			added[Pos{ y, x }] = false;
		}
	}

	priority_queue<CostEdge> pq;
	const Pos startPos = Pos{ 1, 1 }; // 임의의 값을 정하는 것도 가능
	pq.push(CostEdge{ 0, startPos });
	best[startPos] = 0;
	parent[startPos] = startPos;

	while (pq.empty() == false)
	{
		CostEdge bestEdge = pq.top();
		pq.pop();

		// 새로 연결된 정점
		Pos v = bestEdge.vtx;
		// 이미 추가되었다면 스킵
		if (added[v])
			continue;

		added[v] = true;

		// 맵에 적용
		{
			int y = (parent[v].y + v.y) / 2;
			int x = (parent[v].x + v.x) / 2;
			_tile[y][x] = TileType::EMPTY;
		}

		// 방금 추가한 정점에 인접한 간선들을 추가
		for (CostEdge& edge : edges[v])
		{
			// 이미 추가 되었으면 스킵
			if (added[edge.vtx])
				continue;
			// 다른 경로로 더 좋은 후보가 발견 되었으면 스킵
			if (edge.cost > best[edge.vtx])
				continue;

			best[edge.vtx] = edge.cost;
			parent[edge.vtx] = v;
			pq.push(edge);
		}
	}
}