[미로] 길 찾기 알고리즘 - 오른손 법칙

오른손 법칙이란? 미로의 시작 점에서 오른손을 벽에 대고 이동하면서, 벽에서 손을 떼지 않고 계속 이동하는 방법이다.

알고리즘 :

• 플레이어는 초반 방향에 대해서 오른손 방향에 벽이 있는지 여부를 확인하고, 벽이 없다면 오른 방향으로 회전 후 이동한다.
• 만약, 오른 방향에 벽이 있으면서 직진 방향이 뚫려 있다면, 직진한다.
• 오른 방향, 직진 모두 벽이 있다면 왼쪽으로 회전한다.

[ 오른 방향 회전 → 시계 방향 ]

• 북→동→남→서→북 순으로 이동하기 위해서는, 시계 방향으로 회전한다.
  • (방향 개수+현재 방향 인덱스-1)%방향 개수

[ 왼 방향 회전 → 반 시계 방향]

• 북→서→남→동→북 순으로 이동하기 위해서는 반 시계 방향으로 회전한다.
  • (현재 방향 인덱스+1)%방향 개수

현재 코드에서 제한 사항:

• 출구로 나갈 수 있는 길이 없는 경우에 (보드 사이즈^2)만큼 이동해보고, 출구를 못 찾으면 게임 끝이다.

아래 코드에 대한 변수 설명:

• _path: 플레이어 이동 루틴을 보여주기 위해서 Pos를 저장하는 벡터
• pos: 플레이어의 이동 위치, 구조체로, row-col을 저장하기 위해 pair로 이루어져있음.
• newDir: 새로운 방향
• D_COUNT: 방향 개수

//주요 오른손 법칙 알고리즘
//이동을 위한 UP/LEFT/DOWN/RIGHT 배열
int rows[4] = {-1,0,1,0};
int cols[4] = {0,-1,0,1};

while (pos != exitPos)
	{
		//오른쪽 방향 이동
		if (cnt == (_board->GetSize() * _board->GetSize()))
			break; //못나오는 경우, 게임 끝

		int32 newDir = (D_COUNT + _dir - 1) % D_COUNT;

		Pos nextRight =Pos{ make_pair(pos.pos.first + rows[newDir], pos.pos.second + cols[newDir])};
		Pos nextUp = Pos{ make_pair(pos.pos.first + rows[_dir], pos.pos.second + cols[_dir]) };
		
		if (CanGo(Pos{ nextRight }))
		{
			//오른쪽 비어있음 이동
			_dir = newDir;
			pos = nextRight;
			_path.push_back(nextRight);
		}
		else if (CanGo(Pos{ nextUp }))
		{
			//직선 비어있음 이동		
			pos = nextUp;
			_path.push_back(nextUp);
		}
		else
		{
			//왼쪽으로 회전
			_dir = (_dir + 1) % D_COUNT;
		}
		cnt++;
	}