[Maze] Chapter 02. 오른손 법칙 (우수법)

GitHub : https://github.com/developeSHG/Data_Structure-Algorithm/commits/01.Maze

GitHub - developeSHG/Data_Structure-Algorithm: Data Structure & Algorithm

 

결과물

 

 

---

 

 

만약 미로에 갇혔을 때, 탈출하려면 무식하면서도 직관적인 방법이 하나 있다.

바로 오른손 법칙. 오른손으로 벽을 만지면서 가는 것을 얘기한다.  우수법이라고도 한다.

하지만 100% 확률로 모든 미로에서 적용되는 것은 아니고, 출구까지 길이 어떻게든 이어져있다는 게 보장이 되고, 순환 구조로 뺑뺑이를 돌지 않는 미로라고 하면 적용된다.

 

하지만, 길찾기 알고리즘이라고 하기엔 최적의 길이 아닌 불필요한 길까지 통과하게 되니 최적화된 최단거리를 찾아주는 코드라고 볼 수 없다. 무식한 출구찾기 알고리즘이다.

 

Player.cpp

- Init에서 Board(미로판)의 출구까지 오른손 법칙의 규칙으로 pos를 path에 저장해둠.

- Update에서 100ms을 기준으로 pos를 변화. (Init에서 미리 출구까지의 path를 갖고 있으니 tick이 경과하면 pathIndex를 변경)

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;
			/*
			switch (_dir)
			{
			case DIR_UP:
				_dir = DIR_LEFT;
				break;
			case DIR_LEFT:
				_dir = DIR_DOWN;
				break;
			case DIR_DOWN:
				_dir = DIR_RIGHT;
				break;
			case DIR_RIGHT:
				_dir = DIR_UP;
				break;
			}
			*/
		}
	}
}

void Player::Update(uint64 deltaTick)
{
	if (_pathIndex >= _path.size())
		return;

	_sumTick += deltaTick;
	if (_sumTick >= MOVE_TICK)
	{
		_sumTick = 0;

		_pos = _path[_pathIndex];
		_pathIndex++;
	}
}

bool Player::CanGo(Pos pos)
{
	TileType tileType = _board->GetTileType(pos);
	return tileType == TileType::EMPTY;
}