Print

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

[tuxu]

Hi there.
     
     I was trying a new version of a game called FreeOrion of  which I'm also a fan.
     The game consists of rivaling space empires, elaborate research tree to  each of these and a relatively huge map of the universe to play on.
     The developers took a design decision that made me a very happy man;   They game itself runs as a *master* process called freeorion.exe and  afaik it acts like a manager that binds the whole thing together. Each  empire in the game take its turn after you click "end turn". in games  like "Space Empires" (which is also great) end turn waiting is a long  one, each empire takes its time to do it's will and the player is left  to hang dry...
    In FreeOrion, on the contrary, the end turn is relatively short because  of the way the game handels computations and memory management; The  freeorion.exe process spawns number of other processes that are each  called freeorionca.exe. The number of processes correlates to the  numbers of player entities in the game(CPU and Human), which means that  dual-core, core2duo and core2quad users can tap into the potential of  their computers and see the game in all its glory.
   
   Under the assumption that DF is indeed a glorious app\game, I had hoped  to see our benevolent developers in bay12games(“Flattery    is all right so long as you don't inhale”-  Adlai E. Stevenson )  take the  same decision and breaking the game to more chew-able bits for  multi-cored users.
     
     To be specific, thing about all the thing that has to be executed so a  world will be generated, maybe these bits could be splitted? maybe the  map itself would be divided(computation-wise) into 16  sections(DFmapper.exe)? think about the things that are happening in the  actual game, how many level cartographies can a map hold, maybe the  performance will improve if each level would get a process(DFLevel.exe)?  Where are all the creatures on the map and what are they  doing(DFentities)? What would  have happened if each of these processes will report back to a master  process(dwarfort.exe)?
 
  I strongly believe that these client processes working under the master  process and info being transferred between them would greatly improve  the game for all the people that are not using a good'ol' single core  CPU.
 
  Thank you for taking the time to read,
   -Tuxu.
     
     
     

[Lord Shonus]

This is a feature that has to be in a game from the beginning. It cannot be added without recoding the entire game.

[Asteranx]

This is a feature that has to be in a game from the beginning. It cannot be added without recoding the entire game.

Not technically true.  Though it would undoubtedly require significant effort to make the _whole_ of DF multi-core aware, I'm sure certain time consuming systems/processes (Fluid Dynamics, Pathfinding, certain AI tasks) could be broken off into separate threads with relative ease.

A system like FreeOrion's works because the game is turn based, and the child apps likely use the main game's network interface to take their turns via the same mechanism a remote player would.  Such a system wouldn't work very well in a real-time app like DF.

[LeegleechN]

There is at lot of potential in parallelizing computations like pathfinding using threads. A process based model will not work. In a large fortress, the pathfinding is enough to take up several cores on its own, especially when proper z-level pathfinding is added (taking travel time between z-levels into account). If and when it happens, most likely the pathfinding task will be split off into a set of threads, and everything else would run in the main thread.

[Elvensoul]

There is at lot of potential in parallelizing computations like pathfinding using threads. A process based model will not work.

Wrong. You obviously have no clue about multi-processing. Using different processes like in free orion is as possible as multi-threading is. When you apply multi-processing you need to synchronize the processes either via sockets, file or RAM and that can be done as real-time as you are able to implement it. (usually multi-threading spawns threads from a single process over different cpus while multi-processing uses different processes that have to communicate to each other)
True is that its a lot of hassle to convert DF to a multi-threading/processing design, but it should be possible to "outsource" at least a few parts. (I guess Toady will use different cores for gfx... somewhere in the future)

[tuxu]

A system like FreeOrion's works because the game is turn based, and the child apps likely use the main game's network interface to take their turns via the same mechanism a remote player would.  Such a system wouldn't work very well in a real-time app like DF.

Use this to set the maximum frame rate during play.  The movies are always capped at 100.  A frame in this case is not graphical but related to the movement speed of a creature.  A healthy, unencumbered dwarven peasant takes one step every 10 frames.

[FPS_CAP:100]

that means DF is turn based.

[sweitx]

A system like FreeOrion's works because the game is turn based, and the child apps likely use the main game's network interface to take their turns via the same mechanism a remote player would.  Such a system wouldn't work very well in a real-time app like DF.

Use this to set the maximum frame rate during play.  The movies are always capped at 100.  A frame in this case is not graphical but related to the movement speed of a creature.  A healthy, unencumbered dwarven peasant takes one step every 10 frames.

[FPS_CAP:100]

that means DF is turn based.

Actually still wouldn't work.  In the example of free orion, each entity makes their own decision based on a static world state regardless of the decision the other entity make, and all entity makes a decision once per turn.

In Dwarf Fortress, the major processor hogs are path finding (whether dwarf, creatues, and liquid). 

The first  difficulty with parallelizing dwarf path finding is that dwarves, as far as I understand them, only path-find when needed.  In most "turns", a dwarf simply follow the path it already found, and rarely is the case the more then one dwarf needs to find a path in the same turn. 

Second, thread spawning is an expensive operation with overhead.  In freeorion you'll have about a few dozen thread, in dwarf fortress, the dwarves along will have 100+ threads (depending on population size + animals/creatures).  If you do not terminate thread and simply let them spin/sleep, you incur a processor penalty.  If you only spawn thread as needed, you still incur a processor penalty for no gain as most "turns" only require 1 path-finding.

Third, the way fluid dynamics are handled in Dwarf Fotress, as Toady One explained, is similar to a full tile of fluid attempting to "path-find" its way from its spawn point to a valid destination.  This pathfinding will depend on other spawned fluids as two units of fluid may try to path to the same destination, and therefore requiring one thread to repath, effectively remove the advantage of parallelism.  Parallelism may actually work if Toady One used cellular automaton to model fluid, but now you'll need to process every single fluid tile on the map, so unless you have a really large number of processor cores, there won't be much improvement in speed.

In short, Dwarf Fortress is effectively real time (when you have 100 "turns" per second, you effectively have a real time game), where the amount of processing needed per turn is relative small (parallelism in general require that you need to do a large amount of work, at the same time).  In Free Orion, each "turn" last a few minutes, and with each entity requiring a lot of work done at the same time, without minimal knowledge of what other entity is doing (perfect for parallelism).

[tuxu]

Pathfinding, fluids or not can be resolved in the way it does now and still use my idea.
Thats why I mentioned a supervising process that would act as an oversight function for the various game mechanics processes and among other things - its job would be to prevent redundancies.

For an example, lets say that we have a spring at the north-eastern side of the map and it should yield a river that would flow to the south-Western side of the map in a diagonal line(give or take). Had we used the xcore idea we would have a pathfind_a.exe that would give a "whole map general directions", the path finding here would not be as acurate since its underlings would inheret the general path data and polish the path.
Pathfind_b.exe would be spawned 4 times now by pathfind_a.exe and these new processes would take care of every pathfinding in their domains(each pathfind_b.exe process gets quarter of the map).
After calulating the paths they would submit the info back to pathfind_a.exe for revision. if everithing works and all the paths makes sense and are combining then info=output, else, pathfind_a.exe will redefine new "path specific general directions" and send it back to pathfind_b.exe for calculation and number crunching, when pathfind_b.exe is done it will re-send the data to pathfind_a.exe and if the process repeats itself more times than it will be logged as an error, be debugged, and yada yada yada...

As to the claim that DF is real time; it doesn't matter what illusion the player may be held under, it is still turn based through and through(which is not necessarily a bad thing).

[Garthor]

Your suggestion would not work and is literally identical to a single-threaded process, except with a whole bunch of overhead.

You do not seem to know much of anything about multithreaded programming, or programming in general, so I suggest you just drop this.  It would be a colossal amount of work for absolutely minimal gain.  Only in situations where multiple processes need to be done at the same time and have absolutely minimal interdependencies is multithreading reasonably helpful.

Also, your definition of "turn-based" is pretty terrible, as every game in the history of ever has had a simulation framerate, so according to you there has never been a real-time game ever.

[immibis]

Why on earth would you spawn multiple processes when you have multithreading, anyway?

[Olreich]

Spawning a thread would actually be quite useful for DF pathfinding. Spawning a process might not be, but when the game needs to pathfind, it could spin off a new thread to handle that, and have the thread report back when it's done with an event (window message, or a more awesome form of event handling). This would allow Dwarves to sit there and "think" about where to go, rather than slowing down the entire game. An example includes a map where my fortress was about 400 tiles away from trees. I build an almost direct path to them, but every time my woodcutter would path-find to a tree or back to the stockpile, my game would stop for half a second, translating to about 70 frames worth of calculation for that single path. Of course, it was a length 400 path, but it was still just a single dwarf's path. It took me forever to figure it out, and I eventually fixed it by making a cascading stockpile system, (place wood stockpiles that take from each other back to the fortress) and that almost fixed the problem, but then I had 5 dwarves that did nothing but haul wood through 8 stockpiles to get it close enough so my carpenter didn't pause my game to think. It would have been much better to have my woodcutter be "dumb" and sit there while his pathfinding thread is taken care of in the background and my dwarves run happily around the fort around him. There would be a same 70 frame delay, but I wouldn't notice it anymore. Thus, multiple-threads = awesome.

Anyways, this parrellization could account for a good 50% of the processor load or more for a large fortress (sure one dwarf needing a new length 40 path every few seconds isn't bad, but get 300 of them all needing that every few seconds and suddenly, your fps is 7). In the pathfinding project that fizzled awhile ago, this was suggested and accepted as a good method to fix the problem of pathfinding.

I'm not sure how easily it would be to implement, or how much overhead would be created by having 100-200 pathing attempts open at a time, but if it improves pathing by even 10%, it's a huge boon to anyone with a multi-core processor. The i7 crowd would finally have something to do with their 8 hardware threads.