최초의 상태는 이런 상태임.
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;
}
}