Kuba386

As I've already noticed, components use message systems to communicate with each other. Message is handled in that same thread it has been send from. I am trying to make async pathfinding requests being processed in worker thread. The problem is that pathfinder returns path results as messages, and therefore I need to send a message from worker thread and have it handled in main thread(otherwise strange things can happen.) I came up with a solution to create a global array of messages and send them in main loop of the game. I've tried to create a global array of messages and a loop in Frame() function to process them, but there are two problems: 1. If you want to push data to queue located in main thread from worker thread, then you would need to lock main thread. Is it safe? And how to get mutex class of main thread? 2. How to send message from Frame() function? I don't know how to do it from function outside component class (in Frame() function i can't call GetSimState().GetComponentManager() ). I've created class CCmpPathfinderWorker, which is going to handle worker thread for pathfinding. 1. : // imagine this function is executed in worker thread in CCmpPathfinderWorker class void CCmpPathfinder::ProcessShortRequests(const std::vector<AsyncShortPathRequest>& shortRequests) { for (size_t i = 0; i < shortRequests.size(); ++i) { WaypointPath path; ControlGroupMovementObstructionFilter filter(shortRequests[i].avoidMovingUnits, shortRequests[i].group); ComputeShortPath(filter, shortRequests[i].x0, shortRequests[i].z0, shortRequests[i].clearance, shortRequests[i].range, shortRequests[i].goal, shortRequests[i].passClass, path); CMessagePathResult msg(shortRequests[i].ticket, path); m_Parent->GetSimContext().GetComponentManager().PostMessage(shortRequests[i].notify, msg); // <-- here is the problem // m_Parent is a pointer to CCmpPathfinder class instance that is hosting this CCmpPathfinderWorker instance } } 2. : This is what I wanted to do: // somewhere is Frame() function in main.cpp //..... for(std::pair<entity_id_t, CMessage> i : some_global_messages_queue) { SomeMagicFunctionThatWouldMakeItWork().PostMessage(i.first, i.second); } //..... Because "SomeMagicFunctionThatWouldMakeItWork()" sadly doesn't exists this is probably wrong way to do it. So how would be correct? I guess this is not implemented* because no one before needed to send messages from thread to thread (not sure). I could implement it if it isn't. But would be nice if you share some of your knowledge about this problem with me. EDIT: Maybe we should implement this as a component? If it isn't already implemented somehow. I will try do something with it tomorrow. * - I guess there is no implemented way to send messages from worker thread and process it on main thread.

Okay, at this point I see enough problems with GPU utilization on pathfinding. Sorted from most important to less important: - it would be hard to keep both GPU and CPU pathfinders deterministic and the same. - not available for all players. - will use GPU resources that are needed for rendering. - probably not needed very much. Multithreading is more important here. Therefore maybe utilizing GPU can wait. There are more important optimizations that have to be done first. Retries? Are retries what we do in a problematic situation? (I haven't read all of the code yet, today I had no time to do it.) Well.... We should not only reduce number of retries but remove them. That is actually multiplying our time complexity by number of retries.(hmm... you probably are already perfectly aware of this sad fact(no, not probably, sure you are)) Well, seems that multithreading and reducing number of retries to 0 would solve our problems with pathfinding. Not however sure if reducing retries to 0 is possibile or it has to be incredibly hard if we haven't done it yet. Well there is still lot of work for me. Thats both good and bad Yeah, @Imarok working with already made pathes is certainly a good thing to do. And it would be nice to talk to people who already worked with pathfinder. Tomorrow I'll probably have lot of time and I will complete reading the code and maybe start to write something. EDIT: This is a nice visualization of some pathfinding algortihms https://www.youtube.com/watch?v=rZHtHJlJa2w

If we only parallelize processing single request we could do it the same way we do it for unparallelized algorithm. I don't have 100% understanding of current pathfinding code yet, put parallelization of single request seems not to produce any new problems. However if we want to process multiple requests at once then it would be a little bit problematic. Today when I'm back from school I AM going to write a prototype code for GA* pathfinding.

GPUs have much much better floating point performance and precision. And can run thousands of threads in parallel, in opposite to CPU. CPU is however much faster on single thread. That's why using GPU only makes sense when you can have high degree od parallelization. We could also Have OpenCL version(for AMD(and Intel?)). OpenCL and CUDA are generally the same thing however CUDA only works for NVIDIA, and OpenCL is słowem.

Yeah certainly it will. I said that this 'boost' may be not enough. Then only option would be redesigning pathfinding. This is mainly what's wrong with it. I will try to multithread pathfinder, but many better programmers already failed to do so. Therefore I'm not sure how much I can do. There are many other things to multithread. Like NetClient or map generation. I can try multithread them too, but I'm really not sure how much can I do here. EDIT: If I do it all I will become a multithreading specialist EDIT 2: I just realized that what I said here may bet quite not nice. I really understand and respect these huge amount of work people have already put into this game. Only pointing out things that are still left undone.

Running pathfinder in separate thread and applying these GPU optimizations are one of last things we can do without completely redesigning pathfinder. It already has lots od optimizations, looks that there is really nothing else to do. If multithreading and GPU-based parallelization won't give us results, we would have to seriously think about redesigning pathfinder. These are my toughts of pathfinding in 0 A.D. after first day spent on reading code and searching the internet for pathfinding algorithms. Correct me if I understand something wrong.

You mean time constraints? Yeah, copying data to GPU memory takes some time. I'm not yet sure how much would it be for this case. We could use shared memory, but only pascal(10xx) and higher nvidia cards support it Not sure what you mean here... The time taken for copying data to GPU memory and copying result back is a real problem. Using shared memory seems to be only good solution, however it is only supported on nvidia cards with pascal or newer architecture. Not sure about AMD. EDIT: Wait... Hmmm... Maybe time needed to copy data from RAM to GPU memory won't be that much.... END_EDIT Let's say it's possible to implement with CUDA shared memory. Then it would be a ~6x speedup (based on benchmarks in the article), however available only for owners of nvidia cards with at least pascal architecture. This is already not looking as good as it is in my first post here... They calculate expanded states independently, only states that have the same 'parent'. Not all of states. Main purpose of this is to parallelize heuristic function, however parallelization of heuristic function is not actually needed for pathfinding purposes. GA* algorithm parallelizes open list and heuristic function calls. In some usages of A* heuristic functions are a bottleneck, and then GA* algorithm provides great speedup (~x30). However in pathfinding usages of A* heuristic functions are very simple and doesn't really need to be parallelized. That's why GA* algorithm only provides ~x6 speedup for pathfinding purposes. I'm already there, but recently has been very inactive there(like I forgot ). Thank you for reminding me, I will take part in next round Maybe running pathfinder in separate thread(s) would be a nice idea? I'm not sure, but I think I could do it. (This would however take me a while)

Oh, probably mostly some time. Code is quite well-organized and I'm quickly getting into it. I'm probably too young to be considered a real programmer(15 years old), but I'm learning fast and already have some C++ experience (programming since 11 years old). Probably many of you have programming experience much greater than 4 years but it's better than nothing. My main area of interest is computer science (training hard to get some nice title in Polish Olympiad in Informatics), and that's why I'm mostly interested in things like pathfinder optimizations. My amount of free time isn't very big, but maybe I could still help the project a bit. I will also have good chance to learn something.

I recently got interested in helping with 0 A.D. development, especially optimization. I was thinking how could we accelerate pathfinding and in consequence reduce lag. It already seems quite optimized, A* with JPS optimization. One of things that are still possible to do is to apply parallelism to pathfinding. Toady I've found this: https://www.aaai.org/ocs/index.php/AAAI/AAAI15/paper/download/9620/9366 By using method shown in the article we could not only run many pathfinding requests in parallel, but parallelize a single pathfinding request in a GPU-friendly way. We could use CUDA or OpenCL to implement it. Authors of the article have achieved 30x(EDIT: actually it's only x6 speedup. See my third post.) speedup of A* algorithm, which is quite considerable, however I am not sure how much would it speedup 0 A.D. pathfinding. I am not familiar with 0 A.D. code enough to start working on it, or even assess how much could it actually speedup 0 A.D. pathfinging. I have found few posts from 2012 about running multiple pathfinding queries in parallel(not parallelising single request), saying that this wouldn't be really useful for players without strong GPUs or multicore processors. https://wildfiregames.com/forum/index.php?/topic/16018-supreme-commander-2-pathfinding/&amp;tab=comments#comment-239673 Well, today we have 2018(2019 soon), and even things as basic as desktop environments have multi core CPUs in their requirements, and most 3D RTS games have dedicated GPUs in their requirements. Sure it would be much more useful for player with NVIDIA GTX 1080 than for player with intel i3 integrated GPU, however I think that speedup for most of players could still be considerable. Maybe it will turn out too hard to implement, not as efficient as I assume here, not good for every player, etc... But maybe it will turn out that it really speeds up pathfinding , at least for players with dedicated GPUs.

I sign up (if rank 1155 isn't too bad) UTC +2 (central/western Europe)