[길찾기 알고리즘] 1. 미로 준비 (5) 오른손 법칙

개념

- 미로에 오른손을 기준으로 벽을 짚고 가면 목적지까지 도달

- 최단 경로는 아님

- 모든 벽이 이어져 있어야 유효

- 중간에 벽이 끊겨 있으면 무한히 순환

Player.cs

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

namespace CSharpAlgorithm
{
    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 rand = 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)
        {
            PosY = posY;
            PosX = posX;
            _board = board;

            // 상하좌우 이동 좌표 변화
            // 현재 바라보고 있는 방향 기준
            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)
                {
                    // 오른쪽 방향으로 90도 회전
                    _dir = (_dir - 1 + 4) % 4;
                    // 이동
                    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;  // 0.1초
        int _sumTick = 0;
        int _lastIndex = 0;
        public void Update(int deltaTick)
        {
            if (_lastIndex >= _points.Count)
                return;
            // 프레임 맞추기
            _sumTick += deltaTick;
            if (_sumTick >= MOVE_TICK)
            {
                _sumTick = 0;

                // 0.1 초마다 실행할 로직
                PosY = _points[_lastIndex].Y;
                PosX = _points[_lastIndex].X;
                _lastIndex++;
            }
        }
    }
}

Board.cs

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

namespace CSharpAlgorithm
{
    class Board
    {
        const char CIRCLE = '\u25A0';

        public TileType[,] Tile { get; private set; }   // 2차원 배열
        public int Size { get; private set; }

        // 목적지 좌표
        public int DestY { get; private set; }
        public int DestX { get; private set; }

        Player _player;

        public enum TileType
        {
            Empty,
            Wall,
        }

        public void Initialize(int size, Player player)
        {
            // 미로 변의 길이 홀수인지 확인
            if (size % 2 == 0)
                return;

            _player = player;

            Tile = new TileType[size, size];
            Size = size;

            // 목적지 설정
            DestY = Size - 2;
            DestX = Size - 2;

            // GenerateByBinaryTree();
            GenerateBySideWinder();
        }
        public void GenerateByBinaryTree()
        {
            // 바둑판 모양
            for (int y = 0; y < Size; y++)
            {
                for (int x = 0; x < Size; x++)
                {
                    if (x % 2 == 0 || y % 2 == 0)
                        Tile[y, x] = TileType.Wall;
                    else
                        Tile[y, x] = TileType.Empty;
                }
            }
            // 빈 공간에서 아래 or 오른쪽으로 길 만들기
            Random rand = new Random();
            for (int y = 0; y < Size; y++)
            {
                for (int x = 0; x < Size; x++)
                {
                    if (x % 2 == 0 || y % 2 == 0)
                        continue;

                    // 마지막 위치 예외 처리
                    if (y == Size - 2 && x == Size - 2)
                        continue;
                    // 오른쪽 벽 예외 처리
                    if (y == Size - 2)
                    {
                        Tile[y, x + 1] = TileType.Empty;
                        continue;
                    }
                    // 아래쪽 벽 예외 처리
                    if (x == Size - 2)
                    {
                        Tile[y + 1, x] = TileType.Empty;
                        continue;
                    }

                    if (rand.Next(0, 2) == 0)
                        // 오른쪽으로 길 생성
                        Tile[y, x + 1] = TileType.Empty;
                    else
                        // 아래쪽으로 길 생성
                        Tile[y + 1, x] = TileType.Empty;
                }
            }
        }
        public void GenerateBySideWinder()
        {
            // 바둑판 모양
            for (int y = 0; y < Size; y++)
            {
                for (int x = 0; x < Size; x++)
                {
                    if (x % 2 == 0 || y % 2 == 0)
                        Tile[y, x] = TileType.Wall;
                    else
                        Tile[y, x] = TileType.Empty;
                }
            }
            // 빈 공간에서 아래 or 오른쪽으로 길 만들기
            Random rand = new Random();
            for (int y = 0; y < Size; y++)
            {
                int count = 1;
                for (int x = 0; x < Size; x++)
                {
                    if (x % 2 == 0 || y % 2 == 0)
                        continue;

                    // 마지막 위치 예외 처리
                    if (y == Size - 2 && x == Size - 2)
                        continue;
                    // 오른쪽 벽 예외 처리
                    if (y == Size - 2)
                    {
                        Tile[y, x + 1] = TileType.Empty;
                        continue;
                    }
                    // 아래쪽 벽 예외 처리
                    if (x == Size - 2)
                    {
                        Tile[y + 1, x] = TileType.Empty;
                        continue;
                    }

                    // 오른쪽 또는 아래쪽으로 확장
                    // 방향 변경 시 지나온 길 중 벽 위치에서 길 만들기
                    if (rand.Next(0, 2) == 0)
                    // 오른쪽으로 길 생성
                    {
                        Tile[y, x + 1] = TileType.Empty;
                        count++;
                    }
                    else
                    // 아래쪽으로 길 생성
                    {
                        int randIndex = rand.Next(0, count);
                        Tile[y + 1, x] = TileType.Empty;
                        count = 1;
                    }
                }
            }
        }
        public void Render()
        {
            ConsoleColor prevColor = Console.ForegroundColor;

            for (int y = 0; y < Size; y++)
            {
                for (int x = 0; x < Size; x++)
                {
                    // 플레이어 좌표가 현재 좌표와 일치하면 플레이어 전용 색상으로 표시
                    if (y == _player.PosY && x == _player.PosX)
                        Console.ForegroundColor = ConsoleColor.Blue;
                    // 목적지 좌표 다른 색상으로 표시
                    else if (y == DestY && x == DestX)
                        Console.ForegroundColor = ConsoleColor.Yellow;
                    else
                        Console.ForegroundColor = GetTileColor(Tile[y, x]);

                    Console.Write(CIRCLE);
                    Console.Write(' ');
                }
                Console.WriteLine();
            }

            Console.ForegroundColor = prevColor;
        }

        ConsoleColor GetTileColor(TileType type)
        {
            switch (type)
            {
                case TileType.Empty:
                    return ConsoleColor.Green;
                case TileType.Wall:
                    return ConsoleColor.Red;
                default:
                    return ConsoleColor.Green;
            }
        }
    }
}

Program.cs

using System;

namespace CSharpAlgorithm
{
    class Program
    {
        static void Main(string[] args)
        {
            Board board = new Board();
            Player player = new Player();
            board.Initialize(25, player);
            player.Initialize(1, 1, board);

            Console.CursorVisible = false;
            
            const int WAIT_TICK = 1000 / 30;
            int lastTick = 0;


            while (true)
            {
                #region 프레임 관리
                // 만약 경과한 시간이 1/30초보다 작으면
                int currentTick = System.Environment.TickCount;
                if (currentTick - lastTick < WAIT_TICK)
                    continue;
                int deltaTick = currentTick - lastTick;
                lastTick = currentTick;
                #endregion

                // 입력

                // 로직
                player.Update(deltaTick);

                // 렌더링
                Console.SetCursorPosition(0, 0);
                board.Render();
            }
        }
    }
}

내용 출처 : Inflearn Rookiss님 강의 [C#과 유니티로 만드는 MMORPG 게임 개발 시리즈] Part2: 자료구조와 알고리즘

https://www.inflearn.com/course/%EC%9C%A0%EB%8B%88%ED%8B%B0-mmorpg-%EA%B0%9C%EB%B0%9C-part2