길찾기 알고리즘 A* Algorithm 에이스타 알고리즘

길찾기에서 사용되는 알고리즘 중 가장 흔하게 사용하는 것이 에이스타 알고리즘입니다.

 

용어 설명

- openList = 갈 수 있는 길
- closeList = 이미 지나간 길
- current = 현재 위치
- NeighborNode = 탐색한 길
- 이동비용 = 도착지점까지의 거리
- 가중치 = 일반적으로 직선 : 10, 대각선 : 14

1. CreateNode : 맵을 만든다.

2. SetTargetLocation : 시작지점과 도착지점을 구한다.

3. PathFinding : 길 찾기 알고리즘을 한다.

- 시작지점을 openList에 담는다.

- openList 중에 이동 비용이 낮은 길을 찾아 current에 담는다.

- current를 openList에서 지우고 closeList에 담는다.

- current를 기준으로 4개 방향에 대해 탐색한다.

  (일반적으로는 8개 방향인데 현재 코드는 사선으로 움직이지 못하는 코드라서 4개의 방향만 탐색한다.)

  (4개의 방향 중 막다른길, openList, closeList에 포함하는 경우 탐색하지 않는다.)

- 이동 비용을 계산한다.

  (이동 비용 : current의 G + 가중치)

- current의 이동비용이 NeighborNode의 이동 비용보다 작으면 NeighborNode의 이전 길은 current로 설정해준다.

- NeighborNode는 openList에 담는다.

4. 위와 같은 방법을 반복하여 목표지점을 찾는다.

 

코드 예시

public class AStarNode
{ public bool isWall; public AStarNode ParentNode;

// G : 시작노드부터 이동하려는 위치 거리
// H : 시작노드부터 목표지점까지 거리(타일 수)
// F : G + H
public int x, y, G, H;

public int F
{
get
{
return G + H;
}
}

public AStarNode(bool isWall, int x, int y)
{
this.isWall = isWall;
this.x = x; this.y = y;
}
}

using System.Collections.Generic;
using UnityEngine;
public class AStarLogic : MonoBehaviour
{ private AStarNode[,] nodes;
private AStarNode startNode;
private AStarNode endNode;
private AStarNode currentNode;
private List<AStarNode> openList = new List<AStarNode>();
private List<AStarNode> closeList = new List<AStarNode>();
public Vector2Int TestStartLocation;
// 시작 위치
public Vector2Int TestEndLocation;
// 도착 위치
public int TestXSize;
// 맵 X크기
public int TestYSize;
// 맵 Y크기
[ContextMenu("테스트")]
public void Test()
{ CreateNode(TestXSize, TestYSize);
SetTargetLocation(TestStartLocation, TestEndLocation);
PathFinding(); }
/// <summary> 
/// x,y 크기에 맞는 노드 배열을 만든다.
/// </summary> 
public void CreateNode(int xSize, int ySize)
{ nodes = new AStarNode[xSize, ySize];
for (int x = 0; x < xSize; x++)
{ for (int y = 0; y < ySize; y++)
{ bool isWall = false; 
// 벽 여부 (막힌 길) 
nodes[x, y] = new AStarNode(isWall, x, y);
}
}
}
/// <summary> 
/// 시작 지점과 목표 지점
/// </summary> 
public void SetTargetLocation(Vector2Int startLocation, Vector2Int endLocation)
{ startNode = nodes[startLocation.x, startLocation.y];
endNode = nodes[endLocation.x, endLocation.y];
}
/// <summary> 
/// 길 찾기 알고리즘
/// </summary> 
public void PathFinding()
{ openList.Clear();
// 갈 수 있는 길 목록
closeList.Clear();
// 한번 들른 곳 목록
// 맨 처음에는 시작 지점부터
openList.Add(startNode);
while (openList.Count > 0)
{ // 갈 수 있는 길 중에 가중치가 낮은 길을 찾는다.
currentNode = openList[0];
for (int i = 1; i < openList.Count; ++i) { if (openList[i].F <= currentNode.F && openList[i].H < currentNode.H)
{ currentNode = openList[i]; }
}
// 찾은 길은 갈 수 있는 곳 목록에서 지운다. 
// 한번 들른 곳 목록에 넣어준다. 
// 이로써 한번 갔던 길을 중복으로 검색하는 일은 없어진다. openList.Remove(currentNode); 
closeList.Add(currentNode);
// 목적지에 도착했는지 체크한다. 
if (currentNode == endNode) 
{
//for (int i = 0; i < closeList.Count; i++)
// Debug.Log(i + "번째는 " + closeList[i].x + ", " + closeList[i].y); 
return; }
// 갈 수 있는 길을 찾아서 목록에 넣어준다. 
// 순서는 일반적으로 위 -> 오른쪽 -> 아래 -> 왼쪽 순이다.
OpenListAdd(currentNode.x, currentNode.y + 1);
OpenListAdd(currentNode.x + 1, currentNode.y);
OpenListAdd(currentNode.x, currentNode.y - 1);
OpenListAdd(currentNode.x - 1, currentNode.y); } }
void OpenListAdd(int checkX, int checkY)
{
// 상하좌우 범위를 벗어났다면 빠져나온다.
if (checkX < 0 || checkX >= nodes.GetLength(0) || checkY < 0 || checkY >= nodes.GetLength(1))
return;
// 한번 들른 곳이면 빠져나온다.
if (closeList.Contains(nodes[checkX, checkY]))
return;
// 벽인 경우 빠져나온다.
if (nodes[checkX, checkY].isWall)
return;
//
이동 비용을 구한다.
// 직선 : 현재 위치의 G + 10 (현재 위치 - 확인할 위치를 계산하여 x,y중 하나라도 0인 경우)
// 대각선 : 현재 위치의 G + 14 (현재 위치 - 확인할 위치를 계산하여 x,y 둘 다 0이 아닌 경우)
// 직선의 비용은 10
// 대각선의 비용은 14
AStarNode NeighborNode = nodes[checkX, checkY];
int MoveCost = currentNode.G + (currentNode.x - checkX == 0 || currentNode.y - checkY == 0 ? 10 : 14);
// 이동 비용이 확인할 위치의 G보다 작거나
// 갈 수 있는 길 목록에서 현재 확인하려는 위치가 없다면
if (MoveCost < NeighborNode.G || !openList.Contains(NeighborNode))
{
// 이동비용, 거리, 현재 위치를 담는다. 
NeighborNode.G = MoveCost; NeighborNode.H = (Mathf.Abs(NeighborNode.x - endNode.x) + Mathf.Abs(NeighborNode.y - endNode.y)) * 10; 
NeighborNode.ParentNode = currentNode; 
// 위와 같은 방법을 통해 parentNode가 시작점과 이어지게 된다. 
// 예)
// 시작점 : x:0,y:0 
// 도착점 : x:2,y:0 
// 도착점(2,0) -> 이전(1,0) -> 시작점(0,0)으로 연결 되어 있다.
openList.Add(NeighborNode);
}
}
}