[C#] 미로 만들기와 길 찾기 알고리즘 Part 3 : BFS 길 찾기

인트로

C# 콘솔 프로그래밍으로 미로를 만들고 BFS, A* 알고리즘으로 미로의 출구를 찾는 프로그램을 작성하려 한다.

 

Part3에선 BFS, A* 길 찾기 알고리즘으로 미로의 출구를 찾으려 한다.

 

본 포스팅에선 BFS를 사용해 출구를 찾는다.

 

BFS를 알고 싶다면?

[Algorithm] BFS (Breadth First Search, 너비 우선 탐색) 알고리즘

[Algorithm] BFS (Breadth First Search, 너비 우선 탐색) 알고리즘

(+ Visual Studio 기준으로 포스팅을 이어나갈 예정입니다.)

(++ 코드가 많습니다. 더보기를 클릭해서 코드를 확인하세요.)

 

[C#] 미로 만들기와 길찾기 알고리즘 Part 1 : 미로 만들기(1)

[C#] 미로 만들기와 길찾기 알고리즘 Part 1 : 미로 만들기(2)

[C#] 미로 만들기와 길찾기 알고리즘 Part 1 : SideWinder 미로(3)

[C#] 미로 만들기와 길찾기 알고리즘 Part 2 : Player 만들기

 

출구 만들기

보드에 출구(목적지)를 표시해야 한다. Board 클래스에 DestY DestX 프로퍼티를 정의해서 렌더링 할 때 목적지를 노란색으로 표시하도록 코드를 수정한다.

class Board
{
    ...
    
    public int DestY { get; private set; }
    public int DestX { get; private set; }
    
    ...
    
    public void InitializeBoard(int size, Player player)
    {
        ...
        
        DestY = Size - 2;
        DestX = Size - 2;
        
        ...
    }
    
    public void Render()
    {
        ...

        for (int y = 0; y < Size; y++)
        {
            for (int x = 0; x < Size; x++)
            {
                ...
                
                else if (y == DestY && x == DestX)
                    Console.ForegroundColor = ConsoleColor.Yellow;
                    
                ...
            } 
        }
    }
}

 

이제는 Board에 목적지 정보가 있으니 Player 쪽에서 목적지 정보를 받아올 필요가 없어졌다.

public void InitializePlayer(int posY, int posX, Board board)
{
    PosY = posY;
    PosX = posX;

    _board = board;
}

목적지를 완성했다!

 

BFS 길찾기 알고리즘

인접 행렬 또는 인접 리스트 없이 타일 정보만 이용해서 가상의 그래프를 그려낼 수 있고 BFS 길 찾기 알고리즘을 적용할 수 있다. 하나의 타일을 노드라고 생각하고 상하좌우 바닥(노드)이 Empty라면 연결된 노드, Wall이라면 연결되지 않은 노드라고 판단할 수 있다.

 

BFS 코드를 작성하기 전에 미로 상의 X, Y좌표를 담을 Pos클래스를 정의했다.

class Pos
{
    public int Y;
    public int X;

    public Pos(int y, int x) { Y = y; X = x; }
}

※ BFS 코드 ※

여느 BFS 코드와 유사하다. 주목할 포인트는 parent와 path를 정의해서 찾아왔던 길을 기록하는 코드이다.

List<Pos> path = new List<Pos>();

...

public void InitializePlayer(int posY, int posX, int destY, int destX, Board board)
{
    ...

    BFS();
}

...

private void BFS()
{
    int[] dirY = new int[] { -1, 0, 1, 0 };
    int[] dirX = 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 + dirY[i];
            int nextX = nowX + dirX[i];

            if (nextX <= 0 || nextX >= _board.Size || nextY <= 0 ||  nextY >= _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);
        }
    }
    
    CalcPathFromParent(parent);
}

private void CalcPathFromParent(Pos[,] parent)
{
    int y = _board.DestY;
    int x = _board.DestX;

    while (parent[y, x].Y != y || parent[y, x].X != x)
    {
        path.Add(new Pos(y, x));

        Pos pos = parent[y, x];
        y = pos.Y;
        x = pos.X;
    }
    path.Add(new Pos(y, x));
    path.Reverse();
}

 

BFS를 통해 path 정보를 채웠으니 Player가 자신의 위치를 갱신할 수 있도록 코드를 수정한다.

const int MOVE_TICK = 100;
private int _sumTick = 0;
int _index = 0;

public void Update(int deltaTick)
{
    if (_index >= path.Count)
        return;

    _sumTick += deltaTick;

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

        PosY = path[_index].Y;
        PosX = path[_index].X;

        _index++;
    }
}

똑똑한 Player로 진화했다.