I’m engaged on a recreation the place the participant and enemies transfer between discreet tiles, with solely orthagonal motion (like pokemon). The sport additionally runs on a flip system, so the participant makes a transfer enter, then the enemies calculate their paths and start transferring concurrently with the participant to the primary node of their path. My enemies calculate their paths one after one other and set transfer factors on the place they intend to journey to. This lets enemies test if there’s already a transfer level the place they’re attempting to pathfind to, during which case they’re going to select an alternate adjoining level to maneuver to. After all of the paths are calculated the enemies transfer concurrently. I additionally applied enemy aggro, so solely enemies throughout the bounds of the digital camera path to the participant. The remainder path to a random adjoining node to maintain the paths quick. My downside is I have been playtesting with 20 enemies on a fairly small grid (56×28) and it takes 130 ms or so to calculate the paths of all of the enemies. This ends in some fairly undesirable motion, for the reason that participant’s management is locked till all enemies have completed transferring. The participant noticeably pauses for the enemies to complete transferring in between taking steps.
I’ve posted the related sections of my code beneath, does anybody see a obtrusive concern with how I am approaching this? I’ve tailored a pathfinding tutorial collection by Sebastian Lague on YouTube to suit my recreation. I additionally appeared on the A* Pathfinding Challenge by Aron Granburg, however stayed away from it as a result of it appeared far more sophisticated to adapt to my particular challenge. If anybody is acquainted with the A* pathfinding challenge, is it extremely optimized to the purpose the place it could be value it to scrap what I’ve and attempt to use that as a substitute?
Additionally related: I modified my mounted timestep in my unity challenge settings to 0.001 from 0.02. Since I needed to embrace a WaitForFixedUpdate to verify enemies had been precisely checking for collision this sped up the enemy turns fairly a bit, and it does not appear to have created important overhead.
Additionally additionally related (possibly): Efficiency differs when I’ve the scene view open. On this case enemy pathfinding takes ~ 255 ms slightly than the ~130 ms when the sport view is maximized.
From TurnSystem.cs:
public IEnumerator EnemyTurn(bool playerTookMoveAction)
{
System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch();
playerController.LockControl(true);
sw.Begin();
WaitForFixedUpdate wait = new WaitForFixedUpdate();
for (int i = 0; i < enemies.Depend; i++)
{
if (enemies[i].GetTookFightAction()) proceed;
yield return StartCoroutine(enemies[i].SetMovePoint());
yield return wait;
}
sw.Cease();
print("Elapsed Time: " + sw.ElapsedMilliseconds/1000f);
for (int i = 0; i < enemies.Depend; i++)
{
if (enemies[i].GetTookFightAction()) proceed;
StartCoroutine(enemies[i].TakeStep());
}
whereas(enemiesFinishedAction < enemies.Depend)
{
yield return null;
}
enemiesFinishedAction = 0;
for (int i = 0; i < enemies.Depend; i++)
{
enemies[i].SetAggro();
}
StartCoroutine(playerController.UnlockControlAfterMovement());
OnReadyToSpawn();
}
public void AddEnemy(EnemyAIController enemy)
{
enemies.Add(enemy);
}
public void RemoveEnemy(EnemyAIController enemy)
{
enemies.Take away(enemy);
}
public void EnemyFinishedAction()
{
enemiesFinishedAction++;
}
From EnemyAIController.cs:
public void OnPathFound(Vector2[] newPath, bool pathSuccessful)
{
if (pathSuccessful && newPath.Size > 0)
{
path = newPath;
}
}
public IEnumerator SetMovePoint()
{
if (!isLocked)
{
if (isAggroed)
{
goal = playerMovePoint.place;
}
else
{
goal = GetRandomAdjacentTarget();
}
yield return PathRequestManager.RequestPath(rework.place, goal, OnPathFound);
if (path != null && !Physics2D.OverlapCircle(path[0], 0.3f, collisionLayer))
{
movePoint.place = path[0];
}
else
{
movePoint.place = GetAlternateWaypoint();
}
}
else yield return null;
}
protected Vector2 GetRandomAdjacentTarget()
{
float random = UnityEngine.Random.Vary(0,4);
if (random == 0) return new Vector2 (rework.place.x, rework.place.y - 2);
if (random == 1) return new Vector2 (rework.place.x - 2, rework.place.y);
if (random == 2) return new Vector2 (rework.place.x, rework.place.y + 2);
if (random == 3) return new Vector2 (rework.place.x + 2, rework.place.y);
return rework.place;
}
protected Vector2 GetAlternateWaypoint()
{
if (path != null && path[0] != null && path[0] != (Vector2)movePoint.place)
{
if(path[0].x != movePoint.place.x)
{
if (goal.y > movePoint.place.y && !Physics2D.OverlapCircle(new Vector2(movePoint.place.x, movePoint.place.y + 1), 0.3f, collisionLayer))
{
return new Vector2(movePoint.place.x, movePoint.place.y + 1);
}
else if (goal.y <= movePoint.place.y && !Physics2D.OverlapCircle(new Vector2(movePoint.place.x, movePoint.place.y - 1), 0.3f, collisionLayer))
{
return new Vector2(movePoint.place.x, movePoint.place.y - 1);
}
}
else if (path[0].y != movePoint.place.y)
{
if (goal.x > movePoint.place.x && !Physics2D.OverlapCircle(new Vector2(movePoint.place.x + 1, movePoint.place.y), 0.3f, collisionLayer))
{
return new Vector2(movePoint.place.x + 1, movePoint.place.y);
}
else if (goal.x <= movePoint.place.x && !Physics2D.OverlapCircle(new Vector2(movePoint.place.x - 1, movePoint.place.y), 0.3f, collisionLayer))
{
return new Vector2(movePoint.place.x - 1, movePoint.place.y);
}
}
}
return movePoint.place;
}
From PathRequestManager.cs:
public class PathRequestManager : MonoBehaviour
{
Queue<PathRequest> pathRequestQueue = new Queue<PathRequest>();
PathRequest currentPathRequest;
static PathRequestManager occasion;
Pathfinding pathfinding;
bool isProcessingPath;
personal void Awake()
{
occasion = this;
pathfinding = GetComponent<Pathfinding>();
}
public static IEnumerator RequestPath(Vector2 pathStart, Vector2 pathEnd, Motion<Vector2[], bool> callback) //does this have to be static?
{
PathRequest newRequest = new PathRequest(pathStart, pathEnd, callback);
occasion.pathRequestQueue.Enqueue(newRequest);
occasion.TryProcessNext();
yield return null;
}
personal void TryProcessNext()
{
if (!isProcessingPath && pathRequestQueue.Depend > 0)
{
currentPathRequest = pathRequestQueue.Dequeue();
isProcessingPath = true;
pathfinding.StartFindPath(currentPathRequest.pathStart, currentPathRequest.pathEnd);
}
}
public void FinishedProcessingPath(Vector2[] path, bool success)
{
currentPathRequest.callback(path, success);
isProcessingPath = false;
TryProcessNext();
}
struct PathRequest
{
public Vector2 pathStart;
public Vector2 pathEnd;
public Motion<Vector2[], bool> callback;
public PathRequest(Vector2 _start, Vector2 _end, Motion<Vector2[], bool> _callback)
{
pathStart = _start;
pathEnd = _end;
callback = _callback;
}
}
}
From Pathfinding.cs:
public class Pathfinding : MonoBehaviour
{
PathRequestManager requestManager;
AStarGrid grid;
personal void Awake()
{
requestManager = GetComponent<PathRequestManager>();
grid = GetComponent<AStarGrid>();
}
public void StartFindPath(Vector2 startPos, Vector2 targetPos)
{
StartCoroutine(FindPath(startPos, targetPos));
}
IEnumerator FindPath(Vector2 startPos, Vector2 targetPos)
{
Vector2[] waypoints = new Vector2[0];
bool pathSuccess = false;
Node startNode = grid.NodeFromWorldPoint(startPos);
Node targetNode = grid.NodeFromWorldPoint(targetPos);
if(startNode.walkable && targetNode.walkable)
{
Heap<Node> openSet = new Heap<Node>(grid.MaxSize);
HashSet<Node> closedSet = new HashSet<Node>();
openSet.Add(startNode);
whereas (openSet.Depend > 0)
{
Node currentNode = openSet.RemoveFirst();
closedSet.Add(currentNode);
if (currentNode == targetNode)//discovered the trail
{
pathSuccess = true;
break;
}
foreach(Node neighbor in grid.GetNeighbors(currentNode))
{
if(!neighbor.walkable || closedSet.Incorporates(neighbor)) proceed;
int newMovementCostToNeighbor = currentNode.gCost + GetDistance(currentNode, neighbor);
if (newMovementCostToNeighbor < neighbor.gCost || !openSet.Incorporates(neighbor))
{
neighbor.gCost = newMovementCostToNeighbor;
neighbor.hCost = GetDistance(neighbor, targetNode);
neighbor.guardian = currentNode;
if (!openSet.Incorporates(neighbor))
{
openSet.Add(neighbor);
}
else
{
openSet.UpdateItem(neighbor);
}
}
}
}
}
yield return null;
if (pathSuccess)
{
waypoints = RetracePath(startNode, targetNode);
}
requestManager.FinishedProcessingPath(waypoints, pathSuccess);
}
Vector2[] RetracePath(Node startNode, Node endNode)
{
Checklist<Node> path = new Checklist<Node>();
Node currentNode = endNode;
whereas(currentNode != startNode)
{
path.Add(currentNode);
currentNode = currentNode.guardian;
}
Vector2[] waypoints = SimplifyPath(path);
// Array.Reverse(waypoints);
return waypoints;
}
Vector2[] SimplifyPath(Checklist<Node> path)//I simplified this part of code since I simply wanted the primary waypoint of the trail returned, this did assist efficiency
{
Checklist<Vector2> waypoints = new Checklist<Vector2>();
// Vector2 directionOld = Vector2.zero;
for(int i = Mathf.Max(path.Depend - 1, 0); i < path.Depend; i ++)
// for(int i = 1; i < path.Depend; i ++)
{
// Vector2 directionNew = new Vector2(path[i-1].gridX - path[i].gridX, path[i-1].gridY - path[i].gridY);
// if(directionNew != directionOld)
// {
waypoints.Add(path[i].worldPosition);
// }
// directionOld = directionNew;
}
return waypoints.ToArray();
}
int GetDistance(Node nodeA, Node nodeB)
{
int distanceX = Mathf.Abs(nodeA.gridX - nodeB.gridX);
int distanceY = Mathf.Abs(nodeA.gridY - nodeB.gridY);
return distanceX + distanceY;
}
}
From node.cs:
public class Node : IHeapItem<Node>
{
public bool walkable;
public Vector2 worldPosition;
public int gridX;
public int gridY;
public int gCost;
public int hCost;
public Node guardian;
int heapIndex;
public Node( bool _walkable, Vector2 _worldPos, int _gridX, int _gridY)
{
walkable = _walkable;
worldPosition = _worldPos;
gridX = _gridX;
gridY = _gridY;
}
public int fCost
{
get
{
return gCost + hCost;
}
}
public int HeapIndex
{
get
{
return heapIndex;
}
set
{
heapIndex = worth;
}
}
public int CompareTo(Node nodeToCompare)
{
int evaluate = fCost.CompareTo(nodeToCompare.fCost);
if (evaluate == 0)
{
evaluate = hCost.CompareTo(nodeToCompare.hCost);
}
return -compare;
}
}
From Heap.cs
public class Heap<T> the place T : IHeapItem<T> {
T[] objects;
int currentItemCount;
public Heap(int maxHeapSize) {
objects = new T[maxHeapSize];
}
public void Add(T merchandise) {
merchandise.HeapIndex = currentItemCount;
objects[currentItemCount] = merchandise;
SortUp(merchandise);
currentItemCount++;
}
public T RemoveFirst() {
T firstItem = objects[0];
currentItemCount--;
objects[0] = objects[currentItemCount];
objects[0].HeapIndex = 0;
SortDown(objects[0]);
return firstItem;
}
public void UpdateItem(T merchandise) {
SortUp(merchandise);
}
public int Depend {
get {
return currentItemCount;
}
}
public bool Incorporates(T merchandise) {
return Equals(objects[item.HeapIndex], merchandise);
}
void SortDown(T merchandise) {
whereas (true) {
int childIndexLeft = merchandise.HeapIndex * 2 + 1;
int childIndexRight = merchandise.HeapIndex * 2 + 2;
int swapIndex = 0;
if (childIndexLeft < currentItemCount) {
swapIndex = childIndexLeft;
if (childIndexRight < currentItemCount) {
if (objects[childIndexLeft].CompareTo(objects[childIndexRight]) < 0) {
swapIndex = childIndexRight;
}
}
if (merchandise.CompareTo(objects[swapIndex]) < 0) {
Swap (merchandise,objects[swapIndex]);
}
else {
return;
}
}
else {
return;
}
}
}
void SortUp(T merchandise) {
int parentIndex = (merchandise.HeapIndex-1)/2;
whereas (true) {
T parentItem = objects[parentIndex];
if (merchandise.CompareTo(parentItem) > 0) {
Swap (merchandise,parentItem);
}
else {
break;
}
parentIndex = (merchandise.HeapIndex-1)/2;
}
}
void Swap(T itemA, T itemB) {
objects[itemA.HeapIndex] = itemB;
objects[itemB.HeapIndex] = itemA;
int itemAIndex = itemA.HeapIndex;
itemA.HeapIndex = itemB.HeapIndex;
itemB.HeapIndex = itemAIndex;
}
}
public interface IHeapItem<T> : IComparable<T> {
int HeapIndex {
get;
set;
}
}
From AStarGrid.cs
public class AStarGrid : MonoBehaviour
{
public bool displayGridGizmos;
public LayerMask unwalkableMask;
public Vector2 gridWorldSize;
public float nodeRadius;
Node[,] grid;
float nodeDiameter;
int gridSizeX, gridSizeY;
personal void Awake()
{
nodeDiameter = nodeRadius *2;
gridSizeX = Mathf.RoundToInt(gridWorldSize.x/nodeDiameter);
gridSizeY = Mathf.RoundToInt(gridWorldSize.y/nodeDiameter);
CreateGrid();
}
public int MaxSize
{
get
{
return gridSizeX * gridSizeY;
}
}
personal void CreateGrid()
{
grid = new Node[gridSizeX, gridSizeY];
Vector2 worldBottomLeft = (Vector2)rework.place - Vector2.proper * gridWorldSize.x/2 - Vector2.up * gridWorldSize.y/2;
for (int x = 0; x < gridSizeX; x++)
{
for (int y = 0; y < gridSizeY; y++)
{
Vector2 worldPoint = worldBottomLeft + Vector2.proper * (x * nodeDiameter + nodeRadius) + Vector2.up * (y * nodeDiameter + nodeRadius);
bool walkable = (Physics2D.OverlapCircle(worldPoint,nodeRadius,unwalkableMask) == null);
grid[x,y] = new Node (walkable, worldPoint, x, y);
}
}
}
public Checklist<Node> GetNeighbors(Node node)
{
Checklist<Node> neighbors = new Checklist<Node>();
for (int x = -1; x <= 1; x++)
{
for (int y = -1; y <= 1; y++)
{
if (x == 0 && y == 0 || Mathf.Abs(x) + Mathf.Abs(y) == 2) proceed;
int checkX = node.gridX + x;
int checkY = node.gridY + y;
if(checkX >= 0 && checkX < gridSizeX && checkY >= 0 && checkY < gridSizeY)// if checkX and checkY are on the grid
{
neighbors.Add(grid[checkX, checkY]);
}
}
}
return neighbors;
}
public Node NodeFromWorldPoint(Vector2 worldPosition)
{
float percentX = worldPosition.x / gridWorldSize.x + 0.5f;
float percentY = worldPosition.y / gridWorldSize.y + 0.5f;
int x = Mathf.FloorToInt(Mathf.Clamp((gridSizeX) * percentX, 0, gridSizeX - 1));
int y = Mathf.FloorToInt(Mathf.Clamp((gridSizeY) * percentY, 0, gridSizeY - 1));
return grid[x,y];
}
public Checklist<Node> path;
void OnDrawGizmos()
{
Gizmos.DrawWireCube(rework.place,new Vector2(gridWorldSize.x,gridWorldSize.y));
if (grid != null && displayGridGizmos) {
foreach (Node n in grid) {
Gizmos.coloration = Colour.purple;
if (n.walkable)
Gizmos.coloration = Colour.white;
Gizmos.DrawCube(n.worldPosition, Vector3.one * (nodeDiameter-.8f));
}
}
}
}
