Chapter 3-4. 오른 손 법칙

Date:     Updated:

카테고리:

태그:

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

Chapter 3. 미로 준비

🚖 목적지

📜Board.cs

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

namespace Algorithm
{
    class Board
    {
        const char CIRCLE = '\u25cf';

        public TileType[,] Tile { get; private set; }  // 맵의 타일들을 담을 배열
        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 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.WriteLine(); 
            }
        }


        void GenerateBySideWinder()
        {
             // ...
        }

        void GenerateByBinaryTree()
        {
             // ...
        }

        ConsoleColor GetTileColor(TileType type)
        {
            // ...
        }
    }
}

image

미로 배열에서 인덱스 [Size - 2][Size - 2] 즉, [DestY][DestX]에 해당하는 타일을 목적지로 정했다. 때문에 미로의 멤버로 DestY, DestX 을 추가해주었고 렌더링시 해당 타일의 위치가 목적지인 [DestY][DestX]와 일치하다면 노란색으로 칠하게 조건문을 추가하였다.


🚖 오른 손 법칙

오른손으로 벽을 만지면서 가면 언젠가는 출구에 도달한다.

  • 길 찾기 알고리즘이라기 보단 길을 가다보니 목적지를 찾았다 이런 느낌이다.
  • 효율적인 길을 찾는 것이 아님. 따라서 길 찾기 알고리즘이 아니다. 단지 오른손으로 벽을 만지면서 출구에 도달하게 되는 것 뿐!
  • 한계
    • 벽이 다 하나로 이루어져 있는 경우에만 가능.
    • 써클이 있다면 무한 루프를 돌게 됨.
    • 오른 손이 닿는 곳이 항상 있어야 된다는 전제가 필요

📜Player.cs

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;

            // 현재 바라보고 있는 방향을 기존으로 좌표 변화를 나타냄
            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++;
            }
        }
    }
}

플레이어의 위치를 0.01 초마다 실행되는 Update 함수에서 0.01초마다 결정하지 말고 Initialize 초기화 될 때 출발지부터 목적지까지 도달하는 길을 게임 시작 전 미리 찾아 해답이 된 길(타일)들을 리스트에 저장한 후 미리 찾아져 저장된 해답 길(리스트 원소들)을 Update 함수에서 가져와보자.

Initialize 때 미리 길 찾아 놓기

  • Initialize(int posY, int posX, Board board)
    • 플레이어 위치 초기 위치를 설정할 때, 오른손 법칙에 의해 찾은 길(방문했던 타일들)을 리스트에 미리 저장한다.
        enum Dir  // 반시계방향
        {
            Up = 0,
            Left = 1,
            Down = 2,
            Right = 3
        }

        int _dir = (int)Dir.Up;

        List<Pos> _points = new List<Pos>();
  • 방향은 4 개의 방향. 반시계 방향으로 Up 👉 Left 👉 Down 👉 Right. 차례 대로 0, 1, 2, 3
  • dir : 현재 플레이어가 바라보고 있는 방향(월드 기준)
    • 연산을 편하기 하기 위해 int 로 변환
  • 오른손 법칙을 통해 길을 찾으면서 방문했던 위치의 타일들을 리스트인 _points에 저장한다.
    • Update 함수에선 이 리스트에 있는 타일들을 꺼내서 PosX, PosY에 설정만 해주면 된다.
            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 };
  • 인덱스 0 👉 Up에 대응한다.
    • 현재 바라보고 있는 방향이 Up일 땐
      • 플레이어 입장에서의 앞 방향으로 가려면 현재 위치에서 PosY += -1(frontY[0]), PosX += 0 (frontX[0]) 해야 한다.
      • 플레이어 입장에서의 오른쪽 방향으로 가려면 현재 위치에서 PosY += 0(rightY[0]), PosX += 1 (rightX[0]) 해야 한다.
  • 인덱스 1 👉 Left에 대응한다.
    • 현재 바라보고 있는 방향이 Left일 땐
      • 플레이어 입장에서의 앞 방향으로 가려면 현재 위치에서 PosY += 0(frontY[1]), PosX += -1 (frontX[1]) 해야 한다.
      • 플레이어 입장에서의 오른쪽 방향으로 가려면 현재 위치에서 PosY += -1(rightY[1]), PosX += 0 (rightX[1]) 해야 한다.
  • 인덱스 2 👉 Down에 대응한다.
    • 현재 바라보고 있는 방향이 Down일 땐
      • 플레이어 입장에서의 앞 방향으로 가려면 현재 위치에서 PosY += 1(frontY[2]), PosX += 0 (frontX[2]) 해야 한다.
      • 플레이어 입장에서의 오른쪽 방향으로 가려면 현재 위치에서 PosY += 0(rightY[2]), PosX += -1 (rightX[2]) 해야 한다.
  • 인덱스 3 👉 Right에 대응한다.
    • 현재 바라보고 있는 방향이 Right일 땐
      • 플레이어 입장에서의 앞 방향으로 가려면 현재 위치에서 PosY += 0(frontY[3]), PosX += 1 (frontX[3]) 해야 한다.
      • 플레이어 입장에서의 오른쪽 방향으로 가려면 현재 위치에서 PosY += 1(rightY[3]), PosX += 0 (rightX[3]) 해야 한다.
            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;
                }
            }

오른손 법칙

목적지에 도달했다면 아래 과정을 멈춘다.

  • 1️⃣ 현재 바라보는 방향을 기준으로 오른쪽으로 갈 수 있다면 👉 현재 위치에서 rightY, rightX 더해도 벽이 아닌지 검사
    • 1️⃣ 오른쪽으로 간다.
      • 오른쪽으로 90 도 회전한 후
        • Up을 바라보고 있었다면 이제 Right을 바라본다. (0 👉 3)
        • Left을 바라보고 있었다면 이제 Up을 바라본다. (1 👉 0)
        • Down을 바라보고 있었다면 이제 Left을 바라본다. (2 👉 1)
        • Right을 바라보고 있었다면 이제 Down을 바라본다. (3👉 2)
      • 2️⃣ 방향이 바뀐 현재 바라보는 방향을 기준으로 앞으로 간다.
        PosY = PosY + frontY[_dir];
        PosX = PosX + frontX[_dir];
        
      • ⭐ 위치를 업데이트 했으니 리스트 _points에 변경된 플레이어의 타일 위치를 추가한다.
  • 2️⃣ 현재 바라보는 방향을 기준으로 앞 쪽으로 갈 수 있다면 👉 현재 위치에서 frontY, frontX 더해도 벽이 아닌지 검사
    • 현재 바라보는 방향을 기준으로 앞으로 간다.
      PosY = PosY + frontY[_dir];
      PosX = PosX + frontX[_dir];
      
    • ⭐ 위치를 업데이트 했으니 리스트 _points에 변경된 플레이어의 타일 위치를 추가한다.
  • 오른쪽, 앞쪽 방향으로 전진할 수 없다면, 왼쪽 방향으로 90 도 회전하여 다음 방향을 검사.
    • 다음 반복을 하러 간다.
    • 이런식으로 반 시계 방향으로 4 개의 방향의 갈 수 있느 곳을 검사한다.

Update


        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.01초마다 실행
            {
                _sumTick = 0;

                PosY = _points[_lastIndex].Y;
                PosX = _points[_lastIndex].X;
                _lastIndex++;
            }
        }
  • 0.01 초마다 플레이어 위치 설정하기
    • 그저 Initialize 에서 오른손 법칙에 의해서 찾은 길의 타일들을 미리 리스트 _points에 저장해 두었던걸 꺼내어 설정하면 된다.

image



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

맨 위로 이동하기

댓글남기기