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

* 초록색은 스타트룸, 회색은 안전가옥 , 빨간색은 보스룸이다.

10X10

10X10

10X10

5X5

5X5

8X5

7X4

15X25

시작지점을 랜덤한 포인트로 3군데를 잡아주고 해당 포인트들을 비교하여 거리가 가장 먼 두곳을 스타트 포인트와 엔드 포인트로 잡아주고 남은 하나의 포인트를 안전가옥으로 잡아주었다.

그리고 보스룸까지는 A*알고리즘을 반대로 사용하였고(가중치가 가장 높은 루트) 반대로 안전가옥까지는 가중치가 낮은 원래의 알고리즘을 적용하였다.

 

현재 A* 알고리즘을 사용하는 스크립트에서 경로 리스트를 반환하면 보스룸을 향하는 길 리스트와 같은 값을 반환하는 문제가 있는데 해결하지 못하고 일단 두개의 스크립트(...;;) 를 만들어 해결하였다.

물론 해결했다기 보단 구현했다는게 맞을것이다 안전 가옥의 경우 몇몇 경우 보스방으로 가는 길목에 위치하는 경우도 있어 이런경우를 막기 위해 ( 원래는 길목에 위치하지 못하게 하려 했다.)

 

결론적으로 봤을때 맵의 배열이 작아질수록 맵이 오밀조밀해지는 문제가 생기고 맵이 커질수록 문제가 사라지긴 하지만 랜덤성이 강해 초반에 정해준 3개의 포인트 외에 여러 포인트를 더 정해주고 해당 포인트 들 사이에서 고르게 하는게 나을지도 모르겠다.

 

일단 오늘은 여기까지

 

using UnityEngine;
using System;
using System.Text;
using System.Collections.Generic;
using System.Linq;
using static AstarLogic;
using static AstarLogic2;

public class MapGenerator : MonoBehaviour
{
    public AstarLogic astarLogic;
    public AstarLogic2 astarLogic2;

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

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

    private List<float> disList;

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


    public Vector2 startRoomPos;
    public Vector2 endRoomPos;
    public Vector2 safeHousePos;

    private int[,] mapLocation;


    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);
        //새로운 리스트 생성
        var sortedList = new List<Vector2>();
        sortedList.Add(furthestPoints[0]);
        sortedList.Add(furthestPoints[1]);
        sortedList.AddRange(temp.Except(furthestPoints).OrderBy(p => Vector2.Distance(p, furthestPoints[0])));
        sortedList.ForEach(point => { Debug.Log(point); });





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


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

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

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

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

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


        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} vectorList 값 : {1}</color>", sortedList[0], this.mapVectorPos[i, j]);
                    startX = j;
                    startY = i;
                }
                else if(this.mapVectorPos[i,j] == this.endRoomPos)
                {
                    Debug.LogFormat("<color=yellow>보스룸 위치 : {0} vectorList 값 : {1}</color>", sortedList[1], this.mapVectorPos[i, j]);
                    bossX = j;
                    bossY = i;
                }
                else if(this.mapVectorPos[i,j] == this.safeHousePos)
                {
                    Debug.LogFormat("<color=yellow>세이프 하우스 위치 : {0} vectorList 값 : {1}</color>", sortedList[2], this.mapVectorPos[i, j]);
                    safeX = j;
                    safeY = i;               
                }
            }
        }

        List<AStarNode> toBossList;
     
        this.astarLogic.Init(this.maxCol, this.maxRow, startX, startY, bossX, bossY, out toBossList);

        List<AStarNode2> toSafeHouseList;

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


        //for (int i = 0; i < this.maxRow; i++)
        //{
        //    for (int j = 0; j < this.maxCol; j++)
        //    {
        //        if (j == startX && i == startY || j == bossX && i == bossY)
        //        {
        //            this.mapLocation[j, i] = 1;
        //            Debug.Log("방 있는곳 발견");
        //        }
        //        else
        //        {
        //            this.mapLocation[j, i] = 0;

        //        }
        //        sb.Append(string.Format("{0}\t", this.mapLocation[j, i]));
        //    }
        //}
        //Debug.LogFormat(sb.ToString());

        toBossList.ForEach(t => { Debug.LogFormat("보스방까지의 노드 리스트 :{0} , {1}",t.x,t.y);});
        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;
            Debug.LogFormat("생성된 일반맵 위치 : {0}", (Vector2)go.transform.position);
            if ((Vector2)go.transform.position == this.startRoomPos)
            {
                Destroy(go);
            }
            else if ((Vector2)go.transform.position == this.endRoomPos)
            {
                Destroy(go);
            }
            else if ((Vector2)go.transform.position == this.safeHousePos)
            {
                Destroy(go);
            }
        }

        foreach (AStarNode2 node in toSafeHouseList)
        {
            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;
                Debug.LogFormat("두번째로 일반맵 위치 : {0}", (Vector2)go.transform.position);

            }

        }

        for (int i = 0; i < this.maxRow; i++)
        {
            for (int j = 0; j < this.maxCol; j++)
            {        
                sb.Append(string.Format("{0}\t", this.mapLocation[i, j]));
            }
        }
        Debug.LogFormat(sb.ToString());
    }




    private void MakeRanLocation( )
    {
        int cunt = 0;
        while (cunt !=3)
        {
            Debug.Log("count");
            var X = UnityEngine.Random.Range(0, this.maxRow);
            var Y = UnityEngine.Random.Range(0, this.maxCol);
            if(cunt == 3) { break; }
            else if (this.mapLocation[X, Y] == 1)
            {
                continue;
            }
            else
            {
                this.mapLocation[X, Y] = 1;
                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();

        
        return new List<Vector2> { furthestPoints.p1, furthestPoints.p2 };
    }
}