I do not think this would be optimal use of programmer time, to say at least. Most efficient and safe use would be main thread waiting for completing all pathfinding threads.
A valid argument and very possibly correct. I was only arguing that it was possible and a
potential source of optimization. It's certainly got its pros and cons and the cons of potential loss of determinism, the load of ensuring non-volatile data, and most importantly increased programming effort may swamp any pros.
And you claim this will be more effective and less problematic than just doing The Right Thing?
Sorry, you're going to have to define "The Right Thing" for me here, I wasn't aware that there was a single correct choice for complex problems such as this.
"Queue populated with any changes from the main thread" sounds like waste of CPU cycles and memory space (what is average DF map nowadays, tens of megabytes?) in itself. Your pathfinding threads must be synchronized with your mysterious "set of pathing data that is updated on pathfinding thread" anyway - or you will have same problems as with taking data directly from main thread.
There is indeed overhead involved and that overhead may be greater than the gains realized. But I'm not talking about duplicating the entire world state to pathfinding. Merely a small subset or derivation of it that contains only the pathing costs. And then updating (nothing mysterious) that cost set via differentials whenever there are world changes such as constructions, mining, door locking, etc that may affect pathing. Burrows, traffic designations, door ownership, and such may increase the size of that data set (or it may be possible to encode those flags into the upper bits of an int32 if max cost is a byte for example).
And remember I never said it's the best or most efficient method, only that it's *a* method that will technically work. There are likely superior choices if one looks hard enough.
However, data in main thread can and will change unpredictably from point of view of pathfinding thread. Armok forbid it will change during pathfinding nearby this particular tile that changed (simplest example). I have only very general concept about A*, but I imagine it will lead to Bad Things (especially with arcane optimisations). Other example, rather extreme: if memory will get reallocated for whatever reason, you are screwed completely. Crash time!
No, no it will not. That's the whole point of doing all of that complicated junk. You can argue that the method I've described is too inefficient, difficult to program, or without some additional changes causes a loss in determinism but you cannot reasonably say that it does not work or will cause a crash due to data volatility.
You have no whasoever basis to saying that. Data that can be obsolete at all - can and will be arbitraily obsolete (many, many ticks ago).
Sure I do, I can in fact simply say it by fiat by blocking the main thread if more than X frames have passed until requested paths are done. And can maintain determinism by
always waiting X frames before using calced paths even if they're ready sooner. There is still a net gain in speed even when blocking the main thread like this.
I currently play fort with 15 FPS (yes, I am masohist, why you ask?). I hate to think how old pathfinding would be here.
Ironically under those circumstances (assuming you have a multicore machine) the pathfinding would likely complete even before the current frame is finished. A situation far more likely to occur when as you describe the single core the main thread is running on is swamped and other cores are almost freely available. And if setup properly where paths are requested near the beginning of the loop and utilized near the end then you'd actually use your asynchronous paths on the same frame they were requested.
Anyway, I really do not like concept where some things that happens in one ticks seeps into next ticks. This fact in itself can create big problems, unrelated to threading or pathfinding.
A reasonable position. I find myself going either way. If the game is currently 100% deterministic then yeah I'd say we need to preserve that (which we can still do with synchronous or even asynchronous pathfinding threads as detailed above). But if it's already not deterministic (and most games aren't, even when you think they are) then meh whatever works fastest and still produces reasonable results. Dwarves can be stupid enough now that I'm not sure anyone would actually notice if there were actually any problems.
That situation is identical to a synchronous pathfinding call whose results are invalidated 1 frame later.
No, it is not. All things that happens in one tick are contained and predictable. If you start to doing things over two or more ticks, you open very, very big can of worms, or rather extremely nasty and esoteric bugs.
Agreed, it is not 100% the same. It does cause determinism problems. But for most intents and purposes and specifically for the comment I was responding to which involved dwarves walking into walls that weren't there when their path was calculated then it is exactly the same thing.
It is just not worth it.
That may very well be true. I've no way of knowing without the source and even then it would probably be a judgment call.
Author
Topic: Will we ever get to a point where forts don't die FPS deaths? (Read 65568 times)