미로 탐색 알고리즘 : 우선법

우선법 ( Right Hand On Wall )

갈림길을 만났을 때 우선적으로 오른쪽으로 간다.

while(Still_In_Maze){

    Turn Right;
    while(Wall_Ahead){
    
    	Turn Left;
    }
    Go Foward;
}

 

기본 함수들

void Maze::GoForward(int &x, int &y, int dir){

    x = (dir == LEFT ? --x : dir == RIGHT ? ++x : x);
    y = (dir == UP ? --y : dir == DOWN ? ++y : y);
}

bool Maze::StillInMaze(int x, int y){

    if(x > 0 && z < MAZE_SIZE -1 && y > 0 && y < MAZE_SIZE -1)
    	return true;
    else
    	return false;
}

bool Maze::WallAhead(int x, int y, int dir){

    x = (dir == LEFT ? --x : dir == RIGHT ? ++x : x);
    y = (dir == UP ? --y : dir == DOWN ? ++y : y);
    return m_arrayMaze[y][x]!=0;
}

 

UP = 1, RIGHT = 2, DOWN = 4, LEFT = 8

-> bit를 하나씩 쉬프트 하면 4가지 동작이 순환되듯이 돌아간다.

 

void Maze::TurnLeft(int &dir){

    dir >>= 1;
    dir = (dir == 0 ? LEFT : dir);
} // 왼쪽으로 돌아라

void Maze::TurnRight(int &dir){

    dir <<= 1; // 왼쪽으로 쉬프트
    dir = (dir > LEFT ? UP : dir);
} // 오른쪽으로 돌아라

void Maze::RightHandOnWall(int x, int y, int dir){

    while (StillInMaze(x,y)){
    
        TurnRight(dir);
        while (WallAhead(x,y,dir)){
        
        	TurnLeft(dir);
        }
        GoFoward(x,y,dir);
} // 우선법