[유니티 프로젝트] 이차원 배열과 A* 알고리즘을 사용한 랜덤 맵 생성 .2

A* 알고리즘을 이용하여 반대로 시작지점에서 가장 "먼" 지점의 (가중치가 가장 높은) 맵을 거쳐 보스방으로의 길을 생성하게 하였다.

알고리즘의 경우 100% 내것으로 만들어 사용하지 못하였으나 어느정도 굵은 개요는 이해했기에 좀더 다양하게 응용하여 추가적인 맵을 생성해볼 예정이다.

(초록색은 시작 맵, 파란색은 보스방까지 이어주는 복도맵들이다, 붉은 색은 보스방이다.)

맵 배열 사이즈는 정사각형 또는 직사각형에 상관없이 다양한 모습으로 맵이 생성된다.

 

 

맵 제너레이터( or Director)

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

public class MapGenerator : MonoBehaviour
{
    public AstarLogic astarLogic;   

    public int maxRow;
    public int maxCol;

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

    public GameObject startRoom;
    public GameObject BossRoom;

    public Vector2 startRoomPos;
    public Vector2 endRoomPos;


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

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

        this.compareDic = new Dictionary<Vector2,float>();
        var ranCol = UnityEngine.Random.Range(0,maxCol);
        var ranRaw = UnityEngine.Random.Range(0,maxRow);

        for (int i = 0; i < this.maxRow; i++)
        {
            for (int j = 0; j < this.maxCol; j++)
            {
                var dist = Vector2.Distance(this.mapPos[ranCol, ranRaw] , this.mapPos[j, i]);
                this.compareDic.Add(this.mapPos[j, i], dist);
            }           
        }

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

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

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

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

        int endX = 0;
        int endY = 0;   
        for (int i = 0; i < this.maxRow; i++)
        {
            for (int j = 0; j < this.maxCol; j++)
            {
                if (this.mapPos[j,i] == BossRoomPos.Key)
                {
                    endX = j;
                    endY = i;
                    break;
                }
             
            }
        }

        List<AStarNode> list;
        astarLogic.Init(this.maxCol, this.maxRow, ranCol, ranRaw, endX, endY, out list);

        int newx = 32;
        int newy = -32;
        foreach (AStarNode node in list) 
        {
            
           var go =  GameObject.Instantiate(this.startRoom);
            go.transform.position = new Vector2(node.x* newx, node.y* newy);
            if(go.transform.position == bossRoomGo.transform.position)
            {
                Destroy(go);
            }
        }
        
    }
}

A*알고리즘

 

using System.Collections.Generic;
using System.Numerics;
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 = new List<AStarNode>();
    private List<AStarNode> closeList = new List<AStarNode>();

    public Vector2Int TestStartLocation;    // 시작 위치
    public Vector2Int TestEndLocation;      // 도착 위치
    public int TestXSize;       // 맵 X크기
    public int TestYSize;       // 맵 Y크기

    public MapGenerator mapgen;

    [ContextMenu("테스트")]
    public void Init(int maxCol, int maxRaw, int startX, int startY, int endX, int endY, out List<AStarNode> t)
    {
        CreateNode(maxCol, maxRaw);
        SetTargetLocation( startX, startY,  endX, endY);
        t = PathFinding();
     
         
    }

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

        for (int x = 0; x < xSize; x++)
        {
            for (int y = 0; y < ySize; y++)
            {             
                this.nodes[x, y] = new AStarNode(x, y);
            }
        }
    }

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

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

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

        while (openList.Count > 0)
        {
            // 갈 수 있는 길 중에 가중치가 낮은 길을 찾는다.
            this.currentNode = this.openList[0];
            for (int i = 1; i < 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);
        }
    }
}

현재 제작한 맵 제너 레이터의 한계로는 그리드의 사이즈 별로 좀 더 다양한 모양의 맵 구성이 나오지 못한다는 것인데 이건 랜덤한 포인트(완전 랜덤은 아니다)를 지정하여 안전가옥 맵  또는 히든 맵을 넣어주면 좀더 버라이어티한 맵 구성이 나올수 있을것으로 기대한다.