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

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

인트로

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

Part3에선 여러 길 찾기 알고리즘으로 미로의 출구를 찾으려 한다.

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

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

출구 만들기

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

↓↓↓ BFS를 알고 싶다면? ↓↓↓

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

인접 행렬 또는 인접 리스트 없이 타일 정보만 이용해서 가상의 그래프를 그려낼 수 있고 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 path = new List(); ... 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 q = new Queue(); 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); } } 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로 진화했다.

from http://kangworld.tistory.com/57 by ccl(A) rewrite - 2021-08-31 00:26:16