[랜덤 맵 생성] A* 알고리즘을 이용한 절차적 맵 제작 방법 정리

A* 알고리즘을 이용한 절차적 맵 생성은 아래와 같은 단계로 이루어져 있다.

 

• 맵 생성 절차

1. 우선 맵의 배열 수를 정해준다.  정해준 MAX ROW ,MAX COL 은  2차원 배열로 맵의 전체 크기를 뜻한다.

2. 정해진 2차원 배열의 인덱스중 절반을 중복되지 않게 무작위로 고른다. 

private void MakeRanLocation()
    {
        int cunt = 0;
        while (cunt <= Math.Ceiling((double)(this.maxCol * this.maxRow) / 2))
        {
            var Y = UnityEngine.Random.Range(0, this.maxRow);
            var X = UnityEngine.Random.Range(0, this.maxCol);
            if (this.mapLocation[Y, X] == 1)
            {
                continue;
            }
            else
            {
                this.mapLocation[Y, X] = 1;
                cunt++;
            }
        }
    }

3. 이후 무작위로 정해진 배열 인덱스에 룸의 길이만큼을 곱해 룸의 위치를 담은 vector2 값을 배열에 저장한다.(룸은 가로와 새로의 비율이 1대1이다)

 // 만든 랜덤 포인트 들을 임시리스트에 저장
        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));
                }

            }
        }

4. 이렇게 생성된 Vector2  리스트들을 각각 비교하여 가장 거리가 먼 두지점과 2번째로 거리가 먼 지점을 정해준다.

private 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;
    }

5. 생성된 리스트중 0번 인덱스를 Start 룸으로 지정해주고 1번째 인덱스를 boss 룸으로 지정해준다. 이후 4번째 인덱스 (Vector2 List 인덱스 들중 보스지점 에서 2번째로 가까운 지점) 을 선택해 안전가옥으로 지정해준다.

 

// 리스트에서 가장 거리가 먼 두 점을찾아 내림차순으로 넣은 Vecotr2 리스트 생성
        var furthestPoints = FindFurthestPoints(temp);

        //스타트 Vector2 포지션
        this.startRoomPos = furthestPoints[0];
        // 보스룸 Vector2 포지션
        this.BossRoomPos = furthestPoints[1];
        //안전가옥 Vector2 포지션
        if(this.maxCol*this.maxRow <= 6)
        {
            this.safeHousePos = furthestPoints[furthestPoints.Count - 1];

        }
        else
        {
            this.safeHousePos = furthestPoints[furthestPoints.Count - 2];
        }
      
        //시작룸 생성
        var startRoomGo = GameObject.Instantiate(this.startRoom);
        startRoomGo.transform.position = this.startRoomPos;
        this.wholeRoomList.Add(startRoomGo);

        //보스룸 생성
        var bossRoomGo = GameObject.Instantiate(this.BossRoom);
        bossRoomGo.transform.position = this.BossRoomPos;
        this.wholeRoomList.Add(bossRoomGo);

        //안전가옥 생성
        var safeHouseGo = GameObject.Instantiate(this.safeHouseRoom);
        safeHouseGo.transform.position = this.safeHousePos;
        this.wholeRoomList.Add(safeHouseGo);

 

6. a* 알고리즘을 역으로 적용하여 시작룸에서 보스룸 까지 가중치가 가정 큰 배열 인덱스 리스트를 생성하여 해당 위치에 복도 역할을 겸하는 일반룸들을 생성해준다.

자세한 사항은 아래 A* 분석 글 참조

https://bueong-e.tistory.com/256

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

7. 이번에도 A*알고리즘을 이용하지만 역으로 세이프 하우스 지점에서 스타트 룸까지 가장 가중치가 큰 루트 리스트를 생성하여 일반룸을 생성해준다 (만약 이미 일반룸이 자리에 있으면 더 이상 생성하지 않는다)

List<AStarNode> toBossList = new List<AStarNode>();

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

        toBossList.ForEach(t => { Debug.LogFormat("보스 방까지의 노드 리스트 :{0} , {1}", t.y, t.x); });

        List<AStarNode> toSafeHouseList = new List<AStarNode>();

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

        toSafeHouseList.ForEach(t => { Debug.LogFormat("안전 가옥 부터 스타트 까지의 노드 리스트 :{0} , {1}", t.y, t.x); });



        //보스방 까지의 일반 룸 생성
        foreach (AStarNode node in toBossList)
        {
            var checkVec = new Vector2(node.x * this.mapDist, node.y * -this.mapDist);
            if (checkVec == this.startRoomPos || checkVec == this.BossRoomPos || checkVec == this.safeHousePos) continue;
            else
            {
                //생성후 포지션 잡아주기
                var go = GameObject.Instantiate(this.normalRoom);
                go.transform.position = new Vector2(node.x * this.mapDist, node.y * -this.mapDist);
                //2차원 맵 배열에 표시
                this.mapLocation[node.y, node.x] = 1;
                //일반룸 리스트에 목록 추가
                this.normalRoomList.Add(go);
                this.wholeRoomList.Add(go);
                sb.Append(String.Format("({0},{1}) {2}", node.y, node.x, checkVec));
            }
        }

        Debug.Log("====보스방까지 생성된 일반룸 목록 ====");
        Debug.Log(sb.ToString());
        sb.Clear();

        //세이프 하우스 부터 스타트 룸 까지의 일반 룸 생성
        foreach (AStarNode node in toSafeHouseList)
        {
            var checkVec = new Vector2(node.x * this.mapDist, node.y * -this.mapDist);
            if (this.mapLocation[node.y, node.x] != 0 || checkVec == this.startRoomPos || checkVec == this.BossRoomPos || checkVec == this.safeHousePos) continue;
            else
            {
                //생성후 포지션 잡아주기
                var go = GameObject.Instantiate(this.normalRoom);
                go.transform.position = new Vector2(node.x * this.mapDist, node.y * -this.mapDist);
                //2차원 맵 배열에 표시
                this.mapLocation[node.y, node.x] = 1;
                //일반룸 리스트에 목록 추가
                this.normalRoomList.Add(go);
                this.wholeRoomList.Add(go);
                sb.Append(String.Format("({0},{1}) {2}", node.y, node.x, checkVec));
            }
        }

8.  만약 스테이지가 4스테이지에 접어들면 히든룸을 맵에 배치시켜준다. 히든룸은 일반룸중 하나를 골라 랜덤 생성되며 해당 랜덤 룸은 유저에게는 알려지지 않는다.

private void MakeHiddenRoom()
    {
        //노말룸리스트인덱스 중 랜덤 인덱스 설정
        var num = UnityEngine.Random.Range(0, this.normalRoomList.Count - 1);
        //랜덤 인덱스위치에 히든룸 생성
        var hiddenGO = UnityEngine.Object.Instantiate(this.hiddemRoom);
        this.wholeRoomList.Add(hiddenGO);
        //히든룸 포지션에 랜덤룸 포지션 담기 및 위치 변경
        this.hiddemRoomPos = this.normalRoomList[num].transform.position;
        hiddenGO.transform.position = this.hiddemRoomPos;
        //기존 위치에 있던 노말룸 제거
        Debug.LogFormat("파괴된 노말룸 포지션 {0}", this.hiddemRoomPos);
        Destroy(this.normalRoomList[num]);
        this.normalRoomList.Remove(this.normalRoomList[num]);
        this.wholeRoomList.Remove(this.wholeRoomList.Find(x => (Vector2)x.transform.position == this.hiddemRoomPos));
    }

9. 이제 2창원 맵 배열을 탐색하며 해당 인덱스의 좌 우 , 상,하 를 확인하여 방이 존재한다면 포탈을 생성해준다 (포탈은 이어지는 방의 종류에 따라 다르게 생성해준다)

private void MakePortal()
    {
        //포탈 생성
        for (int i = 0; i < this.maxRow; i++)
        {
            for (int j = 0; j < this.maxCol; j++)
            {
                // 기준방 발견 
                if (this.mapLocation[i, j] != 0)
                {
                    //배열을 벗어나지 않는다면 윗칸 보기
                    if (i - 1 >= 0)
                    {
                        //벗어나지 않았는데 방이 있다면
                        if (this.mapLocation[i - 1, j] != 0)
                        {
                            //생성된 룸 리스트에서 현재 검색중인 배열과 같은 위치에 있는 룸 찾기
                            foreach (var room in this.wholeRoomList)
                            {
                                if ((Vector2)room.transform.position == new Vector2(j * this.mapDist, i * -this.mapDist))
                                {
                                    GameObject go = null;
                                    //찾으면 포탈 생성해서 해당 포인트에 자식으로 넣어주고 로컬 포지션 0으로 초기화
                                    if (this.mapLocation[i - 1, j] == 4)
                                    {
                                        go = Instantiate(this.bossPortal, room.transform.GetChild(0)); // 보스룸
                                    }
                                    else if (this.mapLocation[i - 1, j] == 3)
                                    {
                                        go = Instantiate(this.safeRoomPortal, room.transform.GetChild(0)); //상점
                                    }
                                    else
                                    {
                                        go = Instantiate(this.portal, room.transform.GetChild(0)); // 일반룸
                                    }
                                    go.transform.localPosition = Vector2.zero;
                                }
                            }
                        }
                    }
                    //배열을 벗어나지 않는다면 아랫칸 보기
                    if (i + 1 < this.maxRow)
                    {
                        //벗어나지 않았는데 방이 있다면
                        if (this.mapLocation[i + 1, j] != 0)
                        {
                            //생성된 룸 리스트에서 현재 검색중인 배열과 같은 위치에 있는 룸 찾기
                            foreach (var room in this.wholeRoomList)
                            {
                                if ((Vector2)room.transform.position == new Vector2(j * this.mapDist, i * -this.mapDist))
                                {
                                    GameObject go = null;
                                    //찾으면 포탈 생성해서 해당 포인트에 자식으로 넣어주고 로컬 포지션 0으로 초기화
                                    if (this.mapLocation[i + 1, j] == 4)
                                    {
                                        go = Instantiate(this.bossPortal, room.transform.GetChild(2)); // 보스룸
                                    }
                                    else if (this.mapLocation[i + 1, j] == 3)
                                    {
                                        go = Instantiate(this.safeRoomPortal, room.transform.GetChild(2)); //상점
                                    }
                                    else
                                    {
                                        go = Instantiate(this.portal, room.transform.GetChild(2)); // 일반룸
                                    }
                                    go.transform.localPosition = Vector2.zero;
                                }
                            }
                        }
                    }
                    //배열을 벗어나지 않는다면 오른쪽 칸 보기
                    if (j + 1 < this.maxCol)
                    {
                        //벗어나지 않았는데 방이 있다면
                        if (this.mapLocation[i, j + 1] != 0)
                        {
                            //생성된 룸 리스트에서 현재 검색중인 배열과 같은 위치에 있는 룸 찾기
                            foreach (var room in this.wholeRoomList)
                            {
                                if ((Vector2)room.transform.position == new Vector2(j * this.mapDist, i * -this.mapDist))
                                {
                                    GameObject go = null;
                                    //찾으면 포탈 생성해서 해당 포인트에 자식으로 넣어주고 로컬 포지션 0으로 초기화
                                    if (this.mapLocation[i, j + 1] == 4)
                                    {
                                        go = Instantiate(this.bossPortal, room.transform.GetChild(1)); // 보스룸
                                    }
                                    else if (this.mapLocation[i, j + 1] == 3)
                                    {
                                        go = Instantiate(this.safeRoomPortal, room.transform.GetChild(1)); //상점
                                    }
                                    else
                                    {
                                        go = Instantiate(this.portal, room.transform.GetChild(1)); // 일반룸
                                    }
                                    go.transform.localPosition = Vector2.zero;
                                }
                            }
                        }
                    }
                    //배열을 벗어나지 않는다면 왼쪽 칸 보기
                    if (j - 1 >= 0)
                    {
                        //벗어나지 않았는데 방이 있다면
                        if (this.mapLocation[i, j - 1] != 0)
                        {
                            //생성된 룸 리스트에서 현재 검색중인 배열과 같은 위치에 있는 룸 찾기
                            foreach (var room in this.wholeRoomList)
                            {
                                if ((Vector2)room.transform.position == new Vector2(j * this.mapDist, i * -this.mapDist))
                                {
                                    GameObject go = null;
                                    //찾으면 포탈 생성해서 해당 포인트에 자식으로 넣어주고 로컬 포지션 0으로 초기화
                                    if (this.mapLocation[i, j - 1] == 4)
                                    {
                                        go = Instantiate(this.bossPortal, room.transform.GetChild(3)); // 보스룸
                                    }
                                    else if (this.mapLocation[i, j - 1] == 3)
                                    {
                                        go = Instantiate(this.safeRoomPortal, room.transform.GetChild(3)); //상점
                                    }
                                    else
                                    {
                                        go = Instantiate(this.portal, room.transform.GetChild(3)); // 일반룸
                                    }
                                    go.transform.localPosition = Vector2.zero;
                                }
                            }
                        }
                    }
                }

            }
        }
        var trans = this.wholeRoomList.Find(x => x.gameObject.name.Contains("Boss")).transform.GetChild(4).transform;
        Instantiate(this.nextStagePortal, trans);  
    }

10 . 마무리로 시작룸을 제외한 모든 룸들의 액티브 상태를 OFF 해준다.

 

https://tv.kakao.com/v/436522765

배열의 크기 , 비율에 따라 다양한 맵이 생성된다.

---

• 미니맵

미니맵의 경우 UI 카메라를 이용. 각 룸의 위에 UI 이미지를 추가하여 UI카메라로 표현한다.

 

https://bueong-e.tistory.com/260

[유니티 프로젝트] 랜덤 생성맵 포탈 구현 (맵간의 이동) 및 미니맵 포지션 구현

 

추가적으로 플레이어의 위치에 따라 미니맵에서의 플레이어 위치 또한  실시간으로 변한다.

 

 

포탈을 이용한 룸의 이동 또는 맵의 구성은 이전 블로그 포스팅들 참조