[유니티 프로젝트] A*알고리즘을 이용한 랜덤 맵 생성 .3

기존구성에서 랜덤하게 히든 룸을 선정해주는 코드를 추가하였다. (히든룸은 암상인의 출현 지역이다)

전체적인 알고리즘은 이러하다

 

우선 스테이지의 최대 룸 생성 가능 갯수중 3분의 1만큼의 랜덤한 영역을 정하고 해당 영역들의 벡터값을 비교하여 가장 먼 룸 두개를 선정해주었다.

그 후 두 포지션중 하나를 스타트룸과 보스룸(스테이지 엔드조건) 으로 잡아주고 스타트룸부터 보스룸까지의 경로를 A*알고리즘을 뒤집어 최대경로를 뽑아내었다.

이후 해당 경로들을 이어주고 보스룸 까지의 경로들중 선정되지 못한 경로들을 모아 가중치가 가장 높은 포지션 (시작 룸과 가장 멀리 떨어져 있는 포지션) 을 안전구역으로 잡아주고 다시 시작지점까지의 최대 가중치 경로로 이어주었다 (만약 중간에 미리 만들어준 방들이 존재한다면 패스)

이후 랜덤한 확률에 따라 (아직 확률을 정하지 않아 일단 확정적으로 생성되게 하였다.) 히든룸 출현 여부를 결정하고 히든맵이 출현한다면 이미 만들어진 경로들중 스타트룸과 안전가옥 보스룸을 제외한 나머지 경로들중 하나를 잡아 히든룸을 생성시켜주었다. (이미 있던 일반룸은 파괴한다)

5X6

5X6

4x4

10X10

10X15

10X15

12X12

3X3

*아직 코드정리는 하지 않았다.

작동해보니 히든룸은 최소 4X4 사이즈 이상일때 등장시키는게 이상적일듯 하다.

 

맵 제너레이터 

using UnityEngine;
using System;
using System.Text;
using System.Collections.Generic;
using System.Linq;
using static AstarLogic;
using System.Collections;
using Unity.VisualScripting;
using UnityEditor.Experimental.GraphView;

public class MapGenerator : MonoBehaviour
{
    public AstarLogic astarLogic;

    public int maxRow;
    public int maxCol;
    public int mapDist = 32;

    private Vector2[,] mapVectorPos;
    private Dictionary<Vector2, float> compareDic;

    private List<GameObject> normalRoomList;

    public GameObject startRoom;
    public GameObject BossRoom;
    public GameObject normalRoom;
    public GameObject safeHouseRoom;
    public GameObject hiddemRoom;


    public Vector2 startRoomPos;
    public Vector2 BossRoomPos;
    public Vector2 safeHousePos;
    public Vector2 hiddemRoomPos;

    private int[,] mapLocation;

    public bool isHiddenRoom = false;


    public void Awake()
    {
        this.mapVectorPos = new Vector2[maxRow, maxCol];
        this.mapLocation = new int[maxRow, maxCol];

        //this.compareDic = new Dictionary<Vector2, float>();




        StringBuilder sb = new StringBuilder();

        int x = 0;
        int y = 0;

        for (int i = 0; i < this.maxRow; i++)
        {
            for (int j = 0; j < this.maxCol; j++)
            {
                this.mapVectorPos[i,j] = new Vector2(x, y);
                sb.Append(string.Format("{0}.{1}({2},{3})\t", i, j, x, y));
                x += this.mapDist;
            }
            y -= this.mapDist;
            x = 0;
            sb.Append('\n');
        }

        Debug.LogFormat(sb.ToString());
        sb.Clear();

        //var startX = UnityEngine.Random.Range(0, this.maxCol);
        //var startY = UnityEngine.Random.Range(0, this.maxRow);

        //for (int i = 0; i < this.maxRow; i++)
        //{
        //    for (int j = 0; j < this.maxCol; j++)
        //    {
        //        var dist = Vector2.Distance(this.mapVectorPos[startX, startY], this.mapVectorPos[j, i]);
        //        this.compareDic.Add(this.mapVectorPos[j, i], dist);
        //    }
        //}

        this.MakeRanLocation();
       

        List<Vector2> temp = new List<Vector2>();   

        for (int i = 0; i < this.maxRow; i++)
        {
            for (int j = 0; j < this.maxCol; j++)
            {
                if (this.mapLocation[i,j] == 1)
                {
                    temp.Add(new Vector2(j * this.mapDist, i * -this.mapDist));
                    sb.Append(string.Format("{0}.{1}({2},{3})\t", i, j, j * this.mapDist, i * -this.mapDist));
                }
                
            }
        }

        Debug.LogFormat(sb.ToString());
        sb.Clear();

        // 리스트에서 가장 거리가 먼 두 점을 찾기
        var furthestPoints = FindFurthestPoints(temp);
        
        //sortedList.ForEach(point => { Debug.Log(point); });


        this.startRoomPos = furthestPoints[0];
        Debug.LogFormat("<color=blue>시작룸 위치 : {0}</color>", this.startRoomPos);

        this.BossRoomPos = furthestPoints[1];
        Debug.LogFormat("<color=red>보스방 위치 : {0}</color>", this.BossRoomPos);
        //var BossRoomPos = this.compareDic.First(x => x.Value == this.compareDic.Values.Max());

        //this.safeHousePos = furthestPoints[2];
        //Debug.LogFormat("<color=green>세이프 하우스 위치 : {0}</color>", this.BossRoomPos);

        var startRoomGo = GameObject.Instantiate(this.startRoom);
        startRoomGo.transform.position = this.startRoomPos;

        var bossRoomGo = GameObject.Instantiate(this.BossRoom);
        bossRoomGo.transform.position = this.BossRoomPos;

        //var safeHouseGo = GameObject.Instantiate(this.safeHouseRoom);
        //safeHouseGo.transform.position = this.safeHousePos;

        List<Vector2> tempVecList = new List<Vector2>();
        tempVecList.Add(this.startRoomPos);
        tempVecList.Add(this.BossRoomPos);
       


        //2차원 맵 배열에서 실제로 방이 없는 곳 초기화

        for (int i = 0; i < this.maxRow; i++)
        {
            for (int j = 0; j < this.maxCol; j++)
            {
                if (this.mapLocation[i, j] == 1)
                {
                    if(!tempVecList.Contains(new Vector2(j * this.mapDist, i * -this.mapDist)))
                    {
                        this.mapLocation[i, j] = 0;
                    }
                }
            }
        }



        int startX = 0;
        int startY = 0;
        int bossX = 0;
        int bossY = 0;
        int safeX = 0;
        int safeY = 0;

        for (int i = 0; i < this.maxRow; i++)
        {
            for (int j = 0; j < this.maxCol; j++)
            {
                if (this.mapVectorPos[i,j] == this.startRoomPos)
                {
                    Debug.LogFormat("<color=yellow>시작룸 위치 : {0},{1} vectorList 값 : {2}</color>", i,j, this.mapVectorPos[i, j]); ; ;
                    startX = j;
                    startY = i;
                }
                else if(this.mapVectorPos[i,j] == this.BossRoomPos)
                {
                    Debug.LogFormat("<color=yellow>보스룸 위치 : {0},{1} vectorList 값 : {2}</color>",i,j, this.mapVectorPos[i, j]);
                    bossX = j;
                    bossY = i;
                }
            }
        }
        this.normalRoomList = new List<GameObject> ();
        List<AStarNode> toBossList;
        List<AStarNode> nonSelectedList;
     
        this.astarLogic.Init(this.maxCol, this.maxRow, startX, startY, bossX, bossY, out toBossList ,out nonSelectedList);
        toBossList.ForEach(t => { Debug.LogFormat("보스방까지의 노드 리스트 :{0} , {1}", t.y, t.x); });
        Debug.Log(toBossList.Count);
        //List<AStarNode> toSafeHouseList;

        //this.astarLogic.Init(this.maxCol, this.maxRow, startX, startY, safeX, safeY, out toSafeHouseList);


        nonSelectedList.ForEach(t => { Debug.LogFormat("선택받지 못한 노드 리스트 :{0},{1}\n가중치 : {2}",t.y,t.x,t.G);});
        //toSafeHouseList.ForEach(t => { Debug.LogFormat("세이프 하우스 까지의 노드 리스트 :{0} , {1}", t.x, t.y); });

        foreach (AStarNode node in toBossList)
        {
            var go = GameObject.Instantiate(this.normalRoom);
            go.transform.position = new Vector2(node.y * this.mapDist, node.x * -this.mapDist);
            this.mapLocation[node.x, node.y] = 1;
            this.normalRoomList.Add(go);
            Debug.LogFormat("생성된 보스방까지의 일반맵 위치 : {0}", (Vector2)go.transform.position);
            if ((Vector2)go.transform.position == this.startRoomPos)
            {
                this.normalRoomList.Remove(go);
                Destroy(go);
            }
            else if ((Vector2)go.transform.position == this.BossRoomPos)
            {
                this.normalRoomList.Remove(go);
                Destroy(go);
            }
        }

        
        nonSelectedList.Sort((x, y) => y.G.CompareTo(x.G));
        nonSelectedList.ForEach(t => { Debug.LogFormat("선택받지 못한 노드 리스트 정렬 후 :{0} , {1}\n가중치 : {2}", t.y, t.x, t.G); });

        if(nonSelectedList.Count != 0)
        {
            safeX = nonSelectedList[0].x;
            safeY = nonSelectedList[0].y;
            var safeGo = UnityEngine.Object.Instantiate(this.safeHouseRoom);
            this.safeHousePos = new Vector2(safeY * this.mapDist, safeX * -this.mapDist);
            safeGo.transform.position = this.safeHousePos;
            this.mapLocation[safeX, safeY] = 1;
        }
        else
        {
            Vector2 tempVector;
            while (true)
            {
                safeY = UnityEngine.Random.Range(0, this.maxRow);
                safeX = UnityEngine.Random.Range(0, this.maxCol);
                tempVector = new Vector2(safeX * this.mapDist, safeY * -this.mapDist);
                if (this.mapLocation[safeY, safeX] == 1 && tempVector != this.startRoomPos && tempVector != this.BossRoomPos)
                {
                    var hiddenGO = UnityEngine.Object.Instantiate(this.safeHouseRoom);
                    this.safeHousePos = tempVector;
                    hiddenGO.transform.position = this.safeHousePos;
                    this.mapLocation[safeY, safeX] = 1;
                    break;
                }
                tempVector = Vector2.zero;
            }
        }
        

        

        List<AStarNode> toStartList;
        this.astarLogic.Init(this.maxCol, this.maxRow, safeY, safeX,startX ,startY , out toStartList, out nonSelectedList);



        foreach (AStarNode node in toStartList)
        {
            if (this.mapLocation[node.x, node.y] == 1) continue;
            else
            {
                var go = GameObject.Instantiate(this.normalRoom);
                go.transform.position = new Vector2(node.y * this.mapDist, node.x * -this.mapDist);
                this.mapLocation[node.x, node.y] = 1;
                this.normalRoomList.Add(go);
                Debug.LogFormat("세이프 하우스로 향하는 일반맵 위치 : {0}", (Vector2)go.transform.position);
                
            }         
            
        }

       

        if (this.isHiddenRoom)
        {
            Vector2 tempVector;
            while (true)
            {
                var Y = UnityEngine.Random.Range(0, this.maxRow);
                var X = UnityEngine.Random.Range(0, this.maxCol);
                tempVector = new Vector2(X * this.mapDist, Y * -this.mapDist);
                if (this.mapLocation[Y, X] == 1 && tempVector != this.startRoomPos && tempVector != this.BossRoomPos && tempVector != this.safeHousePos)
                {
                    var hiddenGO = UnityEngine.Object.Instantiate(this.hiddemRoom);
                    this.hiddemRoomPos = tempVector;
                    hiddenGO.transform.position = this.hiddemRoomPos;
                    this.mapLocation[Y, X] = 1;                  
                    break;
                }
                tempVector = Vector2.zero;
            }           
        }

        for(int i = 0; i < this.normalRoomList.Count;i++)
        {
            if ((Vector2)this.normalRoomList[i].transform.position == this.hiddemRoomPos) 
            {
                Debug.Log("노말룸 파괴");
                Destroy(this.normalRoomList[i]);
                this.normalRoomList.Remove(this.normalRoomList[i]);
            }
        }

        for (int i = 0; i < this.maxRow; i++)
        {
            for (int j = 0; j < this.maxCol; j++)
            {        
                sb.Append(string.Format("<color=pink>{0}</color>\t", this.mapLocation[i, j]));
            }
        }
        Debug.LogFormat("====최종 배열====");
        Debug.LogFormat(sb.ToString());
    }


    private void MakeRanLocation( )
    {
        int cunt = 0;
        while (cunt !=(this.maxCol*this.maxRow)/3)
        {
            var X = UnityEngine.Random.Range(0, this.maxRow);
            var Y = UnityEngine.Random.Range(0, this.maxCol);
            if(cunt == (this.maxCol * this.maxRow) / 3) { break; }
            else if (this.mapLocation[X, Y] == 1)
            {
                continue;
            }
            else
            {
                this.mapLocation[X, Y] = 1;
                cunt++;
            }          
        }
        Debug.LogFormat("생성된 랜덤 포인트들 {0}", cunt);
    }

    List<Vector2> FindFurthestPoints(List<Vector2> points)
    {
        // 리스트에서 가능한 모든 두 점 쌍을 생성한다.
        var pairs = from p1 in points
                    from p2 in points
                    where p1 != p2
                    select new { p1, p2 };

        // 각 쌍의 거리를 계산
        var distances = pairs.Select(pair => new { pair.p1, pair.p2, distance = Vector2.Distance(pair.p1, pair.p2) });

        // 거리가 가장 먼 두 점을 찾는다.
        var furthestPoints = distances.OrderByDescending(pair => pair.distance).First();

        
        var top2List = new List<Vector2> { furthestPoints.p1, furthestPoints.p2 };

        //새로운 리스트 생성
        var sortedList = new List<Vector2>();
        sortedList.Add(top2List[0]);
        sortedList.Add(top2List[1]);
        sortedList.AddRange(points.Except(top2List).OrderBy(p => Vector2.Distance(top2List[0],p)));

        return sortedList;  
    }
}

A* 알고리즘

using System.Collections.Generic;
using System.Numerics;
using System.Text;
using UnityEngine;

public class AstarLogic : MonoBehaviour
{
    public class AStarNode
    {
        public AStarNode ParentNode;

        // G : 시작노드부터 이동하려는 위치 거리
        // H : 시작노드부터 목표지점까지 거리(타일 칸 수)
        // F : G + H
        public int x, y, G, H;

        public int F
        {
            get
            {
                return G + H;
            }
        }

        public AStarNode(int x, int y)
        {
            this.x = x;
            this.y = y;
        }
    }

    private AStarNode[,] nodes;
    private AStarNode startNode;
    private AStarNode endNode;
    private AStarNode currentNode;
    private List<AStarNode> openList;
    private List<AStarNode> closeList;

    private List<AStarNode> nonSelectedList;

    private StringBuilder sb;

    public void Init(int maxCol, int maxRaw, int startX, int startY, int targetX, int targetY, out List<AStarNode> toBossList, out List<AStarNode> nonSelectedList)
    {
        this.nonSelectedList = new List<AStarNode>();

        this.openList = new List<AStarNode>();
        this.closeList = new List<AStarNode>();
        this.sb = new StringBuilder();


        Debug.LogFormat("들어온 타겟 x,y : {0},{1}", targetY, targetX);

        CreateNode(maxCol, maxRaw);
        SetTargetLocation(startX, startY, targetX, targetY);
        PathFinding();

        toBossList = this.closeList;
        nonSelectedList = this.nonSelectedList;
        Debug.LogFormat("방문리스트 방 갯수{0}",this.closeList.Count);    
            
    }

    /// <summary>
    /// x,y 크기에 맞는 노드 배열을 만든다.
    /// </summary>
    public void CreateNode(int maxCol, int maxRaw)
    {
        this.nodes = new AStarNode[maxRaw, maxCol];

        for (int y = 0; y < maxRaw; y++)
        {
            for (int x = 0; x < maxCol; x++)
            {             
                this.nodes[y, x] = new AStarNode(y, x);
                this.sb.Append(string.Format("<color=white>{0},{1}\t</color>", this.nodes[y, x].x, this.nodes[y, x].y));

            }
        }
        Debug.Log("====생성된 노드 리스트====");
        Debug.Log(this.sb.ToString());
        this.sb.Clear(); 
    }

    /// <summary>
    /// 시작 지점과 목표 지점
    /// </summary>
    public void SetTargetLocation(int startX, int startY, int targetX, int targetY)
    {
        this.startNode = this.nodes[startY, startX];
        this.endNode = this.nodes[targetY, targetX];
    }

    /// <summary>
    /// 길 찾기 알고리즘
    /// </summary>
      public List<AStarNode> PathFinding()
    {
        this.openList.Clear();   // 갈 수 있는 길 목록
        this.closeList.Clear();  // 한번 들른 곳 목록

        // 맨 처음에는 시작 지점부터
        this.openList.Add(this.startNode);

        while (openList.Count > 0)
        {
            // 갈 수 있는 길 중에 가중치가 낮은 길을 찾는다.
            this.currentNode = this.openList[0];
            for (int i = 1; i < this.openList.Count; ++i)
            {
                if (this.openList[i].F >= this.currentNode.F &&
                    this.openList[i].H < this.currentNode.H)
                {
                    this.currentNode = this.openList[i];
                }
            }

            // 찾은 길은 갈 수 있는 곳 목록에서 지운다.
            // 한번 들른 곳 목록에 넣어준다.
            // 이로써 한번 갔던 길을 중복으로 검색하는 일은 없어진다.
            this.openList.Remove(this.currentNode);
            this.closeList.Add(this.currentNode);

            // 목적지에 도착했는지 체크한다.
            if (this.currentNode == this.endNode)
            {
                for (int i = 0; i < this.closeList.Count; i++)
                    Debug.Log(i + "번째는 " + this.closeList[i].x + ", " + this.closeList[i].y);
                return this.closeList;
            }

            // 갈 수 있는 길을 찾아서 목록에 넣어준다.
            // 순서는 일반적으로 위 -> 오른쪽 -> 아래 -> 왼쪽 순이다.
            OpenListAdd(this.currentNode.x, this.currentNode.y + 1);
            OpenListAdd(this.currentNode.x + 1, this.currentNode.y);
            OpenListAdd(this.currentNode.x, this.currentNode.y - 1);
            OpenListAdd(this.currentNode.x - 1, this.currentNode.y);
        }
        return this.closeList;   
    }

     void OpenListAdd(int checkX, int checkY)
    {
        // 상하좌우 범위를 벗어났다면 빠져나온다.
        if (checkX < 0 || checkX >= this.nodes.GetLength(0) || checkY < 0 || checkY >= this.nodes.GetLength(1))
            return;

        // 한번 들른 곳이면 빠져나온다.
        if (this.closeList.Contains(this.nodes[checkX, checkY]))
            return;

        // 이동 비용을 구한다.
        // 직선 : 현재 위치의 G + 10 (현재 위치 - 확인할 위치를 계산하여 x,y중 하나라도 0인 경우)
        // 대각선 : 현재 위치의 G + 14 (현재 위치 - 확인할 위치를 계산하여 x,y 둘 다 0이 아닌 경우)
        // 직선의 비용은 10
        // 대각선의 비용은 14
        AStarNode NeighborNode = this.nodes[checkX, checkY];
        int MoveCost = this.currentNode.G + (this.currentNode.x - checkX == 0 || this.currentNode.y - checkY == 0 ? 10 : 14);

        // 이동 비용이 확인할 위치의 G보다 작거나
        // 갈 수 있는 길 목록에서 현재 확인하려는 위치가 없다면
        if (MoveCost < NeighborNode.G || !this.openList.Contains(NeighborNode))
        {
            // 이동비용, 거리, 현재 위치를 담는다.
            NeighborNode.G = MoveCost;
            NeighborNode.H = (Mathf.Abs(NeighborNode.x - this.endNode.x) + Mathf.Abs(NeighborNode.y - this.endNode.y)) * 10;
            NeighborNode.ParentNode = this.currentNode;

            // 위와 같은 방법을 통해 parentNode가 시작점과 이어지게 된다.
            // 예)
            // 시작점 : x:0,y:0
            // 도착점 : x:2,y:0
            // 도착점(2,0) -> 이전(1,0) -> 시작점(0,0)으로 연결 되어 있다.

            this.openList.Add(NeighborNode);
        }
        else
        {
            this.nonSelectedList.Add(NeighborNode);
        }
    }
}