Jump to content
Kuba386

Parallel GPU-based A* algorithm in pathfinding

Recommended Posts

On 12/21/2018 at 6:01 PM, aeonios said:

networking, at least on multiplayer.

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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites

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).

  • Like 2

Share this post


Link to post
Share on other sites
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 by odalman
  • Like 1

Share this post


Link to post
Share on other sites
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...

Share this post


Link to post
Share on other sites

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 by Aeros
  • Like 3

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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).

  • Like 3

Share this post


Link to post
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.


×
×
  • Create New...