개요
https://www.youtube.com/playlist?list=PLFt_AvWsXl0cq5Umv3pMC9SPnKjfp9eGW
위의 재생목록 링크를 통해 유니티에서 A* 알고리즘을 공부하며 정리하는 글이다.
5번째 영상인 Unit을 보고 정리한 글이다.
요약하자면 싱글턴패턴으로 pathRequestManager라는 스태틱 클래스를 선언하고
pathRequest 큐를 만들어서 길찾기를 원하는 유닛이 길찾기 요청을 하면
큐에 넣어서 순서대로 경로 계산후 해당 유닛에게 경로정보를 보낸다.
이렇게 관리하면 많은 유닛이 한번에 경로를 탐색할 수 있다.
pathRequestManager 클래스 전체 코드
public class PathRequestManager : MonoBehaviour
{
public static PathRequestManager instance;
private Queue<PathRequest> pathRequestQueue = new Queue<PathRequest>();
private PathRequest curPathRequest;
private PathFinding pathFinding;
private bool isProcessingPath=false;
private void Awake()
{
if (instance == null)
instance = this;
else
Destroy(gameObject);
pathFinding = GetComponent<PathFinding>();
}
public static void RequestPath(Vector3 pathStart,Vector3 pathEnd,Action<Vector3[], bool> callBack)
{
PathRequest newRequest = new PathRequest(pathStart, pathEnd, callBack);
instance.pathRequestQueue.Enqueue(newRequest);
instance.TryProcessNext();
}
private void TryProcessNext()
{
if(!isProcessingPath && pathRequestQueue.Count > 0)
{
isProcessingPath = true;
curPathRequest = pathRequestQueue.Dequeue();
pathFinding.StartFindPath(curPathRequest.pathStart, curPathRequest.pathEnd);
}
}
public void FinishedProcessingPath(Vector3[] path, bool success)
{
curPathRequest.callBack(path, success);
isProcessingPath = false;
TryProcessNext();
}
struct PathRequest
{
public Vector3 pathStart;
public Vector3 pathEnd;
public Action<Vector3[], bool> callBack;
public PathRequest(Vector3 _pathStart, Vector3 _pathEnd, Action<Vector3[],bool> _callBack)
{
pathStart = _pathStart;
pathEnd = _pathEnd;
callBack = _callBack;
}
}
} static instance로 관리된다.
pathRequest구조체를 담는 queue, pathRequestQueue를 선언해준다.
각 요청이 진행되고 있을 때는 다른 요청을 처리하지 못하도록 isProcessingPath변수를 선언해줬다.
PathRequest구조체
struct PathRequest
{
public Vector3 pathStart;
public Vector3 pathEnd;
public Action<Vector3[], bool> callBack;
public PathRequest(Vector3 _pathStart, Vector3 _pathEnd, Action<Vector3[],bool> _callBack)
{
pathStart = _pathStart;
pathEnd = _pathEnd;
callBack = _callBack;
}
}기본적인 길찾기 요청 정보 구조체다. 시작 벡터, 끝벡터, 경로 정보를 담은 Vector3[], 랑 경로를 찾았는지 여부를 인자로 받는 Action을 가지고 있다.
pathRequestManager::RequestPath함수
public static void RequestPath(Vector3 pathStart,Vector3 pathEnd,Action<Vector3[], bool> callBack)
{
PathRequest newRequest = new PathRequest(pathStart, pathEnd, callBack);
instance.pathRequestQueue.Enqueue(newRequest);
instance.TryProcessNext();
}static함수로 선언하였다. 이 코드 저자분의 코딩 스타일인 것 같다.
static으로 선언된만큼 static 함수나 static 프로퍼티만 사용가능하므로
큐에 새로운 요청을 넣거나 tryProcessNext함수를 호출할 때,
static인 instance를 호출해서 함수를 사용해야한다.
동작은 인자로 들어온 시작벡터,끝벡터, action으로 새 요청 구조체를 만들고
요청 큐에 넣어준다. 그 후, TryProcessNext함수를 호출한다.
pathRequestManager::TryProcessNext함수
private void TryProcessNext()
{
if(!isProcessingPath && pathRequestQueue.Count > 0)
{
isProcessingPath = true;
curPathRequest = pathRequestQueue.Dequeue();
pathFinding.StartFindPath(curPathRequest.pathStart, curPathRequest.pathEnd);
}
}현재 진행중인 길찾기 요청이 없거나, 요청 큐사이즈가 비어있지 않을 때,
큐에서 요청 구조체 하나를 꺼낸 후 해당 구조체의 길찾기 요청을 시도한다.
길찾기 요청은 pathFinding클래스에 추가한 StartFindPath함수를 호출하는식으로 이뤄진다.
pathRequestManager::FinishedProcessingPath함수
public void FinishedProcessingPath(Vector3[] path, bool success)
{
curPathRequest.callBack(path, success);
isProcessingPath = false;
TryProcessNext();
}길찾기 요청이 이뤄지고 해당 경로까지 받았을 때 실행되는 함수이다.
인자로 받은 경로와 성공 여부를 요청구조체의 Action에 인자로 넣어준 후,
해당 Action을 실행해준다.
길찾기 요청을 끝난 상태이므로 isProcessingPath 변수를 false로 설정 후,
TryProcessNext함수를 실행한다.
PathFinding 수정
내부에 pathRequestManager을 선언해준다.
PathRequestManager requestManager;
private Agrid agrid;
private void Awake()
{
requestManager = GetComponent<PathRequestManager>();
agrid = GetComponent<Agrid>();
}Awake함수에서 Getcomponent로 해당 클래스를 가져온다.
싱글턴 클래스라 PathRequestManager.instance식으로 호출해도 되지만 이 분의 코딩 스타일인것 같다.
StartFindPath함수
public void StartFindPath(Vector3 startNode, Vector3 endNode)
{
StartCoroutine(FindPath(startNode,endNode));
} 원래 길찾기 함수였던 Findpath를 Ienumerable로 변경 후
따로 선언한 StartFindPath 함수에서 해당 코루틴을 호출한다
FindPath함수
private IEnumerator FindPath(Vector3 startPos, Vector3 targetPos)
{
Vector3[] wayPoints=new Vector3[0];
bool pathSuccess=false;코루틴으로 사용하기 위해 Ienumerator형으로 변경해줬다.
경로의 배열을 구해야하기때문에 Vector3형 배열과
경로를 구했는지 여부를 확인하기 위한 bool형 변수를 선언했다.
A* 알고리즘 시작 부분부터 while문 끝나는 부분까지
if (startNode.walkable && targetNode.walkable)
{
Heap<Node> openSet = new Heap<Node>(agrid.MaxSize);
HashSet<Node> closedSet = new HashSet<Node>();
....
} StartNode랑 targetNode가 지나갈수 있을 때만 알고리즘 실행하도록 이 조건문을 씌운다.
코루틴이므로 알고리즘이 끝난 후에
yield return null;
if (pathSuccess)
{
wayPoints = RetracePath(startNode, targetNode);
}
requestManager.FinishedProcessingPath(wayPoints, pathSuccess); 이런식으로 수정된 RetracePath를 통해 경로를 벡터3의 배열로 받은 다음,
위에 적었던 pathRequestManager의 FinishedProcessingPath함수에 해당 경로와
성공여부를 인자로 넘겨준다.
RetracePath수정
/// <summary>
/// StartNode부터 endNode까지 a* 알고리즘으로 찾은 경로(list<Node>)를 agrid의 path에 넣어준다.
/// </summary>
/// <param name="startNode"></param>
/// <param name="endNode"></param>
private Vector3[] RetracePath(Node startNode, Node endNode)
{
List<Node> path = new List<Node>();
Node curNode = endNode;
while (curNode != startNode)
{
path.Add(curNode);
curNode = curNode.Parent;
}
Vector3[] wayPoints = SimplifyPath(path);
Array.Reverse(wayPoints);
return wayPoints;
}바뀐점은 이제 Vector3의 배열을 반환한다.
그리고 현재 경로에는 모든 노드가 다들어가있는데 이걸
더 최적화 하기위해 Simplify함수를 사용한다.
또한 배열로 바뀌었기 때문에 List.Reverse에서
System 네임스페이스에 포함된 Array.Reverse함수로 뒤집어야한다.
Simplify함수
Vector3[] SimplifyPath(List<Node> path)
{
List<Vector3> wayPoints = new List<Vector3>();
Vector2 directionOld = Vector2.zero;
for(int i = 1; i < path.Count; i++)
{
Vector2 directionNew = new Vector2(path[i - 1].gridX - path[i].gridX, path[i - 1].gridY - path[i].gridY);
if(directionOld!= directionNew)
{
//삽질
wayPoints.Add(path[i].worldPosition);
directionOld = directionNew;
}
//만약 일직선이라면 어떻게 되는지 체크
}
return wayPoints.ToArray();
}List<Node> 를 받아와서 방향이 바뀔때만 노드를 저장하는 방식이다.
Vector2 directionNew = new Vector2(path[i - 1].gridX - path[i].gridX, path[i - 1].gridY - path[i].gridY); 바로 전 노드의 grid에서 행렬과 현재 노드의 grid에서의 행렬을 빼주는 식으로 방향을 구한다.
이전 방향인 directionOld와 다른 방향이라면 경로 List인 wayPoint에 넣어주고
같은 방향이면 넣어주지 않는다.
이런식으로 방향이 다를때만 노드를 저장해서 경로노드의 갯수를 줄인다.
여기서 헷갈렸던 점은 방향이 바뀔때만 노드를 저장하는 방식이라
만약 일직선의 길일때는 노드가 하나일텐데라는 부분이였다.
노드가 하나인데 어떻게 이동을 하지라는 생각이 들어 다시 코드를 봐밨다.
이 부분은 곰곰히 생각하면 알 수 있는게, path는 아직 Reverse연산을 하기 전이다.
따라서 일직선의 길에서는 하나남은 노드가 목적지이다.
후술할 Unit클래스에서 나오지만 경로를 받은 후, 해당 경로로 이동을 할 때,
현재지점에서 경로의 노드로 이동하는 형식이다.
경로의 노드는 목적지 하나만 있으므로 목적지로 이동을 똑바로한다.
Unit 클래스
이제 경로 매니저들도 만들었으므로 임시 유닛들을 생성해서 경로 매니저에
길찾기 요청을 보낸 후 해당 경로로 움직이게 하는 클래스를 만든다.
public class Units : MonoBehaviour
{
public Transform target;
private float speed=5f;
Vector3[] path;
int targetIndex=0;
private void Start()
{
PathRequestManager.RequestPath(transform.position, target.position, OnPathFound);
}
public void OnPathFound(Vector3[] newPath, bool pathSuccessful)
{
if (pathSuccessful)
{
path = newPath;
targetIndex = 0;
StopCoroutine("FollowPath");
StartCoroutine("FollowPath");
}
}
private IEnumerator FollowPath()
{
Vector3 currentWayPoint = path[0];
while (true)
{
if(transform.position == currentWayPoint)
{
targetIndex++;
if (targetIndex > path.Length)
yield break;
currentWayPoint = path[targetIndex];
}
transform.position = Vector3.MoveTowards(transform.position, currentWayPoint, speed * Time.deltaTime);
yield return null;
}
}
private void OnDrawGizmos()
{
if (path != null)
{
for(int i = targetIndex; i < path.Length; i++)
{
Gizmos.color = Color.black;
Gizmos.DrawCube(path[i], Vector3.one);
if (i == targetIndex)
{
Gizmos.DrawLine(transform.position, path[i]);
}
else
Gizmos.DrawLine(path[i - 1], path[i]);
}
}
}
}
start함수에서 PathRequestManager클래스의 static 함수 RequestPath를 호출한다.
OnPathFound함수
RequestPath 함수의 인자 Action<vector3[],bool>에 넣어줄 함수이다.
public void OnPathFound(Vector3[] newPath, bool pathSuccessful)
{
if (pathSuccessful)
{
path = newPath;
targetIndex = 0;
StopCoroutine("FollowPath");
StartCoroutine("FollowPath");
}
}RequestPath함수가 실행되면 newPath와 pathSuccessful에 값이 할당된다.
pathSuccessful이 true일때만 FollowPath코루틴을 실행한다.
FollowPath함수
private IEnumerator FollowPath()
{
Vector3 currentWayPoint = path[0];
while (true)
{
if(transform.position == currentWayPoint)
{
targetIndex++;
if (targetIndex > path.Length)
yield break;
currentWayPoint = path[targetIndex];
}
transform.position = Vector3.MoveTowards(transform.position, currentWayPoint, speed * Time.deltaTime);
yield return null;
}
}OnPathFound 함수로 받아온 path의 0번째 인덱스를 currentWayPoint에 저장해준다.
그 후, path의 length만큼 반복하며, 현재 postion을 path의 다음 인덱스로 움직인다.
OnDrawGizmos함수
각 유닛에서 타겟까지의 경로를 시각화하기위해 넣어줬다.
private void OnDrawGizmos()
{
if (path != null)
{
for(int i = targetIndex; i < path.Length; i++)
{
Gizmos.color = Color.black;
Gizmos.DrawCube(path[i], Vector3.one);
if (i == targetIndex)
{
Gizmos.DrawLine(transform.position, path[i]);
}
else
Gizmos.DrawLine(path[i - 1], path[i]);
}
}
}
path가 null이 아닐때만 그린다.
targetIndex가 현재 내위치이므로 targetIndex부터 path.length만큼 그린다.
각 노드에는 DrawCube로 박스를 그리고,
노드를 잇는 경로에는 DrawLine을 통해 선을 그려준다.
i가 targetIndex일때는 i-1값이 존재하지않으므로 현재 포지션에서 i번째 까지 선을 긋게 했다.
실행 예
player을 네 개 생성해준 후, target으로 가게끔 설정해줬다.
방향이 바뀔때마다 노드가 생겼고, 해당 길을 따라 열심히 잘들 간다.
밑에 저 아이 경로를 보고 왜 직선으로 안 가지? 라고 생각했다가 당연하단걸 깨달았다.
격자 노드들을 생성해서 각 노드로 이동하는 방식이라
노드들을 다 뚫으며 직선으로 갈수가 없다.
생각
원래 강의를 쭉 보고 이해한 후, 다시 처음으로 돌아가서 코드 짜는거 보고 따라 짜는 방식으로 짰는데
이상하게 이번 정리를 할때 집중이 잘 안 되서, 코드를 따라짤때 빼먹고 짠 부분이 많아서
수많은 오류를 경험했다.,
Simplify함수에서
if(directionOld!= directionNew)
{
//삽질
wayPoints.Add(path[i].worldPosition);
directionOld = directionNew;
}이부분을 path[i].worldPosition이 아니라 directionOld를 넣어서 wayPoint List에
directionOld값만 들어간다던가,
Simplify함수에서
for(int i = 1; i < path.Count; i++)
{
}반복문이 path.Count가 되어야하는데 비어있는 List인 wayPoint.Count로 적어서
반복문자체가 실행이 안 되었다.
이 두 부분 찾는데 좀 시간이 걸렸었다.. ㅋㅋ
레퍼런스
