Print

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

[Sizik]

I think world gen continuing while playing the game would be a good place for Toady to try out multithreading, once he gets to working on that.

[No1]

Well like I and Telgin said the threads needs to be able to run without interfering with each other and because the most computationally heavy that DF does is probably path finding then that would probably benefit the most. The way that path finding is done with A* gives it pretty "simple" way of multithreading. Lets say we have 4 cores and want to utilize all of them, because pathfinding is done by "walking" to a tile and see if the entity can get to the next tile etc then the four first tiles that is tried could run on their own core this and that the fact that pathfinding is not changing anything in the world. Of course we need some way to keep track of visited tiles but having one structure that is thread safe is better then requiring to make every one safe.

[Kogut]

Not for a long time yet, as I assume Toady will eventually multithread parts of the game.  Eventually.

"It's complicated, and from what I gather it would be a really difficult long project and it's probably not going to happen."

This is a statement from Toady himself?

While I don't for a second deny the claim that it's a long and difficult project, I think Toady understands that it's probably an unavoidable necessity and will probably get around to it eventually, in some form.  The game's processor demands are probably going to scale faster than single threaded processor speed.  Actually, can anyone comment on how much slower the current version runs than 40d?  Any slower?

I know there are a thousand intricacies I can't appreciate without looking at the code, but the update step has to be parallelizable in some fashion.  Whether it's worth spending time instead of adding features, well, that's Toady's call.  Then there's the whole issue of whether or not to do it now and save difficulty later, or put it off...

From one of the DF talks (9?). And I think that there is posssibility for huge improvements without multithreading ("bug #3942 - Dwarves owning broken clothing. Clothes don't rot, ANNIHILATES FPS." etc etc etc). And based on random, unverified anecdotal evidence - recent versions of DF are faster than 40.

PS: nickname of  author + title of thread + thread = 

[Olith McHuman]

I've played dwarf fortress over a remote desktop connection on a local wireless network (from my laptop to my desktop), and even then the input lag can be annoying. The display is jumpy when I scroll around quickly too, my router can't seem to handle all the data. This is with a good quality wireless n dual band router (basically, it gives you 2 networks on 2 different frequencies), so the devices don't even have to share air time (as I understand it). Remote desktop from a computer outside my house? Unplayable. In game scrolling menus in particular are hard to use - the lag messes up your timing.

[Telgin]

Probably more of a limitation of Remote Desktop than anything else.  It wasn't really designed with gaming in mind, so the fact that DF is playable at all is pretty impressive in my opinion.

Well like I and Telgin said the threads needs to be able to run without interfering with each other and because the most computationally heavy that DF does is probably path finding then that would probably benefit the most. The way that path finding is done with A* gives it pretty "simple" way of multithreading. Lets say we have 4 cores and want to utilize all of them, because pathfinding is done by "walking" to a tile and see if the entity can get to the next tile etc then the four first tiles that is tried could run on their own core this and that the fact that pathfinding is not changing anything in the world. Of course we need some way to keep track of visited tiles but having one structure that is thread safe is better then requiring to make every one safe.

Pathfinding does seem like a natural choice for parallelizing the code, but I wonder if he's profiled it yet in any significant fashion to try and figure out which parts of the code are the computational kernels.  I suspect pathfinding is one of the bigger ones though.

Of course, while I firmly believe that multithreading either the pathfinding phase or the entire update step is doable, it's still going to be pretty tricky.  Pathfinding in simple cases can sort of ignore race conditions since it only needs to read data and doesn't write, but there's the complication of what happens when you do write the updated positions.  In DF, for example, if multiple creatures are on a tile, only one is standing.  So you've still got to go through and atomically move the entities to enforce that rule.  This would still be faster, of course.  Dividing the actual pathfinding up into a number of threads in a thread pool should provide some speedup, although a linear one in the size of the pathfinding step is quite unlikely.

I suspect that this is the heart of why Toady has been putting it off.  The complications and intricacies of a thousand small things like that.

[No1]

I think there are "easier" and possible better optimizations, in an older thread I posted in there was a discussion about a heuristics for path finding. Simple speaking it would make large areas in the world to "rooms" and just save their exists. Basically when you path through your fortress it would just check if each rooms has the goal tile, if it does not it would move to the next adjacent room and if it contains the tile it would search from the entrance to that tile.

The generation of those "rooms" looked quite complex if it would be done dynamical but I imagine that it could be done manual, the player uses some designations similar to traffic zones to designate rooms that the path finder will consider as a single node.

[Telgin]

I strongly suspect that Toady has the pathfinding quite optimized by this point.  In particular I suspect Toady probably does something similar to this already.  There are probably a couple of levels of pathfinding granularity that help to cull some of the work by discarding large chunks of pointless tiles.  Or something that achieves similar results.

At the very least, he is probably caching successful paths so that when multiple creatures need to navigate between similar areas they can reuse some of the work.  Although that sounds like an interesting academic problem... how would you reuse partial results of pathfinding?

Anyway, the room designation for pathfinding purposes might help some, but it would only benefit dwarves and I suppose domesticated animals (which admittedly is most of the pathfinding).  Wouldn't want players to be able to designate arbitrary rooms outside for siegers to use.

[No1]

What I know is that Toady uses a A* implementation, it is a pretty simple implementation that yields a huge performance increase. Basically it searches in the general direction towards the target tile. Unless the entity needs to move away from its goal to get around something it is a good heuristics.

At the very least, he is probably caching successful paths so that when multiple creatures need to navigate between similar areas they can reuse some of the work.  Although that sounds like an interesting academic problem... how would you reuse partial results of pathfinding?

Unless we get a definitive response on that I'm going to assume no. What I mentioned was basically a reusing of paths, lets say you have three areas(A,B and C) and to get from A to C you need to pass B. In this case if you know the best path through B (granted that B does not have more then a few exits) you would only require a path from inside A to the entrance to B, a path from the exit of B to the goal in C as the path inside B is already known.

Yes to prevent abuse the non friendly (animals and enemies) could ignore the designations and there are often more friendly creatures so it should improve performance.

[malvado]

Well, what could probably benefit directly from multiple cores would be :

*Pathfinding : Either a dedicated core or shared. (probably would make sense to share pathfinding with Combat)
*Temperature : This is a pretty big hit on fps and probably would help to allow it to have its own core.
*Rotting and decay on clothing , corpses , blood , water , weapons and so on. Own dedicated core?

As for the topic, I really doubt that cloud computing will be able to give this game the horsepower it needs.

[thepodger]

Really, I think DF is a testament to how a well written and optimized program can perform amazingly well despite its tremendous complexity.  Just think about all of the stuff the game has to keep track of and marvel at how it could ever achieve >100FPS.  I know I do.

But optimization can only get you so far.

Actually, DF is pretty much a textbook example of a very low complexity program that is obscenely inefficient and CPU hungry.  This isn't an attack on the game or Toady, its something he's been pretty open and humble about.  He's a mathematician by trade, not a programmer.

-edit-
Quoted wrong post.

[Telgin]

That sort of multithreading helps, but ultimately runs into the same sort of issues as running on a single core: it's not scalable.  Dividing the program this way doesn't allow you to just throw more cores at it and make it go faster, whereas finding some way of parallelizing on a per tile, per creature or similar basis lets you just throw more cores at it and the entire update process goes faster.

Of course, doing it on a per task basis like that is easier, and might be a way to temporarily speed the game up until a true solution is found.

[Caldfir]

From many, many, many threads and people who have actually done the research, the pathfinding could be very substantially sped up by a room-division type algorithm.  This improvement would probably lead to much better direct speedup of the game than multithreading (though you could multithread as well at some point), and be far simpler to implement. 

The real question isn't if but when Toady will decide to update pathfinding, because really people on these forums have collected the data on the algorithms that should be more efficient already.  I recall the Toad mentioning at some point that a vague mid-future goal is to improve the pathfinding/AI of flyers and swimmers as well, so pathfinding would be a likely optimization at that point.  To me it seems like a pretty major thing, but then again there are lots of major things DF needs done, each with an argument about why they are most important. 

Anywho, we are so incredibly offtopic here.  I recommend someone start up a pathfinding discussion thread (or resurrect one of the old ones) if this discussion is to continue. 

[YetAnotherStupidDorf]

AFAIK Toady already did some advanced optimisations (that sounded exactly like sort of optimisation that you talk about) of pathfinding code. We know, because there was nasty bug with it in early 0.31.x. Results weren't pretty.

[Kogut]

AFAIK Toady already did some advanced optimisations (that sounded exactly like sort of optimisation that you talk about) of pathfinding code. We know, because there was nasty bug with it in early 0.31.x. Results weren't pretty.

I am quite interested in details of this bug, maybe you know id of this problem on bugtracker?

[Telgin]

I recall the Toad mentioning at some point that a vague mid-future goal is to improve the pathfinding/AI of flyers and swimmers as well, so pathfinding would be a likely optimization at that point.

I hope he does fix this sooner than later.  The flier pathing causes enough problems with the pony mod, and I'm sure it afflicts many others.  Had several ponies starve on top of walls...

Anyway, we are getting a bit off topic with the path finding discussion, but it's DF performance related so I don't think it's a big deal.  I'm curious to know just what proportion of DF's time is actually spent doing path finding.  Without knowing more about DF's code or any profiling attempts that Toady has done, we don't know for sure that path finding speedups would dramatically improve frame rates.  Probably, but maybe not.

And while using a room-based pathing system would probably help a good bit for indoor path finding, finding a way to do this automatically for the user would probably be tricky, and I'd hate to have to manually specify that sort of thing for every room in my fort.  And it wouldn't really help for above ground or cavern pathing.

Of course, most pathing for most people is probably done by dwarves indoors, but I do wonder what the overall pathing ratios to indoors vs outdoors is.  There's animals and such to consider, even when not worrying with invaders.