Dan
|
I have just recently started using A* Pathfinding, and let me say it has been quite helpful. I have it set up in my environment and can start pathfinding and everything works quickly, save for one thing (which I\’ll get to in a moment). But first, some background info:
I am currently creating an RTS wherein I need to move a large number of units (hopefully, hundreds) around as the user clicks the mouse. I have set up some benchmarks where I have 100 to 150 units moving relatively smoothly through the scene.
However — here\’s the problem — when the user clicks the mouse, it takes a moment for all of the path calculations to happen. After several frames, the first units start moving, but it takes up to a second for all of the units to start moving, leading me to believe that the paths are computed concurrently, and not in parallel. I looked at the console and noticed that each of the paths is computed in \”0.00 ms\” — fast enough for me, it seems.
So my questions are, when is the path finding computed? Can I compute a path and start moving my unit in the same frame? Can I set up some sort of multi-threaded computation so it runs in parallel? Or is there some other way to speed it up?
I am using the free version of A* Pathfinding, with Unity 3.5 Release Candidate.
Thanks!
Dan
|
Dan
|
Here’s a code snippet…
protected virtual void Update ()
{
// Checks to make sure the path is valid and that we can move, etc. etc.
.....
//Direction to the next waypoint
Vector3 dir = m_path.vectorPath[m_waypoint];
dir.y = transform.position.y;
transform.LookAt(dir);
transform.position += (dir - transform.position).normalized * Time.deltaTime * m_movementSpeed;
if (Vector3.Distance(transform.position, dir) < POSITION_TOLERANCE)
{
m_waypoint++;
}
if (Vector3.Distance(GetPosition(), m_moveToLocation) < POSITION_TOLERANCE)
{
Debug.Log("Idle");
m_state = UnitState.Idle;
}
......
}
public virtual void MoveTo(Vector3 newLocation)
{
if (!m_canMove)
return;
m_seeker.StartPath(transform.position, newLocation, PathfindingCallback);
}
private void PathfindingCallback(Path path)
{
m_path = path;
m_moveToLocation = m_path.endPoint;
m_state = UnitState.Moving;
m_waypoint = 0;
}
MoveTo() gets called when the mouse is clicked at a location.
Also, one thing that I just noticed… my framerate is very poor in that second or so when the paths are being calculated, but when all the paths are finished being calculated, everything runs very smoothly. Which makes sense.
|
Aron Granberg
|
Hi
Since each path needs a lot of info for every node in the graph, such as the parent node, g score, h score and also some other values. I calculate all paths in sequence. Otherwise, for say a 100*100 grid graph, memory usage would increase with about 200 KB for every concurrent path calculation (might be more than 4 variables I use though, haven’t checked) plus the information to store the different data (perhaps 40 kb extra if you are lucky). It might not seem like a lot, but it does add up. One problem I had with the 2.x pathfinder was that it used way too much memory, so every few seconds the GC (Garbage Collector) would get called and it would cause lag in the game.
In the Pro version I run all path calculations, still in sequence, but in another thread which on multi-core computers frees up the main game thread to do other stuff.
Due to the way the system is structured, I think you can get the path calculation back the same frame, but that would be if the functions executed in an optimal way, so I would count with the next frame at best.
Now counting on it, I think it might be worth a try to make a really multithreaded pathfinder which can run, say 5 paths at the same time… I was actually surprised that it wasn’t more than 200 KB. Now the problem is how to structure it to avoid a performance hit…
Also, another thing which can use up CPU power is post-processing. In some cases the post-processing might even use more power than the path calculation. So check the modifiers you are using. Using a lower number of iterations or a larger segment length on the simple smooth modifier helps speed things up for example.
|
Aron Granberg
|
Okay, more realistic tests I have done indicate about half a mb for every new concurrent thread.
|
Dan
|
Thanks for the quick reply, Aron.
When I boil down my problem, I think the real issue is that calculating say 100 paths (1 for each of 100 units) bogs down the main game thread. I’ve been thinking that a better alternative would be to create one path and vary the start and end points so as to somehow reuse paths.
Is there a noticeable difference in the performance of this kind between the Pro and Free versions? I’ve been thinking about purchasing the Pro version if it will help with some of the issues I am having here.
Dan
|
Dan
|
Update:
What I realized is that Unity decides to wait after it finds a path. I don’t know why, but it does; I ran some tests and the pathfinding is executed instantly (0 ms to calculate) but the frame afterward lags terribly. I ended up creating my own pathfinding utility and I got the same exact results: I would click, everything would freeze for a few frames, and then everything would run smoothly thereafter. However, because I got the same results with both A* Pathfinding and my own utility, I have concluded that Unity is doing something weird, like Garbage Collecting at an odd time. Or my computer is being weird.
I have decided to try the Unity built-in pathfinding and see if I get better performance for my specific situation. I will post back here if I find out why Unity is acting like this…
Dan
|
Aron Granberg
|
Huh, weird…
Have you tried disabling all other scripts like movement and similar and run nothing but the pathfinding and see if you get similar results?
|
Dan
|
Yes I have. I set up a blank project with no obstacles and nothing except for A* pathfinding. I have the objects (just a bunch of cubes) move around randomly using Seeker.StartPath(). The frame (or sometime several frames) after the pathfinding finishes is/are extremely slow, even though the pathfinding takes hardly any time at all. It’s all very strange.
Dan
|
Dan
|
I suppose I could upload a package if someone else feels inclined to poke around a bit. I’m convinced that either I’m doing something completely wrong or that Unity is being weird. I’m inclined to think the latter because I essentially stripped down my code to a copy-paste of what the Getting Started guide says.
Actually, perhaps this is better: is there some sort of demo package of A* pathfinding that I can download, which has multiple objects moving around and doing pathfinding, so I could compare results?
|
Dan
|
Okay, so here’s something interesting… I moved the entire project onto a Mac computer and everything works great. No annoying pauses, no lagging, no FPS spikes. So I guess I will be working on this project on that computer from now on.
Note for the general programming populace: always test on multiple machines!
I will play around with the built-in Unity pathfinding, A* pathfinding, and my own implementation and see what will work best for me.
Thanks,
Dan
|
Aron Granberg
|
That’s odd, and since I’m on a mac, that means I cannot test it either : (
Did you try build the game and check if the lag occurred then as well?
|
Dan
|
Ah, sorry for my belated response, I haven’t checked this forum recently.
I did try building it, and it still had all of the lag issues. I suspect that my Unity installation is what is causing the problem, and that Garbage Collection is slowing down for some odd reason. I have been meaning to reinstall Unity and see if that helps. But for the time being, I am content working on my Mac.
Dan
|
Hasan Bozok
|
I think you are doing wrong with calculating paths for all units.If i were you, In creation queue of units , i create an empty gameobject which will generate a formation for units and give them the position where should they stay.That empty game object calculates the path and it gives each unit a vector3 array which stands for where unit will stand next.
|
