Chapter 3-4. 오른 손 법칙
카테고리: Algorithm Lesson 2
인프런에 있는 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)
{
// ...
}
}
}
미로 배열에서 인덱스 [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에 설정만 해주면 된다.
- Update 함수에선 이 리스트에 있는 타일들을 꺼내서
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]) 해야 한다.
- 플레이어 입장에서의 앞 방향으로 가려면 현재 위치에서 PosY +=
- 현재 바라보고 있는 방향이
- 인덱스 1 👉
Left에 대응한다.- 현재 바라보고 있는 방향이
Left일 땐- 플레이어 입장에서의 앞 방향으로 가려면 현재 위치에서 PosY +=
0(frontY[1]), PosX +=-1(frontX[1]) 해야 한다. - 플레이어 입장에서의 오른쪽 방향으로 가려면 현재 위치에서 PosY +=
-1(rightY[1]), PosX +=0(rightX[1]) 해야 한다.
- 플레이어 입장에서의 앞 방향으로 가려면 현재 위치에서 PosY +=
- 현재 바라보고 있는 방향이
- 인덱스 2 👉
Down에 대응한다.- 현재 바라보고 있는 방향이
Down일 땐- 플레이어 입장에서의 앞 방향으로 가려면 현재 위치에서 PosY +=
1(frontY[2]), PosX +=0(frontX[2]) 해야 한다. - 플레이어 입장에서의 오른쪽 방향으로 가려면 현재 위치에서 PosY +=
0(rightY[2]), PosX +=-1(rightX[2]) 해야 한다.
- 플레이어 입장에서의 앞 방향으로 가려면 현재 위치에서 PosY +=
- 현재 바라보고 있는 방향이
- 인덱스 3 👉
Right에 대응한다.- 현재 바라보고 있는 방향이
Right일 땐- 플레이어 입장에서의 앞 방향으로 가려면 현재 위치에서 PosY +=
0(frontY[3]), PosX +=1(frontX[3]) 해야 한다. - 플레이어 입장에서의 오른쪽 방향으로 가려면 현재 위치에서 PosY +=
1(rightY[3]), PosX +=0(rightX[3]) 해야 한다.
- 플레이어 입장에서의 앞 방향으로 가려면 현재 위치에서 PosY +=
- 현재 바라보고 있는 방향이
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에 변경된 플레이어의 타일 위치를 추가한다.
- 오른쪽으로 90 도 회전한 후
- 1️⃣ 오른쪽으로 간다.
- 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에 저장해 두었던걸 꺼내어 설정하면 된다.
- 그저 Initialize 에서 오른손 법칙에 의해서 찾은 길의 타일들을 미리 리스트
🌜 개인 공부 기록용 블로그입니다. 오류나 틀린 부분이 있을 경우
언제든지 댓글 혹은 메일로 지적해주시면 감사하겠습니다! 😄
댓글남기기