Bay 12 Games Forum

Please login or register.

Login with username, password and session length
Advanced search  
Pages: 1 ... 6 7 [8] 9

Author Topic: The threaded pathfinding thread with the previously unhelpful title.  (Read 16106 times)

Felblood

  • Bay Watcher
  • No, you don't.
    • View Profile
Re: The threaded pathfinding thread with the previously unhelpful title.
« Reply #105 on: January 26, 2009, 01:43:12 am »

My dwarvesgoblins don't divert until they actually reach it and find "Huh, this door is locked now."

Hmm. I'll have to re-check my observations. I was more concerned with the re-calculation upon sliding under, so I was overly hasty with that part of the experiment; It's quite likely I am relaying false information.
Logged
The path through the wilderness is rarely direct. Reaching the destination is useless,
if you don't learn the lessons of the dessert.
--but you do have to keep walking.

MuonDecay

  • Bay Watcher
  • Say hello to my little μ
    • View Profile
Re: The threaded pathfinding thread with the previously unhelpful title.
« Reply #106 on: January 26, 2009, 07:31:00 am »

So... we haven't heard from Optimizt in a while, now... hopefully nothing major has come up in the way of frustrations  :o
Logged

Tormy

  • Bay Watcher
  • I shall not pass?
    • View Profile
Re: The threaded pathfinding thread with the previously unhelpful title.
« Reply #107 on: January 26, 2009, 10:31:09 am »

So... we haven't heard from Optimizt in a while, now... hopefully nothing major has come up in the way of frustrations  :o

Well, perhaps once v1.0 is completed, Toady will consider these options, but I am not sure about that, since the engine itself would have to be rewritten partially.
Logged

Gertack

  • Bay Watcher
    • View Profile
Re: The threaded pathfinding thread with the previously unhelpful title.
« Reply #108 on: January 27, 2009, 07:35:29 pm »

Armchair pathfinding:

http://www.dgp.toronto.edu/people/JamesStewart/270/9798s/Laffra/DijkstraApplet.html
http://www.catonmat.net/blog/mit-introduction-to-algorithms-part-twelve/

Incidentally, the book in the second link is quite good (I have it).

Ok, not strictly threading, but most recent pathfinding talk.

Although I'm not convinced my 0-FPS 5x5 fort is due to pathfinding, since I abandoned it and the 14 reclaim dwarves sitting around in military mode with no other obvious creatures still only had around 20-FPS. Or if it is pathfnding it is because the game is having a lot of missed/impossible pathfinding failures while scanning.  But then these are only guesses since I can't profile it.
Logged

Morberis

  • Bay Watcher
    • View Profile
Re: The threaded pathfinding thread with the previously unhelpful title.
« Reply #109 on: January 28, 2009, 05:06:15 am »

So... we haven't heard from Optimizt in a while, now... hopefully nothing major has come up in the way of frustrations  :o

Well, perhaps once v1.0 is completed, Toady will consider these options, but I am not sure about that, since the engine itself would have to be rewritten partially.


It's going to have to be done far before 1.0, partly because by the time 1.0 comes out even the worst computers are likely to have 4 cores and be the equivalent of DOS machines now.

But in a more serious note, yes it does need to be done and done soon. The longer he waits the more stuff gets piled on and the more stuff that needs to get revised which of course means more work. If he gets it done relatively soonish we'll all experience a massive speed boost, well those of us with computers after 2000 anyway and it'll be less work in the long run for him.

The future is multi-core and with the number of features increasingly bogging down the game the only way to get DF to run well is to optimize it. And besides, who doesn't want to embark to 10x10 areas and still get 100fps?
Logged

Tormy

  • Bay Watcher
  • I shall not pass?
    • View Profile
Re: The threaded pathfinding thread with the previously unhelpful title.
« Reply #110 on: January 28, 2009, 10:16:13 am »

So... we haven't heard from Optimizt in a while, now... hopefully nothing major has come up in the way of frustrations  :o

Well, perhaps once v1.0 is completed, Toady will consider these options, but I am not sure about that, since the engine itself would have to be rewritten partially.


It's going to have to be done far before 1.0, partly because by the time 1.0 comes out even the worst computers are likely to have 4 cores and be the equivalent of DOS machines now.

But in a more serious note, yes it does need to be done and done soon. The longer he waits the more stuff gets piled on and the more stuff that needs to get revised which of course means more work. If he gets it done relatively soonish we'll all experience a massive speed boost, well those of us with computers after 2000 anyway and it'll be less work in the long run for him.

The future is multi-core and with the number of features increasingly bogging down the game the only way to get DF to run well is to optimize it. And besides, who doesn't want to embark to 10x10 areas and still get 100fps?

Well yeah, v1.0 will be huge...I don't know that how will it run on 1 core only. The future of gaming is in the quad+ core processors , that is for sure.
Logged

ShadeJS

  • Bay Watcher
    • View Profile
Re: The threaded pathfinding thread with the previously unhelpful title.
« Reply #111 on: January 28, 2009, 01:55:11 pm »

In the abstract, I could see DF having a peak thread granularity of:

DF Main thread
-> BACKGROUND WORLD (and generating the composition of Settlers, Caravans, Sieges, etc.)
-> TEMPERATURE
-> WEATHER
-> ECONOMY
-> CAVEINS/STRESS
-> ONE THREAD PER FLOWING FLUID
-> GUI THREAD
-> PATHING
-> MODE THREADS for Adventure and Fortress, etc.
edit: -> COMBAT THREAD
edit: -> You could thing of some other 'Large Conceptual Blocks' but you get the point.

In the case of pathing it would probably make sense to use caching and tiled approach (and for the sake of simplicity you could peg a tile to a 1x1 embark size)-- You could try a thread pool design (Sub threads under the master pathing thread) but I think per unit threads would get pretty ugly pretty quickly (even if just for pathing).

I'd be really wary of ever hammering the segfaults and quirks out of any design that had more granularity than the above... And threads have overhead as well so doing the 'big win' threads first would be best (Pathing, GUI)...

Not that I'm claiming to know anything or offering to do any work :)
« Last Edit: January 28, 2009, 01:58:08 pm by ShadeJS »
Logged

Granite26

  • Bay Watcher
    • View Profile
Re: The threaded pathfinding thread with the previously unhelpful title.
« Reply #112 on: January 28, 2009, 01:58:25 pm »

In the abstract, I could see DF having a peak thread granularity of:

DF Main thread
-> BACKGROUND WORLD (and generating the composition of Settlers, Caravans, Sieges, etc.)
-> TEMPERATURE
-> WEATHER
-> ECONOMY
-> CAVEINS/STRESS
-> ONE THREAD PER FLOWING FLUID
-> GUI THREAD
-> PATHING
-> MODE THREADS for Adventure and Fortress, etc.

In the case of pathing it would probably make sense to use caching and tiled approach (and for the sake of simplicity you could peg a tile to a 1x1 embark size)-- You could try a thread pool design (Sub threads under the master pathing thread) but I think per unit threads would get pretty ugly pretty quickly (even if just for pathing).

I'd be really wary of ever hammering the segfaults and quirks out of any design that had more granularity than the above... And threads have overhead as well...

Not that I'm claiming to know anything or offering to do any work :)
There's a LOT of cross dependance there...

ShadeJS

  • Bay Watcher
    • View Profile
Re: The threaded pathfinding thread with the previously unhelpful title.
« Reply #113 on: January 28, 2009, 02:11:47 pm »

In the abstract, I could see DF having a peak thread granularity of:

DF Main thread
-> BACKGROUND WORLD (and generating the composition of Settlers, Caravans, Sieges, etc.)
-> TEMPERATURE
-> WEATHER
-> ECONOMY
-> CAVEINS/STRESS
-> ONE THREAD PER FLOWING FLUID
-> GUI THREAD
-> PATHING
-> MODE THREADS for Adventure and Fortress, etc.

In the case of pathing it would probably make sense to use caching and tiled approach (and for the sake of simplicity you could peg a tile to a 1x1 embark size)-- You could try a thread pool design (Sub threads under the master pathing thread) but I think per unit threads would get pretty ugly pretty quickly (even if just for pathing).

I'd be really wary of ever hammering the segfaults and quirks out of any design that had more granularity than the above... And threads have overhead as well...

Not that I'm claiming to know anything or offering to do any work :)
There's a LOT of cross dependance there...

Yeah, it would get ugly... I am mostly just mentally toying with how far you could push a threaded design (Using 'big logical chunks')... Just a pathing subthread to 100% saturate one core would give the most upside with the least 'thread hell'...
Logged

Andir

  • Bay Watcher
    • View Profile
Re: The threaded pathfinding thread with the previously unhelpful title.
« Reply #114 on: January 28, 2009, 02:41:09 pm »

There's a LOT of cross dependance there...
A proper world thread with proper locking should be able to interface with all those different threads with no problems.  It all boils down to encapsulation so that a rogue thread could not modify a tile while another thread was processing something from it.

For instance, Temperature would simply be a parameter of the tile. (I don't know why you need a thread for this unless you want to deal with temperatures increasing or decreasing over time)  When you set the tile to contain magma, a function in the world tile assignment routine would set the temperature (or differential... +1 degree per cycle up to magma_temp, sending such task to the temp thread) based on the requested tile assignment.  Open tile temps could be calculated by weather.  If a cold front comes in with rain, it collects all tile associated with this front, tells the world thread that this tile is not under weather processing so no other weather threads attach.  Now the weather thread set's the tile to contain the "rain" effect and it's temperature should decrease by x degrees until it reaches y temp.  The rain effect in the tile could trigger a water fill if the tile is marked as non-porous.  Anything over 1 level would fire off a/the liquid thread that collected information about surrounding tiles, mark them as fluid processed tiles, remove the weather if level 7, and begin level calculations.

Each thread handling process would be a templated process using common functions (start, stop, pause, removetile, addtile...) so when the fluid processing thread detects that the tile level is 7, it can call the weather thread (if assigned) and tell it to remove this tile.  If there is a route caching thread or something as well, it can notify it of the removal of said tile so it can handle the situation.  This of course means that the tiles will need a thread handler pointer array, but this would be minor.  (small array containing only handles, at most an associative array or dictionary threads[WEATHER]->removeTile(x, y, z);  or some such)  I'm sure that's the long way around.  I'd have to sit down and draw it out to determine actual communications.
Logged
"Having faith" that the bridge will not fall, implies that the bridge itself isn't that trustworthy. It's not that different from "I pray that the bridge will hold my weight."

Sowelu

  • Bay Watcher
  • I am offishially a penguin.
    • View Profile
Re: The threaded pathfinding thread with the previously unhelpful title.
« Reply #115 on: January 28, 2009, 03:33:50 pm »

Hmm.  Many of these processes have to be finished every single frame.  Temperature is complicated because it's not just per-tile but also every object and spatter.  Stress has to be every frame too, for the most part.  For things that are going to run at the beginning or end or whatever of every frame, I just don't see any value in all that expensive context switching.  Plus, you potentially double your memory overhead.  I'll explain:

Let's say you have one thread.  It runs stress stuff, then it runs critters moving around and acting, then it runs temperature.  At the beginning of each frame, it can focus entirely on stress--and if that changes the map, it can happen right away, before pathfinding and temperature care.  Then, critters move, and a dragon breathes fire.  At the end of the tick, that fire has some effect.

But with multiple threads...Well, let's say you're running temperature, and you just calculated the tiles right in front of the dragon.  Whoops!  It just breathed fire so that's not valid any more.  Or, the game just decided that a bridge under one of your dwarves is now on fire.  Well, that kind of messes with the action he was taking...

Of course, normally you'd say "That bridge can't burn down right now.  The current temperature calculations can't take effect until next tick."  But that means you gotta store the new values somewhere while you're working...  Eh, there's probably a single buffer like that already, but when you have like ten threads that all need their own buffer, and then need to be recombined, it gets really ugly.

I just don't see any value in splitting up tasks that always need to run in a certan order, into different threads.  Pathfinding is fine because it's not part of the WORLD--The little dwarfy AIs can pause for a little bit while making decisions, and besides, their requests are bursty in a way that physics isn't.  You get nice gains when you can amortize burstiness.
Logged
Some things were made for one thing, for me / that one thing is the sea~
His servers are going to be powered by goat blood and moonlight.
Oh, a biomass/24 hour solar facility. How green!

Andir

  • Bay Watcher
    • View Profile
Re: The threaded pathfinding thread with the previously unhelpful title.
« Reply #116 on: January 28, 2009, 05:25:56 pm »

A missed frame here or there isn't going to make a big difference.  We are talking about 60 frames per second or more.  If it took 4 seconds to calculate something like this, then sure.  But when you update the world tile and the renderer just passed that tile, it will catch it on the next pass.

Think of it like a burning forest with bird hoping from tree to tree.  If the bridge under your dwarf caught on fire, he'd have a little time to react and just because the tree caught on fire, it doesn't mean the bird will too.  It's not instantly going to burn him to a crisp.

As far as path finding and cave-ins are concerned, think of it this way.  You know how to get to work.  You plan out your route (in your head most likely) and you get in your car and go.  You get part way there and you find out an oil tanker flipped over in the road ahead.  You have to detour.  You call up your memory of the location and decide on an alternate route.

The dragon scenario is the same as the fire one.  Your dwarf will most likely spend more than one frame in a tile.  He COULD be there for hundreds of iterations before he makes his next move depending on how much is going on in the world.  The likeliness of him escaping that fire is slim, but if he does... he's a lucky dwarf!  That burning tile will be fully realized the next time that dwarf needs to process.  Maybe he's trapped... he likely would have been anyway with the dragon breath... or maybe he finds a neighboring tile that's not on fire and escapes before burning to a crisp.

How you described it (doing everything before every frame) is why a lot of developers don't grasp threading.  They think that everything HAS to happen in a specific order.  They must have total control of when and where things happen with a thread join to make sure it does.  Drawing a screen, yes.  You want to make sure every tile is in the buffer before committing. (They don't have to be up to the CPU tick accurate, but they do have to complete at least one iteration update before displaying or there will be holes in the world.)  Telling a dwarf to take the next step?  Not so much.  If he misses a frame, you'll likely never even see it.  Processing cave-ins?  If I remove a pillar from a cave roof in the real world (yes, I know this isn't the real world game, but bear with me...) it doesn't all finalize before I can make the next step.  Pieces of rock will begin falling and I might be able to make it through before it all comes crashing down.  In your example, there's no depth of time or variance.  The cave in just happens... all at once.  Dwarf dead.

As far as your multiple buffers are concerned... they just aren't needed.  The refresh time per frame is so minuscule that a tile not updated with water in the draw buffer will likely go unnoticed.  You write that data right into the singular world.  No joining or funky mem-copy to merge separate copies of a world.  You set the temp of the tile located at X, Y, Z to N.  This is why you'd have tile locking handled by the world, so no two temperature threads could update the temperature memory location of the same tile.  If you only had one temperature thread, it would be a little easier since that one thread would be the only thing updating that tile's temp.
Logged
"Having faith" that the bridge will not fall, implies that the bridge itself isn't that trustworthy. It's not that different from "I pray that the bridge will hold my weight."

Baughn

  • Noble Phantasm
  • The Haruhiist
  • Hiss
    • View Profile
Re: The threaded pathfinding thread with the previously unhelpful title.
« Reply #117 on: January 28, 2009, 05:43:34 pm »

In general, the solution is to have two buffers: Last frame, and next frame.

All calculations read only from the last-frame buffer, and write only to the next-frame buffer. You can have as many threads as you like; they'll never clash, unless they write the same data (try to avoid that).

Of course, that would require an *enormous* re-design, and is extremely difficult in languages that aren't designed for this from the bottom up, eg. purely functional ones. So I don't think Toady will go for it. :P


EDIT: On a sidenote, this wouldn't necessarily double memory use and/or require all data to be copied per-frame. For data structures that don't change, it's possible to copy just a pointer instead of the whole thing.

Of course, when you start doing a lot of that, accounting for memory use becomes insanely complex and you end up dooming yourself to memory-leak hell unless you use a GC. Also, it requires entirely different skills than you develop when writing code that mutates data, which is another reason Toady won't be doing it.

Annoyingly (to some)???, this means those who promoted functional programming were right all along; the discipline and code patterns used in functional programming are exactly the ones you need to do threading well.
« Last Edit: January 28, 2009, 05:50:33 pm by Baughn »
Logged
C++ makes baby Cthulhu weep. Why settle for the lesser horror?

Sowelu

  • Bay Watcher
  • I am offishially a penguin.
    • View Profile
Re: The threaded pathfinding thread with the previously unhelpful title.
« Reply #118 on: January 28, 2009, 05:58:34 pm »

No, no, no.  Of course it's permissible for a dwarf to miss a frame, but when one basic physics or logic or something thread is only halfway done with its world processing in one frame before another thread starts doing the same thing...that's where race conditions and nasty bugs come in.

It's possible, but it's a HUGE headache, and is no fun at all to debug.

Again, what's the benefit?  There's a clear benefit in letting a dwarf's pathfinding run out-of-order, but not in running temperature or and fluid out-of-order.  You might only have to run them every few frames...so why not just run them every few frames, instead of putting them in another thread?

I really, -really- don't see why you would split up temperature or fluid into different threads...instead of moving the parallelization into that process.  Fluid calculations can run pretty easily in parallel, especially the parts that scan fluids to see where a change is necessary.  Temperature can run REALLY easily in parallel, each thread gets a quarter of the map.

I'm all for splitting off pathfinding, but I don't see any compelling reason to split temperature off into its own single thread.

Besides...If temperature or fluid code starts lagging behind, you're going to be blocking on it anyway.  It's no fun when all of a sudden the goblins can outrun your floods of water because the threads are running at a different FPS, for example--much worse than lagging pathfinding by several frames (though that's also bad, like, in combat).  You might as well throw all your non-pathfinding threads at tasks like those, so you finish it as quickly as possible.
« Last Edit: January 28, 2009, 06:01:22 pm by Sowelu »
Logged
Some things were made for one thing, for me / that one thing is the sea~
His servers are going to be powered by goat blood and moonlight.
Oh, a biomass/24 hour solar facility. How green!

dreiche2

  • Bay Watcher
    • View Profile
Re: The threaded pathfinding thread with the previously unhelpful title.
« Reply #119 on: January 29, 2009, 07:39:30 am »

I also think that it might be easier to parallelize the workload of specific tasks rather than assigning tasks to different threads. Also, I think it would be important to keep the game flow deterministic, because otherwise things like bug hunting are going to be a pain in the ass.

Like I stated in my thread, I think it boils down to waiting for Toady to release the relevant parts of the code (e.g. pathfinding) in a test program, like he did with the opengl stuff. Until then, all is just speculation. And I think he's got other priorities right now (certainly the ongoing porting would have to finished first). Maybe after the next release.
Logged
Pages: 1 ... 6 7 [8] 9