Parallel GPU-based A* algorithm in pathfinding

[aeonios]

7 minutes ago, ffffffff said:

NetServer is threaded? i guess and NetClient awaiting patch for thread from @elexis? maybe now merging ideas and work here? EAE tnx

Not the last time I checked. It was an idea being thrown around, something that probably ought to be done but which hasn't yet. I don't know if anyone is even working on it.

[elexis]

Networking code has to be threaded, because any slow code that suddenly consumes 10 seconds or more will trigger a timeout disconnect.

The NetServer NetClient code are equally affected, but only the NetServer had been threaded to fix that (ages ago).

In a23(a) we had such a 10 second lag on gamestart which literally broke every single 4v4 we started and left at least one player unable to start the game, which was one of the reasons we needed a re-release. We had addressed this 10 second lag and added timeout tolerance to 60 seconds, but the problem must be fixed with threading. (Other than the disconnect issue, there is also no reason other than subideal code why slow code should trigger network lag.)

The according ticket is at #3700 and the according patch resting somewhere on a dusty git branch. But don't expect that this NetClient threading will make the game more performant (FPS-wise).

[odalman]

On 12/18/2018 at 5:05 PM, wraitii said:

I also have (this one indeed very WIP) patch for unit-pushing, which removes most of the need for the short-range pathfinder (it's still useful to keep around for stuff such as finding your way around a resource).

I find this interesting and imagine that it is what I remember from Settlers 3 (there are videos online for the young people). It worked with a lot of units on a Pentium II 400 MHz. Units would automatically step aside if another unit was coming too close (quite realistic). Hope to see this in 0 A.D.

Edited January 30, 2019 by odalman

[Sundiata]

11 minutes ago, odalman said:

I find this interesting and imagine that it is what I remember from Settlers 3 (there are videos online for the young people). It worked with a lot of units on a Pentium II 400 MHz. Units would automatically step aside if another unit was coming too close (quite realistic). Hope to see this in 0 A.D.

Could go up to more than a thousand units (even several thousand I believe)... Not bad for 1998...

[Aeros]

I'm interested if this find is of any resource to any programmers who might still be developing. Pathfinding and why we hit this lag one large maps with large amounts of units has perplexed staff since inception, and similarly perplexes programmers who have joined in their attempts to solve it. Despite computers being some 10-20 times faster than they were when the engine was first being developed, the pathfinding remains bottlenecked by some thread or function even today. Its clearly not an issue of a computer's performance. When the engine was first designed we were making it work on a pentium 2 and a 64mb geforce MX graphics card as minimum system requirement !

 

My guess is the interplay between the way commands are scheduled within the game and the net code that communicates it to the clients. But then again I'm not a programmer.

 

I remember at one point we had interviewed some of Ensemble Studio's (Age of Empires devs) programmers for how they built their pathfinding system. But here we are, with the majority of the contributors on the project being in areas other than high level code and programming, the issue remains ripe for someone capable of  tackling this.  We have had extremely tallented coders on the project in the past, but their numbers were in the handfuls and they all end up with serious day jobs one way or another where there is no time to do similar work for free at the end of the day. This is not a bad thing and in my opinion is normal and rational, all who work on the game did so for the experience of it and to learn how to do this. The team at its inception was a modding group for age of kings, not a developer. 

 

I think all it takes is reviewing the game's source code from the ground up, which due to so many contributors over the years, is not the easiest process. Though I'm convinced its not an impossible issue for someone who wants the credit and the glory of solving this bug. The source code is publicly available.  https://sourceforge.net/projects/zero-ad/

 

I doubt a multie-threaded application will solve the pathfinding since I don't believe the issue is with computational power, but rather communication within different parts of the game's engine with one area "waiting" for a response from another thread which is performing poorly and is not optimized well for its simple task. A modern CPU today can for sure handle pathfinding for 500 units at 60 frames per second in real time...it did back in 1997....  

 

The topic however is very interesting and worth studying, the future of gaming and Direct X 12 will be multi threaded and parallel processed. Someone with tallent will come along and work magic here. Its an excellent credit to get your foot in the game industry. There were a handful of people from the beginning that used their experience with 0ad to get an entry into the game industry or a related job, myself included. 

Edited February 26, 2019 by Aeros

[nani]

I always remember this link when I think of making something fast

https://lists.freebsd.org/pipermail/freebsd-current/2010-August/019310.html

[Stan`]

2 hours ago, Aeros said:

The topic however is very interesting and worth studying, the future of gaming and Direct X 12 will be multi threaded and parallel processed. Someone with tallent will come along and work magic here. Its an excellent credit to get your foot in the game industry. There were a handful of people from the beginning that used their experience with 0ad to get an entry into the game industry or a related job, myself included. 

I did try that too

Actually threading the pathfinder makes it faster. I can render the game at 20x with very little lag with the patch so it does help. It gives more time for other areas of the code.

But yeah the goal is the vertex pathfinder rewrite. See D13 on code.wildfiregames.com.

@wraitii will be able to tell you more.

[elexis]

On 2/26/2019 at 8:14 AM, stanislas69 said:

I can render the game at 20x with very little lag

We can't distinguish how fast it actually runs, this gamespeed number is an upper limit. Also the rendering is cut to 1 frame per simulation update when doing signficant fast-forwards. Running a non-visual replay with one and multiple threads would provide a comparison.

Threading indeed won't solve the slow algorithm (laptops with only one core won't benefit), nor is the problem related in any way to networking code. It's just that the pathfinding is too slow, burns too much CPU cyles, with threading the other cores burn too many cycles more equally. It will make the CPU fan more noisy I suppose, but it should probably still be done (and then the algorithm improvements on top of that).

[jrevel]

Hi, I'm new to the forum, and I did not have the time yet to look to the source code in depth, but I have already worked on the pathfinding of a shipped game, and there is a thing that might be important to remember : pathfinding IS slow. Even A* has an exponential complexity, so it must not be used lightly.

I believe than we can earn way more performance by trying to call less the pathfinding instead of trying to optimize it, as it seems already quite good.

For example, a simple optimisation can be to limit the maximum number of calls per frame to A*. The rest is delayed to the next frame. That means that calls to A* will be asynchronous, but it is still possible to give a movement to the character during the computation. So the character will try to move in straight line, until the exact path is returned. I don't think it will be noticed until requests take more than a few frames to complete.

Another optimisation might be to use steering behavior for entity movement, instead of trying to compute the exact path for every unit when the user gives the same order to multiple entities : it is possible to compute a single path for the whole group and apply that kind of algorithm : https://gamedevelopment.tutsplus.com/tutorials/understanding-steering-behaviors-path-following--gamedev-8769

Steering behaviour can be used more globally to simplify path finding : no need to compute collisions when computing the path, the steering behaviour allows to follow the path while being repelled by colliding entities.

[Guest]

1 is already done and in game IIRC. There were two seperate people wanting to nuke the vertex pathfinder and do something similiar. Unfortunately, none of them seems to be active anymore.

[jrevel]

There are some ComputePathAsync functions, but the actual threading/limitation of request per frame still seems in todo : 

maybe simply putting the processing of paths in a separate thread might help a lot 

[Stan`]

11 minutes ago, jrevel said:

There are some ComputePathAsync functions, but the actual threading/limitation of request per frame still seems in todo : 

maybe simply putting the processing of paths in a separate thread might help a lot 

Well you could look at D14 and tell us why it segfaults  and then improve it

[jrevel]

What is D14 ?

[Stan`]

33 minutes ago, jrevel said:

What is D14 ?

https://code.wildfiregames.com/D14

[Imarok]

9 hours ago, jrevel said:

Another optimisation might be to use steering behavior for entity movement, instead of trying to compute the exact path for every unit when the user gives the same order to multiple entities : it is possible to compute a single path for the whole group and apply that kind of algorithm :

I think @wraitii uploaded a patch to phabricator that implements pushing. That seems to be an alternative to steering.

[Stan`]

2 hours ago, Imarok said:

I think @wraitii uploaded a patch to phabricator that implements pushing. That seems to be an alternative to steering.

That would be https://code.wildfiregames.com/D1490

[Ceres]

Years later...

@Stan`
@wraitii

As you know, I have no programming skills, but somehow I arrived here and now wonder if the topics in this thread are still open.

Do you guys still think that optimization of the pathfinder (short, long range) is possible? And it's multithreading still a topic?

Finally, would you consider what was written above about steering? Or is the (now available?) pushing its "replacement"?

Sorry about these technical questions from a technical noob that I am.

[Stan`]

Just now, Ceres said:

Do you guys still think that optimization of the pathfinder (short, long range) is possible? And it's multithreading still a topic?

If you have played the last bundled you've tested pathfinder threadings. But yeah there are a few other things we might thread or make use the new threadpool.

I'm not sure we batch paths although maybe when you use formations.

 

 

[Ceres]

Thank you, @Stan`

I have not yet tested the last bundled pre-release a25 but will do so and report back (in the other thread for that purpose).

[tuxayo]

On 08/06/2021 at 10:30 PM, Stan` said:

If you have played the last bundled you've tested pathfinder threadings.

IIUC, using the dev version one should have a multithreaded pathfinder.

I tried an experiment about that. The idea is that, if there is are intensive pathfinding calculations. Then the 0ad process should use more than on thread of CPU usage. That is to say, for a 4 thread CPU we should see a CPU usage > 25% (for the 0ad process)

I pulled atlas, made two groups of 200 cavs earch. Made a lot of house.

I made the two groups run past each other, cross the houses. And most of the time the 0ad process CPU usage is a 23/24% with a peak at 28%

Is this test valid?

If so then it means that all and the path finding is in one thread. Even further that would mean that the rendering is in the same thread.

Edited July 12, 2021 by tuxayo

[Stan`]

3 hours ago, tuxayo said:

 

If so then it means that all and the path finding is in one thread. Even further that would mean that the rendering is in the same thread.

That's incorrect. What that means is pathfinder is no longer a bottle neck after threading. You can check what it's doing per thread by starting the profiler2 https://trac.wildfiregames.com/wiki/Profiler2

The threading will eliminate most of the lag spikes but not all.