BFS를 이용한 길찾기

오른손법칙때 사용한 미로맵 포스팅 클릭

이전에 오른손법칙으로 길찾는 방법은 사실 길찾는 방법이 아니고 움직이는 방법이라 볼 수 있는데
이제부터는 미로맵을 그래프로 만들고 BFS로 탐색 후 길찾는 법을 알아보자.

---

void BFS()
{
	int[] deltaY = new int[] {-1, 0, 1, 0};
    int[] deltaX = new int[] {0, -1, 0, 1};
    
    bool[,] found = new bool[_board.Size,_board.Size];
    Pos[,] parent = new Pos[_board.Size,_board.Size];
    
    Queue<Pos> q = new Queue<Pos>();
    q.Enqueue(new Pos(PosY,PosX));
    found[PosY,PosX] = true;
    parent[PosY,PosX] = new Pos(PosY,PosX);
    while(q.Count > 0)
    {
    	Pos pos = q.Dequeue();
        int nowY = pos.Y;
        int nowX = pos.X;
        
        for(int i=0; i< 4; i++)
        {
        	int nextY = nowY + deltaY[i];
            int nextX = nowX + deltaX[i];
            
            if(nextY < 0 || nextY >= _board.Size || nextX < 0 || nextX >= _board.Size)
            	continue;
            if(_board.Tile[nextY,nextX] == Board.TileType.Wall)
            	continue;
            if(found[nextY,nextX])
            	continue;
                
            q.Enqueue(new Pos(nextY,nextX));
            found[nextY,nextX] = true;
            parent[nextY,nextX] = new Pos(nowY,nowX);
            
        }
    }
    
    int y = _board.DestY;
    int x = _board.DestX;
    while(parent[y,x].Y != y || parent[y,x].X != x) //시작점까지 루프
    {
    	_points.Add(new Pos(y,x));
        Pos pos = parent[y,x];
        y = pos.Y;
        x = pos.X;
    }
    _points.Add(new Pos(y,x)); //시작점 추가
    _points.Reverse();
}

---

부분별로 주석 설명

1. 필요한 변수 선언

	//deltaY,deltaX는 미로를 그래프로 바꾸려할 때 다음 움직임을 더해서 움직임 (순서는 {위,왼쪽,아래,오른쪽)
	int[] deltaY = new int[] {-1, 0, 1, 0};
    int[] deltaX = new int[] {0, -1, 0, 1};
    //found는 이미 방문한 곳을 체크하기위해 선언
	//parent는 미로맵을 모두 탐색 후 목적지좌표에서 parent를 거슬러 올라가보면 시작점으로 추적하기 위해 선언
    bool[,] found = new bool[_board.Size,_board.Size];
    Pos[,] parent = new Pos[_board.Size,_board.Size];
    //Queue q는 BFS가 선입선출로 관리하기 편하여 선언
    Queue<Pos> q = new Queue<Pos>();
    //시작점 추가 후 방문노드 true, parent는 시작점은 자기자신
    q.Enqueue(new Pos(PosY,PosX));
    found[PosY,PosX] = true;
    parent[PosY,PosX] = new Pos(PosY,PosX);

2. BFS로 미로맵을 탐색

while(q.Count > 0)
    {
    	//큐에서 꺼내서 현재 y,x좌표를 저장
    	Pos pos = q.Dequeue();
        int nowY = pos.Y;
        int nowX = pos.X;
        //상하좌우로 갈수있는지 체크
        for(int i=0; i< 4; i++)
        {
        	int nextY = nowY + deltaY[i];
            int nextX = nowX + deltaX[i];
            //사이즈를 벗어나거나 벽 그리고 이미 방문한곳이면 스킵
            if(nextY < 0 || nextY >= _board.Size || nextX < 0 || nextX >= _board.Size)
            	continue;
            if(_board.Tile[nextY,nextX] == Board.TileType.Wall)
            	continue;
            if(found[nextY,nextX])
            	continue;
            //갈수 있는곳이면 저장 큐에 저장
            q.Enqueue(new Pos(nextY,nextX));
            found[nextY,nextX] = true;
            parent[nextY,nextX] = new Pos(nowY,nowX);
            
        }
    }

3. 모든 미로맵을 저장했으니 목적지좌표로부터 Parent를 추적하여 시작점까지 업데이트

	//목적지 좌표 받아와서
	int y = _board.DestY;
    int x = _board.DestX;
    
    while(parent[y,x].Y != y || parent[y,x].X != x) //시작점까지 루프
    {
    	//좌표 추가 후
    	_points.Add(new Pos(y,x));
        //pos에 부모좌표 저장
        Pos pos = parent[y,x];
        //부모좌표를 y,x로 업데이트
        y = pos.Y;
        x = pos.X;
    }
    _points.Add(new Pos(y,x)); //시작점에서 while문이 끝나니 시작점 따로 추가
     //좌표들이 목적지좌표로부터 시작점순으로 저장되어있으니 역순으로 저장
    _points.Reverse();