A* 알고리즘
A*는 다익스트라와 비슷하며 시작점과 끝점을 알고 있고 끝점으로 가기위해 가는길의 비용과 더불어 추가로 가까워질수록 추가적인 수치를 계산하면서 간다고 생각하면 된다.
이전에 했던 미로맵에서 A* 길찾기 알고리즘을 적용해보자.
구현에 필요한 것을 알아보자.
가산점 F = G + H
F = 최종 점수 (작을수록 좋다, 경로에 따라 달라진다.)
G = 시작점에서 해당 좌표까지 이동하는데 드는 비용 ( 작을 수록 좋음, 경로에 따라 달라짐)
H(Heuristic) = 목적지에서 얼마나 가까운지 (작을 수록 좋음, 경로에 따라 달라지지않음)
(y,x)를 바로 이동하지는 않고 방문여부를 체크하는 closed 배열
bool [,] closed = new bool[_board.Size,_board.Size]; //배열로 하면 메모리를 잡아먹는 대신 연산속도가 빠르고 List로 관리하면 메모리는 덜 잡아먹지만 연산속도가 떨어진다.(y,x) 가는 길을 한번이라도 발견했는지
//발견 X => MaxValue
//발견 O => F = G + H
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;
}
}시작점 발견 후 예약 진행
//1.open[현재Y좌표,현재X좌표] = (F 점수계산( G는 현재 모두 0인 상태) (H만 계산) )
open[PosY,PosX] = Math.Abs(_board.DestY - PosY) + Math.Abs(_board.DestX - PosX);제일 좋은 후보를 찾는다.
while문을 돌면서 제일 좋은 후보를 찾는데 이전 시간에 배운 제일 좋거나 안좋은 케이스를 찾을 때 우선순위 큐가 좋다는 것을 배웠으니 이용해보자.
//우선순위큐안에 뭐를 넣어야하는지..... -> 새로운 구조체 생성
struct PQNode : IComparable<PQNode>
{
public int F;
public int G;
public int Y;
public int X;
public int CompareTo(PQNode other)
{
if( F == other.F)
return 0;
return F <other.F ? 1 : -1;
}
}
//상하좌우를 체크하기위한 deltaY,X
int[] deltaY = new int[] {-1, 0 , 1 , 0};
int[] deltaX = new int[] {0, -1, 0, 1};
//이동하는 비용 G를 위한 배열
//상하좌우로 이동할때 1씩 비용이 든다 가정
int[] cost = new int[] { 1 , 1 , 1 ,1 };
//어디서 왔는지 추적하기 위해 부모
Pos[,] parent = new Pos[_board.Size,_board.Size];
//오픈리스트에 있는 정보들 중에서, 가장 좋은 후보를 빠르게 뽑아오기 위한 도구
PriorityQueue<PQNode> = new PriorityQueue<PQNode>();
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)
{
//1.제일 좋은 후보 가져온다.
PQNode node = pq.Pop();
//2.동일한 좌표를 여러 경로로 찾아서, 더 빠른 경로로 인해서 이미 방문(closed)된 경우 스킵
if(closed[node.Y,node.X])
continue;
//3.방문한다.
closed[node.Y,node.X] = true; // 한번 방문한것은 다시는 돌아오지않는다.
//목적지 도착했으면 바로 종료
if(node.Y == _board.DestY && node.X == _board.DestX)
break;
//현재 내 좌표에서 상하좌우 갈 수있는곳을 체크해서 이동가능한 곳을 다 예약(openList)
for(int i = 0; i< deltaY.Length; i++)
{
int nextY = node.Y + deltaY[i];
int nextX = node.X + deltaX[i];
//유효범위를 벗어나면 스킵
if(nextX < 0 || nextX >= _board.Size || nextY < 0 || nextY >=_board.Size)
continue;
//벽으로 막혔으면 스킵
if(_board.Tile[nextY.nextX] == BoardTileType.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();
}여기까지 구현해보면 정상적으로 길찾기가 완료될 것이다.
이전에 했던 BFS 와의 차이점은 아직까지는 잘 모르겠다.
A*을 사용했을때만의 장점을 한번 알아보자.
만약 미로판에서 대각선으로 이동이 가능하다고 했을 때,
- g 계산식을 추가
1.1 상하좌우는 1에서 10을 곱해서 10의 비용
1.2 대각선은 1.414로 소수점을 버리기위해 10을 곱해서 14의 비용
- h 계산식 * 10
// UP LEFT DOWN RIGHT UP-LEFT DOWN-LEFT DOWN-RIGHT UP-RIGHT
int[] deltaY = new int[] { -1 , 0 , 1 , 0 , -1 , 1 , 1 , -1};
int[] deltaX = new int[] { 0 , -1 , 0 , 1 , -1 , -1 , 1 , 1};
int[] cost = new int[] { 10, 10, 10, 10, 14, 14, 14, 14};나머지 위에 코드에서 비용계산하는 곳에 10씩 곱해주면 대각선으로도 이동가능한 A*에서만 가능한 길찾기가 가능하다.
* 이 글은 수정 될 수 있습니다.
Ghost