Kruskal -> 맵 생성

CJB_ny·2022년 12월 11일
0

DataStructure & Algorithm

목록 보기
24/35
post-thumbnail

최초의 상태는 이런 상태임.

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

	std::vector<CostEdge> edges;

	// edges 후보를 랜덤 cost로 등록한다.
	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;
				edges.emplace_back(CostEdge{ randValue, Pos{ y, x }, Pos{ y, x + 2 }});
			}

			// 아래로 연결하는 간선후보
			if (y < _size - 2)
			{
				const int32 randValue = ::rand() % 100;
				edges.emplace_back(CostEdge{ randValue, Pos{ y, x }, Pos{ y + 2, x } });
			}
		}
	}

	std::sort(edges.begin(), edges.end());

	DisjointSet sets(_size * _size);

	for (CostEdge& edge : edges)
	{
		int32 u = edge.u.y * _size + edge.u.x;
		int32 v = edge.v.y * _size + edge.v.x;

		// 같은 그룹이라면은 스킵 (안그러면 사이클 발생)
		if (sets.Find(u) == sets.Find(v)) continue;

		// 두 그룹을 합친다.
		sets.Merge(u, v);

		int32 y = (edge.u.y + edge.v.y) / 2;
		int32 x = (edge.u.x + edge.v.x) / 2;
		_tile[y][x] = TILE_TYPE::EMPTY;
	}
}
profile
https://cjbworld.tistory.com/ <- 이사중

0개의 댓글