Unity BSP알고리즘 맵제작

저번에 절차적으로 생성했던것에서 BSP 알고리즘을 사용해 보았다

기반코드는 대부분 전에 했던것에서 약간만 추가되었다

Unity2D 절차 지향적 맵 생성

 

 

1. 맵 생성코드

using System.Collections.Generic;
using UnityEngine;
using Random = UnityEngine.Random;
namespace PKW_Tilemap
{
    public class RandomSquareColliderWithBSP : RandomSquareWithBSP
    {
        protected override void RunGenerator()
        {
            CreateRoom();
        }

        private void CreateRoom()
        {
            List<BoundsInt> _roomList = ProcedualTilemap.BinarySpacePartitioning(new BoundsInt((Vector3Int)startPosition,
                               new Vector3Int(_randomSquareSO.maxWidth, _randomSquareSO.maxHeight, 0)), _randomSquareSO.minWidth, _randomSquareSO.minHeight);
            List<Vector2Int> _roomCenterList = new List<Vector2Int>();
            foreach (BoundsInt _room in _roomList)
            {
                Vector2Int _center = (Vector2Int)Vector3Int.RoundToInt(_room.center);
                _roomCenterList.Add(_center);
            }

            HashSet<Vector2Int> _floorPosition = CreateRooms(_roomList);
            HashSet<Vector2Int> _corridor = ConnectRooms(_roomCenterList);

            _floorPosition.UnionWith(_corridor);

            tilemapVisualizer.PaintFloorTile(_floorPosition);
            WallGenerator.GenerateWall(_floorPosition, tilemapVisualizer);
        }

        private HashSet<Vector2Int> CreateRooms(List<BoundsInt> _roomList)
        {
            HashSet<Vector2Int> _squareSet = new HashSet<Vector2Int>();
            HashSet<Vector2Int> _newRoom = new HashSet<Vector2Int>();
            foreach (BoundsInt _room in _roomList)
            {
                for (int col = offset; col < _room.size.x - offset; col++)
                {
                    for (int row = offset; row < _room.size.y - offset; row++)
                    {
                        Vector2Int _pos = new Vector2Int(_room.x + col, _room.y + row);
                        _newRoom.Add(_pos);
                    }
                }
                //SaveRoomData((Vector2Int)_room.min, _newRoom);
                _squareSet.UnionWith(_newRoom);

                _newRoom.Clear();
            }

            return _squareSet;
        }

        private HashSet<Vector2Int> ConnectRooms(List<Vector2Int> _roomCenterList)
        {
            HashSet<Vector2Int> _corridor = new HashSet<Vector2Int>();
            Vector2Int _curCenter = _roomCenterList[Random.Range(0, _roomCenterList.Count)];
            _roomCenterList.Remove(_curCenter);

            while (_roomCenterList.Count > 0)
            {
                Vector2Int _closestCenter = GetClosestCenter(_curCenter, _roomCenterList);
                _roomCenterList.Remove(_closestCenter);

                HashSet<Vector2Int> _newCorridor = CreateCorridor(_curCenter, _closestCenter);
                _curCenter = _closestCenter;
                _corridor.UnionWith(_newCorridor);
            }

            return _corridor;
        }

        private HashSet<Vector2Int> CreateCorridor(Vector2Int _curCenter, Vector2Int _closestCenter)
        {
            HashSet<Vector2Int> _corridor = new HashSet<Vector2Int>();
            Vector2Int _curPos = _curCenter;
            _corridor.Add(_curPos);

            while (_curPos.y != _closestCenter.y)
            {
                if (_curPos.y < _closestCenter.y)
                {
                    _curPos.y += Vector2Int.up.y;
                }
                else
                {
                    _curPos.y += Vector2Int.down.y;
                }
                _corridor.Add(_curPos);
            }
            while (_curPos.x != _closestCenter.x)
            {
                if (_curPos.x < _closestCenter.x)
                {
                    _curPos.x += Vector2Int.right.x;
                }
                else
                {
                    _curPos.x += Vector2Int.left.x;
                }
                _corridor.Add(_curPos);
            }

            return _corridor;
        }

        private Vector2Int GetClosestCenter(Vector2Int curCenter, List<Vector2Int> roomCenterList)
        {
            float _distance = float.MaxValue;
            Vector2Int _closestCenter = Vector2Int.zero;

            foreach (Vector2Int _center in roomCenterList)
            {
                float _curDistance = Vector2Int.Distance(curCenter, _center);
                if (_curDistance < _distance)
                {
                    _distance = _curDistance;
                    _closestCenter = _center;
                }
            }

            return _closestCenter;
        }
    }
}

 

2. 맵 분리코드

    public static List<BoundsInt> BinarySpacePartitioning(BoundsInt _spaceSplited, int _minWidth, int _minHeight)
    {
        Queue<BoundsInt> _roomList = new Queue<BoundsInt>();
        List<BoundsInt> _roomListTemp = new List<BoundsInt>();
        _roomList.Enqueue(_spaceSplited);

        while (_roomList.Count > 0)
        {
            BoundsInt _room = _roomList.Dequeue();
            // 현재 수직 또는 수평으로 나눠준다.
            if (_room.size.x >= _minWidth && _room.size.y >= _minHeight)
            {
                if (Random.value < 0.5f)
                {
                    if (_room.size.x >= _minWidth * 2)
                    {
                        SplitVertically(_room, _roomList, _minWidth);
                    }
                    else if (_room.size.y >= _minHeight * 2)
                    {
                        SplitHorizontally(_room, _roomList, _minHeight);
                    }
                    else
                    {
                        _roomListTemp.Add(_room);
                    }
                }
                else
                {
                    if (_room.size.y >= _minHeight * 2)
                    {
                        SplitHorizontally(_room, _roomList, _minHeight);
                    }
                    else if (_room.size.x >= _minWidth * 2)
                    {
                        SplitVertically(_room, _roomList, _minWidth);
                    }
                    else
                    {
                        _roomListTemp.Add(_room);
                    }
                }
            }
        }

        return _roomListTemp;
    }

    private static void SplitHorizontally(BoundsInt _room, Queue<BoundsInt> _roomList, int _minHeight)
    {
        int _splitPointY = Random.Range(_minHeight, _room.size.y - _minHeight);
        BoundsInt _room1 = new BoundsInt(_room.min, new Vector3Int(_room.size.x, _splitPointY, _room.size.z));
        BoundsInt _room2 = new BoundsInt(new Vector3Int(_room.min.x, _room.min.y + _splitPointY, _room.size.z),
            new Vector3Int(_room.size.x, _room.size.y - _splitPointY, _room.size.z));

        _roomList.Enqueue(_room1);
        _roomList.Enqueue(_room2);
    }

    private static void SplitVertically(BoundsInt _room, Queue<BoundsInt> _roomList, int _minWidth)
    {
        int _splitPointX = Random.Range(_minWidth, _room.size.x - _minWidth);
        BoundsInt _room1 = new BoundsInt(_room.min, new Vector3Int(_splitPointX, _room.size.y, _room.size.z));
        BoundsInt _room2 = new BoundsInt(new Vector3Int(_room.min.x + _splitPointX, _room.min.y, _room.size.z),
                           new Vector3Int(_room.size.x - _splitPointX, _room.size.y, _room.size.z));

        _roomList.Enqueue(_room1);
        _roomList.Enqueue(_room2);
    }
}

 

만들다 보니 한가지 서로 연결하는 방식을 생각해 보았는데 서로 나누어 주면서 그래프 처럼 up, left, right, down에 방을 미리 연결해 두는 것이다 이렇게 방을 연결해 두면 이 연결을 따라 맵 순간이동을 구현할 수도 있으니 좋은 방식인것 같은데 한번 구현해봐야 겠다