koobas.hobune.stream
[Solved] VERY LOW FPS using Astar path finding
Hi every One I'm using Astar path finding system for AI in my 2d android game. As soon as the player reaches close enough to zombie (AI) the path finding algorithm will run and fps drops about 30 fps it's been worse in new scene I created after updating unity to 2019.3.9f1 and I hardly get 3 - 4 fps for a couple of zombies using path finding codes. this video is where i learned my path finding and converted form 3d to 2d to suits my need. I don't thing I'm going to get away from this one without a help does updating unity cause problem? this is profiler image Is this for Astar path finding ? Do you know have a better idea to solve this? And this is zombie's script :
void Update()
{
zombieController();
}
private void zombieController() { RaycastHit2D[] hits = Physics2D.CircleCastAll((Vector2)transform.position, 1f, Vector2.zero); foreach (RaycastHit2D hit in hits) {
GameObject targetInRadius = hit.collider.gameObject;
if (targetInRadius.CompareTag("Player"))
{
pathFind(transform.position, targetInRadius.transform.position);
pathFinding = mylist;
if (pathFinding != null && pathFinding.Count > 0)
{
target = pathFinding[0].vPosition;
rb.velocity = (target - (Vector2)transform.position).normalized * 0.3f;
}
}
}
}
public void pathFind(Vector3 a_StartPos, Vector3 a_TargetPos)
{
Node StartNode = grid.NodeFromWorldPoint(a_StartPos);//Gets the node closest to the starting position
Node TargetNode = grid.NodeFromWorldPoint(a_TargetPos);//Gets the node closest to the target
List<Node> OpenList = new List<Node>();//List of nodes for the open list
HashSet<Node> ClosedList = new HashSet<Node>();//Hashset of nodes for the closed list
OpenList.Add(StartNode);//Add the starting node to the open list to begin the program
while (OpenList.Count > 0)//Whilst there is something in the open list
{
Node CurrentNode = OpenList[0];//Create a node and set it to the first item in the open list
for (int i = 1; i < OpenList.Count; i++)//Loop through the open list starting from the second object
{
if (OpenList[i].FCost < CurrentNode.FCost || OpenList[i].FCost == CurrentNode.FCost && OpenList[i].ihCost < CurrentNode.ihCost)//If the f cost of that object is less than or equal to the f cost of the current node
{
CurrentNode = OpenList[i];//Set the current node to that object
}
}
OpenList.Remove(CurrentNode);//Remove that from the open list
ClosedList.Add(CurrentNode);//And add it to the closed list
if (CurrentNode == TargetNode)//If the current node is the same as the target node
{
GetFinalPath(StartNode, TargetNode);//Calculate the final path
}
foreach (Node NeighborNode in grid.neighboringNodes(CurrentNode))//Loop through each neighbor of the current node
{
if (NeighborNode.bIsWall || ClosedList.Contains(NeighborNode))//If the neighbor is a wall or has already been checked
{
continue;//Skip it
}
int MoveCost = CurrentNode.igCost + (GetManhattenDistance(CurrentNode, NeighborNode) / GetManhattenDistance(CurrentNode, NeighborNode));//Get the F cost of that neighbor
if (MoveCost < NeighborNode.igCost || !OpenList.Contains(NeighborNode))//If the f cost is greater than the g cost or it is not in the open list
{
NeighborNode.igCost = MoveCost;//Set the g cost to the f cost
NeighborNode.ihCost = GetManhattenDistance(NeighborNode, TargetNode);//Set the h cost
NeighborNode.ParentNode = CurrentNode;//Set the parent of the node for retracing steps
if (!OpenList.Contains(NeighborNode))//If the neighbor is not in the openlist
{
OpenList.Add(NeighborNode);//Add it to the list
}
}
}
}
}
void GetFinalPath(Node a_StartingNode, Node a_EndNode)
{
List<Node> FinalPath = new List<Node>();//List to hold the path sequentially
Node CurrentNode = a_EndNode;//Node to store the current node being checked
while (CurrentNode != a_StartingNode)//While loop to work through each node going through the parents to the beginning of the path
{
FinalPath.Add(CurrentNode);//Add that node to the final path
CurrentNode = CurrentNode.ParentNode;//Move onto its parent node
}
FinalPath.Reverse();//Reverse the path to get the correct order
mylist = FinalPath;
}
int GetManhattenDistance(Node a_nodeA, Node a_nodeB)
{
int ix = Mathf.Abs(a_nodeA.iGridX - a_nodeB.iGridX);//x1-x2
int iy = Mathf.Abs(a_nodeA.iGridY - a_nodeB.iGridY);//y1-y2
return ix + iy;//Return the sum
}
this is grid making acript:
public Vector2 gridWorldSize;
public float nodeRadius;
float nodeDiameter;
int gridCountX;
int gridCountY;
Node[,] grid;
Vector2 bottemLeft;
//public List<Node> FinalPath;
// Start is called before the first frame update
void Start()
{
nodeDiameter = nodeRadius * 2;
gridCountX = Mathf.RoundToInt(gridWorldSize.x / nodeDiameter);
gridCountY = Mathf.RoundToInt(gridWorldSize.y / nodeDiameter);
createGrid();
}
void createGrid()
{
bottemLeft = (Vector2)transform.position - Vector2.right * (gridWorldSize.x / 2) - Vector2.up * (gridWorldSize.y / 2);
grid = new Node[gridCountX, gridCountY];
for(int y = 0; y < gridCountY; y++)
{
for(int x=0; x < gridCountX; x++)
{
Vector2 nodePos = bottemLeft + Vector2.right * (nodeDiameter * x + nodeRadius) + Vector2.up * (nodeDiameter * y + nodeRadius);
bool isWall = false;
RaycastHit2D[] hits = Physics2D.CircleCastAll(nodePos, nodeRadius, Vector2.zero);
foreach(RaycastHit2D hit in hits)
{
GameObject hiter = hit.collider.gameObject;
if (hiter.CompareTag("walls"))
{
isWall = true;
}
}
grid[x, y] = new Node(isWall, nodePos, x, y);
}
}
}
public Node NodeFromWorldPoint(Vector3 a_vWorldPos)
{
a_vWorldPos -= transform.position;
float ixPos = ((a_vWorldPos.x + gridWorldSize.x / 2) / gridWorldSize.x);
float iyPos = ((a_vWorldPos.y + gridWorldSize.y / 2) / gridWorldSize.y);
ixPos = Mathf.Clamp01(ixPos);
iyPos = Mathf.Clamp01(iyPos);
int ix = Mathf.RoundToInt((gridCountX - 1) * ixPos);
int iy = Mathf.RoundToInt((gridCountY - 1) * iyPos);
return grid[ix, iy];
}
public List<Node> neighboringNodes(Node currentNode)
{
List<Node> neighbirnode = new List<Node>();
int xCheck = currentNode.iGridX;
int yCheck = currentNode.iGridY;
//Right
if (0 < xCheck + 1 && xCheck+1<gridCountX)
{
neighbirnode.Add(grid[xCheck + 1, yCheck]);
}
//Left
if (0 < xCheck - 1 && xCheck - 1 < gridCountX)
{
neighbirnode.Add(grid[xCheck - 1, yCheck]);
}
//Up
if (0 < yCheck + 1 && yCheck + 1 < gridCountY)
{
neighbirnode.Add(grid[xCheck , yCheck + 1]);
}
//Down
if (0 < yCheck - 1 && yCheck - 1 < gridCountY)
{
neighbirnode.Add(grid[xCheck, yCheck - 1]);
}
//RightUp
if (0 < xCheck + 1 && xCheck + 1 < gridCountX && 0 < yCheck + 1 && yCheck + 1 < gridCountY)
{
neighbirnode.Add(grid[xCheck + 1, yCheck + 1]);
}
//RightDown
if (0 < xCheck + 1 && xCheck + 1 < gridCountX && 0 < yCheck - 1 && yCheck - 1 < gridCountY)
{
neighbirnode.Add(grid[xCheck + 1, yCheck - 1]);
}
//LeftUp
if (0 < xCheck - 1 && xCheck - 1 < gridCountX && 0 < yCheck + 1 && yCheck + 1 < gridCountY)
{
neighbirnode.Add(grid[xCheck - 1, yCheck + 1]);
}
//LeftDown
if (0 < xCheck - 1 && xCheck - 1 < gridCountX && 0 < yCheck - 1 && yCheck - 1 < gridCountY)
{
neighbirnode.Add(grid[xCheck - 1, yCheck - 1]);
}
return neighbirnode;
}
and this is NODE script:
public class Node {
public int iGridX;//X Position in the Node Array
public int iGridY;//Y Position in the Node Array
public bool bIsWall;//Tells the program if this node is being obstructed.
public Vector3 vPosition;//The world position of the node.
public Node ParentNode;//For the AStar algoritm, will store what node it previously came from so it cn trace the shortest path.
public int igCost;//The cost of moving to the next square.
public int ihCost;//The distance to the goal from this node.
public int FCost { get { return igCost + ihCost; } }//Quick get function to add G cost and H Cost, and since we'll never need to edit FCost, we dont need a set function.
public Node(bool a_bIsWall, Vector3 a_vPos, int a_igridX, int a_igridY)//Constructor
{
bIsWall = a_bIsWall;//Tells the program if this node is being obstructed.
vPosition = a_vPos;//The world position of the node.
iGridX = a_igridX;//X Position in the Node Array
iGridY = a_igridY;//Y Position in the Node Array
}
}
so if you already know about the profiler... why not use it accordingly? What exactly is eating up all the performance here?
Thanks @Captain_Pineapple for answer. sorry but I don't know how! the profiler shows most fps drop is when AI use path finding. in the time line of profiler window, it shows the most amounts are for "player loop" , "Update.ScriptRunBehavierUpdate" , "BehavierUpdate"and zombie's script has less ms than all named above as you can see in picture I sent in question. Is this huge amount of fps drop normal just for a couple of AI finding their path using Astar?! I hope I could explained my problem well.
you should just click in the timeline wherever you want to investigate what you are searching for and search through the call stack. There you should (kind of as you already listed) see how much time is needed for what actions. Pay attention to the columns named GC Alloc and Time ms. Those are the ones that you should try and keep low. So which are the heavy ones in your project?
I accidentally figured out A fps boost by adding some walls to add border to my scene. I've been using path finding algorithm in a scene with no collider and that needed huge proccessing because there was too many possible pathes to be analyzed. but i still had fps drop while some thing about 10 zombies was finding their path. so i tried to run path finding algorithm for them every 0.5 seconds instead of every frame and that also helped my fps to increase. (Another solution can be limiting zombies. by letting one zombie to use path finding at a time.although I haven't tried this. tell me if you got a good result trying it.) After all I got better result doing what I said but I was expecting to use path finding for more number of zombies and in a bigger area so if any of you found a way to do it don't doubt letting me know
