Hello everyone! Maybe someone can help me since I think I have a mistake.
When my units move the game fps goes from 120 to 30 ?
Here is a photo for you to see. I really have no idea why it could be.
Thanks in advance!
How big is your map? How far can your Units move?
Like I mentioned in the video, the pathfinding implemented in the course is something super simple so you can learn how the algorithm works, it is not intended to be performant at all.
But since the game is turn based having a single frame take a long time isn’t a big issue, after calculating the framerate goes back to normal.
1 Like
There are a lot of ways the pathfinding here could be implemented:
-
I would pre-define neighbors for the PathNodes in the path node class so that it would be possible to extract this list directly without having to find the neighbors for each cell each iteration.
-
Calculate path. The path is iterated twice: Once to put the path nodes into a list, and then once more to create a list of the grid positions. Since we do not really need the path nodes list for anything, you could just create the grid positions list in the first loop (this one would not speed up the path finding by a lot, but it is a really easy update). Something like this:
private List<GridPosition> CalculatePath(PathNode endNode) {
PathNode currentNode = endNode;
List<GridPosition> gridPositions = new List<GridPosition>();
gridPositions.Add(currentNode.GetGridPosition());
while (currentNode.GetCameFromPathNode() != null) {
gridPositions.Add(currentNode.GetCameFromPathNode().GetGridPosition());
currentNode = currentNode.GetCameFromPathNode();
}
gridPositions.Reverse();
return gridPositions;
}
-
Pre-allocate some of the lists that are created each iteration. This will prevent some garbage collection.
-
Always profile before you do any optimizations. Since this is a turn-based game, running this path finding on a desktop should not have too much of a performance impact in general (but obviously, it should not be updated each frame).
Sebastian Lauge also has a nice tutorial on A* path finding in Unity on Youtube that also shows how to run the path finding on a separate thread. That would probably be the best optimisation if you run the path finding very frequently. You can find it here: https://www.youtube.com/watch?v=-L-WgKMFuhE&list=PLFt_AvWsXl0cq5Umv3pMC9SPnKjfp9eGW
2 Likes
I actually wrote the CalculatePath method ahead of time in the video to get rid of the error in the main algorithm. Since I had a data structures and algorithms class in college, I had an idea of what was supposed to happen. I wrote mine like this though:
private List<GridPosition> CalculatePath(PathNode endNode)
{
List<GridPosition> finalPath = new List<GridPosition>();
finalPath.Add(endNode.GetGridPosition());
PathNode currentNode = endNode;
PathNode nextNode = currentNode.GetPreviousNode();
while(nextNode != null)
{
currentNode = nextNode;
finalPath.Add(currentNode.GetGridPosition());
nextNode = currentNode.GetPreviousNode();
}
finalPath.Reverse();
return finalPath;
}
I did it this way because I believe it’s less expensive to swap data references using the nextNode variable and reduce the get method calls on each iteration of the while loop. Is this correct, or do I have that idea backward? Is there a drawback to using the nextNode variable?
Also, I sort of agree with your first point. I think the tradeoff is that you would increase load times on a large level in exchange for faster pathfinding, but it would also use more memory. Does that sound right? I am not 100% sure since I am still learning things about how C# and Unity work together.
2 Likes
There are sound arguments for pre-caching the neighbors, or not doing so and fetching them every turn. Pre-caching the neighbors does allow for a slightly faster processing time on the A*, as you’ve already ruled out invalid positions, it’s just a matter of getting the list of neighbors. There is a cost in memory, however, that must be considered.
The biggest thing to avoid is creating and destroying pathnodes themselves, which is why Hugo creates all of the valid PathNodes in advance. Creating and destroying nodes puts them in the garbage, and if you’ve ever played a game where you get a sudden pause right in the middle of your battle: That’s the garbage collector quite literally blocking execution of your program to clean up the trash.
2 Likes
I fully agree that it is important to create the nodes up-front. In fact, not doing so would make the whole process much more complicated as you would have to generate the nodes whenever you do a path search. Honestly, it would not make any sense not to create them.
There is a very small memory cost assiciated with caching the neighbors. Obviously, the cost would increase with the map size but since the PathNode is a reference type, the cost would be 8 bytes (x64) per neighbor, so at maximum 64 bytes per node (with 8 neighbors). So in a 100x100 grid it would consume about 640 kb of RAM. That is nothing to worry about - even on a mobile device. I agree that the garbage-collector would not be the big issue when finding neighbors but since a list is a reference type, and you create lists of nodes over and over again, at some point it will trigger the garbage collector.
That being said, this is a teaching course. Not an performace optimisation course. I seriously doubt that for this type of game the path finding would be a performance bottlenech. If I was to implement A* in any serious game, I would use an asset like A* Pathfinding Project since path finding is so much more than just implementing the algorithm.
2 Likes
I actually used this very same “light” version of A* in a turn based RogueLike game I wrote a couple of years ago. It’s not the fastest version around by any means. Up to about a 100x100 partially filled dungeon of tiles, you don’t really notice the calculation time. What was actually more of a drag was when I moved enemies in the same way as the player when the enemies were still obscured (Fog of war, line of sight were both implemented). I fixed that by just moving the enemy to it’s destination in a single frame if the enemy could not be seen.
2 Likes
Hello guys. How can I improve the performance of the pathfinding then? I read the whole conversation, and, I’m still a newbie so couldn’t really understand what is the best/more affordable solution, taking in consideration how the rest of the project is already built.
Is it by using the “A* Pathfinding Project” asset a good solution? Will it work good with the rest of the project? Or will I need to redo the whole project to make it work?
If it’s an easy implementation, can anyone give me some lights about it?
By the way, I’m not sure if it’s the Pathfinding what it’s slow itself, or if it’s the UpdateGridVisuals(), as, the pathfinding I understand is created once when you click on the target gridcell, but then, it gets “lagged” on every gridcell the Unit moves into (meaning, everytime the “UpdateGridVisuals()” is called).
Thanks so much!
The A* Pathfinding Project asset has Grid pathfinding and is extremely performant so if that’s your goal then I can recommend that asset, it’s what I’ve used in pretty much all my Steam games. I made a full review and getting started guide here Code Monkey - The PERFECT Pathfinding!
You don’t have to redo the whole project, just the parts that interact with the pathfinding.
You can check what exactly is taking up the most time by using the Profiler. Enable Deep Profile and it will tell you how much time each function is taking.
4 Likes
Will try, thanks for answering!