Unity유니티_랜덤맵(tile) 생성_flood fill(seed fill) 알고리즘

오늘은 랜덤맵을 만들때

flood fill(seed fill) 알고리즘을 활용해 보고자 한다.

 

flood fill(seed fill) 알고리즘은 언제 사용하나?

• 현재 위치에서 막히지 않고 접근 가능한 영역의 좌표를 알고 싶을때
• 그림판의 채우기 기능 구현
• 맵에서 막히지 않게 구조물 만들기

flood fill(seed fill) 알고리즘을 사용하면, 옅은 회색 부분에 모두 접근 할수 있는지 알 수 있다.

flood fill(seed fill) 은 어떻게 동작하는 걸까?

1. 십자 모양으로 (위, 아래, 왼쪽, 오른쪽)을 살펴보면서 
2. 이미 확인을 했는가? 아니면 막혀있는가? 를 확인
3. 만약에 확인도 안했고 막혀 있지도 않으면 "갈수 있는 장소에 추가"
4. 더이상 살펴볼 곳이 남지 않을 때까지 수행

응용하기

• 실제 접근 가능한 영역 과 이론적으로 접근 가능한 영역 비교
• 실제 접근 가능한 영역이, 이론적으로 접근 가능한 영역 보다 작으면
• 막힌 곳이 있다는 뜻!! ==> 생성 취소

---

Properties 

    public Transform tileTF; // 바닥 기본 타일 
    public Transform wallTF; // 벽
    public Vector2 mapSize; // 맵크기

    [Range(0, 1)]
    public float tileOutlineThickness; // 바닥 테두리 두께 조절

    [Range(0, 1)]
    public float wallDensity; // 벽이 만들어질 밀도

    List<Vector2> tilePositions; // 바닥이 생성될 좌표 리스트
    Queue<Vector2> shuffledPositions; // 랜덤하게 섞인 좌표 리스트 ==> 향후 벽을 랜덤하게 만들때 사용

    int seed = 10; // 난수 생성시 사용되는 숫자
    public Vector2 centerPosition; // 맵 중앙 좌표값
    Transform mapHolder;

 

---

Methods

 

맵 만드는 전체 함수 

• 바닥이 생성될 위치정보를 만듬 (맵 크기만큼)
• 바닥과 외벽 objects 만들기
• 중앙에서 막히지 않게 장애물들 만들기

    public void GenerateMap()
    {   
        // 바닥이 생성될 위치정보 생성
        tilePositions = new List<Vector2>();
        for (int x=0; x<mapSize.x; x++)
        {
            for (int y=0; y<mapSize.y; y++)
            {
                tilePositions.Add(new Vector2(x, y));
            }
        }

        // 맵 중앙값 설정
        centerPosition = new Vector2((int)mapSize.x / 2, (int)mapSize.y / 2);

        //위치정보 섞고
        shuffledPositions = new Queue<Vector2>(Shuffle(tilePositions, seed));

        // 만약 holder가 있으면 없애고, 자식 오브젝트로 holder 오브젝트 만들기
        string holder = "MapHolder";
        if (transform.Find(holder))
        {
            Destroy(transform.Find(holder).gameObject);
        }
        mapHolder = new GameObject(holder).transform;
        mapHolder.parent = transform;

        // 바닥깔기 + 외벽 포함
        for (int x = -1; x <= mapSize.x; x++)
        {
            if (x == -1 || x == mapSize.x)
            {
                for (int y = -1; y <= mapSize.y; y++)
                {
                    Vector2 setTilePos = new Vector2(x, y);
                    Transform outerWall = Instantiate(wallTF, setTilePos, Quaternion.identity, mapHolder);
                    outerWall.localScale = Vector2.one;
                }
            }
            else
            {
                for (int y = -1; y <= mapSize.y; y++)
                {
                    if (y == -1 || y == mapSize.y)
                    {
                        Vector2 setTilePos = new Vector2(x, y);
                        Transform outerWall = Instantiate(wallTF, setTilePos, Quaternion.identity, mapHolder);
                        outerWall.localScale = Vector2.one;
                    }
                    else
                    {
                        Vector2 setTilePos = new Vector2(x, y);
                        Transform tile = Instantiate(tileTF, setTilePos, Quaternion.identity, mapHolder);
                        tile.localScale = Vector2.one * (1 - tileOutlineThickness);
                    }
                }
            }
        }

        // 여기서 부터는 벽만들기
        bool[,] wallGrid = new bool[(int)mapSize.x, (int)mapSize.y]; // 벽을 생성 위치 정보를 담을 grind 생성

        int wallCount = (int)(mapSize.x * mapSize.y * wallDensity); // 만들 벽 개수
        int currentWallCount = 0;

        for (int i = 0; i < wallCount; i++)
        {
            //벽을 만들 위치 무작위로 선택
            Vector2 randomPos = GetRandomPosition();
            wallGrid[(int)randomPos.x, (int)randomPos.y] = true;
            currentWallCount++;

            //만약 현재 선택된 위치가 센터가 아니고 + 맵에 막히는 곳이 없다면 해당 장소에 wall 객체 생성
            if (randomPos != centerPosition && IsAccessible(wallGrid, currentWallCount))
            {
                Vector2 wallPos = new Vector2(randomPos.x, randomPos.y);
                Instantiate(wallTF, wallPos, Quaternion.identity, mapHolder);
            }
        }
    }

 

 

★★ flood fill(seed fill) 알고리즘 으로, 막힌곳 있는지 확인 

    // 현재 장소가 중앙에서 막히지 않고 접근 가능한지 확인
    bool IsAccessible(bool[,] wallGrid, int currentWallCount)
    {
        bool[,] checkingGrid = new bool[wallGrid.GetLength(0), wallGrid.GetLength(1)]; // 길찾기위한 gird생성

        Queue<Vector2> accessiblePositions = new Queue<Vector2>(); // 접근 가능한 좌표 잠시 모아두는 곳

        // 센터에서 부터 접근 가능성 체크 시작
        accessiblePositions.Enqueue(centerPosition); 
        checkingGrid[(int)centerPosition.x, (int)centerPosition.y] = true;
        int accessibleCount = 1;

        while(accessiblePositions.Count > 0)
        {
            Vector2 currentPosition = accessiblePositions.Dequeue();
            
            for (int i=-1; i<=1; i++)
            {
                for (int j=-1; j<=1; j++)
                {
                    int nearX = (int)currentPosition.x + i;
                    int nearY = (int)currentPosition.y + j;

                    // 현재 위치에서 위, 아래, 양옆을 확인
                    if (i==0 || j == 0)
                    {
                        //맵의 범위를 넘지 않았는지 확인
                        if (nearX >= 0 && nearX < wallGrid.GetLength(0) && nearY >=0 && nearY < wallGrid.GetLength(0))
                        {
                            //만약 지금 확인중인 위치가 아직 가보지 않을 곳이고 + 벽이 세워져 있지 않다면
                            if(!checkingGrid[nearX,nearY] && !wallGrid[nearX, nearY])
                            {
                                checkingGrid[nearX, nearY] = true;
                                accessiblePositions.Enqueue(new Vector2(nearX, nearY));
                                accessibleCount++;
                            }
                        }
                    }
                }
            }
        }
        // 실제 접근 가능한 위치 갯수와 이론상 접근 가능한 위치 갯수를 비교하여, 현재 막힌 곳이 있는지 확인
        int maxAccessibleCount = (int)(mapSize.x * mapSize.y - currentWallCount);
        return maxAccessibleCount == accessibleCount; // 막혀있지 않다면 True, 막혀 있다면 False 반환
    }

 

 

무작위로 Vector2위치정보를 반환해주는 함수

    public Vector2 GetRandomPosition()
    {
        //하나 뽑아와 
        Vector2 randomPos = shuffledPositions.Dequeue();

        //다시 넣어
        shuffledPositions.Enqueue(randomPos);
        return randomPos;
    }

 

리스트의 순서를 섞어주는 함수

    public List<Vector2> Shuffle(List<Vector2> deck, int seed)
    {
        List<Vector2> shuffledDeck = deck;
        System.Random random = new System.Random(seed);
        for (int i = 0; i < deck.Count; i++)
        {
            Vector2 temp = shuffledDeck[i];
            int randomIndex = random.Next(0, deck.Count);
            shuffledDeck[i] = shuffledDeck[randomIndex];
            shuffledDeck[randomIndex] = temp;
        }
        return shuffledDeck;
    }

끝. 

---

using UnityEngine;
using System.Collections;
using System.Collections.Generic;

public class MapMaker : MonoBehaviour
{
    public Transform tileTF; // 바닥 기본 타일 
    public Transform wallTF; // 벽
    public Vector2 mapSize; // 맵크기

    [Range(0, 1)]
    public float tileOutlineThickness; // 바닥 테두리 두께 조절

    [Range(0, 1)]
    public float wallDensity; // 벽이 만들어질 밀도

    List<Vector2> tilePositions; // 바닥이 생성될 좌표 리스트
    Queue<Vector2> shuffledPositions; // 랜덤하게 섞인 좌표 리스트 ==> 향후 벽을 랜덤하게 만들때 사용

    int seed = 10; // 난수 생성시 사용되는 숫자
    public Vector2 centerPosition; // 맵 중앙 좌표값
    Transform mapHolder;


    public void Start()
    {
        mapSize = GameManager.instance.mapSize;
        GenerateMap();
    }

    public void GenerateMap()
    {   
        // 바닥이 생성될 위치정보 생성
        tilePositions = new List<Vector2>();
        for (int x=0; x<mapSize.x; x++)
        {
            for (int y=0; y<mapSize.y; y++)
            {
                tilePositions.Add(new Vector2(x, y));
            }
        }

        // 맵 중앙값 설정
        centerPosition = new Vector2((int)mapSize.x / 2, (int)mapSize.y / 2);

        //위치정보 섞고
        shuffledPositions = new Queue<Vector2>(Shuffle(tilePositions, seed));

        // 만약 holder가 있으면 없애고, 자식 오브젝트로 holder 오브젝트 만들기
        string holder = "MapHolder";
        if (transform.Find(holder))
        {
            Destroy(transform.Find(holder).gameObject);
        }
        mapHolder = new GameObject(holder).transform;
        mapHolder.parent = transform;

        // 바닥깔기 + 외벽 포함
        for (int x = -1; x <= mapSize.x; x++)
        {
            if (x == -1 || x == mapSize.x)
            {
                for (int y = -1; y <= mapSize.y; y++)
                {
                    Vector2 setTilePos = new Vector2(x, y);
                    Transform outerWall = Instantiate(wallTF, setTilePos, Quaternion.identity, mapHolder);
                    outerWall.localScale = Vector2.one;
                }
            }
            else
            {
                for (int y = -1; y <= mapSize.y; y++)
                {
                    if (y == -1 || y == mapSize.y)
                    {
                        Vector2 setTilePos = new Vector2(x, y);
                        Transform outerWall = Instantiate(wallTF, setTilePos, Quaternion.identity, mapHolder);
                        outerWall.localScale = Vector2.one;
                    }
                    else
                    {
                        Vector2 setTilePos = new Vector2(x, y);
                        Transform tile = Instantiate(tileTF, setTilePos, Quaternion.identity, mapHolder);
                        tile.localScale = Vector2.one * (1 - tileOutlineThickness);
                    }
                }
            }
        }

        bool[,] wallGrid = new bool[(int)mapSize.x, (int)mapSize.y];

        int wallCount = (int)(mapSize.x * mapSize.y * wallDensity);
        int currentWallCount = 0;

        for (int i = 0; i < wallCount; i++)
        {
            //벽을 만들 위치 무작위로 선택
            Vector2 randomPos = GetRandomPosition();
            wallGrid[(int)randomPos.x, (int)randomPos.y] = true;
            currentWallCount++;

            //만약 현재 선택된 위치가 센터가 아니고 + 맵에 막히는 곳이 없다면 해당 장소에 wall 객체 생성
            if (randomPos != centerPosition && IsAccessible(wallGrid, currentWallCount))
            {
                Vector2 wallPos = new Vector2(randomPos.x, randomPos.y);
                Instantiate(wallTF, wallPos, Quaternion.identity, mapHolder);
            }
        }
    }


    bool IsAccessible(bool[,] wallGrid, int currentWallCount)
    {
        bool[,] checkingGrid = new bool[wallGrid.GetLength(0), wallGrid.GetLength(1)]; // 길찾기위한 gird생성

        Queue<Vector2> accessiblePositions = new Queue<Vector2>(); // 접근 가능한 좌표 잠시 모아두는 곳

        // 센터에서 부터 접근 가능성 체크 시작
        accessiblePositions.Enqueue(centerPosition); 
        checkingGrid[(int)centerPosition.x, (int)centerPosition.y] = true;
        int accessibleCount = 1;

        while(accessiblePositions.Count > 0)
        {
            Vector2 currentPosition = accessiblePositions.Dequeue();
            
            for (int i=-1; i<=1; i++)
            {
                for (int j=-1; j<=1; j++)
                {
                    int nearX = (int)currentPosition.x + i;
                    int nearY = (int)currentPosition.y + j;

                    // 현재 위치에서 위, 아래, 양옆을 확인
                    if (i==0 || j == 0)
                    {
                        //맵의 범위를 넘지 않았는지 확인
                        if (nearX >= 0 && nearX < wallGrid.GetLength(0) && nearY >=0 && nearY < wallGrid.GetLength(0))
                        {
                            //만약 지금 확인중인 위치가 아직 가보지 않을 곳이고 + 벽이 세워져 있지 않다면
                            if(!checkingGrid[nearX,nearY] && !wallGrid[nearX, nearY])
                            {
                                checkingGrid[nearX, nearY] = true;
                                accessiblePositions.Enqueue(new Vector2(nearX, nearY));
                                accessibleCount++;
                            }
                        }
                    }
                }
            }
        }

        int maxAccessibleCount = (int)(mapSize.x * mapSize.y - currentWallCount);
        return maxAccessibleCount == accessibleCount;
    }

    // 무작위로 위치 정보 얻기
    public Vector2 GetRandomPosition()
    {
        //하나 뽑아와 
        Vector2 randomPos = shuffledPositions.Dequeue();

        //다시 넣어
        shuffledPositions.Enqueue(randomPos);
        return randomPos;
    }

    //리스트 순서 랜덤하게 섞기
    public List<Vector2> Shuffle(List<Vector2> deck, int seed)
    {
        List<Vector2> shuffledDeck = deck;
        System.Random random = new System.Random(seed);
        for (int i = 0; i < deck.Count; i++)
        {
            Vector2 temp = shuffledDeck[i];
            int randomIndex = random.Next(0, deck.Count);
            shuffledDeck[i] = shuffledDeck[randomIndex];
            shuffledDeck[randomIndex] = temp;
        }
        return shuffledDeck;
    }
}