A* 구현

Jaemyeong Lee·2024년 10월 15일

C#C#과 유니티로 만드는 MMORPG 게임 개발 시리즈 Rookiss 자료구조와 알고리즘

C#과 유니티로 만드는 MMORPG 게임 개발 시리즈

목록 보기

83/208

전체 코드

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Algorithm
{
    // 우선순위 큐를 만들어줌
    class PriorityQueue<T> where T : IComparable<T>
    {
        List<T> _heap = new List<T>();
        // O(logN)
        public void Push(T data)
        {
            // 힙의 맨 끝에 새로운 데이터를 삽입한다.
            _heap.Add(data);

            int now = _heap.Count - 1;
            // 도장 깨기

            while (now > 0)
            {
                // 도장 깨기 시도
                int next = (now - 1) / 2; // 부모의 인덱스
                if (_heap[now].CompareTo(_heap[next]) < 0)
                {
                    break; // 실패
                }
                // 두 값을 교체
                T temp = _heap[now];
                _heap[now] = _heap[next];
                _heap[next] = temp;

                // 검사 위치를 이동
                now = next;
            }

        }
        // O(logN)
        public T Pop()
        {
            // 반환할 데이터를 따로 저장
            T ret = _heap[0];

            // 마지막 데이터를 루트로 이동한다.
            int lastIndex = _heap.Count - 1;
            _heap[0] = _heap[lastIndex];
            _heap.RemoveAt(lastIndex);

            lastIndex--;

            // 역으로 내려가는 도장 깨기 시작
            int now = 0;
            while (true)
            {
                int left = 2 * now + 1;
                int right = 2 * now + 2;

                int next = now;
                // 왼쪽 값이 현재 값보다 크면 왼쪽으로 이동
                if (left <= lastIndex && _heap[next].CompareTo(_heap[left]) < 0)
                {
                    next = left;
                }
                // 오른값이 현재값보다 크면(왼쪽 이동 포함), 오른쪽으로 이동
                if (right <= lastIndex && _heap[next].CompareTo(_heap[left]) < 0)
                {
                    next = right;
                }
                // 왼쪽 / 오른쪽 모두 현재값보다 작으면 종료
                if (next == now)
                {
                    break;
                }

                // 두 값을 교채한다.
                T temp = _heap[now];
                _heap[now] = _heap[next];
                _heap[next] = temp;

                // 검사 위치 이동
                now = next;
            }
            return ret;

        }
        public int Count
        {
            get { return _heap.Count; }
        }
    }

    class Knight : IComparable<Knight>
    {
        public int Id { get; set; }

        public int CompareTo(Knight other)
        {
            if (Id == other.Id)
                return 0;
            return Id > other.Id ? 1 : -1;
            throw new NotImplementedException();
        }
    }
}
// BFS와 다익스트라는 목적지를 모르는 상태로 만듬
// 모든 정점을 다지나서 가서 비효율 적임

// 반면 A*는 시작지점과 끝점을 다 알고있음
// 출구에 가까워질 수록 가산점이 들어감
// 

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Algorithm
{
    class Pos
    {
        public Pos(int y, int x) { Y = y; X = x; }
        public int Y;
        public int X;
    }
    struct PQNode : IComparable<PQNode>
    {
        public int F;
        public int G;
        public int Y;
        public int X;

        public int CompareTo(PQNode other)
        {
            if (F == other.F) { return F; }
            return F < other.F ? 1 : -1;
        }
    }
    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;

            //BFS();
            AStar();
        }

        void AStar()
        {
            // UP LEFT DOWN RIGHT UPLEFT, DOWNLEFT, DOWNRIGHT UPRIGHT 
            int[] deltaY = { -1, 0, 1, 0, -1, 1, 1, -1 };
            int[] deltaX = { 0, -1, 0, 1, -1, -1, 1, 1 };
            int[] cost = { 10, 10, 10, 10, 14, 14, 14, 14 };

            // 점수 매기기
            // F = G + H
            // F = 최종 점수 (작을 수록 좋음, 경로에 따라 달라짐)
            // G = 시작점에서 해당 좌표까지 이동하는데 드는 비용 (작을 수록 좋음, 경로에 따라 달라짐)
            // H = 목적지에서 얼마나 가까운지 (작을 수록 좋음, 고정)

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

            // 부모님 추적
            Pos[,] parent = new Pos[_board.Size, _board.Size];

            // (y,x)가는 길을 한 번이라도 발견했는지
            // 발견 X -> MaxValue
            // 발견 O -> F = G + H
            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;
                }
            }

            // 오픈리스트에 있는 정보들 중에서, 가장 좋은 후보를 빠르게 뽑아오기 위한 도구
            PriorityQueue<PQNode> pq = new PriorityQueue<PQNode>();

            open[PosY, PosX] = 10 * (Math.Abs(_board.DestY - PosY) + Math.Abs(_board.DestX - PosX));
            
            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);

            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 (nextX < 0 || nextX >= _board.Size || nextY < 0 || nextY >= _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 = 10 * (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();
        }
        void BFS()
        {
            int[] deltaY = { -1, 0, 1, 0 };
            int[] deltaX = { 0, -1, 0, 1 };


            bool[,] found = new bool[_board.Size, _board.Size];
            // 어디서 부터 왔는지 기억해야함 부모님의 정보를 넣어줌
            Pos[,] parent = new Pos[_board.Size, _board.Size];

            // 미리 만들어준 Pos 사용
            Queue<Pos> q = new Queue<Pos>();
            q.Enqueue(new Pos(PosY, PosX)); // 시작점
            found[PosY, PosX] = true;
            parent[PosY, PosX] = new Pos(PosY, PosX); // 현재 지점을 저장해둠

            while (q.Count > 0)
            {
                Pos pos = q.Dequeue();
                // 
                int nowY = pos.Y;
                int nowX = pos.X;
                for (int i = 0; i < 4; i++)
                {
                    int nextY = nowY + deltaY[i];
                    int nextX = nowX + deltaX[i];

                    
                    if (nextY < 0 || nextY >= _board.Size || nextX < 0 || nextX >= _board.Size) // 범위를 벗어남
                        continue;
                    if (_board.Tile[nextY, nextX] == Board.TileType.Wall) // 벽이면
                        continue;
                    if (found[nextY, nextX]) // 이미 방문 했으면
                        continue;

                    q.Enqueue(new Pos(nextY, nextX));
                    found[nextY, nextX] = true; // 찾았다
                    parent[nextY, nextX] = new Pos(nowY, nowX); // 현재 지점을 저장해줌

                }
            }
            // 도착 지점에서 출발 지점으로 거슬러 올라가며 경로 저장
            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;
            }
            // 끝점에 도달하면 while문을 빠져나옴 따라서
            // 시작점은 ADD를 안해준 상황

            _points.Add(new Pos(y, x)); // 출발점 추가
            _points.Reverse(); // 최단 경로로 정렬
        }


        public void RightHand()
        {
            // 현재 바라보고 있는 방향을 기존으로 좌표 변화를 나타냄
            int[] frontY = new int[] { -1, 0, 1, 0 };
            int[] frontX = new int[] { 0, -1, 0, 1 };
            int[] rightY = new int[] { 0, -1, 0, 1 };
            int[] rightX = new int[] { 1, 0, -1, 0 };

            _points.Add(new Pos(PosY, PosX));

            // 목표 지점에 도달할 때까지 뺑뺑이를 돌겠다
            // 목적지 도착하기 전에는 계속 실행
            // 실시간으로 로직 돌리기 전에, 렌더링도 하기 전에, 미리 길을 찾아 보는 것이다.
            // 현재 바라보는 방향이 어디냐에 따라 오른손 위치가 다름.(왼쪽을 보고 있는 상태라면 오른손은 절대 기준으로 위쪽일것)
            while (PosY != _board.DestY || PosX != _board.DestX)
            {
                // 1. 현재 바라보는 방향을 기준으로 오른쪽으로 갈 수 있는지 확인
                if (_board.Tile[PosY + rightY[_dir], PosX + rightX[_dir]] == Board.TileType.Empty)
                {
                    // 오른쪽으로 가기
                    // 1. 오른쪽 방향으로 90 도 회전
                    _dir = (_dir - 1 + 4) % 4;
                    // 2. 앞으로 한 보 전진
                    PosY = PosY + frontY[_dir];
                    PosX = PosX + frontX[_dir];

                    _points.Add(new Pos(PosY, PosX));
                }
                // 2. 현재 바라보는 방향을 기준으로 앞 쪽으로 갈 수 있는지
                else if (_board.Tile[PosY + frontY[_dir], PosX + frontX[_dir]] == Board.TileType.Empty)
                {
                    // 앞으로 한 보 전진
                    PosY = PosY + frontY[_dir];
                    PosX = PosX + frontX[_dir];

                    _points.Add(new Pos(PosY, PosX));
                }
                else
                {
                    // 왼쪽 방향으로 90 도 회전 해주고 다음 반복 하러 (반시계방향으로 여러 방향 따져봄) 
                    _dir = (_dir + 1 + 4) % 4;
                }
            }
        }
        const int MOVE_TICK = 10;   // 10밀리세컨즈 = 0.01 초 마다 움직이게
        int _sumTick = 0;
        int _lastIndex = 0;
        public void Update(int deltaTick)
        {
            if (_lastIndex >= _points.Count)
            {
                _lastIndex = 0;
                _points.Clear();
                _board.Initialize(_board.Size, this);
                Initialize(1, 1, _board);
            }

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

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

**1. A* 알고리즘이란?**

A* 알고리즘은 최단 경로를 찾는 데 사용되는 탐색 알고리즘입니다. 주어진 시작점에서 목표점까지 가는 최적의 경로를 찾으며, 다익스트라 알고리즘과 휴리스틱 함수를 조합하여 효율적으로 동작합니다.

**1.1 A* 알고리즘의 핵심 요소**

G: 시작점에서 현재 노드까지의 이동 비용
H: 현재 노드에서 목적지까지의 예상 비용(휴리스틱, Heuristic)
F: F = G + H → 가장 작은 F 값을 가진 노드를 우선적으로 탐색

1.2 다익스트라 vs A*

알고리즘	탐색 방식
다익스트라	`F = G` 기준으로 최단 거리 노드를 방문
A*	`F = G + H` 기준으로 최적의 경로를 탐색
차이점	A*는 `H`를 고려하여 목적지 방향으로 더 빠르게 탐색

2. `Pos` 클래스

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

(Y, X) 좌표 정보를 저장하는 클래스
플레이어 위치, 경로 저장, 부모 노드 추적 등에 사용됨

3. `Player` 클래스

플레이어의 위치 및 A* 알고리즘을 통한 경로 탐색을 담당하는 클래스입니다.

3.1 필드 및 변수

public int PosY { get; private set; }
public int PosX { get; private set; }
Random _random = new Random();
Board _board;

PosY, PosX: 플레이어의 현재 좌표
_random: 무작위 동작을 위한 랜덤 객체
_board: 게임 맵을 저장하는 객체

enum Dir { Up = 0, Left = 1, Down = 2, Right = 3 }
int _dir = (int)Dir.Up;

네 가지 방향(위, 왼쪽, 아래, 오른쪽) 열거형
_dir: 플레이어가 현재 바라보는 방향

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

A* 경로를 저장하는 리스트

4. `PQNode` 구조체 (우선순위 큐 노드)

struct PQNode : IComparable<PQNode>
{
    public int F;
    public int G;
    public int Y;
    public int X;

    public int CompareTo(PQNode other)
    {
        return F.CompareTo(other.F);
    }
}

F: 총 비용(F = G + H)
G: 시작점에서 해당 좌표까지 이동하는 비용
Y, X: 좌표 정보
CompareTo: F 값이 작은 노드가 우선순위 큐에서 먼저 꺼내짐

**5. `AStar()` 함수 (A* 알고리즘 실행)**

5.1 탐색 방향 및 비용

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

deltaY, deltaX: 상하좌우 이동 시 좌표 변화량
cost: 이동 비용 (모든 방향 동일)

5.2 탐색 상태 배열

bool[,] closed = new bool[_board.Size, _board.Size];
int[,] open = new int[_board.Size, _board.Size];
Pos[,] parent = new Pos[_board.Size, _board.Size];
PriorityQueue<PQNode> pq = new PriorityQueue<PQNode>();

closed: 이미 방문한 노드 표시
open: 최적 경로 비용(F) 저장
parent: 각 노드의 부모 노드 저장 (경로 추적용)
pq: 우선순위 큐 → F 값이 작은 노드가 우선 탐색됨

5.3 시작점 예약

open[PosY, PosX] = 10 * (Math.Abs(_board.DestY - PosY) + Math.Abs(_board.DestX - PosX));
pq.Push(new PQNode() { F = open[PosY, PosX], G = 0, Y = PosY, X = PosX });
parent[PosY, PosX] = new Pos(PosY, PosX);

G = 0, H = 맨해튼 거리(남은 타일 수 * 10)

**5.4 A* 탐색 루프**

while (pq.Count > 0)
{
    PQNode node = pq.Pop();
    if (closed[node.Y, node.X]) continue;
    closed[node.Y, node.X] = true;

    if (node.Y == _board.DestY && node.X == _board.DestX) break;

우선순위 큐에서 F 값이 가장 작은 노드를 꺼냄
이미 방문한 좌표는 무시
목적지 도착 시 루프 종료

5.5 인접 노드 탐색 및 예약

for (int i = 0; i < deltaY.Length; i++)
{
    int nextY = node.Y + deltaY[i];
    int nextX = node.X + deltaX[i];

    if (nextX < 0 || nextX >= _board.Size || nextY < 0 || nextY >= _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 = 10 * (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);
}

유효한 이동인지 확인 (맵 범위, 벽 여부, 방문 여부)
비용(G, H, F) 계산 후 우선순위 큐에 추가
부모 노드(parent 배열)에 현재 노드를 저장 (경로 추적용)

6. `CalcPathFromParent()` - 경로 추적

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();
}

목적지에서 시작점까지 역추적하여 경로 리스트에 저장
리스트를 뒤집어 정방향으로 변환

Jaemyeong Lee

李家네_공부방

이전 포스트

우선순위 큐

다음 포스트

A* 구현

C#과 유니티로 만드는 MMORPG 게임 개발 시리즈

전체 코드

**1. A* 알고리즘이란?**

**1.1 A* 알고리즘의 핵심 요소**

1.2 다익스트라 vs A*

2. `Pos` 클래스

3. `Player` 클래스

3.1 필드 및 변수

4. `PQNode` 구조체 (우선순위 큐 노드)

**5. `AStar()` 함수 (A* 알고리즘 실행)**

5.1 탐색 방향 및 비용

5.2 탐색 상태 배열

5.3 시작점 예약

**5.4 A* 탐색 루프**

5.5 인접 노드 탐색 및 예약

6. `CalcPathFromParent()` - 경로 추적

우선순위 큐

에디터 입문

0개의 댓글

A* 구현

C#과 유니티로 만드는 MMORPG 게임 개발 시리즈

전체 코드

1. A* 알고리즘이란?

1.1 A* 알고리즘의 핵심 요소

1.2 다익스트라 vs A*

2. Pos 클래스

3. Player 클래스

3.1 필드 및 변수

4. PQNode 구조체 (우선순위 큐 노드)

5. AStar() 함수 (A* 알고리즘 실행)

5.1 탐색 방향 및 비용

5.2 탐색 상태 배열

5.3 시작점 예약

5.4 A* 탐색 루프

5.5 인접 노드 탐색 및 예약

6. CalcPathFromParent() - 경로 추적

우선순위 큐

에디터 입문

0개의 댓글

**1. A* 알고리즘이란?**

**1.1 A* 알고리즘의 핵심 요소**

2. `Pos` 클래스

3. `Player` 클래스

4. `PQNode` 구조체 (우선순위 큐 노드)

**5. `AStar()` 함수 (A* 알고리즘 실행)**

**5.4 A* 탐색 루프**

6. `CalcPathFromParent()` - 경로 추적