경위

Terraria나 DQ Builders등에서 일정한 조건을 만족하면, 벽이나 도어로 둘러싸인 공간이 방으로서 인식되어 플레이어에게 있는 메리트를 줄 수 있지요?
그것을 보고 있는 동안에 「방 인식은 어떻게 할 수 있었을까」라고 의문이 나 버렸습니다.

그러나 여러가지 찾았습니다만, 이 기능에 대한 문장이나 설명은 그다지 없는 것 같습니다.
제일의 의문은 「어떻게 둘러싸인 공간을 식별하고 있는 것일까?」라고 하는 점이지요?
우연히 wikipedia에서 읽은 flood fill 알고리즘이 여기에서 사용할 수 있기 때문에 이번에는 그것을 사용하여 실험해 보았습니다.

Flood fill이란?

플러드 fill은 다양한 이미지 편집 도구 (예 : 윈도우 페인트)의 "채우기"기능에서 사용되는 알고리즘입니다.
이 기능을 사용한 적이 있는 분은 이미 떠올랐다고 생각합니다만, 클릭한 픽셀과 연결되어 있는 같은 색의 구역 밖에 색을 칠하는 기능입니다.
즉, 아래 그림과 같은 느낌으로 둘러싸인 공간을 식별할 수 있습니다.


Flood fill, 사실은 매우 간단합니다.
퍼포먼스 개선을 위해서, 바리에이션은 많이 있습니다만, 이번은 제일 이해하기 쉬운 재귀를 사용하고 있는 방법으로 원리를 설명합니다.

현재 처리중인 포인트를 n이라고합니다.
0. 특정 시작점을 n으로 설정합니다.
1. n이 이미 처리되었으면 다음 처리를 모두 건너 뛰고 돌아갑니다.
2. 만약 n이 처리해야 할 포인트로서 인식하는 조건(벽이 아닌 것, 색이 지정값인 것 등)을 만족시키지 않으면, 이하의 처리를 전부 스킵 해 돌아옵니다.
3. n을 처리해야 할 포인트로 인식하고 처리합니다 (어느 영역 (벽에 둘러싸인 영역)에 속한 포인트 목록에 추가, 색상을 지정 값으로 변경하는 등).
4. n을 처리됨으로 표시합니다.
5. n 아래의 포인트를 n으로 1부터 다시 실행합니다.
6. n 왼쪽 포인트를 n으로 1부터 다시 실행합니다.
7. n의 포인트를 n으로 1부터 다시 실행합니다.
8. n 오른쪽 포인트를 n으로 1부터 다시 실행합니다.

간단한 flood fill 구현 예

재귀를 사용하면 실제 코드도 매우 간단합니다.

void FloodFill(Node node, Predicate<Node> shouldProcess, Action<Node> process)
{
    if (node.IsProcessed) return;
    if (!shouldProcess(node)) return;

    process(node);
    node.IsProcessed = true;

    foreach (Node neighbour in node.Neighbours)
    {
        FloodFill(neighbour, shouldProcess, process);
    }
}

방 인식

그럼, 방 인식에 있어서 어떻게 flood fill을 응용할까요?

사실 그것은 그렇게 간단합니다.
위의 코드를 사용하는 경우, 맵상 전부의 포인트를 하나씩 node에 넣어, shouldProcess에 벽인가 어떤가의 판정 로직을 넣어,
process에 응하는 에리어의 포인트 리스트에 추가한다 ・에리어 정보를 갱신하는 로직을 넣어 실행하면 맵에 있는 에리어가 전부 식별됩니다.
그 후, 에어리어마다 방으로서 인식하는 조건(예를 들면, 라이트가 있는지, 에리어 사이즈가 맞는지 등)에 만족하고 있는지 어떤지를 체크하면 완료입니다.

예

void ScanForHouses(Map map)
{
    List<Area> areas = new List<Area>();

    foreach (Node node in map.Nodes)
    {
        Area area = null;

        FloodFill(node, n => !n.IsWall, n =>
        {
            if (area == null) area = new Area();

            area.Nodes.Add(n);
            if (n.IsLight) area.LightCount++;
        });

        if (area != null) areas.Add(area);
    }

    foreach (Area area in areas)
    {
        // ライトが一つ以上、サイズが10～100間のエリアを部屋として認識します
        area.IsHouse = area.LightCount > 0 && area.Nodes.Count > 10 && area.Nodes.Count < 100;
    }
}

결론

의외 쉽게 방 인식을 구현할 수있었습니다.
물론, 재귀로 flood fill을 구현하는 것이 성능적으로 좋다고는 말할 수 없습니다. Stack overflow 할 수도 있습니다.
그 경우, 재귀가 아니라, stack나 queue를 사용해 flood fill를 실장하면 대체로 해결할 수 있습니다. 둘 다 꽤 쉽습니다.
더 자세한 이야기나 다른 구현 변형을 알고 싶은 분은 레퍼런스를 읽으면 좋다고 생각합니다. 기본 원리가 바뀌지 않습니다.

레퍼런스

htps // 엔.ぃきぺぢ아. 오 rg / ぃ き / F ぉ 오 d_ 푹 l