BFS 길찾기

출구 만들기

보드에 출구(목적지)를 표시해야 한다. 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>();
 
...
 

   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로 진화했다.

 

 

ref : https://kangworld.tistory.com/57