개요
https://www.youtube.com/playlist?list=PLFt_AvWsXl0cq5Umv3pMC9SPnKjfp9eGW
위의 재생목록 링크를 통해 유니티에서 A* 알고리즘을 공부하며 정리하는 글이다.
현재 기준으로 재생목록의 마지막 영상인 Threading을 보고 정리한 글이다.
PathRequestManager 수정
PathRequestManager에서 쓰레드를 사용하도록 수정되었다.
전체코드를 먼저 작성 후, 수정된 함수들을 작성했다.
PathRequestManager 전체 코드
using System.Collections;
using System;
using System.Threading;
using System.Collections.Generic;
using UnityEngine;
public class PathRequestManager : MonoBehaviour
{
Queue<PathResult> results = new Queue<PathResult>();
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>();
}
private void Update()
{
if (results.Count > 0)
{
int itemsInQueue = results.Count;
lock (results)
{
for(int i=0;i < itemsInQueue; ++i)
{
PathResult result = results.Dequeue();
result.callBack(result.path, result.success);
}
}
}
}
public static void RequestPath(PathRequest request)
{
//PathRequest newRequest = new PathRequest(pathStart, pathEnd, callBack);
//instance.pathRequestQueue.Enqueue(newRequest);
//instance.TryProcessNext();
ThreadStart threadStart = delegate
{
instance.pathFinding.FindPath(request, instance.FinishedProcessingPath);
};
threadStart.Invoke();
}
//private void TryProcessNext()
//{
// if(!isProcessingPath && pathRequestQueue.Count > 0)
// {
// isProcessingPath = true;
// curPathRequest = pathRequestQueue.Dequeue();
// pathFinding.StartFindPath(curPathRequest.pathStart, curPathRequest.pathEnd);
// }
//}
public void FinishedProcessingPath(PathResult result)
{
//curPathRequest.callBack(path, success);
//isProcessingPath = false;
//TryProcessNext();
//PathResult result = new PathResult(path,success,originalRequest.callBack);
lock (results)
{
results.Enqueue(result);
}
}
}
public struct PathResult
{
public Vector3[] path;
public bool success;
public Action<Vector3[], bool> callBack;
public PathResult(Vector3[] path, bool success, Action<Vector3[], bool> callBack)
{
this.path = path;
this.success = success;
this.callBack = callBack;
}
}
public 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;
}
}PathResult구조체
public struct PathResult
{
public Vector3[] path;
public bool success;
public Action<Vector3[], bool> callBack;
public PathResult(Vector3[] path, bool success, Action<Vector3[], bool> callBack)
{
this.path = path;
this.success = success;
this.callBack = callBack;
}
}pathRequest구조체를 RequestPath함수에 넣은 후, 결과로 받을 구조체이다.
RequestPath함수
변경된 함수중 하나인 static함수 RequestPath이다.
public static void RequestPath(PathRequest request)
{
//PathRequest newRequest = new PathRequest(pathStart, pathEnd, callBack);
//instance.pathRequestQueue.Enqueue(newRequest);
//instance.TryProcessNext();
ThreadStart threadStart = delegate
{
instance.pathFinding.FindPath(request, instance.FinishedProcessingPath);
};
threadStart.Invoke();
}주석 처리된 부분이 기존 코드다.
기존엔 pathRequest구조체 큐에 PathRequest구조체를 생성 후 enqueue해줬다.
그 다음 TryProcessNext함수를 통해 top값의 pathRequest구조체를 꺼내 실행해줬지만,
이제 ThreadStart를 이용해 pathFinding클래스의 FindPath함수를 쓰레드가 호출하는 식으로 변경되었다.
FinishedProcessingPath함수 수정
public void FinishedProcessingPath(PathResult result)
{
//curPathRequest.callBack(path, success);
//isProcessingPath = false;
//TryProcessNext();
//PathResult result = new PathResult(path,success,originalRequest.callBack);
lock (results)
{
results.Enqueue(result);
}
}기존엔 processingPath가 끝났다면 PathRequest구조체의 callBack함수를 호출해줘 호출한 Unit이 길을 찾게 해주고,
TryProcessNext로 다음 pathRequest구조체를 진행시켰다.
이제는 pathResult구조체 큐인 results를 lock을 통해 멀티쓰레드로부터 락을 걸어준 후,
인자로 들어온 result 구조체를 enqueue해주면 할 일이 끝난다.
Update함수
private void Update()
{
if (results.Count > 0)
{
int itemsInQueue = results.Count;
lock (results)
{
for(int i=0;i < itemsInQueue; ++i)
{
PathResult result = results.Dequeue();
result.callBack(result.path, result.success);
}
}
}
}매 프레임마다 results 큐를 체크하여, Dequeue연산 후,
해당 PathResult구조체의 Action을 실행해준다.
PathFinding 클래스 수정
이 클래스에서 수정된 부분은 StartFindPath함수가 사라지고,
FindPath가 Ienumerator형에서 void로 바뀐부분이다.
StartFindPath함수 호출하는 부분이 이제 FindPath함수를 직접호출하는 부분으로 변경되었다.
PathFinding 전체 클래스
using System.Collections;
using System.Diagnostics;
using System.Collections.Generic;
using UnityEngine;
using System;
public class PathFinding : MonoBehaviour
{
//PathRequestManager requestManager;
private Agrid agrid;
private void Awake()
{
//requestManager = GetComponent<PathRequestManager>();
agrid = GetComponent<Agrid>();
}
//public void StartFindPath(Vector3 startNode, Vector3 endNode)
//{
// StartCoroutine(FindPath(startNode,endNode));
//}
/// <summary>
/// startPos에서 targetPos까지 a* 알고리즘을 통해 최적의 경로를 찾아(list<node>형태) retracepath함수를 호출해 agrid클래스에 넘겨줌
/// </summary>
/// <param name="startPos"></param>
/// <param name="targetPos"></param>
public void FindPath(PathRequest request, Action<PathResult> callBack)
{
Stopwatch sw= new Stopwatch();
sw.Start();
Vector3[] wayPoints=new Vector3[0];
bool pathSuccess=false;
Node startNode = agrid.GetNodeFromWorldPoint(request.pathStart);
Node targetNode = agrid.GetNodeFromWorldPoint(request.pathEnd);
if (startNode.walkable && targetNode.walkable)
{
Heap<Node> openSet = new Heap<Node>(agrid.MaxSize);
//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);
Node curNode = openSet.RemoveFirst();
closedSet.Add(curNode);
if (curNode == targetNode)
{
sw.Stop();
UnityEngine.Debug.Log("path found " + sw.ElapsedMilliseconds + "ms");
pathSuccess = true;
break;
}
foreach (Node elem in agrid.GetNeighbours(curNode))
{
//통과하지 못하거날 이미 처리한 노드라면 contineu
if (!elem.walkable || closedSet.Contains(elem)) continue;
int newGCost = curNode.gCost + GetDistance(elem, curNode)+elem.movePenalty;
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);
}
else
openSet.UpdateItem(elem);
}
}
}
}
// yield return null;
if (pathSuccess)
{
wayPoints = RetracePath(startNode, targetNode);
pathSuccess = wayPoints.Length > 0;
}
//requestManager.FinishedProcessingPath(wayPoints, pathSuccess);
callBack(new PathResult(wayPoints,pathSuccess,request.callBack));
}
/// <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;
}
/// <summary>
/// 모든 노드벡터를 다 지닐 필요는 없다. 방향이 바뀔때만 저장
/// </summary>
/// <param name="path"></param>
/// <returns></returns>
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();
}
/// <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);
}
}
FindPath함수
/// <summary>
/// startPos에서 targetPos까지 a* 알고리즘을 통해 최적의 경로를 찾아(list<node>형태) retracepath함수를 호출해 agrid클래스에 넘겨줌
/// </summary>
/// <param name="startPos"></param>
/// <param name="targetPos"></param>
public void FindPath(PathRequest request, Action<PathResult> callBack)
{
Stopwatch sw= new Stopwatch();
sw.Start();
Vector3[] wayPoints=new Vector3[0];
bool pathSuccess=false;
Node startNode = agrid.GetNodeFromWorldPoint(request.pathStart);
Node targetNode = agrid.GetNodeFromWorldPoint(request.pathEnd);
if (startNode.walkable && targetNode.walkable)
{
Heap<Node> openSet = new Heap<Node>(agrid.MaxSize);
//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);
Node curNode = openSet.RemoveFirst();
closedSet.Add(curNode);
if (curNode == targetNode)
{
sw.Stop();
UnityEngine.Debug.Log("path found " + sw.ElapsedMilliseconds + "ms");
pathSuccess = true;
break;
}
foreach (Node elem in agrid.GetNeighbours(curNode))
{
//통과하지 못하거날 이미 처리한 노드라면 contineu
if (!elem.walkable || closedSet.Contains(elem)) continue;
int newGCost = curNode.gCost + GetDistance(elem, curNode)+elem.movePenalty;
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);
}
else
openSet.UpdateItem(elem);
}
}
}
}
// yield return null;
if (pathSuccess)
{
wayPoints = RetracePath(startNode, targetNode);
pathSuccess = wayPoints.Length > 0;
}
//requestManager.FinishedProcessingPath(wayPoints, pathSuccess);
callBack(new PathResult(wayPoints,pathSuccess,request.callBack));
}인자로 PathRequest request, Action<PathResult> callBack를 받는다.
첫번째 인자로는 이전 구현에서도 받던 PathRequest구조체를 받고,
두번째 인자로는 PathRequestManager클래스의 FinishedProcessingPath함수를
action형태로 받는다.
FinishedProcessingPath함수의 인자가 PathResult라서 Action<PathResult>이다.
함수 내부에서 바뀐 부분은, startNode, targetNode값을
PathRequest.pathStart, PathRequest.pathEnd값으로 할당해주는 부분이다.
그 후, 경로를 구해 wayPoints 배열을 구했다면,
두번째 인자로 받은 callBack Action에 해당 PathResult구조체를 인자로 넣은 후,
실행한다.
한 가지 오류를 fix했는 데, 바로 target을 움직일때 wayPoints가 비어있게 되어 index에러가 나는 현상이다.
이 에러는 타겟을 약간 움직이거나 해서 waypoint에 아무 노드값도 안담겨있을 때 발생하는 에러로,
if (pathSuccess)
{
wayPoints = RetracePath(startNode, targetNode);
pathSuccess = wayPoints.Length > 0;
}pathSuccess값은 wayPoints.Length값이 0보다 클때만 true로 반환하게 변경하였다.
Unit 클래스 수정
UpdatePath함수에서 길찾기 요청하는 부분만 수정되었다.
이렇게 세 값을 넣어 함수 호출하는 부분을
PathRequestManager.RequestPath(transform.position,target.position, OnPathFound);PathRequest구조체로 따로 선언해서 인자로 넣어준다.
PathRequestManager.RequestPath(new PathRequest(transform.position,target.position, OnPathFound));실행 예
이렇게 다양하게 seeker 오브젝트를 나열한 뒤 실행하면
각 오브젝트마다 쓰레딩을 통해 경로를 계산한 뒤
지난 강의에서 구현한 line구조체들의 선을 지나며 부드럽게 잘 간다.
레퍼런스
코딩 창고!
안녕하세요 저도 현재 Sebastian Lague 유튜버 a* 알고리즘 영상을 보고있는데 지금 3일동안 보고있는데도 너무 어렵고 수학 공식들이 이해가 안가서 너무 힘든데 jh Seo님은 금방금방 이해하셨나요?? 아니면 노력하신건가요 이렇게 이해하시고 코드를 해석하시는거 보고 대단하다 생각해서 질문올립니다.