미로 - 오른손 법칙

오른손 법칙

• 미로를 통과하기 위한 길찾기 알고리즘 중 가장 간단한 알고리즘.

• 오른손으로 벽을 짚으며 미로를 빠져나가는 알고리즘이다.

• 오른쪽에 갈 수 있는 길이 있으면 오른쪽 길로 가고 오른쪽 길이 막혀있으면 앞으로 전진, 앞으로 가는길 또한 막혀있다면, 왼쪽 방향으로 몸을 회전하여 길을 탐색.

• 간단하지만 불 필요한 움직임이 있을 수 밖에 없는 알고리즘.

enum Dir
{
	DIR_UP = 0,
	DIR_LEFT = 1,
	DIR_DOWN = 2,
	DIR_RIGHT = 3,

	DIR_COUNT = 4,
};


class Player
{
	enum
	{
		MOVE_TICK=100
	};
public:
	void	Init(Board* board);
	void	Update(uint64 deltaTick);

	void	SetPos(Pos pos) { _pos = pos; }
	Pos		GetPos() { return _pos; }

	bool	CanGo(Pos pos);
private:
	Pos _pos = {};
	int32 _dir = DIR_UP;
	Board* _board = nullptr;

	vector<Pos> _path;
	uint32 _pathIndex = 0;
	uint64 _sumTick = 0;
};


// Init
void Player::Init(Board* board)
{
	_pos = board->GetEnterPos();
	_board = board;
	
	Pos pos = _pos;

	_path.clear();
	_path.push_back(pos);
	// 목적지 도착 전엔 계속 싦행
	Pos dest = board->GetExitPos();

	Pos front[4] =
	{
		Pos{-1,0},// UP
		Pos{0,-1},// LEFT
		Pos{1,0},// DOWN
		Pos{0,1}// RIGHT
	};

	while (pos != dest)
	{
		// 1. 현재 바라보는 방향을 기준으로 오른쪽으로 갈 수 있는지 확인.
		int32 newDir = (_dir - 1 + DIR_COUNT) % DIR_COUNT;
		if (CanGo(pos + front[newDir]))
		{
			// 오른쪽 방향으로 90도 회전.
			_dir = newDir;

			// 앞으로 한 보 전진.
			pos += front[_dir];
			_path.push_back(pos);
		}
		// 2. 현재 바라보는 방향을 기준으로 전진할 수 있는지 확인
		else if (CanGo(pos + front[_dir]))
		{
			// 앞으로 한 보 전진.
			pos += front[_dir];
			_path.push_back(pos);
		}
		else
		{
			// 왼쪽 방향으로 90도 회전.
			_dir = (_dir + 1) % DIR_COUNT;
		}
	}
}

• 우선 현재 위치가 목적지의 위치인지 판별하여 while문을 반복한다.

• 현재 위치를 기준으로 오른쪽 방향이 갈 수 있는 길인지 판별 (해당 tile이 Empty인지)

• 갈 수 있다면 오른쪽 방향으로 90도 회전하여 전진, 갈 수 없다면 현재 바라보는 방향이 갈 수 있는 길인지 탐색.

• 갈 수 있다면 앞으로 전진, 갈 수 없다면 왼쪽 방향으로 90도 회전 후 위 과정 반복.

결과

• 노란색 Player가 파란색 목적지를 향해 열심히 달려가는 것을 볼 수 있다.

• 보면 알 수 있지만 최단 거리로 가는 것이 아니라 불필요한 움직임이 있다는 것을 알 수 있다.