Print

Please login or register.
1 Hour 1 Day 1 Week 1 Month Forever
Login with username, password and session length

[Sean Mirrsen]

I think it's safe to say none of us know the intrinsics of those processes fully. Well, none of us who are present in the discussion, at least.

I still think it'll only really work if done in hardware. Doing it in software would require disassembling the executable in question, and running it through an emulator that would artificially increase its ILP.

[zagibu]

If it were this easy, it would have been done a long time ago. It's not only about calculations, it's also about data. How do you share data between multiple cores in a program, that isn't designed this way? Also, what happens if one of the cores manipulates data, while the other core is still working with an old "copy"? The second core will simply overwrite the result of the first one. To repeat what others have said: you can't simply break up any chain of instructions in smaller bits and run them in parallel. You can break up some, true, but they are so rare in a program designed for single core, that the management overhead quickly eats up all the advantages.

[NSQuote]

Prehaps path-finding could get it's own core?

It'd definitely help the framerate, at least.

[Wyrm]

If DF is object-oriented as claimed, then each object can manage its own data, including how it handles one core changing a piece of data another core is still working on. It might actually manage the change by storing a delta, which is then integrated into the base data after it can reasonably be assured that everyone's done with it. Or it might use a semaphore, or some other mechanism. All the thread that wants to use the object needs to know is that what it might be trying to change is too busy to effect it, so that it may preemt that particular change until later.

There are tools and techniques that may be used, and if the program really is OO, half the work is already done.

[Draco18s]

Cellular Automata.

"The Map" is its own object that manages its own data.  Such as water.  Good luck making water work (and pathing!) without some object accessing data which isn't its.

[Quietust]

Prehaps path-finding could get it's own core?

One potential method (which has probably been suggested plenty of times in the past, but I'll say it anyways) would be to allow a short delay between a unit requesting a path and it actually needing to act on it. When a unit decides to perform a task that requires movement, several frames must elapse (depending on how quickly the unit walks) before the path is actually required (i.e. which way the unit will start walking), and that short delay could be used to make the pathing request asynchronous - if the path isn't ready by the time the unit is ready to start moving, then it can do the path calculation in the main thread like it does today (and cancel any existing asynchronous request, since it'd probably be faster than waiting for the request to complete). The main problem with this method, of course, is terrain changes during that brief delay.

[Andeerz]

I really wish I knew more about how this game is programmed and how exactly processors work... But from what I do know from my meager experience in C++, what you are saying, Quietust, seems like thinking in the right direction... but I'm not sure I follow entirely.

I don't exactly see how this would help.  Then again, I am not at all familiar with how pathing and processors work other than a very superficial, possibly erroneous, understanding.

Am I correct in assuming that the processor can only calculate a single thing at a time?  And that two cores means that two things can be calculated at the same time?

Assuming that's correct, then am I correct to assume that pathing works as follows?  When a path is requested, the game takes into account the positional state of everything at a given instant.  It then calculates the path, and there you go.  As the dwarf travels along the path it periodically requests the path again to make sure that it is still viable.

If all of that is true, then why is it hard to relegate every pathing request as it happens to another core?  What dependencies are there that prevent it from being done asynchronously without it screwing up something down the line of calculations that might depend on it?

[G-Flex]

hat the processor can only calculate a single thing at a time?  And that two cores means that two things can be calculated at the same time?

Sorta. The basic point is that if you have more cores, you can process more things at the same time, but only if those things are capable of being processed in parallel and the program/OS/hardware knows to do so. Obviously, you can't just arbitrarily split up a list of instructions and have things perform them out of order.

[Andeerz]

Ok!  Thanks.

But what makes path finding something that is hard to do in parallel with other processes?  Is it only because there are often other processes that are dependent on the position of the thing moving?  If so, what are these processes?  I can think of some processes where this might be the case, like the pathfinding needed to follow other moving things.  Am I thinking about this right?   

[Draco18s]

But what makes path finding something that is hard to do in parallel with other processes?

Changes in map state.  Doors, water, magma, constructions all change the walkable space.

[LoSboccacc]

But what makes path finding something that is hard to do in parallel with other processes?

that it has not be written to work in parallel with other processes.
threading it's the kind of thing that is very hard to add if you don't think about it upfront.

not that it's an impossible feat. only that late threading addition comes with all sort of unintended side effects.

and path finding is one of the most natural thing to thread, as it's already an asynchronous process, even if done in the same thread (a path request may take more than one game frame to complete - when dwarves have that question mark over them)

but when you take it from being asynchronous to being a full fledged separate thread, handling all the locking to simulate the previous behavior to avoid bugs and weird stuff is very hard to do. and if you don't do that but just rewrite it as a proper dispatched request, avoiding bugs is still very hard, because the locks that allow to handle terrain updates (water, doors, bridges, digging) when removed may broke the path finding in very subtle and disastrous ways.

[Andeerz]

Ah.  I see.  Thanks guys.  Well, would it be correct to say that perhaps path-finding, as it is assumed to be already asynchronous, would be the easiest (least-hard would probably be a better word) thing to multi-thread? 

I can see what you guys say about the difficulties of multi-threading path finding, but I think we are all just speculating here since we have no specific knowledge of the code of the game.  I would love to know exactly how changes in the walkable space make this difficult, if indeed this is the most important factor (which I don't doubt).  Basically, I would like to know how the path-finding normally updates the path taken when path changes happen.

[Soralin]

But what makes path finding something that is hard to do in parallel with other processes?

Changes in map state.  Doors, water, magma, constructions all change the walkable space.

Which really isn't a problem, because changes that happen while you're calculating a path are dwarfed by the much larger and more often occurrence, of changes that happen after you're done calculating your path.  The former only has a handful of frames in which it can happen, the latter has hundreds or even thousands of frames in which it can happen, while the dwarf is walking to their destination.  Fortunately, the latter is already covered, if a dwarf runs into an obstacle that wasn't there before, they simply find a new path.  And if a new shorter path opens up, they simply ignore it for the rest of the trip, until they look for a new path.  Which means the former is covered as well.

There would be instances where it would take part of the map on one frame, and part of it on another, but even without any extra measures to deal with that, there aren't many situations where it would produce a different path than just looking for a path a few frames earlier or later.  And the few instances where it does, wouldn't result in much of a change in behavior anyway, just very rarely taking, or not taking, a path they otherwise wouldn't, or would have, where rapidly changing terrain is in place.  Say for example, where you have one drawbridge opening, while another is closing at the same time, they might see both as being open, and try to path through that area.  But, even if they did that, they would notice it and find a new path as soon as they ran into something which wasn't there when they were thinking about it, just the same as if there was one drawbridge, and it closed after they were done making a path that crossed over it.  Just as they do in any other situation where they take a path that changes while they're taking it.  I'd say it's too small a difference to worry about much.  Although you might want to make sure that it doesn't read out any individual tile which is halfway through being written.

[Gamli]

I found parallel programming very easy.  I wrote a multi-processor 2D fractional Brownian motion algorithm using OpenMP + C++.

Then again I like to do template meta-programming in my sleep so my definition of easy might be unhelpful.  Also I bought Visual Studio Professional in order to do that, which costs over $1,000.

But I assume Dwarf Fortress would benefit the most from distributing fluid dynamics and path-finding in parallel.  Actually distributing boozing-up in parallel too as those lazy hairballs never seem to do anything else anyway.

if ( ! this->findPathTo (_worksite) )
    this->boozeUp();

[LoSboccacc]

I found parallel programming very easy.  I wrote a multi-processor 2D fractional Brownian motion algorithm using OpenMP + C++.

Then again I like to do template meta-programming in my sleep so my definition of easy might be unhelpful.  Also I bought Visual Studio Professional in order to do that, which costs over $1,000.

But I assume Dwarf Fortress would benefit the most from distributing fluid dynamics and path-finding in parallel.  Actually distributing boozing-up in parallel too as those lazy hairballs never seem to do anything else anyway.

if ( ! this->findPathTo (_worksite) )
    this->boozeUp();

well, duh. nobody says it's hard when you build a program ground up to be multithreaded. it's the conversion the problem.