BFS를 이용한 길찾기 구현

전체 코드

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

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

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

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

1. BFS 개요

1.1 BFS란?

BFS(Breadth-First Search, 너비 우선 탐색)는 그래프에서 최단 경로를 찾을 때 사용되는 탐색 알고리즘입니다.
BFS는 한 정점에서 시작하여 인접한 모든 정점을 먼저 탐색한 후, 탐색된 정점에서 다시 인접한 정점을 탐색하는 방식으로 진행됩니다.
이를 통해 모든 경로의 가중치가 같다면, 가장 먼저 도착한 경로가 최단 경로임을 보장할 수 있습니다.

1.2 BFS를 사용한 길 찾기 원리

미로를 그래프로 표현할 수 있습니다.

• 미로의 각 타일(칸)을 정점(Vertex) 으로 봅니다.
• 한 칸에서 이동 가능한 칸이 있으면 간선(Edge) 이 연결된 것으로 봅니다.
• 벽인 칸은 연결이 되지 않습니다.
• BFS를 사용하면 최단 경로를 찾을 수 있습니다.

---

2. BFS 길찾기 알고리즘

2.1 BFS 탐색 과정

1. 초기화

   • Queue 를 사용하여 시작 지점을 삽입하고, 방문 체크 배열(found)을 설정합니다.
   • 부모 정보 배열(parent)을 생성하여 경로를 추적할 수 있도록 합니다.

2. 탐색 과정

   • Queue에서 정점을 꺼내고, 4방향(상, 좌, 하, 우) 을 확인합니다.
   • 이동 가능한 곳이면 Queue에 삽입하고, found를 갱신하며, 부모 정보도 기록합니다.
   • 도착 지점이 Queue에서 꺼내지면 탐색을 중단합니다.

3. 경로 추적

   • 도착 지점에서 출발 지점까지 부모 노드를 따라가며 최단 경로를 리스트에 저장합니다.
   • 저장된 경로 리스트를 역순으로 뒤집어 최단 경로를 얻습니다.

---

3. BFS 길찾기 예제 코드

using System;
using System.Collections.Generic;

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

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

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

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

            BFS();
        }

        void BFS()
        {
            int[] deltaY = { -1, 0, 1, 0 }; // Up, Left, Down, Right
            int[] deltaX = { 0, -1, 0, 1 };

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

            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];

                    // 범위를 벗어나거나, 벽이면 continue
                    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;
            }
            _points.Add(new Pos(y, x)); // 출발점 추가
            _points.Reverse(); // 최단 경로로 정렬
        }

        public void Update(int deltaTick)
        {
            if (_points.Count == 0)
                return;

            PosY = _points[0].Y;
            PosX = _points[0].X;
            _points.RemoveAt(0);
        }
    }
}

---

4. 코드 설명

4.1 BFS() 함수

• Queue를 활용하여 BFS 탐색을 진행합니다.
• 4방향(상, 좌, 하, 우) 이동을 확인하여 큐에 추가합니다.
• found 배열을 활용해 중복 방문을 방지합니다.
• parent 배열을 사용하여 경로를 추적합니다.

4.2 경로 추적

• 도착 지점에서 시작하여 parent 정보를 따라가며 리스트에 저장합니다.
• 리스트를 Reverse() 하여 출발점에서 도착점으로 가는 최단 경로를 얻습니다.

4.3 Update() 함수

• _points 리스트를 활용하여 경로를 따라 이동합니다.
• 리스트에서 첫 번째 요소를 제거하며 이동 경로를 업데이트합니다.

---

5. BFS의 한계점

5.1 BFS의 단점

• 가중치가 있는 그래프에서는 사용할 수 없음
  BFS는 모든 간선의 비용이 동일한 경우에만 최단 경로를 찾을 수 있습니다.
  만약 지형별 이동 비용이 다르다면 BFS는 사용할 수 없습니다.

• 대각선 이동이 포함된 경우
  BFS는 4방향 이동을 기준으로 하기 때문에 대각선 이동이 포함되면 거리가 다르게 측정될 수 있습니다.

5.2 해결 방법

• 가중치가 있는 그래프에서 최단 경로를 찾으려면 다익스트라(Dijkstra) 알고리즘을 사용해야 합니다.
• A* 알고리즘을 활용하면 특정 목표 지점까지의 탐색을 최적화할 수 있습니다.

---