I noticed that the biggest performance problem in my game is that the moving units have to find very short paths, very often. This happens when they clutter around each other and try to find a place to stand that is not occupied.
Often these paths are only one or two steps away on the grid, so a full blown path search seems overkill. It also invokes GetNearest often to find start and end - which here also should not be necessary, because before running StartPath I already know the start node (the unit stores it) and use GetNearest to find the closest viable spot.
So how would I shortcut StartPath for these situations? Can you point me in the right direction?
Sometimes it really helps to spell out the problem. I created an overloaded version of ABPath that takes start and end node when you construct it (instead of start and end position).
This way, in Prepare, I can leave away the GetNearest and just use the given start and end node. Obviously this only works because I always know the start and end node already.
The increase in performance is significant though:
There are a number of Checks You could run for simpler paths~ For example, raycast to target to see if you can just move in a strait line:
Also you might want to consider using local avoidance for this issue, that would allow for much less frequent path calls
If you want any more indepth performance boosting ideas (Like matrix positioning) I would need to know a little more about why, and when your calling StartPath
Hope that helps~
Burdock
EDIT: After looking at your Alpha, I have a few questions, #1: Are you using a point graph? #2: Why are you calculating paths more then 1-2 times per second ??
Thanks for your response! It’s a custom graph that I generate with the level. I wanted multiple floors but the grid graph didn’t give me enough control (since some of the floors move, e.g. elevators, which have their own grid).
The frequent recalculating happens when multiple units get close and block each other’s paths (they may only walk on the grid). I don’t know how I would take it into account.
When a unit sees that it’s target position is blocked (they may walk through each other, but not stand on the same spot), it finds a path to the closest free position.
I’ve already cut down significantly on the cost by avoiding GetNearest, which seems to be the most expensive part of finding a path. In fact it runs pretty good now. With 128 units trying to cram into the same elevator I still have more than 20fps (outside of the editor).
Yeah I was considering that. But it seemed like it would cause more trouble than good. If I claim the whole path from start to end, other units are blocked needlessly.
If I claim nodes for the time in which they’re needed, I can still get units that walk on the path and then stop there, e.g. if their movement got cancelled for whatever reason (e.g. they spot an enemy or whatever).
The only thing I can think of right now that may make sense is to claim x nodes up ahead. But I think it would still block other units where it’s not necessary.
That could be an option. Right now I’m doing it the other way around - first go there and if it’s blocked by arrival, go somewhere close by. That avoids finding the nearest node to the end node. Nearest Node has actually the worst performance impact.
You are using a grid graph, right?
And GetNearest has the worst performance impact!?
Then you must be performing huuge amounts of them. A GetNearest call on a GridGraph involves little more than a matrix multiplication, some rounding and a bit more math. That is of course assuming that the queried point is relatively close to a walkable point. If it is not, it will go much slower since it will have to search outwards for the closest walkable node.
As I wrote before, it’s a custom graph (with custom nodes). I’m not exactly sure what makes GetNearest so slow, though. It’s actually not the amount. Calling it once already causes a performance spike. Probably it calculates the distance to every node in the graph.
If you are using a custom graph type and you are not overriding the GetNearest or GetNearestForce methods, the default implementation will just compare distances to all nodes in the graph. If there is some structure to your graph which you can use to reduce the calculation times, override the GetNearest and GetNearestForce methods.
Look in the Base.cs script, it has the default implementation.
[EDIT] Looking at the profiler screenshot. Just how many nodes do you have in that graph? 50 ms is huge!
