Chapter 6. A* 길찾기 알고리즘 구현

Date: 2020.10.09 Updated: 2020.10.09

카테고리: Algorithm Lesson 2

태그: C Sharp Data Structure Algorithm

인프런에 있는 Rookiss님의 [C#과 유니티로 만드는 MMORPG 게임 개발 시리즈] Part2: 자료구조와 알고리즘 강의를 듣고 정리한 필기입니다. 😀
🌜 강의 들으러 가기 Click

Chapter 6. A* 길찾기 알고리즘

🚖 A* 길찾기 알고리즘 개념

다익스트라와 비교

다익스트라
- 해당 지점에서 갈 수 있는 모든 경로에 대한 최단 거리를 찾는다. 👉 비효율적
  - 따라서 시작 지점만 알면 된다. 목적지를 주진 않는다.
  - 다익스트라를 목적지 찾으면 종료하게끔 개선할 수도 있지만 그래도 아쉽다. 매번 모든 지점마다 갈 수 있는 모든 경로에 대한 최단 거리를 찾아 비교하기 때문에.
- 예약된 정점들 중 최고의 정점을 선택할 땐
  - 최단 거리 경로를 유지할 수 있는 정점을 선택한다.
A*
- 모든 경로를 다 찾지 않는다.
  - 시작 지점, 끝 지점 목적지. 이렇게 두 개가 주어진다. 목적지를 알고 있다.
- 예약된 정점들 중 최고의 정점을 선택할 땐
  - 1️⃣ 최단 거리 경로를 유지할 수 있는 정점도 고려하고 👉 G
    - 어떤 경로를 따라왔냐에 따라 해당 정점의 비용은 그때 그때 다르므로 가변적이다.
  - 2️⃣ 이에 더하여 목적지에 얼마나 가까운 정점인지 또한 고려한다. 👉 H (휴리스틱)
    - 목적지에 얼마나 가까운 정점인지를 고려하는건 피타고라스로 실제 남은 거리를 쓸 수도 있고 그냥 목적지까지 벽을 무시하고 그냥 가로 세로 총 몇 개의 타일이 남았는지 세는 등등 다양하게 정의할 수 있다.
      - 이런 정의 방법을 휴리스틱 함수라고 하며 어떤 휴리스틱 함수를 사용하느냐에 따라 A* 알고리즘의 효율성이 좌지우지 된다.
    - 어떤 경로를 따라왔냐와는 상관 없이 해당 정점이 목적지와 얼마나 가까운 정점인지는 고정적인 값이다.
  - 최종 점수 👉 F = G + H
- 다익스트라 버전에서 2️⃣ 를 고려한 알고리즘이라고 할 수 있겠다.
  - 다익스트라 👉 f = g 기준으로 다음 방문 정점 선택
  - A * 👉 f = g + h 기준으로 다음 방문 정점 선택

이 예제에서는 H를 [목적지까지 남은 X 방향의 타일 + Y 방향의 타일]로 할 것이다.

🚖 A* 길찾기 알고리즘 구현 : 📜Player.cs

BFS, 다익스트라랑 거의 똑같은 구조로 흘러간다. h를 고려한다는 것을 제외하고는 비슷

🚔 상하좌우 이동만 가능할 때

using System;
using System.Collections.Generic;
using System.Text;

namespace Algorithm
{
    class Pos
    {
        public Pos(int y, int x) { Y = y; X = x; }
        public int Y;
        public int X;
    }

    class Player
    {
        public int PosY { get; private set; }
        public int PosX { get; private set; }

        Random _random = new Random();

        Board _board;

        enum Dir  // 반시계방향
        {
            Up = 0,
            Left = 1,
            Down = 2,
            Right = 3
        }

        int _dir = (int)Dir.Up;

        List<Pos> _points = new List<Pos>();

        public void Initialize(int posY, int posX, Board board)
        {
            PosX = posX;
            PosY = posY;
            _board = board;

            AStar(); // ⭐A * 알고리즘⭐
        }

        struct PQNode : IComparable<PQNode>
        {
            public int F;
            public int G;
            // F랑 G만 알아도 H 는 구할 수 있으니 생략
            public int Y;
            public int X;

            public int CompareTo(PQNode other)
            {
                if (F == other.F)  // F 값을 기준으로 크기를 비교
                    return 0;
                return F < other.F ? 1 : -1;
            }
        }

        void AStar()
        {
            int[] deltaY = new int[] { -1, 0, 1, 0 };
            int[] deltaX = new int[] { 0, -1, 0, 1 };
            int[] cost = new int[] { 1, 1, 1, 1 };

            // 점수 매기기
            // F = G _ H
            // F = 최종 점수 (작을 수록 좋음. 경로에 따라 달라짐)
            // G = 시작점에서 해당 좌표까지 이동하는데 드는 비용 (작을 수록 좋음. 경로에 따라 달라짐)
            // H = 목적지로부터 얼마나 가까운 곳인지를 따지는 보너스 점수 (작을 수록 좋음. 고정인 값)

            // (y, x) 이미 방문 했는지 여부 (방문 = closed 상태)
            bool[,] closed = new bool[_board.Size, _board.Size];

            // (y, x) 가는 길을 한번이라도 발견 했었는지 여부 (한번이라도 예약 되있는지 여부)
            // 발견(예약)이 안됐다면 Int32.MaxValue 로 저장이 되어 있을 것.
            // F = G + H 값이 저장된다. (이 F 값이 가장 작은 정점이 방문 정점으로 선택될 것)
            int [,] open = new int[_board.Size, _board.Size];
            for (int y = 0; y < _board.Size; y++)
                for (int x = 0; x < _board.Size; x++)
                    open[y, x] = Int32.MaxValue;

            Pos [,] parent = new Pos[_board.Size, _board.Size];

            // 우선순위 큐 : 예약된 것들 중 가장 좋은 후보를 빠르게 뽑아오기 위한 도구. 
            PriorityQueue<PQNode> pq = new PriorityQueue<PQNode>();

            // 시작점 발견 (시작점 예약 진행)
            open[PosY, PosX] = Math.Abs(_board.DestY - PosY) + Math.Abs(_board.DestX - PosX);  // 시작점이니까 G는 0이고, H 값임.
            pq.Push(new PQNode() { F = Math.Abs(_board.DestY - PosY) + Math.Abs(_board.DestX - PosX), G = 0, Y = PosY, X = PosX });
            parent[PosY, PosX] = new Pos(PosY, PosX);

            while(pq.Count > 0)
            {
                // 제일 좋은 후보를 찾는다.
                PQNode node = pq.Pop();

                // 동일한 좌표를 여러 경로로 찾아서, 더 빠른 경로로 인해서 이미 방문(closed) 된 경우 스킵
                if (closed[node.Y, node.X])
                    continue;

                // 방문 한다.
                closed[node.Y, node.X] = true;

                // 목적지에 도착했으면 바로 종료
                if (node.Y == _board.DestY && node.X == _board.DestX)
                    break;

                // 상하좌우 등 이동할 수 있는 좌표인지 확인해서 예약(open)한다.
                for (int i = 0; i < deltaY.Length; i++)
                {
                    int nextY = node.Y + deltaY[i];
                    int nextX = node.X + deltaX[i];

                    // 유효 범위를 벗어났으면 스킵
                    if (nextY < 0 || nextY >= _board.Size || nextX < 0 || nextX >= _board.Size)
                        continue;
                    // 벽으로 막혀서 갈 수 없으면 스킵
                    if (_board.Tile[nextY, nextX] == Board.TileType.Wall)
                        continue;
                    // 이미 방문한 곳이면 스킵
                    if (closed[nextY, nextX])
                        continue;

                    // 비용 계산
                    int g = node.G + cost[i];
                    int h = Math.Abs(_board.DestY - nextY) + Math.Abs(_board.DestX - nextX);

                    // 다른 경로에서 더 빠른 길을 이미 찾았으면 스킵
                    if (open[nextY, nextX] < g + h)
                        continue;

                    // 예약 진행
                    open[nextY, nextX] = g + h;
                    pq.Push(new PQNode() { F = g + h, G = g, Y = nextY, X = nextX });
                    parent[nextY, nextX] = new Pos(node.Y, node.X);
                }
            }

            CalcPathFromParent(parent);
        }

        void CalcPathFromParent(Pos[,] parent)
        {
            int y = _board.DestY;
            int x = _board.DestX;
            while (parent[y, x].Y != y || parent[y, x].X != x)
            {
                _points.Add(new Pos(y, x));
                Pos pos = parent[y, x];
                y = pos.Y;
                x = pos.X;
            }
            _points.Add(new Pos(y, x));
            _points.Reverse();
        }

        const int MOVE_TICK = 10;   // 10밀리세컨즈 = 0.01 초 마다 움직이게
        int _sumTick = 0;
        int _lastIndex = 0;
        public void Update(int deltaTick)
        {
            if (_lastIndex >= _points.Count)
                return;

            _sumTick += deltaTick;
            if (_sumTick >= MOVE_TICK)  // 이부분은 0.1초마다 실행
            {
                _sumTick = 0;

                PosY = _points[_lastIndex].Y;
                PosX = _points[_lastIndex].X;
                _lastIndex++;
            }
        }
    }
}

우선순위 큐에 넣을 데이터

예약한 데이터를 우선순위큐에 넣으며, POP 하면 가장 작은 값이 나오게 할 것이다.

PQNode라는 타입의 데이터로 F, G, Y, X 정보를 묶어서, 예약하기로 결정한 좌표를 우선순위 큐에 넣을 것이다.
- F 👉 해당 좌표의 최종 점수 F = G + H
- G 👉 시작점에서 해당 좌표까지 이동하는데 드는 비용
- H 는 F - G 로 알 수 있으므로 넣지 않음
- Y 👉 예약한 Y 좌표
- X 👉 예약한 X 좌표
비교 함수
- int, float 같은 기본 데이터 타입이 아니기 때문에 PQNode 타입의 비교 기준을 만들어 주어야 함
  - F 값이 작을 수록 루트에 위치하게 한다. 즉, 오름 차순. 예약 목록, 즉 우선순위 큐에서 F 값이 가장 작은 것을 POP 하게 할 것이다.
    - 최종점수 F 값이 작을 수록 최단 경로를 만들기에 적합한 좌표
  - F < other.F ? 1 : -1
    - 나의 F가 다른 PQNode 객체의 F보다 작으면 1 리턴. 크면 -1 리턴.
      - 우선 순위 큐에 PQNode 객체를 넣으면 이 비교 기준을 통해 힙 트리를 만들게 된다.

필요한 변수들

      int[] deltaY = new int[] { -1, 0, 1, 0 };
      int[] deltaX = new int[] { 0, -1, 0, 1 };
      int[] cost = new int[] { 1, 1, 1, 1 };

      bool[,] closed = new bool[_board.Size, _board.Size];

      int [,] open = new int[_board.Size, _board.Size];
      for (int y = 0; y < _board.Size; y++)
          for (int x = 0; x < _board.Size; x++)
              open[y, x] = Int32.MaxValue;

      Pos [,] parent = new Pos[_board.Size, _board.Size];

      PriorityQueue<PQNode> pq = new PriorityQueue<PQNode>();

현재 좌표의 앞 뒤 좌 우 좌표를 알기 위해선 이만큼 더해주기
- deltaY[0], deltaX[0] 👉 Up
- deltaY[1], deltaX[1] 👉 Down
- deltaY[2], deltaX[2] 👉 Left
- deltaY[3], deltaX[3] 👉 Down
현재 좌표 기준 앞 뒤 좌 우로 각각 가기 위한 비용
- cost 전부 1 이지만 나중에 대각선도 갈 수 있게 된다면 대각선 비용은 상하좌우 비용과 다르게 적용될 것이다.
closed 👉 방문한 좌표 표시
open 👉 단 한번이라도 예약된 적이 있는지
- Int32.MaxValue 로 초기화 해둔다.
- 한번이라도 예약된적이 있다면 Int32.MaxValue 값이 아닐 것이다.
parent 👉 방문한 좌표의 부모 좌표 표시 (이전 방문 좌표)
- 미로 길 찾기를 위하여 저장
우선순위 큐 pg
- 현재의 예약 좌표들을 이 우선순위 큐에 PQNode 타입으로 저장한다.
- 이 우선순위큐를 POP 하면 현재의 예약 좌표들 중 가장 F 값이 작은 좌표가 빠져나오게 되고 이를 방문할 것이다.

시작 좌표는 미리 예약

            open[PosY, PosX] = Math.Abs(_board.DestY - PosY) + Math.Abs(_board.DestX - PosX);  // 시작점이니까 G는 0이고, H 값임.
            pq.Push(new PQNode() { F = Math.Abs(_board.DestY - PosY) + Math.Abs(_board.DestX - PosX), G = 0, Y = PosY, X = PosX });
            parent[PosY, PosX] = new Pos(PosY, PosX);

시작 좌표. 현재 PosY, PosX 값은 각각 1, 1
open[1, 1]
- G 는 0
  - 시작 좌표에서 시작 좌표까지의 거리는 0
- H 는
  - 목적지까지 남은 Y 방향의 타일 + X 방향의 타일
  - Math.Abs(_board.DestY - PosY) + Math.Abs(_board.DestX - PosX)
pq 우선순위 큐에 넣어 예약

과정 1️⃣ : 예약된 것들 중에서 방문할(제일 좋은) 정점 고르기

과정 1️⃣2️⃣3️⃣ 무한 반복. 우선순위큐가 빌 때까지 (더 이상 예약 된게 하나도 없을 때까지)

                // 제일 좋은 후보를 찾는다.
                PQNode node = pq.Pop();

                // 동일한 좌표를 여러 경로로 찾아서, 더 빠른 경로로 인해서 이미 방문(closed) 된 경우 스킵
                if (closed[node.Y, node.X])
                    continue;

우선순위큐 POP 👉 예약된 좌표들 중에 가장 좋은 좌표(F 값이 가장 작은)를 꺼내고 이를 방문한다.

우선순위 큐를 쓰기 전엔, 예약된 것들 중에서 일일이 점수 값이 가장 작은 것을 비교해가며 찾았어야 했는데 편해졌다.
3️⃣ 에서 방문하기로 결정되고 1️⃣ 로 넘어온 경우라면 if (closed[node.Y, node.X]) 에 걸린다.
- 방문된 좌표라면 다시 1️⃣ 실행. 우선순위 큐에서 다른거 다시 꺼냄

과정 2️⃣ 방문한다.

                // 방문 한다.
                closed[node.Y, node.X] = true;

                // 목적지에 도착했으면 바로 종료
                if (node.Y == _board.DestY && node.X == _board.DestX)
                    break;

방문한다. 해당 좌표로 closed 업데이트
목적지에 도착했다면 모든 과정을 종료한다.

과정 3️⃣ 새로운 방문 노드를 중심으로 한 다음 예약 목록 선정

                // 상하좌우 등 이동할 수 있는 좌표인지 확인해서 예약(open)한다.
                for (int i = 0; i < deltaY.Length; i++)
                {
                    int nextY = node.Y + deltaY[i];
                    int nextX = node.X + deltaX[i];

                    // 유효 범위를 벗어났으면 스킵
                    if (nextY < 0 || nextY >= _board.Size || nextX < 0 || nextX >= _board.Size)
                        continue;
                    // 벽으로 막혀서 갈 수 없으면 스킵
                    if (_board.Tile[nextY, nextX] == Board.TileType.Wall)
                        continue;
                    // 이미 방문한 곳이면 스킵
                    if (closed[nextY, nextX])
                        continue;

                    // 비용 계산
                    int g = node.G + cost[i];
                    int h = Math.Abs(_board.DestY - nextY) + Math.Abs(_board.DestX - nextX);

                    // 다른 경로에서 더 빠른 길을 이미 찾았으면 스킵
                    if (open[nextY, nextX] < g + h)
                        continue;

                    // 예약 진행
                    open[nextY, nextX] = g + h;
                    pq.Push(new PQNode() { F = g + h, G = g, Y = nextY, X = nextX });
                    parent[nextY, nextX] = new Pos(node.Y, node.X);
                }

우선순위 큐 PUSH 👉 해당 좌표 예약하기

예약하기 적합한 좌표 찾기
- 현재 방문 좌표의 상 하 좌 우 좌표들 검사
  - 이를 nextY, nextX 에 담아 검사한다.
  - 예약 하면 안되는 좌표 스킵
    - 유효 범위를 벗어났다면 스킵
    - 벽이라면 갈 수 없으므로 스킵
      - 연결되지 않은 정점이라고 생각할 수 잇겠다.
    - 이미 방문 했었던 정점이라면 스킵
    - 비용(g + h)이 해당 좌표에서 이미 다른 경로에서 더 적은 비용을 찾았었다면 방금 구한 이 비용으로 새롭게 예약할 필요가 없으니 스킵
      - g 👉 현재 방문중인 노드까지의 G 값에 현재 검사중인 이 nextY, nextX 까지 오기 위한 비용 더하기
      - h 👉 현재 검사중인 이 nextY, nextX 기준 목적지까지 남은 Y 방향의 타일 + X 방향의 타일
  - 위 과정에서 스킵되지 않았다면 최종적으로 예약할 좌표로 선정
    - 해당 좌표의 open에 g + h 비용 저장
    - 해당 좌표를 PQNode로 묶어 우선순위 큐에 PUSH
    - 해당 좌표의 parent를 현재 방문 좌표인 node.Y, node.X로 업뎃

리스트에 방문한 정점들 차례로 추가 (최종 완성된 길)

CalcPathFromParent(parent);  // 실행


        void CalcPathFromParent(Pos[,] parent)
        {
            int y = _board.DestY;
            int x = _board.DestX;
            while (parent[y, x].Y != y || parent[y, x].X != x)
            {
                _points.Add(new Pos(y, x));
                Pos pos = parent[y, x];
                y = pos.Y;
                x = pos.X;
            }
            _points.Add(new Pos(y, x));
            _points.Reverse();
        }

목적지부터 부모의 부모로 쭉쭉 타고 올라가면서 방문할 타일들을 전부 _points 리스트에 저장. 그리고 이 과정이 다 끝나면 리스트 거꾸로!

🚔 대각선 이동도 허용할 때

            int[] deltaY = new int[] { -1, 0, 1, 0, -1, 1, 1, -1 };
            int[] deltaX = new int[] { 0, -1, 0, 1, 1, -1, -1, 1 };
            int[] cost = new int[] { 10, 10, 10, 10, 14, 14, 14, 14 };

            // 출발지 예약
            open[PosY, PosX] = 10 * (Math.Abs(_board.DestY - PosY) + Math.Abs(_board.DestX - PosX));  // 시작점이니까 G는 0이고, H 값임.
            pq.Push(new PQNode() { F = 10 * (Math.Abs(_board.DestY - PosY) + Math.Abs(_board.DestX - PosX)), G = 0, Y = PosY, X = PosX });
            parent[PosY, PosX] = new Pos(PosY, PosX);

            // 예약시 비용 계산
            int g = node.G + cost[i];
            int h = 10 * (Math.Abs(_board.DestY - nextY) + Math.Abs(_board.DestX - nextX));

대각선 방향 추가!
- UpLeft, DownLeft, DownRight, UpRight
- deltaY[4], deltaX[4] 👉 UpLeft
- deltaY[5], deltaX[5] 👉 DownLeft
- deltaY[6], deltaX[6] 👉 DownRight
- deltaY[7], deltaX[7] 👉 UpRight
cost
- 대각선 이동 비용은 14 (\(\sqrt{2} = 1.4\) X 10), 상하좌우 이동 비용은 10 으로 정해보았다.
- 이에 대한 형평성을 위해 H 값에 10 을 곱해주었다.
  - 목적지까지 남은 Y 방향의 타일 + X 방향의 타일
  - 즉 상하좌우 수평적인 방향이므로 하나 이동 당 10 쳐주기로.

cf) 미로 찾기 무한 반복

        const int MOVE_TICK = 100;   // 100밀리세컨즈 = 0.1 초 마다 움직이게
        int _sumTick = 0;
        int _lastIndex = 0;
        public void Update(int deltaTick)
        {
            if (_lastIndex >= _points.Count)
            {
                _lastIndex = 0;
                _points.Clear();
                _board.Initialize(25, this);  // 플레이어보다 먼저 이니셜라이징이 이루어져야 함
                Initialize(1, 1, _board);
            }

            _sumTick += deltaTick;
            if (_sumTick >= MOVE_TICK)  // 이부분은 0.1초마다 실행
            {
                _sumTick = 0;

                PosY = _points[_lastIndex].Y;
                PosX = _points[_lastIndex].X;
                _lastIndex++;
            }
        }
    }

if (_lastIndex >= _points.Count)
- 리스트를 다 다돌면
  - 다시 다 초기화 하고 미로 다시 새롭게 초기화 하고 플레이어도 새로 초기화

🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우 
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄

맨 위로 이동하기

Twitter Facebook LinkedIn

👱‍♀️ ansohxxn

Chapter 6. A* 길찾기 알고리즘 구현

Chapter 6. A* 길찾기 알고리즘

🚖 A* 길찾기 알고리즘 개념

다익스트라와 비교

🚖 A* 길찾기 알고리즘 구현 : 📜Player.cs

🚔 상하좌우 이동만 가능할 때

우선순위 큐에 넣을 데이터

필요한 변수들

시작 좌표는 미리 예약

과정 1️⃣ : 예약된 것들 중에서 방문할(제일 좋은) 정점 고르기

과정 2️⃣ 방문한다.

과정 3️⃣ 새로운 방문 노드를 중심으로 한 다음 예약 목록 선정

리스트에 방문한 정점들 차례로 추가 (최종 완성된 길)

🚔 대각선 이동도 허용할 때

cf) 미로 찾기 무한 반복

공유하기

댓글남기기

참고

2020.10.25
[고득점Kit][DP] 등굣길 ⭐⭐⭐

2020.10.25
[고득점Kit][DP] 정수 삼각형 ⭐⭐⭐

2020.10.24
(C++) 동적 계획법 Dynamic Programming

2020.10.24
[고득점Kit][DFS][DP] N 으로 표현 ⭐⭐⭐

👱‍♀️ ansohxxn

Chapter 6. A* 길찾기 알고리즘

🚖 A* 길찾기 알고리즘 개념

다익스트라와 비교

🚖 A* 길찾기 알고리즘 구현 : 📜Player.cs

🚔 상하좌우 이동만 가능할 때

우선순위 큐에 넣을 데이터

필요한 변수들

시작 좌표는 미리 예약

과정 1️⃣ : 예약된 것들 중에서 방문할(제일 좋은) 정점 고르기

과정 2️⃣ 방문한다.

과정 3️⃣ 새로운 방문 노드를 중심으로 한 다음 예약 목록 선정

리스트에 방문한 정점들 차례로 추가 (최종 완성된 길)

🚔 대각선 이동도 허용할 때

cf) 미로 찾기 무한 반복

공유하기

댓글남기기

참고

2020.10.25 [고득점Kit][DP] 등굣길 ⭐⭐⭐

2020.10.25 [고득점Kit][DP] 정수 삼각형 ⭐⭐⭐

2020.10.24 (C++) 동적 계획법 Dynamic Programming

2020.10.24 [고득점Kit][DFS][DP] N 으로 표현 ⭐⭐⭐

2020.10.25
[고득점Kit][DP] 등굣길 ⭐⭐⭐

2020.10.25
[고득점Kit][DP] 정수 삼각형 ⭐⭐⭐

2020.10.24
(C++) 동적 계획법 Dynamic Programming

2020.10.24
[고득점Kit][DFS][DP] N 으로 표현 ⭐⭐⭐