개요
개요
https://www.youtube.com/playlist?list=PLFt_AvWsXl0cq5Umv3pMC9SPnKjfp9eGW
위의 재생목록 링크를 통해 유니티에서 A* 알고리즘을 공부하며 정리하는 글이다.
3번째 영상을 보고 정리한 글이다.
이번 영상은 요약하자면 저번 강의에서 만든 장애물들과 그리드 위에 두 오브젝트를 만든 후,
A* 알고리즘을 통해 두 오브젝트 사이의 최적의 경로를 찾는다.
Node클래스 수정
각 노드들이 담아야 할 정보들이 추가되어서 클래스에 변수들을 추가했다.
public class Node
{
public bool walkable;
public Vector3 worldPosition;
public int gridX;
public int gridY;
public int gCost;
public int hCost;
public Node Parent;
public int fCost { get { return gCost + hCost; } }
public Node(bool tmpWalkable, Vector3 tmpWorldPosition,int tmpGridX, int tmpGridY)
{
walkable = tmpWalkable;
worldPosition = tmpWorldPosition;
gridX = tmpGridX;
gridY = tmpGridY;
}
}추가된 부분은
-
각 노드가 이차원노드배열 grid에서 몇번째 행, 몇번째 열인지
정보를 담은 gridX, gridY 변수가 추가되었다. -
각 노드의 현재 gCost와 hCost변수가 추가되었고,
gCost,hCost의 합을 반환하는 fCost 프로퍼티가 추가되었다. -
해당 노드의 이전 노드를 가리키는 Node형 변수 Parent가 생겼다.
-
생성자에서 행렬 정보를 추가하기위해 인자로 tmpGridX, tmpdGridY변수를 더 넣어줘야한다.
Grid클래스 수정
-
이름도 살짝 바꿔줬다.
클래스 이름을 Grid로 사용하니까 유니티에서 Grid클래스가 이미 존재한다고 경고가 떠서 그냥 클래스이름을 Agrid로 바꿨다. -
인자로 들어온 노드의 주변 8개노드를 List<Node>형으로 반환하는 GetNeighbours함수가 새로 생겼다.
public List<Node> GetNeighbours(Node node) { List<Node> neighbours = new List<Node>(); for(int i = -1; i <= 1; i++) { for(int j = -1; j <= 1; j++) { //자기 자신 노드는 컨티뉴 if (i == 0 && j == 0) continue; int nextX = node.gridX + i; int nextY = node.gridY + j; if (nextX < 0 || nextY < 0 || nextX >= gridXCnt || nextY >= gridYCnt) continue; neighbours.Add(grid[nextX, nextY]); } } return neighbours; } -
위의 Node클래스의 생성자 인자가 추가됨에 따라 CreateGrid함수도
Node를 생성할때 변경해줘야한다.for (int i = 0; i < gridXCnt; i++) { for (int j = 0; j < gridYCnt; j++) { Vector3 worldPoint = worldBottomLeft + (i * nodeDiameter + nodeRadius) * Vector3.right + (j * nodeDiameter + nodeRadius) * Vector3.forward; bool walkable = !Physics.CheckSphere(worldPoint, nodeRadius, UnWalkableLayer); grid[i, j] = new Node(walkable, worldPoint,i,j); } } -
pathFinding 클래스에서 a* 알고리즘을 이용해 두 오브젝트 사이의 최단 경로를 List<Node>형으로 찾았을때 할당해줄 path변수를 새로 추가했다.
public List<Node> path; -
두 오브젝트사이의 최단 경로를 표시해주기 위해 OnDrawGizmos()함수도
수정했다.private void OnDrawGizmos() { Gizmos.DrawWireCube(transform.position, new Vector3(gridWorldSize.x, 1, gridWorldSize.y)); if (grid != null) { Node playerNode = GetNodeFromWorldPoint(player.transform.position); foreach (Node n in grid) { Gizmos.color = (n.walkable) ? Color.green : Color.red; //if (playerNode == n) Gizmos.color = Color.cyan; if (path.Contains(n)) { Gizmos.color = Color.black; } Gizmos.DrawCube(n.worldPosition, Vector3.one * (nodeDiameter - .1f)); } } }현재 영상에서는 player을 사용하지 않고 두 오브젝트사이 경로만 나타내므로
if (playerNode == n) Gizmos.color = Color.cyan;를 주석처리했다.
PathFinding 클래스
크게 FindPath함수, RetracePath함수, GetDistance함수 이렇게 세개로 나눠진다.
FindPath함수
/// <summary>
/// startPos에서 targetPos까지 a* 알고리즘을 통해 최적의 경로를 찾아(list<node>형태) retracepath함수를 호출해 agrid클래스에 넘겨줌
/// </summary>
/// <param name="startPos"></param>
/// <param name="targetPos"></param>
private void FindPath(Vector3 startPos, Vector3 targetPos)
{
Node startNode = agrid.GetNodeFromWorldPoint(startPos);
Node targetNode = agrid.GetNodeFromWorldPoint(targetPos);
List<Node> openSet = new List<Node>();
HashSet<Node> closedSet = new HashSet<Node>();
openSet.Add(startNode);
while(openSet.Count > 0)
{
//open Set에서 fcost가 제일작은 값을 찾아 curNode 에 넣음, fcost가 같을땐 hcost가 더 작은 값을 고름
Node curNode = openSet[0];
for(int i = 1; i < openSet.Count; i++)
{
if (openSet[i].fCost< curNode.fCost || (openSet[i].fCost==curNode.fCost && openSet[i].hCost < curNode.hCost))
{
curNode = openSet[i];
}
}
openSet.Remove(curNode);
closedSet.Add(curNode);
if (curNode == targetNode)
{
RetracePath(startNode, targetNode) ;
return;
}
foreach(Node elem in agrid.GetNeighbours(curNode))
{
//통과하지 못하거날 이미 처리한 노드라면 contineu
if (!elem.walkable || closedSet.Contains(elem)) continue;
int newGCost = curNode.gCost + GetDistance(elem, curNode);
if (newGCost < elem.gCost || !openSet.Contains(elem))
{
elem.gCost = newGCost;
elem.hCost = GetDistance(elem, targetNode);
elem.Parent = curNode;
if (!openSet.Contains(elem))
{
openSet.Add(elem);
}
}
}
}
}-
인자로 받아온 두 오브젝트의 벡터를 agrid클래스의 GetNodeFromWorldPoint함수를 통해 해당 위치의 노드로 변경한다.
-
openSet은 List<Node> 로, closedSet은 HashSet<Node>으로 선언했다.
-
순서는
-
시작 노드를 openSet에 넣는다.
-
openSet의 노드 중 Fcost가 제일 작은 값을 선택한다. (Fcost가 같다면 Hcost가 제일 작은 값)
-
해당 노드를 curNode로 할당하고, openlist에서 빼고 closedList에 넣는다.
-
만약 해당 curNode가 targetNode라면 후술할 RetracePath함수를 호출하고 종료한다.
-
targetNode가 아니라면, 해당 노드의 주변 노드들을
agrid클래스의 GetNeighbour함수를 통해 불러온다. -
불러온 주변 노드들의 각 노드들에 대해 갱신을 진행하는데
- elem 노드가 지나갈수 없는 상태거나, closedSet에 이미 존재하는 노드라면 continue를 한다.
- 아니라면 현재 curNode를 통해 elem노드로 향하는 새로운 G Cost를 newGCost에 저장한다.
- elem노드의 gCost보다 newGcost가 작거나
해당 노드가 openSet에 아직 등록이 안 되었다면,
curNode를 통해 elem노드로 가도록 elem노드의 정보들을 갱신한다. - openSet에 등록이 안 된 상태면 openSet에 넣어준다.
-
GetDistance함수
/// <summary>
/// 노드끼리 바로 옆에 붙어있으면 길이를 10으로 가정하면, 대각선은 10루트2라서 대충 14로 정함.
/// A와 B의 최소길이는 A부터 B까지 대각선으로 먼저가서 x축이나 y축을 맞춘 후 남은 거리만큼 직선거리로 가면됨.
/// 이 거리가 distY가 더 작을때 14*distY + 10(distX-distY) 로 표현됨
/// </summary>
/// <param name="A"></param>
/// <param name="B"></param>
/// <returns></returns>
private int GetDistance(Node A, Node B)
{
int distX = Mathf.Abs(A.gridX - B.gridX);
int distY = Mathf.Abs(A.gridY - B.gridY);
if (distX > distY)
return 14 * distY + 10*(distX - distY);
return 14 * distX + 10* (distY - distX);
} 인자로 받은 두 노드 의 거리를 구하는 함수다.
노드가 수직으로 붙어있다면 거리를 10으로 설정했고,
대각선으로 붙어있을 때는 10루트2로 14정도로 설정했다.
두 노드의 최단 거리는 한 노드를 먼저 대각선을 통해 이동해
x축이나 y축좌표를 맞춘 후, 남은 거리를 직선으로 이동하면 나타난다.
RetracePath함수
/// <summary>
/// StartNode부터 endNode까지 a* 알고리즘으로 찾은 경로(list<Node>)를 agrid의 path에 넣어준다.
/// </summary>
/// <param name="startNode"></param>
/// <param name="endNode"></param>
private void RetracePath(Node startNode, Node endNode)
{
List<Node> path = new List<Node>();
Node curNode = endNode;
while (curNode != startNode)
{
path.Add(curNode);
curNode = curNode.Parent;
}
path.Reverse();
agrid.path = path;
} RetracePath함수는 인자로 받은 StartNode노드와 EndNode를 이용해서,
end노드부터 시작해서 각 노드의 parent노드를 순회하며 start노드까지의
경로에 해당하는 노드 list를 path에 저장한다.
그 후, Reverse함수를 이용해 순서를 거꾸로 한 후, agrid클래스의 path에 넣어준다.
실행 예
agrid 클래스에 위 구체를 Seeker, 밑의 구체를 Target으로 설정한 후,
실행시켜보면,
이런식으로 경로에 해당하는 path리스트의 노드들은 검정색으로 나타난다.
위치를 움직여보면
이런식으로 경로들을 보여준다.
레퍼런스
