Unity 2D에서 네비게이션(길찾기) 구현하기(Path Finding, A* Algorithm)
전체 소스코드/ 사용방법 : https://github.com//simple-Astar-algorithm
알고리즘 작성 배경
유니티3D에는 Mesh Navigation을 사용하여 손 쉽게 NPC 등의 길찾기를 구현 할 수 있습니다. 하지만 유니티2D에는 Mesh가 없어서 장애물을 피해가야 하는 등의 길찾기는 쉽게 구현할 수 없습니다. 3D모드로 구현 후 90도 회전하여 2D인 척 하는 등의 방법도 있지만, 오히려 그게 더 어려워 보였기 때문에 A*알고리즘을 작성하게 되었습니다.
알고리즘 기초 개념
1. A* 알고리즘에는 기본적으로 3개의 변수가 있습니다.
g-cost : 시점으로부터 경유지 까지 경로의 가중치
h-cost : 경유지점부터 종점까지 경로의 가중치
f -cost : g-cost 와 h-cost의 합
2. 위 세 변수로 경로들을 탐색합니다.
- 매 루프당 g, h -cost는 최신화 됩니다.
- 따라서 f-cost도 최신화 됩니다. 가장 낮은 f-cost를 가지는 노드로 이동 합니다.
- 만약 최소 f-cost가 목적지라면, 탐색을 종료 합니다.
알고리즘 세부 개념
A* 알고리즘엔 OpenSet, ClosedSet 두개의 집합이 있습니다.
현재 노드의 8방향 전부의 f,g,h - cost를 계산 합니다. 만약 OpenSet에 8방향 노드들이 존재하지 않는다면 각각 OpenSet에 넣어 줍니다.
OpenSet에 있는 원소들의 f-cost 값이 현재 플레이어가 도달한 노드의 f-cost 값 보다 작으면 다음 도달해야 할 값으로 그 OpenSet의 노드를 지정하고, 지정된 노드를 ClosedSet으로 넣습니다. 물론 OpenSet의 해당 값은 삭제 합니다.
OpenSet이 0이 될 때 까지 위 과정을 반복 합니다. 중간에 목적지에 도달하면 탈출 합니다.
알고리즘 제반 스크립트
2D에 사각 노드들을 가상으로 지정해 주어야 합니다. 그래야 장애물(unWalkable) 인지 인식을 할 수 있기 때문입니다.
따라서 Grid 클래스를 지정 해주어야 합니다. 이 클래스는 이동 여부를 결정지을 격자의 크기를 조정할 수 있습니다.
Grid 소스 코드 :
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
public class Grid : MonoBehaviour
{
public bool displayGridGizmos;
public Transform player;
public LayerMask OBSTACLE;
public Vector2 gridWorldSize;
public float nodeRadius;
Node[,] grid;
float nodeDiameter;
int gridSizeX, gridSizeY;
private void Awake()
{
nodeDiameter = nodeRadius * 2;
gridSizeX = Mathf.RoundToInt(gridWorldSize.x / nodeDiameter);
gridSizeY = Mathf.RoundToInt(gridWorldSize.y / nodeDiameter);
CreateGrid();
}
[SerializeField]
public List path;
void CreateGrid()
{
grid = new Node[gridSizeX, gridSizeY];
// 지정된 gridWorldSize의 좌측 최하단의 좌표를 구한다.
Vector2 worldBottomLeft = (Vector2)transform.position - Vector2.right * gridWorldSize.x / 2 - Vector2.up * gridWorldSize.y / 2;
for (int x = 0; x GetNeighbours(Node node)
{
List neighbours = new List();
for(int x = -1; x <= 1; x++)
{
for (int y = -1; y <= 1; y++)
{
if(x == 0 && y == 0)
{
continue;
}
int checkX = node.gridX + x;
int checkY = node.gridY + y;
if(checkX >= 0 && checkX < gridSizeX && checkY >= 0 && checkY < gridSizeY)
{
neighbours.Add(grid[checkX, checkY]);
}
}
}
return neighbours;
}
// 노드의 위치를 월드좌표로 바꾼다.
public Node NodeFromWorldPoint(Vector2 worldPosition)
{
float percentX = (worldPosition.x + gridWorldSize.x / 2) / gridWorldSize.x;
float percentY = (worldPosition.y + gridWorldSize.y / 2) / gridWorldSize.y;
percentX = Mathf.Clamp01(percentX);
percentY = Mathf.Clamp01(percentY);
int x = Mathf.RoundToInt((gridSizeX - 1) * percentX);
int y = Mathf.RoundToInt((gridSizeY - 1) * percentY);
return grid[x, y];
}
// Scene View에 기즈모로 격자 그려주는 코드
// 플레이어 : 청록색, 장애물 : 빨강색, 경로 : 검정색
private void OnDrawGizmos()
{
Gizmos.DrawWireCube(transform.position, new Vector2(gridWorldSize.x, gridWorldSize.y));
if(grid != null )
{
Node playerNode = NodeFromWorldPoint(player.position);
foreach (Node n in grid)
{
Gizmos.color = (n.walkable) ? Color.white : Color.red;
if(path != null)
{
if (path.Contains(n)) Gizmos.color = Color.black;
}
if (playerNode == n) Gizmos.color = Color.cyan;
Gizmos.DrawCube(n.worldPosition, Vector2.one * (nodeDiameter - 0.1f));
}
}
}
}
A* 알고리즘 소스코드
<
/div>
IEnumerator FindPath(Vector2 startPos, Vector2 targetPos)
{
Node startNode = grid.NodeFromWorldPoint(startPos);
Node targetNode = grid.NodeFromWorldPoint(targetPos);
bool pathSuccess = false;
if (startNode.walkable && targetNode.walkable)
{
List openSet = new List();
HashSet closedSet = new HashSet();
openSet.Add(startNode);
while (openSet.Count > 0)
{
Node currentNode = openSet[0];
for (int i = 1; i < openSet.Count; i++)
{
if (openSet[i].fCost < currentNode.fCost || openSet[i].fCost == currentNode.fCost && openSet[i].hCost < currentNode.hCost)
{
currentNode = openSet[i];
}
}
openSet.Remove(currentNode);
closedSet.Add(currentNode);
if (currentNode == targetNode)
{
if(pathSuccess == false)
{
PushWay( RetracePath(startNode, targetNode) ) ;
}
pathSuccess = true;
break;
}
foreach (Node neighbour in grid.GetNeighbours(currentNode))
{
if (!neighbour.walkable || closedSet.Contains(neighbour))
continue;
int newMovementCostToNeighbour = currentNode.gCost + GetDistance(currentNode, neighbour);
if (newMovementCostToNeighbour < neighbour.gCost || !openSet.Contains(neighbour))
{
neighbour.gCost = newMovementCostToNeighbour;
neighbour.hCost = GetDistance(neighbour, targetNode);
neighbour.parent = currentNode;
if (!openSet.Contains(neighbour))
{
openSet.Add(neighbour);
}
}
}
}
}
}
Vector2[] RetracePath(Node startNode, Node endNode)
{
List path = new List();
Node currentNode = endNode;
while(currentNode != startNode)
{
path.Add(currentNode);
currentNode = currentNode.parent;
}
path.Reverse();
grid.path = path;
Vector2[] wayPoints = SimplifyPath(path);
return wayPoints;
}
Vector2[] SimplifyPath(List path)
{
List wayPoints = new List();
for(int i = 0; i < path.Count; i++)
{
wayPoints.Add(path[i].worldPosition);
}
return wayPoints.ToArray();
}
구현 결과 사진
길찾기 알고리즘을 찾아보던 중에 2D는 어떻게 하나 싶었는데. 비슷한 고민을 하신 분이 계셨군요 ㅎㅎ 글 잘 읽었습니다!
답글삭제