- 돈까스 스터디 23.01.21 스터디 A*알고리즘 정리 과제
A* 알고리즘
-
주어진 출발 꼭짓점에서부터 목표 꼭짓점까지 가는 최단 경로를 찾아내는 그래프 탐색 알고리즘 중 하나
-
다익스트라 알고리즘과 유사하나 각 꼭짓점
x에 대해 그 꼭짓점을 통과하는 최상의 경로를 추정하는 순위값인휴리스틱 추정값 h(x)을 매기는 방법을 이용한다. -
휴리스틱 추정값의 순서로 꼭짓점을 방문한다.
-
그러므로 A* 알고리즘을 너비 우선 탐색(BFS; Breadth First Search)의 한 예로 분류할 수 있다.
평가함수
-
꼭짓점
x에 대한 평가 함수f(x) -
f(x) = g(x) + h(x)-
g(x): 출발 꼭짓점으로부터 꼭짓점x까지의 경로 가중치 -
h(n): 꼭짓점x으로부터 목표 꼭짓점까지의 추정 경로 가중치
-
-
f(x)가 작은 값부터 탐색하는 특성상 힙(우선순위 큐)이 사용된다. -
휴리스틱 함수
h(x)에 따라 성능이 극명하게 갈리며,
f(x) = g(x)일 때는 다익스트라 알고리즘과 동일하다. -
휴리스틱 함수가 admissible하면 최단경로가 보장된다. admissible하지 않은 휴리스틱 함수를 사용하면 탐색 노드가 증폭될 수 있다.
-
휴리스틱 함수가 admissible하다는 말은 휴리스틱 함수가 목적지까지 남은 거리를 과대평가 하지 않는다는 뜻이다.
동작
-
f(x)를 최소힙(오름차순 우선순위 큐)에 노드로 삽입한다. -
힙에서 최우선 노드를 pop한다.
-
해당 노드에서 이동할 수 있는 노드를 찾는다.
-
그 노드들의
f(x)를 구한다. -
그 노드들을 힙에 삽입한다.
-
목표 노드에 도달할 때까지 반복한다.
의사코드
PQ.push(start_node, g(start_node) + h(start_node)) //우선순위 큐에 시작 노드를 삽입한다.
while PQ is not empty //우선순위 큐가 비어있지 않은 동안
node = PQ.pop //우선순위 큐를 pop한다.
if node == goal_node //만일 해당 노드가 목표 노드이면 반복문을 빠져나온다.
break
for next_node in (next_node_begin...next_node_end) //해당 노드에서 이동할 수 있는 다음 노드들을 보는 동안
PQ.push(next_node, g(node) + cost + h(next_node)) //우선순위 큐에 다음 노드를 삽입한다.
print goal_node_dist //시작 노드에서 목표 노드까지의 거리를 출력한다.실습
-
본인의 코드
Pathfinding.cs -
수업 예시 코드
// TileManager Script
private List<Tile> FindPath(Vector2Int start, Vector2Int end)
{
List<Tile> result = new List<Tile>();
Tile startTile = tiles.Find(_ => _.Index == start);
Tile endTile = tiles.Find(_ => _.Index == end);
List<Tile> openList = new List<Tile>();
startTile.Set(0, GetH(startTile.Index, endTile.Index));
do
{
startTile.IsClose = true;
endTile.IsOpen = false;
openList.Remove(startTile);
startTile.ReFresh();
if (startTile.Index == end) break;
//주변탐색 시작
//대각선 이동 시 상화좌우에 장애물 있을 경우
bool isLT = true;
bool isRT = true;
bool isLB = true;
bool isRB = true;
// 위
if (SetTile(openList, startTile, tiles.Find(_ => _.Index == new Vector2Int(startTile.Index.x, startTile.Index.y + 1)), end) == false)
{
isLT = false;
isRT = false;
}
// 아래
if (SetTile(openList, startTile, tiles.Find(_ => _.Index == new Vector2Int(startTile.Index.x, startTile.Index.y - 1)), end) == false)
{
isLT = false;
isRT = false;
}
// 왼쪽
if (SetTile(openList, startTile, tiles.Find(_ => _.Index == new Vector2Int(startTile.Index.x - 1, startTile.Index.y)), end) == false)
{
isLT = false;
isLB = false;
}
// 오른쪽
if (SetTile(openList, startTile, tiles.Find(_ => _.Index == new Vector2Int(startTile.Index.x + 1, startTile.Index.y)), end) == false)
{
isRT = false;
isRB = false;
}
if (isLT)
{
SetTile(openList, startTile, tiles.Find(_ => _.Index == new Vector2Int(startTile.Index.x - 1, startTile.Index.y + 1)), end);
}
if (isRT)
{
SetTile(openList, startTile, tiles.Find(_ => _.Index == new Vector2Int(startTile.Index.x + 1, startTile.Index.y + 1)), end);
}
if (isLB)
{
SetTile(openList, startTile, tiles.Find(_ => _.Index == new Vector2Int(startTile.Index.x - 1, startTile.Index.y + 1)), end);
}
if (isRB)
{
SetTile(openList, startTile, tiles.Find(_ => _.Index == new Vector2Int(startTile.Index.x + 1, startTile.Index.y - 1)), end);
}
//// 원래는 우선순위 큐로 F값이 가장 낮은 것을 뽑아야함
//var OpenTiles = tiles.Where(_ => _.IsOpen);
//if(OpenTiles.Count() > 0)
//{
// int f = OpenTiles.Min(_ => _.F);
//}
//startTile = tiles.Find(_ => _.IsOpen);
// 우선순위 큐로 구현하면 사라지는 코드
int minF = int.MaxValue;
foreach (var tile in openList)
{
if (tile.F < minF)
{
minF = tile.F;
startTile = tile;
}
}
}
while (openList.Count > 0);
// 결과 만들어주기
return result;
}
private int GetH(in Vector2Int index,in Vector2Int end)
{
return Mathf.Abs(index.x - end.x) + Mathf.Abs(index.y - end.y);
}
private int GetG(in Vector2Int parent, in Vector2Int child)
{
int result = Mathf.Abs(parent.x - child.x) + Mathf.Abs(parent.y - child.y);
if (result > 1)
{
return 14;
}
else
return 10;
}
private bool SetTile(in List<Tile> openList, Tile parent, Tile child, Vector2Int end)
{
if (child == null) return false;
if (child.IsObstacle) return false;
if (child.IsClose) return false;
if(child.IsOpen == false)
{
openList.Add(child);
}
child.Set(GetG(parent.Index, child.Index), GetH(child.Index, end));
return true;
}
