[💬] 던전 게임을 만들어 보기로 했다[2](A star 알고리즘)

[겨(210.97)]

지난번에 길 찾기 알고리즘을 만든다 그러고 갑자기 잠수해 버렸는데

수많은 삽질과 뻘짓과 그리고 게임한다고 낭비한 시간 끝에 결국 만들긴 만들었다.

남의 코드 그냥 가져와서 만들었으면 훨씬 시간이 적게 걸렸을 것을... 엄청 시간 잡아 먹었네.

근데 또 보면 남 코드가 은근히 마음에 안 드는 부분이 꼭 하나씩 나오잖아?

그걸 고치려면 내가 이해를 못 한 상태에서는 못 고치고.

어차피 나중에 또 수정할 일이 생겼을 때 수정할려면 알고는 가야 할 알고리즘 같아서,

바닥부터 코드를 하나하나 다 짠다고 시간이 오래 걸렸네.

우선은 A star 알고리즘에 대해서 좀 이야기를 해야 할 거 같은데, 

http://egloos.zum.com/cozycoz/v/9748811

알고리즘 설명이 필요한 사람은 여기 가라.

내가 짠 코드도 여기 설명을 기준으로 짠 거라서 저 글을 읽고 온 놈을 기준으로 해서 이야기할거다.

0. 자료구조

 - 게임매니저와 맵 구조.

일단 게임 매니저에서는 별 거 없어. 

나는 Grid에다가 게임메니저 스크립트를 삽입해 놓았고, public tilemap에다가 저기 보이는 Tilemap을 그냥 드래그 해서 붙였어.

그 다음에 TileNode 구조를 만들어서 거기에 한번 복사해 주는 방법을 썼지.

최대한 심플하게.

나머지는 전부 Astar에 때려박았는데, 거기 코드가 존나 많음.

자료구조 - Astar 알고리즘

왠지 딱 보면 우선순위 큐 처럼 생긴 무엇인가랑, 맵을 그린 것 처럼 생긴 무엇인가가 보이지?

AStar 알고리즘을 까먹고 온 사람은 저 위로 올라가서 연결된 페이지에서 opened list와 closed list가 무슨 뜻인지를 다시 보고 오시고...

opened list에 우선순위큐를 사용한 이유는 F비용(시작점 ~ 현재지점까지의 이동거리 + 현재지점~종료점까지 이동거리)에 따라서 정렬하기 위해서야.

결론적으로 F 비용이 가장 낮은 경로를 선택하게 되니까, 점을 추가할 때마다 F 비용에 따라서 정렬해 두면 편하겠지.

그 다음에 closed list에 OpenCloseMap은 배열이야.

왜 여기서 배열을 사용했냐 하면, 다시 아까 본 페이지( http://egloos.zum.com/cozycoz/v/9748811 )로 돌아가서

5,6번 항목을 보면 "인접 사각형"이라는 말이 보이지?

괜히 우선순위 큐나 리스트같은 괴랄한 거 쓰는 것 보다는, 빠르고 순서를 명확히 알 수 있는 배열을 사용하면 

인접한 사각형을 찾긴 훨씬 빠르기 때문에 배열을 사용했어. 

X,Y값에 +- 1 하면 그만이잖아?

저기 보이는 NodeInfo는 속도 향상을 위해서 class대신에 struct를 썼어.

    public struct NodeInfo

    {

        public bool isClosed;

        public bool isOpened;

        public PathNode node;

    }

node에 PathNode의 ref를 넣기 위해서는 어쩔수 없이 PathNode는 class를 써야 했지. 

존나 쓸모없이 점 하나를 나타내기 위해서 사용된 구조가 4개나 되는데,

그 중에 PathNode와 NodeInfo는 AStar 내부에서만 연산을 위해서 사용하는 구조고,

실제 타일맵과 정보를 주고받기 위해서는 Point와 TileNode를 사용하도록 만들었어.

1. 길찾기 알고리즘

아까부터 계속 참고한 페이지인 ( http://egloos.zum.com/cozycoz/v/9748811 )에서는 뭔가 어렵게 설명해 놨어.

특히 5,6번 단계에 가면 주술사가 술쳐먹고 주술 쓰는 것 마냥 문장의 주술관계가 좆같이 꼬이면서 설명이 개판이 됨.

그래서 내가 이해한 거 토대로 존나 쉽게 설명해 준다.

보면 2,3번 없지? 잘 돌아감.

우선적으로 알아야 할 건 opened list와 closed list의 개념이야.

opened list는 내가 탐색해야 할 각 셀들.

closed list는 탐색이 끝나서 더 이상 탐색할 필요가 없는 셀들임.

AStar 길찾기 알고리즘의 대략적인 구조는 다음과 같아.

1. 시작 지점을 탐색할 셀들이 모인 리스트(opened list)에 넣음.

2. 탐색할 셀들이 모인 리스트(opened list)에서 F를 기준으로, 가장 낮은 F를 가진 셀(□)을 선택후 제거(pop).

  (이 시점에서 opened list == null 이면 탐색 실패, break)

3. □는 선택되었으니 더 이상 탐색할 필요없는 셀들이 모인 리스트(closed list)에 넣음.

4. □에 인접한 셀들(상,하,좌,우,(+대각선4방향)) 중에서, 

   벽이 아닌(이동 가능한) && 열려 있지 않은 && 닫혀 있지 않은 셀(■)들을 opened list에 넣음.

   이 셀(■) 들은 □를 부모로 가짐.

5. ■에 인접한 셀들(상,하,좌,우,(+대각선4방향)) 중에서, 

   opened list에 있는 && □보다 G 값이 작은 셀(☆)이 있다면, ■의 부모를 ☆로 바꿈.

6. 탐색할 셀들이 모인 리스트(opened list)에 최종지점이 포함되었는지 확인후, 포함되었다면 탐색 성공-종료 / 아니라면 2번부터 반복.

다음부터는 하나하나 설명 들어간다?

1. 시작 지점을 탐색할 셀들이 모인 리스트(opened list)에 넣음.

 여기서 opened list에만 넣는게 아니라 openclosemap에도 넣은 이유는,

 priority queue에서 좌표를 기준으로 한 탐색(위에서의 5번 과정)을 하기에는 연산 속도가 훨씬 커지기 때문임.

물론, G 값을 기준으로 탐색할 수도 있지만 그러기에는 다시 정렬해 줘야 하는 과정이 또 필요해 지므로

그냥 좌표를 기준으로 하는 맵에다 때려박는 쪽이 낫더라고.

2. 탐색할 셀들이 모인 리스트(opened list)에서 F를 기준으로, 가장 낮은 F를 가진 셀(□)을 선택후 제거(pop).

  (이 시점에서 opened list == null 이면 탐색 실패, break)

사실 push단계에서 이미 sort되었다고 한다...

3. □는 선택되었으니 더 이상 탐색할 필요없는 셀들이 모인 리스트(closed list)에 넣음.

패스.

4. □에 인접한 셀들(상,하,좌,우,(+대각선4방향)) 중에서, 

   벽이 아닌(이동 가능한) && 열려 있지 않은 && 닫혀 있지 않은 셀(■)들을 opened list에 넣음.

   이 셀(■) 들은 □를 부모로 가짐.

이건 좀 코드가 길다. 스샷은 패스하고...

public void SetChildren(LinkedList<PathNode> children, Point target, OpenCloseMap mapSpace)

        {

            if (CanBeChild(X - 1, Y, mapSpace))

            {

                children.AddLast(new PathNode(X - 1, Y, this, target));

                mapSpace.Open(children.Last.Value);

            }

            if (CanBeChild(X + 1, Y, mapSpace))

            {

                children.AddLast(new PathNode(X + 1, Y, this, target));

                mapSpace.Open(children.Last.Value);

            }

....

대충 이런 코드를 썼는데, for문을 안 쓰고 하드코딩으로 처리한 이유는 상/하/좌/우 만 할 것인가, 대각선까지 할 것인가의 주석처리가 편해서야.

        private bool CanBeChild(int posX, int posY, OpenCloseMap mapSpace)

        {

            if (mapSpace.IsInMap(posX, posY) && !mapSpace.IsClosed(posX, posY) && !mapSpace.IsOpened(posX, posY)) return true;

            else return false;

        }

좆도 별거 없음. 

5. ■에 인접한 셀들(상,하,좌,우,(+대각선4방향)) 중에서, 

   opened list에 있는 && □보다 G 값이 작은 셀(☆)이 있다면, ■의 부모를 ☆로 바꿈.

이 부분이 핵심이지.

    private void SetG()

        {

            if (Parent != null) G = Parent.G + GetShortestCostToTarget(Parent);

            else G = 0;

        }

        private void SetH(Point target)

        {

            if (target != null) H = GetShortestCostToTarget(target);

            else H = 0;

        }

   public int GetShortestCostToTarget(int targetXpos, int targetYpos)

   {

            int Xlength = Math.Abs(targetXpos - X);

            int Ylength = Math.Abs(targetYpos - Y);

            int diagonalLength = (Xlength > Ylength) ? Ylength : Xlength;

            int straightLength = ((Xlength > Ylength) ? Xlength : Ylength) - diagonalLength;

            return (Xlength + Ylength) * straightCost;//using only straight

            //return straightLength * straightCost + diagonalLength * diagonalCost;(using diagonal)

   }

근데 별 거 없음.

F는 전체 거리

G는 시작지점~이 점까지의 거리

H는 이 점~종료지점까지의 최단거리(예상값)잖아.

G는 부모의 G 값에다가, 부모까지의 가장 짧은 거리를 그냥 더해 주면 다야. 왜냐하면 부모는 항상 바로 옆에 있는 사각형이거든.

상수값 대신에 가장 짧은 거리를 더해 준 이유는, 상하좌우만 쓸 것인가, 대각선까지 쓸 것인가에 따라서 계산 방법이 달라지기 때문이야.

6. 탐색할 셀들이 모인 리스트(opened list)에 최종지점이 포함되었는지 확인후, 포함되었다면 탐색 성공-종료 / 아니라면 2번부터 반복.

4,5,6은 설명을 존나 대충대충 한 거 같은데, 그럴 수 밖에 없는게 알고리즘 자체는 크게 별 거 없었지만 자료구조를 선택하는 과정이 힘들었거든.

그리고 나서 선택한 걸 적용시키는 도중에 에러가 좀 터졌었고.

동영상 잘 올라갔나 모르겠네. 이만 자야지. 

다음에는 슬슬 맵 저장용 구조를 만들고 맵 에디터 UI를 만들어야겠네.

[익명(49.161)]

머하는 겜 입니까

[아이고이아(1.249)]

a*는 필수 인듯...

[이싸카(hackyun)]

개인적으로 궁금한건데, 그렇게 남의코드 긁어다가 분석해서 뜯어고치면서 게임만들정도면 언어공부 얼마나 했어?

[겨(210.97)]

ㅇㅇ/던전 만드는 게임

[겨(210.97)]

이싸카/4년(컴공이다)