A* 알고리즘 구현 (Unity, C# 환경)

A-Star PathFinding.unitypackage

0.03MB

유니티에서 제공하는 NavMesh가 있지만, 이는 지형에 활용하는 개념이기에 그리드(Grid, Board)에서 움직이는 것을 구현하는 것에는 부적합합니다. 그래서 보통은 따로 개발을 하기도 합니다.

 

언젠가는 사용할 것 같아서(예를 들어 보드게임 같이 말이 움직이는 컨텐츠 구현), 개인적으로 공부하면서 작업을 해보고자는 생각에 공부 겸 글을 작성하게 되었습니다.

 

과거에도 한 번 구현하여 블로그에 배포한 적이 있었는데, 그때는 MFC를 통해서 구현한 것을 포스팅 및 배포했었습니다. 하지만 요즘은 전반적으로 툴을 주로 다루기도 하고, 제가 주로 유니티를 다루고 있어서, 이번에는 유티니에서 사용하여 보여드리겠습니다. 유니티를 통한 구현이지만 스크립트는 유니티 환경에 국한되지 않습니다.

길찾기 예제 플레이 영상(간만에 만들어서 그런지 좀 헤맸었네요.😂)

벽이 있는 경우 길찾기

알고리즘의 이해

1. 현재 위치에서 주변 블럭들의 거리 가중치를 계산해준다.

 1) 시작 지점으로부터 현재 지점까지의 거리

 2) 도착 지점으로부터 현재 지점까지의 거리

 3) 1) + 2) = 현재 블럭의 가중치를 의미

2. 시작 지점으로부터 멀어지면서, 도착 지점까지의 거리가 가까운 주변 블럭을 찾는다. (이는 다음 이동할 블럭을 의미한다.)

3. 다음 이동 위치를 기준으로 알고리즘을 반복한다.

 1) 반복하는 도중 막혔다면, 검사하지 않은 블럭들을 찾아서 검사한다.

 

길찾기 스크립트

1. AStar.cs

using System;
using System.Collections.Generic;

namespace Map.PathFinding
{
    public static class AStar
    {
        /// <summary>
        /// 길찾기
        /// </summary>
        /// <param name="board">맵</param>
        /// <param name="start">시작 좌표</param>
        /// <param name="dest">도착 좌표</param>
        /// <returns>시작점 반환</returns>
        public static Block PathFinding(this Board board, Block start, Block dest)
        {
            if (board.Exists(start) && board.Exists(dest))
            {
                board.CheckClear();

                List<Block> waittingBlocks = new List<Block>();
                List<Block> finishedBlocks = new List<Block>();

                Block current = start;

                while (current != null)
                {
                    // 주변 블럭 가져오기
                    var aroundBlocks = board.GetAroundBlocks(current);

                    for (int i = 0; i < aroundBlocks.Count; i++)
                    {
                        var block = aroundBlocks[i];
                        if (!waittingBlocks.Equals(block) && !block.check)
                            waittingBlocks.Add(block);
                    }

                    // 검사 완료 리스트로 이관
                    current.check = true;
                    if (waittingBlocks.Remove(current))
                        finishedBlocks.Add(current);

                    // 이동 불가 시, 길찾기 실패 처리
                    if (aroundBlocks.Count == 0)
                        return null;
                    else
                    {
                        // 부모 세팅
                        aroundBlocks = aroundBlocks.FindAll(block => !block.check);
                    }

                    // 주변 블럭 가격 계산
                    CalcRating(aroundBlocks, start, current, dest);

                    // 다음 검사 블록 가져오기
                    current = GetNextBlock(aroundBlocks, current);
                    if (current == null)
                    {
                        // 다음 블록 탐색 실패 시, 처음부터 재시작
                        current = GetPriorityBlock(waittingBlocks);

                        // 더이상 검사할 곳이 없다면(길을 찾지 못 한 경우 해당),
                        // 길찾기 종료 및 도착점과 가장 가까운 막힌 곳으로 안내.
                        if (current == null)
                        {
                            Block exceptionBlock = null;
                            for (int i = 0; i < finishedBlocks.Count; i++)
                            {
                                if (exceptionBlock == null || exceptionBlock.H > finishedBlocks[i].H)
                                    exceptionBlock = finishedBlocks[i];
                            }
                            current = exceptionBlock;
                            break;
                        }
                    }
                    else if (current.Equals(dest))
                    {
                        break;
                    }
                }

                // 역으로 길을 만들어준다.
                while (!current.Equals(start))
                {
                    current.prev.next = current;
                    current = current.prev;
                }

                start.prev = null;
                return start;
            }
            return null;
        }

        /// <summary>
        /// 검사 대기 블럭 중에서 가격이 가장 낮은 블럭을 가져오기
        /// </summary>
        /// <param name="waittingBlocks"></param>
        /// <returns></returns>
        private static Block GetPriorityBlock(List<Block> waittingBlocks)
        {
            // 블럭 위치에 따른 가격이 제일 낮은 블럭을 반환다.
            Block block = null;
            var enumerator = waittingBlocks.GetEnumerator();
            while (enumerator.MoveNext())
            {
                var current = enumerator.Current;
                if (block == null || block.F < current.F)
                {
                    block = current;
                }
            }

            return block;
        }

        /// <summary>
        /// 다음 이동 블록 가져오기
        /// </summary>
        /// <param name="arounds"></param>
        /// <param name="current"></param>
        /// <returns></returns>
        private static Block GetNextBlock(List<Block> arounds, Block current)
        {
            Block minValueBlock = null;
            for (int i = 0; i < arounds.Count; i++)
            {
                Block next = arounds[i];
                if (!next.check)
                {
                    // 다음 경로 이동을 해야하니, 시작점으로부터의 가격이 더 높은 블록을 탐색한다.
                    if (minValueBlock == null)
                    {
                        minValueBlock = next;
                    }
                    else if (minValueBlock.H > next.H)
                    {
                        minValueBlock = next;
                    }
                }
            }
            return minValueBlock;
        }

        /// <summary>
        /// 주변 블록 가격 계산하기
        /// </summary>
        /// <param name="arounds">주변 블록 리스트</param>
        /// <param name="start">시작 블록</param>
        /// <param name="current">현재 위치 블록</param>
        /// <param name="dest">도착 블록</param>
        private static void CalcRating(List<Block> arounds, Block start, Block current, Block dest)
        {
            if (arounds != null)
            {
                for (int i = 0; i < arounds.Count; i++)
                {
                    var block = arounds[i];
                    bool isDiagonalBlock = Math.Abs(block.x - current.x) == 1 && Math.Abs(block.y - current.y) == 1;
                    int priceFromDest = (Math.Abs(dest.x - block.x) + Math.Abs(dest.y - block.y)) * 10;
                    if (block.prev == null)
                        block.prev = current;
                    block.SetPrice(current.G + (isDiagonalBlock ? 14 : 10), priceFromDest);
                }
            }
        }
    }
}

 

2. Board.cs

using System;
using System.Collections.Generic;

namespace Map
{
    public class Board
    {
        public Block[,] blocks;

        public Board(int width, int height)
        {
            blocks = new Block[width, height];
            for (int i = 0; i < blocks.GetLength(0); i++)
            {
                for (int j = 0; j < blocks.GetLength(1); j++)
                {
                    blocks[i, j] = new Block(i, j);
                }
            }
        }

        public void SetBlock(int x, int y, bool wall)
        {
            blocks[x, y].wall = wall;
        }

        public void CheckClear()
        {
            foreach (Block block in blocks)
            {
                block.Clear();
            }
        }

        public bool Exists(Block block)
        {
            return Exists(block.x, block.y);
        }

        public bool Exists(int x, int y)
        {
            foreach (Block block in blocks)
            {
                if (block.x == x && block.y == y)
                    return true;
            }
            return false;
        }

        /// <summary>
        /// 주변 블록 가져오기
        /// </summary>
        /// <param name="target"></param>
        /// <returns></returns>
        public List<Block> GetAroundBlocks(Block target)
        {
            //[-1,-1] [ 0,-1] [ 1,-1]
            //[-1, 0]         [ 1, 0]
            //[-1, 1] [ 0, 1] [ 1, 1]

            List<Block> arounds = new List<Block>();
            if (Exists(target.x - 1, target.y - 1))
            {
                Block block = blocks[target.x - 1, target.y - 1];
                arounds.Add(block);
            }
            if (Exists(target.x, target.y - 1))
            {
                Block block = blocks[target.x, target.y - 1];
                arounds.Add(block);
            }
            if (Exists(target.x + 1, target.y - 1))
            {
                Block block = blocks[target.x + 1, target.y - 1];
                arounds.Add(block);
            }

            if (Exists(target.x - 1, target.y))
            {
                Block block = blocks[target.x - 1, target.y];
                arounds.Add(block);
            }
            if (Exists(target.x + 1, target.y))
            {
                Block block = blocks[target.x + 1, target.y];
                arounds.Add(block);
            }

            if (Exists(target.x - 1, target.y + 1))
            {
                Block block = blocks[target.x - 1, target.y + 1];
                arounds.Add(block);
            }
            if (Exists(target.x, target.y + 1))
            {
                Block block = blocks[target.x, target.y + 1];
                arounds.Add(block);
            }
            if (Exists(target.x + 1, target.y + 1))
            {
                Block block = blocks[target.x + 1, target.y + 1];
                arounds.Add(block);
            }

            // 대각선 블록인 경우 정방향블록이 벽이면 제외한다.
            for (int i = arounds.Count - 1; i >= 0 ; i--)
            {
                Block block = arounds[i];
                bool isDiagonalBlock = Math.Abs(block.x - target.x) == 1 && Math.Abs(block.y - target.y) == 1;
                if (isDiagonalBlock)
                {
                    // 가로 블록 벽인지 확인
                    Block blockX = arounds.Find(b => b.x == block.x && b.y == target.y);
                    if (blockX.wall)
                        arounds.Remove(block);

                    // 세로 블록 벽인지 확인
                    Block blockY = arounds.Find(b => b.x == target.x && b.y == block.y);
                    if (blockY.wall)
                        arounds.Remove(block);
                }
            }

            // 벽 블록 제거
            arounds.RemoveAll(b => b.wall);

            return arounds;
        }
    }
}

 

3. Block.cs

namespace Map
{
    public class Block
    {
        /// <summary>
        /// 좌표
        /// </summary>
        public int x, y;

        /// <summary>
        /// 닫힌 블럭인지 여부
        /// </summary>
        public bool wall;

        //===========================================================================================================
        // 아래의 변수와 메소드는 계산때만 활용. (상속이나 다른 처리가 필요할 듯.)
        //===========================================================================================================

        /// <summary>
        /// 블럭 위치에 따른 가격 (거리 가중치)
        /// </summary>
        public int F => G + H;

        /// <summary>
        /// 시작점과의 거리
        /// </summary>
        public int G { get; private set; } = 0;

        /// <summary>
        /// 도착점과의 거리
        /// </summary>
        public int H { get; private set; } = 0;

        /// <summary>
        /// 검사 여부
        /// </summary>
        public bool check = false;

        /// <summary>
        /// 이전 블럭
        /// </summary>
        public Block prev = null;

        /// <summary>
        /// 다음 블럭
        /// </summary>
        public Block next = null;

        public Block(int x, int y)
        {
            this.x = x;
            this.y = y;
        }

        /// <summary>
        /// 가격 세팅
        /// </summary>
        /// <param name="g"></param>
        /// <param name="h"></param>
        public void SetPrice(int g, int h)
        {
            this.G = g;
            this.H = h;
        }

        public void Clear()
        {
            check = false;
            G = 0;
            H = 0;
            prev = null;
            next = null;
        }
    }
}

 

사용 예제

// 시작 지점 반환
var startBlock = AStar.PathFinding(보드(맵), 시작지점, 도착지점);

위의 코드를 호출하면 시작 지점을 반환해주고, 시작 지점에서 next로 선언된 블록 변수를 읽어오면됩니다. (연결 리스트 구조)