개요
https://www.youtube.com/playlist?list=PLFt_AvWsXl0cq5Umv3pMC9SPnKjfp9eGW
위의 재생목록 링크를 통해 유니티에서 A* 알고리즘을 공부하며 정리하는 글이다.
A* 알고리즘의 대략적인 설명
-
첫 번째 영상은 전체적인 A* 알고리즘에 대한 설명이였다.
각 노드에서 경로가 제일 적은걸 고르는 방식은 다익스트라와 비슷하지만,
A* 알고리즘의 차별점은 각 노드에서 시작점으로부터 거리(G Cost)뿐만 아니라
각 노드에서 도착점까지의 거리(H Cost)까지 계산해서 합산하며 계산한다.총 코스트인 F Cost는 G cost + H cost가 되고, H cost를 무시할 때
다익스트라 알고리즘과 같은 결과가 나온다.
-
계산하는 대략적인 과정
이 영상에서는 Closed List, Open List두가지 리스트로 노드들을 관리한다,
시작점을 closed List에 노드로 삽입한다.
시작점 주위의 노드들을 g, h, F cost를 계산한 후, Open List에 다 넣어준다.
Open List에서 F cost가 제일 적은 노드를 선택한다.
F cost가 같은 노드가 여러개라면 H cost가 더 작은 노드를 선택한다.
해당 노드를 closed List에 넣고 다시 주위의 노드들을 g,h,f cost를 계산 후,
Open List에 넣어준다.Open List에서 꺼낸 노드가 목표노드일때까지 반복한다.
Node와 Grid 생성하기
기본적인 원리는 맵 전체를 노드로 나눠서 관리하는 방식이다.
Node
Node는 컴퍼넌트로 관리할 부분이 아니라서 Monobehaviour을 뗐다.
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
public class Node
{
public bool walkable;
public Vector3 worldPosition;
public Node(bool tmpWalkable, Vector3 tmpWorldPosition)
{
walkable = tmpWalkable;
worldPosition = tmpWorldPosition;
}
}
각 노드는 걸어갈 수 있는지 여부에 대한 bool형 변수 walkable과
해당 노드의 실제 위치를 담은 Vector3형 변수 worldPosition을 관리한다.
Grid
Grid는 노드들을 맵에 생성하고, OnDrawGizmos함수를 이용해 씬에서 확인해보는 방식으로 구현했다.
public GameObject player;
public LayerMask UnWalkableLayer;
public Vector2 gridWorldSize;
public Node[,] grid;
public int gridXCnt;
public int gridYCnt;
public float nodeRadius;
private float nodeDiameter;- 주요 변수를 설명하자면
UnwalkableLayer은 지나갈 수 없는 레이어마스크를 지정해줘 관리한다.
gridWorldSize는 노드로 나뉘어 관리될 전체 Area의 크기를 Vector2형으로 관리하는 변수다.
grid는 2차원 노드 배열이다.
gridXCnt는 그리드에서 x축 노드의 총 갯수를 관리하는 변수고,
gridYCnt는 그리드에서 y축 노드의 총 갯수를 관리하는 변수다.
nodeDiameter은 각 노드의 지름, nodeRadius는 각 노드의 반지름을 관리하는 변수다.
- 우선 Start함수에서 Init 함수를 호출한다.
private void Init() { nodeDiameter = nodeRadius * 2; gridXCnt = Mathf.RoundToInt( gridWorldSize.x / nodeDiameter); gridYCnt = Mathf.RoundToInt( gridWorldSize.y / nodeDiameter); CreateGrid(); }
-
CreateGrid()함수에서 본격적으로 노드들을 생성하게된다.
private void CreateGrid() { grid = new Node[gridXCnt, gridYCnt]; //현재 포지션에서 x축으로 gridWorldSize의 x값/2 만큼 빼고 z축으로 gridWorldSize.y/2만큼 빼야함. worldBottomLeft = transform.position - Vector3.right * gridWorldSize.x / 2 - Vector3.forward *gridWorldSize.y/2; 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); } } }worldBottomLeft 는 Vector3형 변수로 transform.postion에서
x축으로 -그리드의 x사이즈/2 만큼
z축으로 -그리드의 y사이즈/2만큼 이동한 위치다.반복문을 통해 그리드의 갯수만큼 worldBottomLeft에서 생성한다.
Physics.CheckSphere함수를 통해 해당 position이 UnwalkableLayer인지 체크 후,
walkable변수와 월드 포지션을 노드의 생성자로 넣어준다.이 함수에서 주의할점은 영상에서 y축을 기준으로 잡고 x,z평면에서 진행중이라서
grid에서는 y라고 표현하지만 월드 포지션으로 연산할때는 z축에서 연산해야한다.
대표적으로 - Vector3.forward * gridWorldSize.y /2; 이 부분이다. -
GetNodeFromWorldPoint(Vector3) 함수를 통해 World포지션에 해당하는 노드를 가져온다.
public Node GetNodeFromWorldPoint(Vector3 worldPos) { float percentX = (worldPos.x + gridWorldSize.x / 2) / gridWorldSize.x; float percentY = (worldPos.z + gridWorldSize.y / 2) / gridWorldSize.y; percentX = Mathf.Clamp01(percentX); percentY = Mathf.Clamp01(percentY); int x = Mathf.RoundToInt((gridXCnt-1) * percentX); int y = Mathf.RoundToInt((gridYCnt-1) * percentY); return grid[x, y]; }인자로 들어온 WorldPosition을 전체 grid에서 퍼센트로 바꿔준다.
영상에서 grid는 중심이 (0,0,0)이므로 worldPos.x에 gridWorldSize.x / 2를 더한 후,
전체 그리드 사이즈인 gridWorldSize.x로 나눠준다.
worldPos.y에도 똑같이 (worldPos.z + gridWorldSize.y / 2) / gridWorldSize.y
연산을 해주면 월드 포지션의 x축, z축의 전체 그리드 기준으로 한 퍼센트가 나온다.두 퍼센트를 Clamp01연산을 통해 0~1사이로 변환해준다.
0부터 시작하므로 각 축의 노드 갯수 -1 을 해주고 퍼센트를 곱한 후,
반올림을 해줘서 grid의 행, 열값을 구한다.
전체 코드
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
public class Grid : MonoBehaviour
{
public GameObject player;
public LayerMask UnWalkableLayer;
public Vector2 gridWorldSize;
public Node[,] grid;
public int gridXCnt;
public int gridYCnt;
public float nodeRadius;
private float nodeDiameter;
public Vector3 worldBottomLeft;
private void Init()
{
nodeDiameter = nodeRadius * 2;
gridXCnt = Mathf.RoundToInt( gridWorldSize.x / nodeDiameter);
gridYCnt = Mathf.RoundToInt( gridWorldSize.y / nodeDiameter);
CreateGrid();
}
private void CreateGrid()
{
grid = new Node[gridXCnt, gridYCnt];
//현재 포지션에서 x축으로 gridWorldSize의 x값/2 만큼 빼고 z축으로 gridWorldSize.y/2만큼 빼야함.
worldBottomLeft = transform.position - Vector3.right * gridWorldSize.x / 2 - Vector3.forward *gridWorldSize.y/2;
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);
}
}
}
private void Start()
{
Init();
}
public Node GetNodeFromWorldPoint(Vector3 worldPos)
{
float percentX = (worldPos.x + gridWorldSize.x / 2) / gridWorldSize.x;
float percentY = (worldPos.z + gridWorldSize.y / 2) / gridWorldSize.y;
percentX = Mathf.Clamp01(percentX);
percentY = Mathf.Clamp01(percentY);
int x = Mathf.RoundToInt((gridXCnt-1) * percentX);
int y = Mathf.RoundToInt((gridYCnt-1) * percentY);
return grid[x, y];
}
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;
Gizmos.DrawCube(n.worldPosition, Vector3.one * (nodeDiameter-.1f));
}
}
}
}
실행 예
이런 식으로 배치했다. 빨강 구조물들이 지나가지 못하는 벽들이고, 중간에 하양색 물체가
플레이어다.
실행해보면
이런식으로 플레이어가 있는 곳은 cyan색의 큐브가 생겼고,
벽이 있는 곳들은 red색의 큐브들이 생겼다,
레퍼런스
