여기 잠깐!!

기본적인 알고리즘을 이해하는데 있어서 여기!를 참고해주세요!!

BSP 알고리즘 구현으로 해커톤 날먹이 된다고!?!#

사실 이건 장난이고, 그냥 있어보이게 구현할 수 있도록 구조를 다 만들어둬서 그냥 가져다 쓰시면 됩니다.

물론 이 코드가 체계적으로 작성된 코드는 아니지만! 그래도 쓸만한 애들이라고 생각합니다(최적화는 안되어있는 편 ㅎㅎ)

일단 활용하기 편하도록 Scriptable Object로 다 설정하도록 만들어 뒀습니다.

Scriptable Object 주의

이 Scriptable Object를 인게임 상에서 값을 수정하게 되면, editor 환경에서는 작동을 하나.. 나중에 build 이후로 가게되면 유니티에서 이제 최적화 과정을 거치면서 필요없는 prefabs 등 다른 리소스들을 다 없애는데 이때 Scriptable Object의 값이 변경되면 터집니다!

조심하십쇼!

기본적인 세팅#

일단 저는 부가적으로 Layer를 사용합니다. 참고하실 분은 참고해주세용

1. 벽 세팅#

기본적인 벽을 담을 스프라이트(2D Rect 정도?)를 기반으로 방향, 모서리 등의 위치에 배치할 스프라이트들을 넣으면 됩니다.

[CreateAssetMenu(fileName = "WallTileSettings", menuName = "Compy/Wall Tile Settings")]
public class WallTileSettings : ScriptableObject
{
    
    [System.Serializable]
    public class WallSprites
    {
        [Header("기본 벽 스프라이트")]
        [Tooltip("주변에 아무 연결이 없는 기본적인 벽 스프라이트")]
        public Sprite defaultWall;

        [Header("벽 테두리")]
        [Tooltip("아래쪽으로 연결된 상단 벽면")] // │ 의 윗부분
        public Sprite wallTop;
        [Tooltip("위쪽으로 연결된 하단 벽면")] // │ 의 아랫부분
        public Sprite wallBottom;
        [Tooltip("오른쪽으로 연결된 왼쪽 벽면")] // ─ 의 왼쪽
        public Sprite wallLeft;
        [Tooltip("왼쪽으로 연결된 오른쪽 벽면")] // ─ 의 오른쪽
        public Sprite wallRight;

        [Header("벽 모서리 - 외부")]
        [Tooltip("오른쪽과 아래로 연결된 외부 모서리")] // ┌ 모양
        public Sprite cornerOuterTopLeft;
        [Tooltip("왼쪽과 아래로 연결된 외부 모서리")] // ┐ 모양
        public Sprite cornerOuterTopRight;
        [Tooltip("오른쪽과 위로 연결된 외부 모서리")] // └ 모양
        public Sprite cornerOuterBottomLeft;
        [Tooltip("왼쪽과 위로 연결된 외부 모서리")] // ┘ 모양
        public Sprite cornerOuterBottomRight;

        [Header("벽 모서리 - 내부")]
        [Tooltip("위쪽과 왼쪽이 벽인 내부 모서리")] // ┘ 모양이지만 안쪽으로
        public Sprite cornerInnerTopLeft;
        [Tooltip("위쪽과 오른쪽이 벽인 내부 모서리")] // └ 모양이지만 안쪽으로
        public Sprite cornerInnerTopRight;
        [Tooltip("아래쪽과 왼쪽이 벽인 내부 모서리")] // ┐ 모양이지만 안쪽으로
        public Sprite cornerInnerBottomLeft;
        [Tooltip("아래쪽과 오른쪽이 벽인 내부 모서리")] // ┌ 모양이지만 안쪽으로
        public Sprite cornerInnerBottomRight;

        [Header("단독 벽")]
        [Tooltip("주변에 어떤 연결도 없는 단독으로 서있는 벽")]
        public Sprite singleWall;

        [Header("끝부분")]
        [Tooltip("위쪽 방향으로 돌출된 벽의 끝부분 (아래쪽만 연결)")] // ╽ 모양
        public Sprite endTop;
        [Tooltip("아래쪽 방향으로 돌출된 벽의 끝부분 (위쪽만 연결)")] // ╿ 모양
        public Sprite endBottom;
        [Tooltip("왼쪽 방향으로 돌출된 벽의 끝부분 (오른쪽만 연결)")] // ╾ 모양
        public Sprite endLeft;
        [Tooltip("오른쪽 방향으로 돌출된 벽의 끝부분 (왼쪽만 연결)")] // ╼ 모양
        public Sprite endRight;
    }

    [Header("벽 스프라이트 설정")]
    public WallSprites sprites;

    [Header("벽 렌더링 설정")]
    public string sortingLayerName = "Wall";
    public int sortingOrder = 0;
}

Bsp Generation 세팅#

bsp로 맵 생성을 할 때 사용될 변수들

using System.Collections.Generic;
using UnityEngine;
[CreateAssetMenu(fileName = "MapSettings", menuName = "Compy/Generator Settings")]
public class GeneratorSetting : ScriptableObject
{

    [Header("Map Size")]
    [Tooltip("전체 너비")]
    public int mapWidth = 100;
    
    [Tooltip("전체 높이")]
    public int mapHeight = 100;

    [Header("Room Generation")]
    [Tooltip("방의 최소 크기")]
    [Min(5)]
    public int minRoomSize = 10;
    
    [Tooltip("BSP 분할 최대 횟수")]
    [Range(1, 10)]
    public int maxIterations = 4;

    [Header("Room Constraints")]
    [Tooltip("방 사이의 최소 거리")]
    [Min(1)]
    public int minRoomDistance = 2;
    
    [Tooltip("방의 최대 크기 (전체 공간 대비 비율)")]
    [Range(0.3f, 0.8f)]
    public float maxRoomSizeRatio = 0.6f;

    [Header("Tile Settings")]
    [Tooltip("벽 타일 설정")]
    public WallTileSettings wallTileSettings;

    [Tooltip("기본 타일 프리팹 (스프라이트 렌더러와 콜라이더가 있는 빈 게임오브젝트)")]
    public GameObject tilePrefab;

    [Header("Prefabs")]
    [Tooltip("바닥 타일 프리팹")]
    public GameObject floorPrefab;

    [Header("Layer Settings")]
    [Tooltip("벽 레이어의 이름")]
    public string wallLayerName = "Wall";

    [Header("Advanced Settings")]
    [Tooltip("통로 너비")]
    [Range(1, 5)]
    public int corridorWidth = 3;
    
    [Tooltip("방 생성 시도 최대 횟수")]
    [Min(1)]
    public int maxRoomPlacementAttempts = 10;

    [Tooltip("추가 통로 생성 확률 (0-1)")]
    [Range(0f, 1f)]
    public float extraCorridorChance = 0.2f;
    
    [Header("Structures")]
    [Tooltip("맵에 배치할 구조물들의 정의")]
    public List<CompyStructure> structures = new List<CompyStructure>();

    [Tooltip("구조물 배치 최대 시도 횟수")]
    [Min(1)]
    public int maxPlacementAttempts = 100;

    
    
    
    public void ValidateSettings()
    {
        mapWidth = Mathf.Max(mapWidth, minRoomSize * 2);
        mapHeight = Mathf.Max(mapHeight, minRoomSize * 2);

        minRoomSize = Mathf.Min(minRoomSize, Mathf.Min(mapWidth, mapHeight) / 2);
        
        corridorWidth = Mathf.Min(corridorWidth, minRoomSize - 2);
        minRoomDistance = Mathf.Max(minRoomDistance, corridorWidth);

        ValidateStructures();
    }


    private void ValidateStructures()
    {
        if (structures == null) return;

        foreach (var structure in structures)
        {
            if (structure == null) continue;
            structure.width = Mathf.Min(structure.width, mapWidth - 4);
            structure.height = Mathf.Min(structure.height, mapHeight - 4);

            structure.minCount = Mathf.Min(structure.minCount, structure.maxCount);

            if (structure.padding > 0) 
                structure.padding = Mathf.Min(structure.padding,
                    Mathf.Min(structure.width, structure.height) / 2);
            
        }
    }
    
    public GeneratorSetting Clone()
    {
        var clone = CreateInstance<GeneratorSetting>();        
        clone.mapWidth = this.mapWidth;
        clone.mapHeight = this.mapHeight;
        clone.minRoomSize = this.minRoomSize;
        clone.maxIterations = this.maxIterations;
        clone.minRoomDistance = this.minRoomDistance;
        clone.maxRoomSizeRatio = this.maxRoomSizeRatio;
        clone.wallTileSettings = this.wallTileSettings;
        clone.tilePrefab = this.tilePrefab;
        clone.floorPrefab = this.floorPrefab;
        clone.wallLayerName = this.wallLayerName;
        clone.corridorWidth = this.corridorWidth;
        clone.maxRoomPlacementAttempts = this.maxRoomPlacementAttempts;
        clone.extraCorridorChance = this.extraCorridorChance;

        clone.structures = new List<CompyStructure>(this.structures);
        clone.maxPlacementAttempts = this.maxPlacementAttempts;

        return clone;
    }

#if UNITY_EDITOR
    // 내가 한번 당하지 두번은 안 당할거임 ㄹㅇ

    private void OnValidate()
    {
        ValidateSettings();
    }
#endif
}

BSP Algorithm#

BSP Room#

public class BSPRoom
{
    public int x, y, width, height;

    public BSPRoom(int x, int y, int width, int height) {
        this.x = x;
        this.y = y;
        this.width = width;
        this.height = height;
    }
}

BSP Generator#

기본적인 생성만 가볍게 만들어본 버전입니다.

public class BSPGenerator : MonoBehaviour{
    private enum WallType {
        Single,
        Top,
        Bottom,
        Left,
        Right,
        CornerOuterTopLeft,
        CornerOuterTopRight,
        CornerOuterBottomLeft,
        CornerOuterBottomRight,
        CornerInnerTopLeft,
        CornerInnerTopRight,
        CornerInnerBottomLeft,
        CornerInnerBottomRight,
        EndTop,
        EndBottom,
        EndLeft,
        EndRight,
        Default
    }
    private int mapWidth = 100;
    private int mapHeight = 100;
    private int minRoomSize = 10;
    private int maxIterations = 4; 
    
    private string wallLayerName = "Wall";
    
    private GameObject wallPrefab; 
    private GameObject floorPrefab; 

    private List<BSPRoom> rooms = new List<BSPRoom>();
    private int[,] map;
    private int wallLayerId;

    private GeneratorSetting setting;
    
    private const bool debug = false;

    private bool generateDone;
    
    public void GeneratorInit(GeneratorSetting setting)
    {
        generateDone = false;
        InitWithSettings(setting);
        
        wallLayerId = LayerMask.NameToLayer(wallLayerName);
        
        if (wallLayerId == -1) {
            Debug.LogError($"Layer '{wallLayerName}' not found! 이거 추가좀 이거 왜 안고쳐짐?");
            wallLayerId = 0;
        }

        this.setting = setting;
    }

    private void InitWithSettings(GeneratorSetting setting) {
        mapWidth = setting.mapWidth;
        mapHeight = setting.mapHeight;
        minRoomSize = setting.minRoomSize;
        maxIterations = setting.maxIterations;
        wallLayerName = setting.wallLayerName;
        floorPrefab = setting.floorPrefab;
    }
    
    public void GenerateMap() {
        map = new int[mapWidth, mapHeight];
        for (int x = 0; x < mapWidth; x++) {
            for (int y = 0; y < mapHeight; y++)
                map[x, y] = 1;
        }

        SplitSpace(0, 0, mapWidth, mapHeight, 0);
        
        ConnectRooms();
        
        InstantiateTiles();
        
        generateDone = true;
    }



    private void SplitSpace(int x, int y, int width, int height, int iteration)
    {
        if (iteration >= maxIterations || width < minRoomSize * 2 || height < minRoomSize * 2) {
            int roomWidth = Random.Range(minRoomSize, width - 4);
            int roomHeight = Random.Range(minRoomSize, height - 4);
            int roomX = x + Random.Range(2, width - roomWidth - 2);
            int roomY = y + Random.Range(2, height - roomHeight - 2);

            CreateRoom(roomX, roomY, roomWidth, roomHeight);
            rooms.Add(new BSPRoom(roomX, roomY, roomWidth, roomHeight));
            return;
        }

        bool splitHorizontal = Random.Range(0f, 1f) > 0.5f;
        if (width > height && width / height >= 1.25f) splitHorizontal = false;
        else if (height > width && height / width >= 1.25f) splitHorizontal = true;

        if (splitHorizontal) {
            int splitAt = Random.Range(minRoomSize, height - minRoomSize);
            SplitSpace(x, y, width, splitAt, iteration + 1);
            SplitSpace(x, y + splitAt, width, height - splitAt, iteration + 1);
        }
        else {
            int splitAt = Random.Range(minRoomSize, width - minRoomSize);
            SplitSpace(x, y, splitAt, height, iteration + 1);
            SplitSpace(x + splitAt, y, width - splitAt, height, iteration + 1);
        }
    }

    private void CreateRoom(int x, int y, int width, int height)
    {
        for (int i = x; i < x + width; i++) {
            for (int j = y; j < y + height; j++)
                if (i >= 0 && i < mapWidth && j >= 0 && j < mapHeight) map[i, j] = 0;
        }
    }

    private void ConnectRooms() {
        for (int i = 0; i < rooms.Count - 1; i++) {
            BSPRoom roomA = rooms[i];
            BSPRoom roomB = rooms[i + 1];

            Vector2Int pointA = new Vector2Int(
                roomA.x + roomA.width / 2,
                roomA.y + roomA.height / 2
            );
            Vector2Int pointB = new Vector2Int(
                roomB.x + roomB.width / 2,
                roomB.y + roomB.height / 2
            );
            
            CreateCorridor(pointA.x, pointA.y, pointB.x, pointA.y);
            CreateCorridor(pointB.x, pointA.y, pointB.x, pointB.y);
        }
    }

    private void CreateCorridor(int startX, int startY, int endX, int endY) {
        int x = startX;
        int y = startY;

        while (x != endX || y != endY)
        {
            if (x < endX) x++;
            else if (x > endX) x--;
            
            if (y < endY) y++;
            else if (y > endY) y--;

            if (x >= 0 && x < mapWidth && y >= 0 && y < mapHeight) {
                map[x, y] = 0;
                
                for (int i = -1; i <= 1; i++)
                {
                    for (int j = -1; j <= 1; j++)
                    {
                        int nx = x + i;
                        int ny = y + j;
                        if (nx >= 0 && nx < mapWidth && ny >= 0 && ny < mapHeight)
                            map[nx, ny] = 0;
                    }
                }
            }
        }
    }

    private void InstantiateTiles()
    {
        GameObject wallParent = new GameObject("Walls");
        GameObject floorParent = new GameObject("Floors");
        wallParent.transform.parent = transform;
        floorParent.transform.parent = transform;

        wallParent.layer = LayerMask.NameToLayer("Wall");
        floorParent.layer = LayerMask.NameToLayer("Floor");

        for (int x = 0; x < mapWidth; x++)
        {
            for (int y = 0; y < mapHeight; y++)
            {
                Vector3 position = new Vector3(x, y, 0);
                if (map[x, y] == 1)
                {
                    GameObject wall = Instantiate(setting.tilePrefab, position, Quaternion.identity, wallParent.transform);
                    wall.layer = LayerMask.NameToLayer("Wall");

                    SpriteRenderer wallRenderer = wall.GetComponent<SpriteRenderer>();
                    if (wallRenderer != null)
                    {
                        WallType wallType = DetermineWallType(x, y);
                        ApplyWallSprite(wallRenderer, wallType);
                        
                        wallRenderer.sortingLayerName = setting.wallTileSettings.sortingLayerName;
                        wallRenderer.sortingOrder = setting.wallTileSettings.sortingOrder;
                    }

                    Collider2D collider = wall.GetComponent<Collider2D>();
                    if (collider != null)
                        collider.isTrigger = false;
                }
                else
                {
                    GameObject floor = Instantiate(setting.floorPrefab, position, Quaternion.identity, floorParent.transform);
                    floor.layer = LayerMask.NameToLayer("Floor");

                    SpriteRenderer floorRenderer = floor.GetComponent<SpriteRenderer>();
                    if (floorRenderer != null)
                    {
                        floorRenderer.sortingLayerName = "Floor";
                        floorRenderer.sortingOrder = 0;
                    }
                }
            }
        }
    }

    private WallType DetermineWallType(int x, int y)
    {
        bool up = IsWall(x, y + 1);
        bool down = IsWall(x, y - 1);
        bool left = IsWall(x - 1, y);
        bool right = IsWall(x + 1, y);
        
        // 대각선 방향도 확인
        bool upLeft = IsWall(x - 1, y + 1);
        bool upRight = IsWall(x + 1, y + 1);
        bool downLeft = IsWall(x - 1, y - 1);
        bool downRight = IsWall(x + 1, y - 1);

        // 단독 벽
        if (!up && !down && !left && !right)
            return WallType.Single;

        // 내부 모서리 검사 (벽이 안쪽으로 꺾이는 경우)
        if (up && right && !upRight) return WallType.CornerInnerTopRight;
        if (up && left && !upLeft) return WallType.CornerInnerTopLeft;
        if (down && right && !downRight) return WallType.CornerInnerBottomRight;
        if (down && left && !downLeft) return WallType.CornerInnerBottomLeft;

        // 외부 모서리 검사 (벽이 바깥쪽으로 꺾이는 경우)
        if (!up && !left && right && down) return WallType.CornerOuterTopLeft;
        if (!up && !right && left && down) return WallType.CornerOuterTopRight;
        if (!down && !left && right && up) return WallType.CornerOuterBottomLeft;
        if (!down && !right && left && up) return WallType.CornerOuterBottomRight;

        // 끝부분 검사
        if (up && !down && !left && !right) return WallType.EndBottom;
        if (!up && down && !left && !right) return WallType.EndTop;
        if (!up && !down && left && !right) return WallType.EndRight;
        if (!up && !down && !left && right) return WallType.EndLeft;

        // 테두리 검사
        if (!up && down) return WallType.Top;
        if (up && !down) return WallType.Bottom;
        if (!left && right) return WallType.Left;
        if (left && !right) return WallType.Right;

        return WallType.Default;
    }

    private void ApplyWallSprite(SpriteRenderer renderer, WallType type)
    {
        var sprites = setting.wallTileSettings.sprites;
        
        switch (type)
        {
            case WallType.Single:
                renderer.sprite = sprites.singleWall;
                break;
            case WallType.Top:
                renderer.sprite = sprites.wallTop;
                break;
            case WallType.Bottom:
                renderer.sprite = sprites.wallBottom;
                break;
            case WallType.Left:
                renderer.sprite = sprites.wallLeft;
                break;
            case WallType.Right:
                renderer.sprite = sprites.wallRight;
                break;
            case WallType.CornerOuterTopLeft:
                renderer.sprite = sprites.cornerOuterTopLeft;
                break;
            case WallType.CornerOuterTopRight:
                renderer.sprite = sprites.cornerOuterTopRight;
                break;
            case WallType.CornerOuterBottomLeft:
                renderer.sprite = sprites.cornerOuterBottomLeft;
                break;
            case WallType.CornerOuterBottomRight:
                renderer.sprite = sprites.cornerOuterBottomRight;
                break;
            case WallType.CornerInnerTopLeft:
                renderer.sprite = sprites.cornerInnerTopLeft;
                break;
            case WallType.CornerInnerTopRight:
                renderer.sprite = sprites.cornerInnerTopRight;
                break;
            case WallType.CornerInnerBottomLeft:
                renderer.sprite = sprites.cornerInnerBottomLeft;
                break;
            case WallType.CornerInnerBottomRight:
                renderer.sprite = sprites.cornerInnerBottomRight;
                break;
            case WallType.EndTop:
                renderer.sprite = sprites.endTop;
                break;
            case WallType.EndBottom:
                renderer.sprite = sprites.endBottom;
                break;
            case WallType.EndLeft:
                renderer.sprite = sprites.endLeft;
                break;
            case WallType.EndRight:
                renderer.sprite = sprites.endRight;
                break;
            default:
                renderer.sprite = sprites.defaultWall;
                break;
        }
        
    }

    private bool IsWall(int x, int y)
    {
        if (x < 0 || x >= mapWidth || y < 0 || y >= mapHeight)
            return false;
        return map[x, y] == 1;
    }

   

    public bool isDone()
    {
        return generateDone;
    }
    
    
    public BSPRoom GetRoomFromPosition(Vector2 position)
    {
        if (!generateDone)
        {
            Debug.LogWarning("Map generation is not complete. Cannot find room.");
            return null;
        }

        return rooms.FirstOrDefault(room =>
            position.x >= room.x && position.x < room.x + room.width &&
            position.y >= room.y && position.y < room.y + room.height);
    }


    public BSPRoom GetRoomFromTransform(Transform transform)
    {
        if (transform == null) return null;
        return GetRoomFromPosition(new Vector2(transform.position.x, transform.position.y));
    }
    
    
 

    


    private void OnDrawGizmos()
    {
        if (!debug) return;
        if (map == null) return;

        for (int x = 0; x < mapWidth; x++) {
            for (int y = 0; y < mapHeight; y++) {
                if (map[x, y] == 1)
                    Gizmos.color = Color.black;
                else
                    Gizmos.color = Color.white;
                Vector3 pos = new Vector3(x, y, 0);
                Gizmos.DrawCube(pos, Vector3.one);
            }
        }
    }
}

여기까지 기본적인 맵 생성이였구. 다음 포스트에서 아이템 배치와 다른 지형 배치 등을 다루는 코드를 이어서 작성하도록 하겠습니다.

수고하셨습니다.

Reference#

Compy Blog