A* 길찾기 알고리즘
A* 길찾기 알고리즘과 다익스트라 알고리즘 비교
[다익스트라]
1. 해당 지점에서 갈 수 있는 모든 경로에 대한 최단 거리를 찾는다. (비효율적) 따라서 시작 지점만 알면 된다. 목적지를 주진 않는다. 다익스트라를 목적지 찾으면 종료하게끔 개선할 수도 있지만 그래도 아쉽다. 매번 모든 지점마다 갈 수 있는 모든 경로에 대한 최단 거리를 찾아 비교하기 때문이다.
2. 예약된 정점들 중 최고의 정점을 선택할 땐 최단 거리 경로를 유지할 수 있는 정점을 선택한다.
[A*]
1. 모든 경로를 다 찾지 않는다. (시작 지점, 끝 지점 목적지. 이렇게 두 개가 주어진다. 목적지를 알고 있다.)
2. 예약된 정점들 중 최고의 정점을 선택할 땐
1️⃣ 최단 거리 경로를 유지할 수 있는 정점도 고려하고 👉 G
- 어떤 경로를 따라왔냐에 따라 해당 정점의 비용은 그때 그때 다르므로 가변적이다.
2️⃣ 이에 더하여 목적지에 얼마나 가까운 정점인지 또한 고려한다. 👉 H (휴리스틱)
- 목적지에 얼마나 가까운 정점인지를 고려하는건 피타고라스로 실제 남은 거리를 쓸 수도 있고 그냥 목적지까지 벽을 무시하고 그냥 가로 세로 총 몇 개의 타일이 남았는지 세는 등등 다양하게 정의할 수 있다.
- 이런 정의 방법을 휴리스틱 함수라고 하며 어떤 휴리스틱 함수를 사용하느냐에 따라 A* 알고리즘의 효율성이 좌지우지 된다.
- 어떤 경로를 따라왔냐와는 상관 없이 해당 정점이 목적지와 얼마나 가까운 정점인지는 고정적인 값이다.
- 최종 점수 👉 F = G + H
다익스트라 버전에서 2️⃣ 를 고려한 알고리즘이라고 할 수 있겠다. 다익스트라는 👉 f = g 기준으로 다음 방문 정점 선택한다면, A*는 👉 f = g + h 기준으로 다음 방문 정점 선택한다. 해당 예제에서는 H를 [목적지까지 남은 X 방향의 타일 + Y 방향의 타일]로 할 것이다.
[A* 길찾기 알고리즘 구현 : 📜Player.cs]
BFS, 다익스트라와 유사한 구조로 흘러간다. 휴리스틱(H)를 고려한다는 것을 제외하고는 비슷하다! 😎
상하좌우 이동만 가능할 때
using System;
using System.Collections.Generic;
using System.Text;
namespace Algorithm
{
class Pos
{
public Pos(int y, int x) { Y = y; X = x; }
public int Y;
public int X;
}
class Player
{
public int PosY { get; private set; }
public int PosX { get; private set; }
Random _random = new Random();
Board _board;
enum Dir // 반시계방향
{
Up = 0,
Left = 1,
Down = 2,
Right = 3
}
int _dir = (int)Dir.Up;
List<Pos> _points = new List<Pos>();
public void Initialize(int posY, int posX, Board board)
{
PosX = posX;
PosY = posY;
_board = board;
AStar(); // ⭐A * 알고리즘⭐
}
struct PQNode : IComparable<PQNode>
{
public int F;
public int G;
// F랑 G만 알아도 H 는 구할 수 있으니 생략
public int Y;
public int X;
public int CompareTo(PQNode other)
{
if (F == other.F) // F 값을 기준으로 크기를 비교
return 0;
return F < other.F ? 1 : -1;
}
}
void AStar()
{
int[] deltaY = new int[] { -1, 0, 1, 0 };
int[] deltaX = new int[] { 0, -1, 0, 1 };
int[] cost = new int[] { 1, 1, 1, 1 };
// 점수 매기기
// F = G _ H
// F = 최종 점수 (작을 수록 좋음. 경로에 따라 달라짐)
// G = 시작점에서 해당 좌표까지 이동하는데 드는 비용 (작을 수록 좋음. 경로에 따라 달라짐)
// H = 목적지로부터 얼마나 가까운 곳인지를 따지는 보너스 점수 (작을 수록 좋음. 고정인 값)
// (y, x) 이미 방문 했는지 여부 (방문 = closed 상태)
bool[,] closed = new bool[_board.Size, _board.Size];
// 출발지에서 (y, x) 가는데에 현재까지 업뎃된 최단거리
// (y, x) 가는 길을 한번이라도 발견 했었는지 여부가 될 수도 있다. (한번이라도 예약 되있는지 여부)
// 발견(예약)이 안됐다면 Int32.MaxValue 로 저장이 되어 있을 것.
// F = G + H 값이 저장된다. (이 F 값이 가장 작은 정점이 방문 정점으로 선택될 것)
int [,] open = new int[_board.Size, _board.Size];
for (int y = 0; y < _board.Size; y++)
for (int x = 0; x < _board.Size; x++)
open[y, x] = Int32.MaxValue;
Pos [,] parent = new Pos[_board.Size, _board.Size];
// 우선순위 큐 : 예약된 것들 중 가장 좋은 후보를 빠르게 뽑아오기 위한 도구.
PriorityQueue<PQNode> pq = new PriorityQueue<PQNode>();
// 시작점 발견 (시작점 예약 진행)
open[PosY, PosX] = Math.Abs(_board.DestY - PosY) + Math.Abs(_board.DestX - PosX); // 시작점이니까 G는 0이고, H 값임.
pq.Push(new PQNode() { F = Math.Abs(_board.DestY - PosY) + Math.Abs(_board.DestX - PosX), G = 0, Y = PosY, X = PosX });
parent[PosY, PosX] = new Pos(PosY, PosX);
while(pq.Count > 0)
{
// 제일 좋은 후보를 찾는다.
PQNode node = pq.Pop();
// 동일한 좌표를 여러 경로로 찾아서, 더 빠른 경로로 인해서 이미 방문(closed) 된 경우 스킵
if (closed[node.Y, node.X])
continue;
// 방문 한다.
closed[node.Y, node.X] = true;
// 목적지에 도착했으면 바로 종료
if (node.Y == _board.DestY && node.X == _board.DestX)
break;
// 상하좌우 등 이동할 수 있는 좌표인지 확인해서 예약(open)한다.
for (int i = 0; i < deltaY.Length; i++)
{
int nextY = node.Y + deltaY[i];
int nextX = node.X + deltaX[i];
// 유효 범위를 벗어났으면 스킵
if (nextY < 0 || nextY >= _board.Size || nextX < 0 || nextX >= _board.Size)
continue;
// 벽으로 막혀서 갈 수 없으면 스킵
if (_board.Tile[nextY, nextX] == Board.TileType.Wall)
continue;
// 이미 방문한 곳이면 스킵
if (closed[nextY, nextX])
continue;
// 비용 계산
int g = node.G + cost[i];
int h = Math.Abs(_board.DestY - nextY) + Math.Abs(_board.DestX - nextX);
// 다른 경로에서 더 빠른 길을 이미 찾았으면 스킵 (업뎃 할 필요가 없으니까)
if (open[nextY, nextX] < g + h)
continue;
// 예약 진행
open[nextY, nextX] = g + h;
pq.Push(new PQNode() { F = g + h, G = g, Y = nextY, X = nextX });
parent[nextY, nextX] = new Pos(node.Y, node.X);
}
}
CalcPathFromParent(parent);
}
void CalcPathFromParent(Pos[,] 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 = parent[y, x];
y = pos.Y;
x = pos.X;
}
_points.Add(new Pos(y, x));
_points.Reverse();
}
const int MOVE_TICK = 10; // 10밀리세컨즈 = 0.01 초 마다 움직이게
int _sumTick = 0;
int _lastIndex = 0;
public void Update(int deltaTick)
{
if (_lastIndex >= _points.Count)
return;
_sumTick += deltaTick;
if (_sumTick >= MOVE_TICK) // 이부분은 0.1초마다 실행
{
_sumTick = 0;
PosY = _points[_lastIndex].Y;
PosX = _points[_lastIndex].X;
_lastIndex++;
}
}
}
}
우선순위 큐에 넣을 데이터
예약한 데이터를 우선순위큐에 넣으며, POP 하면 가장 작은 값이 나오게 할 것이다.
struct PQNode : IComparable<PQNode>
{
public int F;
public int G;
// F랑 G만 알아도 H 는 구할 수 있으니 생략
public int Y;
public int X;
public int CompareTo(PQNode other)
{
if (F == other.F) // F 값을 기준으로 크기를 비교
return 0;
return F < other.F ? 1 : -1;
}
}
PQNode라는 타입의 데이터로 F, G, Y, X 정보를 묶어서, 예약하기로 결정한 좌표를 우선순위 큐에 넣을 것이다.
- F 👉 해당 좌표의 최종 점수 F = G + H
- G 👉 시작점에서 해당 좌표까지 이동하는데 드는 비용
- H 는 F - G 로 알 수 있으므로 넣지 않음
- Y 👉 예약한 Y 좌표
- X 👉 예약한 X 좌표
비교 함수
int, float 같은 기본 데이터 타입이 아니기 때문에 PQNode 타입의 비교 기준을 만들어 주어야 한다. 또한 F 값이 작을 수록 루트에 위치하게 한다. 즉, 오름 차순. 예약 목록, 즉 우선순위 큐에서 F 값이 가장 작은 것을 POP 하게 할 것이다. (최종점수 F 값이 작을 수록 최단 경로를 만들기에 적합한 좌표)
F < other.F ? 1 : -1 👉 나의 F가 다른 PQNode 객체의 F보다 작으면 1 리턴. 크면 -1 리턴.
✨우선 순위 큐에 PQNode 객체를 넣으면 이 비교 기준을 통해 힙 트리를 만들게 된다.✨
필요한 변수 목록
int[] deltaY = new int[] { -1, 0, 1, 0 };
int[] deltaX = new int[] { 0, -1, 0, 1 };
int[] cost = new int[] { 1, 1, 1, 1 };
bool[,] closed = new bool[_board.Size, _board.Size];
int [,] open = new int[_board.Size, _board.Size];
for (int y = 0; y < _board.Size; y++)
for (int x = 0; x < _board.Size; x++)
open[y, x] = Int32.MaxValue;
Pos [,] parent = new Pos[_board.Size, _board.Size];
PriorityQueue<PQNode> pq = new PriorityQueue<PQNode>();
현재 좌표의 앞 뒤 좌 우 좌표를 알기 위해선 이만큼 더해주기
- deltaY[0], deltaX[0] 👉 Up
- deltaY[1], deltaX[1] 👉 Down
- deltaY[2], deltaX[2] 👉 Left
- deltaY[3], deltaX[3] 👉 Down
현재 좌표 기준 앞 뒤 좌 우로 각각 가기 위한 비용
cost 전부 1 이지만 나중에 대각선도 갈 수 있게 된다면 대각선 비용은 상하좌우 비용과 다르게 적용될 것이다.
closed 👉 방문한 좌표 표시
사실 없어도 무방하다. 그 이유는 아래 후술.
open 👉 단 한번이라도 예약된 적이 있는지
Int32.MaxValue 로 초기화 해둔다.
한번이라도 예약된적이 있다면 Int32.MaxValue 값이 아닐 것이다.
parent 👉 방문한 좌표의 부모 좌표 표시 (이전 방문 좌표)
미로 길 찾기를 위하여 저장
우선순위 큐 pg
현재의 예약 좌표들을 이 우선순위 큐에 PQNode 타입으로 저장한다.
이 우선순위큐를 POP 하면 현재의 예약 좌표들 중 가장 F 값이 작은 좌표가 빠져나오게 되고 이를 방문할 것이다.
방문 체크를 하지 않아도 된다! 🤠
방문 체크 안해줘도 답이 도출되는데 지장이 없다.
더 좋은, 더 최소의 가중치합(최단경로)를 가지는 경로를 발견했다면 최단경로를 새롭게 업데이트 해야 한다. 근데 이미 우선순위큐 안에 들어가있는 정점을 수정할 수는 없다. 큐는 배열처럼 이미 안에 들어있는 원소에 접근할 수 없기 때문이다. 따라서 어차피 가중치합만 다른 동일한 정점이 큐 안에 두개 있더라도 우선순위 큐 특성상 최소의 가중치합을 가진 정점이 먼저 빠져나오기에 동일한 정점 중 나중에 빠져나오는 정점은 업데이트 “당한”, 더 크고 안좋은 경로를 가진 정점일게 분명하다. 그러므로 어차피 이미 방문된 정점은 예약과정의 *if (open[nextY, nextX] < g + h) continue;* 코드에서 걸러지게 되어 있다. 다익스트라 알고리즘(어쨋든 A* 길찾기도 h를 고려하는 것만 다르지 베이스는 다익스트라이기 때문)
예시
0 👉 2(1) 1(10)
1 👉 0(10) 3(10)
2 👉 0(1) 3(1000)
3 👉 1(10) 2(1000)
closed를 두지 않고, 방문체크를 하지 않는다고 가정했을 때
1. 0 방문, 우선순위큐에 2 (1), 1 (10) 를 넣어 예약, 우선순위 큐 상태는 [ 2 (1), 1 (10) ]
2. 2 방문, 우선순위큐에 3 (1000) 을 넣어 예약. 0 (1) 은 if (open[0] < 1 + 1 ) continue; 을 통해 알아서 걸러지므로 예약되지 못함. open[0] 은 출발지라 이미 0 인 상태이기 때문. 우선순위 큐 상태는 [ 1 (10), 3 (1000) ]
3. 1 방문, 우선순위큐에 0 (10) 을 예약할 수 있는지 확인해보려는데 if (open[0] < 10 + 10 ) continue; 을 통해 알아서 걸러지므로 예약되지 못함.(즉, 0이 방문된 정점인지 아닌지 굳이 검사하지 않더라도 이 과정 하나만으로 알아서 걸러집니다.) 3 (10) 은 if (open[3] < 10 + 10 ) continue; 에 해당되지 않기때문에 예약 가능. open[3] 은 현재 1001 이기 때문. open[3]은 20 으로 업데이트 되고 우선순위 큐 상태는 [ 3 (1000), 3(20) ] 이 됨. (큐에 해가 다른 동일한 두 정점 3 이 들어가있는 상태)
4. 3 방문 (3(20)) , 우선순위큐에 2 (1000)을 예약할 수 있는지 확인해보려는데 if (open[2] < 20 + 1000 ) continue; 을 통해 알아서 걸러지므로 예약되지 못함. open[2]는 1이기 때문. 우선순위큐에 1 (10)을 예약할 수 있는지 확인해보려는데 if (open[1] < 20 + 10 ) continue; 을 통해 알아서 걸러지므로 예약되지 못함. open[1]는 10이기 때문. 3 과 연결되어있는 1 과 2 둘 다 예약되지 못함. 우선순위 큐 상태는 [ 3 (1000) ]
5. 3 방문 (3(1000)), 어차피 앞서 3(20) 방문을 통해 2 와 1 은 3(1000) 에서 가는 것 보다는 더 짧은 경로로 업데이트가 되어 있는 상태이므로 어차피 3(1000)을 통한 2 와 1은 if (open[2] < 1000 + 1000 ) continue; if (open[2] < 1000 + 10 ) continue; 에 걸려 예약되지 못함. 우선순위큐는 비게 되어 종료.
이처럼 방문체크를 굳이 해주지 않아도 if (open[nextY, nextX] < g) continue; 로 재방문된 정점은 어차피 더 크고 안좋은 해를 가진 것이기 떄문에 어차피 여기서 걸러지게 되어 있는 것을 확인할 수 있다.
그럼에도 불구하고 방문 체크를 따로 해주는 이유는 무엇일까?
1️⃣ 가독성, 논리성, 역할분담
open은 좌표마다 현재까지의 최단 경로를 저장해두는 역할이다. if (open[nextY, nextX] < g + h) 로 이미 방문한 정점을 거를 수도 있지만! 그래도 역할을 분담하는게 코드를 이해하는 면에서도 좋을 것이다.
2️⃣ 비용 계산이 복잡하다면 이 복잡한 비용 계산을 피할 수 있게 된다.
방문 체크를 하고 미리 예약 전에 if (closed[nextY, nextX]) 재방문 정점을 걸러준다면, g + h 계산을 피할 수 있다. 경로 계산은 단순히 길이 계산 뿐만아니라 다른 여러 비용까지 합쳐진다면 더 복잡해질 수도 있다. 이 계산 자체를 피할 수가 있으므로 성능상 더 나을 수도 있다.
시작 좌표는 미리 예약한다 😄
open[PosY, PosX] = Math.Abs(_board.DestY - PosY) + Math.Abs(_board.DestX - PosX); // 시작점이니까 G는 0이고, H 값임.
pq.Push(new PQNode() { F = Math.Abs(_board.DestY - PosY) + Math.Abs(_board.DestX - PosX), G = 0, Y = PosY, X = PosX });
parent[PosY, PosX] = new Pos(PosY, PosX);
시작 좌표. 현재 PosY, PosX 값은 각각 1, 1이며, pq 우선순위 큐에 넣어 예약한다.
open[1, 1]
- G 는 0 👉 시작 좌표에서 시작 좌표까지의 거리는 0
- H 는 👉 목적지까지 남은 Y 방향의 타일 + X 방향의 타일 (Math.Abs(_board.DestY - PosY) + Math.Abs(_board.DestX - PosX))
[과정]
과정 1️⃣2️⃣3️⃣를 우선순위 큐가 빌 때까지 무한 반복한다. (더 이상 예약 된게 하나도 없을 때까지)
과정 1️⃣ : 예약된 것들 중에서 방문할(제일 좋은) 정점 고르기
// 제일 좋은 후보를 찾는다.
PQNode node = pq.Pop();
// 동일한 좌표를 여러 경로로 찾아서, 더 빠른 경로로 인해서 이미 방문(closed) 된 경우 스킵
if (closed[node.Y, node.X])
continue;
우선순위큐 POP 👉 예약된 좌표들 중에 가장 좋은 좌표(F 값이 가장 작은)를 꺼내고 이를 방문한다.
우선순위 큐를 쓰기 전엔, 예약된 것들 중에서 일일이 점수 값이 가장 작은 것을 비교해가며 찾았어야 했는데 편해졌다. 3️⃣ 에서 방문하기로 결정되고 1️⃣ 로 넘어온 경우라면 if (closed[node.Y, node.X]) 에 걸린다.
- 방문된 좌표라면 다시 1️⃣ 실행. 우선순위 큐에서 다른거 다시 꺼낸다.
- 위에서도 설명했지만 사실 이미 방문된 정점은 if (open[nextY, nextX] < g + h) 에서도 걸러질 수 있다. 그러나 1️⃣역할분담, 2️⃣비용계산 피하기 차원에서 closed를 따로 두어 방문 체크를 하고 예약 전에 미리 걸러주는 것이다.
과정 2️⃣ : 방문한다.
// 방문 한다.
closed[node.Y, node.X] = true;
// 목적지에 도착했으면 바로 종료
if (node.Y == _board.DestY && node.X == _board.DestX)
break;
방문한다. 해당 좌표로 closed 업데이트하고, 만약 목적지에 도착했다면 모든 과정을 종료한다.
과정 3️⃣ 새로운 방문 노드를 중심으로 한 다음 예약 목록 선정
// 상하좌우 등 이동할 수 있는 좌표인지 확인해서 예약(open)한다.
for (int i = 0; i < deltaY.Length; i++)
{
int nextY = node.Y + deltaY[i];
int nextX = node.X + deltaX[i];
// 유효 범위를 벗어났으면 스킵
if (nextY < 0 || nextY >= _board.Size || nextX < 0 || nextX >= _board.Size)
continue;
// 벽으로 막혀서 갈 수 없으면 스킵
if (_board.Tile[nextY, nextX] == Board.TileType.Wall)
continue;
// 이미 방문한 곳이면 스킵
if (closed[nextY, nextX])
continue;
// 비용 계산
int g = node.G + cost[i];
int h = Math.Abs(_board.DestY - nextY) + Math.Abs(_board.DestX - nextX);
// 다른 경로에서 더 빠른 길을 이미 찾았으면 스킵
if (open[nextY, nextX] < g + h)
continue;
// 예약 진행
open[nextY, nextX] = g + h;
pq.Push(new PQNode() { F = g + h, G = g, Y = nextY, X = nextX });
parent[nextY, nextX] = new Pos(node.Y, node.X);
}
우선순위 큐 PUSH 👉 해당 좌표 예약하기
예약하기 적합한 좌표 찾기
현재 방문 좌표의 상,하,좌, 우 좌표를 검사하고 이를 nextY, nextX 에 담아 검사한다.
예약 하면 안되는 좌표, 유효 범위를 벗어난 좌표, 벽이라거 갈 수 없는 좌표, 이미 방분했던 좌표들은는 스킵한다. 비용(g + h)이 해당 좌표에서 이미 다른 경로에서 더 적은 비용을 찾았었다면 방금 구한 이 비용으로 새롭게 예약할 필요 없으므로 스킵한다.
- g 👉 현재 방문중인 노드까지의 G 값에 현재 검사중인 이 nextY, nextX 까지 오기 위한 비용 더하기
- h 👉 현재 검사중인 이 nextY, nextX 기준 목적지까지 남은 Y 방향의 타일 + X 방향의 타일
위 과정에서 스킵되지 않았다면 최종적으로 예약할 좌표로 선정
- 해당 좌표의 open에 g + h 비용 저장
- 해당 좌표를 PQNode로 묶어 우선순위 큐에 PUSH
- 해당 좌표의 parent를 현재 방문 좌표인 node.Y, node.X로 업뎃
리스트에 방문한 정점들 차례로 추가 (최종 완성된 길)
CalcPathFromParent(parent); // 실행
void CalcPathFromParent(Pos[,] 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 = parent[y, x];
y = pos.Y;
x = pos.X;
}
_points.Add(new Pos(y, x));
_points.Reverse();
}
목적지부터 부모의 부모로 쭉쭉 타고 올라가면서 방문할 타일들을 전부 _points 리스트에 저장. 그리고 이 과정이 다 끝나면 리스트 거꾸로!
만약 대각선 이동도 허용한다면?
대각선 방향 추가!
- UpLeft, DownLeft, DownRight, UpRight
- deltaY[4], deltaX[4] 👉 UpLeft
- deltaY[5], deltaX[5] 👉 DownLeft
- deltaY[6], deltaX[6] 👉 DownRight
- deltaY[7], deltaX[7] 👉 UpRight
이동 비용 cost
대각선 이동 비용은 14(루트 2), 상하좌우 이동 비용은 10 으로 정해보았다.
이에 대한 형평성을 위해 H 값에 10 을 곱해주었다. 👉 목적지까지 남은 Y 방향의 타일 + X 방향의 타일, 즉 상하좌우 수평적인 방향이므로 하나 이동 당 10 쳐주기로
cf) 미로 찾기 무한 반복
const int MOVE_TICK = 100; // 100밀리세컨즈 = 0.1 초 마다 움직이게
int _sumTick = 0;
int _lastIndex = 0;
public void Update(int deltaTick)
{
if (_lastIndex >= _points.Count)
{
_lastIndex = 0;
_points.Clear();
_board.Initialize(25, this); // 플레이어보다 먼저 이니셜라이징이 이루어져야 함
Initialize(1, 1, _board);
}
_sumTick += deltaTick;
if (_sumTick >= MOVE_TICK) // 이부분은 0.1초마다 실행
{
_sumTick = 0;
PosY = _points[_lastIndex].Y;
PosX = _points[_lastIndex].X;
_lastIndex++;
}
}
}
if (_lastIndex >= _points.Count) 👉 리스트를 다 다돌면 전부 초기화 하고 미로 다시 새롭게 초기화 하고 플레이어도 새로 초기화한다. 😁
'공부 > 인프런 - Rookiss' 카테고리의 다른 글
| Part 3-1-1. 싱글톤 (0) | 2023.08.11 |
|---|---|
| Part 3. 유니티 엔진 (0) | 2023.08.10 |
| Part 2-5-2. 트리 : 힙 트리, 우선순위 큐 (0) | 2023.08.10 |
| Part 2-5-1. 트리 : 트리 이론과 구현 (0) | 2023.08.10 |
| Part 2-4-5. 그래프 : 다익스트라 최단 경로 알고리즘 (0) | 2023.08.09 |