Bay 12 Games Forum

Please login or register.

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

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

Sergius

  • Bay Watcher
    • View Profile
Re: The threaded pathfinding thread with the previously unhelpful title.
« Reply #90 on: January 20, 2009, 02:21:12 pm »

We (Programmers) all started at an "Hello world" Programm and developed our skills from there.

(Sorry, I have to post this... it's required.)

I have a friend who's first program is always "Hello Kitty" not "Hello World" because "Saying hello to a kitty is much more sane than talking to the whole world."

Unless it's that world that used its technology to reduce itself to human size so it could use its death rays and defense satellites to fry little monsters while helping save the universe from the big crunch.
Logged

Washii

  • Bay Watcher
  • Schwa?
    • View Profile
    • WashiiPonderings
Re: The threaded pathfinding thread with the previously unhelpful title.
« Reply #91 on: January 20, 2009, 04:21:18 pm »

... Do you want to structure your program in such a way that each execution path assumes it "is" a dwarf and nobody else matters, or have a core serve everybody?  So slice it vertically, slice it horizontally, or slice it off in pieces?  Some are a lot easier than others, but not necessarily the same benefit.
I've thought about this a lot actually.  Splitting each dwarf up into their own thread (or process, as I had the idea to make a dwarf handling client that connect to the world server and act as if they were adventurers) and I don't think there is enough gained in giving each dwarf it's own thread.  They really don't do enough to justify having their own threads.  Groups of 10-25 though... maybe.

I like the thread per groups idea. Even better, why not a thread per profession group?

It would make sense for miners to have a much more brutal algorithm than some farmers that need to find their way from seeds->plot->food stockpile->loop.
Logged

Mel_Vixen

  • Bay Watcher
  • Hobby: accidently thread derailment
    • View Profile
Re: The threaded pathfinding thread with the previously unhelpful title.
« Reply #92 on: January 20, 2009, 05:14:33 pm »

Well maybe not splitting by profession. Group them by places. I mean if one Haulerdwarf in cavern A hauls stone to cavern b he can be grouped with the 3 other Haulerdwarfs that do the same.

Extending this you can use part paths. So if an Herbalistdwarf paths from cavern z to x over cavern a and b our haulers could join him on the path between a and b.

This way you have the same ammount of pathing processes but an good bunch less calculations i think.
« Last Edit: January 20, 2009, 05:37:02 pm by Heph »
Logged
[sarcasm] You know what? I love grammar Nazis! They give me that warm and fuzzy feeling. I am so ashamed of my bad english and that my first language is German. [/sarcasm]

Proud to be a Furry.

Kindjie

  • Bay Watcher
    • View Profile
Re: The threaded pathfinding thread with the previously unhelpful title.
« Reply #93 on: January 20, 2009, 06:20:13 pm »

A* guarantees the optimal path is found. Is that really necessary in Dwarf Fortress? You can get a lot faster algorithms if you throw out that requirement, and dorfs really aren't THAT smart that they should always find the shortest path.

Without thinking about it too much (I'm at work right now), you could maybe try something like this: http://en.wikipedia.org/wiki/Swarm_intelligence
A hybrid approach might even work. I dunno... maybe use it too cull the A* search space somehow? Maybe start with A* until you have enough data to support ant colony optimization?

Just some ideas to consider.  :)
Logged

MuonDecay

  • Bay Watcher
  • Say hello to my little μ
    • View Profile
Re: The threaded pathfinding thread with the previously unhelpful title.
« Reply #94 on: January 20, 2009, 06:50:13 pm »

Erm, incremental approaches are best.

Attempting to retool the way pathfinding works at the same time as trying to multithread it would be too ambitious. That's just more potential causes for behaviour that have to be investigated for every bug that shows up.

The mission statement here is a proof of concept for multithreading. Yes, pathfinding optimization would be good, too, but you don't tack that onto the fundamental experiments as a side-goal, unless you want to swamp yourself with work and errors. The OP is attempting to see if DF can be multithreaded, because that's a contribution they're able to make which would produce a significant benefit. They are not attempting to drop in and wave a magic wand and solve all of the pathfinding problems in one fell swoop. Volunteer effort, incremental improvement. We should be thankful for even that instead of swooping in and asking for "more work, more work!" before we've even seen a hint of the first results.
Logged

Footkerchief

  • Bay Watcher
  • The Juffo-Wup is strong in this place.
    • View Profile
Re: The threaded pathfinding thread with the previously unhelpful title.
« Reply #95 on: January 20, 2009, 06:59:46 pm »

Dug up some rather old posts from Toady regarding multithreading and "room"-based pathfinding.

http://www.bay12games.com/forum/index.php?topic=1788.msg27082#msg27082
Quote from: Toady One
I don't know how to thread something like path-finding -- would it jump off and try to work on something like weather at the same time?  As far as I know, I couldn't do another dwarf's pathfinding at the same time, since they'd write into the same buffer.  At this point I'm not really sure how the program would have to be broken into pieces, since so many things are inter-related.  At another extreme, I guess you can break certain loops locally up into multiple threads, and sometimes get gains from that on processors that are made for that.  I might look into something like this later.  It depends on how bad performance is.  There's a lot to do.

http://www.bay12games.com/forum/index.php?topic=1788.msg27102#msg27102
Quote from: Toady One
As far as the suggestions about giving a different thread to each path-finding dwarf, my issue here is the buffers they use.  I'm under the impression that they can't each write to that buffer, since they'd be stepping on each other's toes.  That means I'd need multiple buffers, which starts to be a memory problem in this case, depending on various things.

[...]

For all the room-based pathfinding comments, I had a few conversations with some of the early testers before the first release about htis, and I still have some issues with how it would work, especially with the Z coordinate and flows, and the storage issue to a lesser extent.  The connections for the rectangle seem irritating to maintain and use when ramps come into play, especially on the slopes, and in a thick forest, before the first tunnel is dug, you might be looking at several thousand rooms already.  I also didn't understand how flooding was handled in Veroule's post.  So the unit does not know in advance if it can get to locations?  This is something I trying to preserve now, because it's something that's very useful to know with precision at all times.  If it has to form a path just to know if a unit should be thinking about an object or building, then it'll slow down, and if it just leaves the question up in the air, the dwarf might take a job they can't complete and suffer an intelligence downgrade.  Not that they're very smart now.

http://www.bay12games.com/forum/index.php?topic=1788.msg27107#msg27107
Quote from: Toady One
So far I don't understand a way to do a room-based or location-based method that does what I need it to do.  I think that somewhere within that sort of thinking, there's a way to support pathing for different modes of travel properly (flying etc.), which is attractive, but I don't see an implementation right now that handles flow issues efficiently, and I think handling 3D connections might be somewhat irritating.  A dwarf must absolutely be able to know "yes, I can do this job or go to this area or item" without forming a path to do it.  In a room-based system, the path formation would be less expensive and would work if the result were stored as a component number that could later be queried.  However, fluid flows would destroy this information, so I'm not sure how to fix that.  You can't just check fluids during pathing, unless you want dwarves to do that every single time they compare their location to a potential destination, or unless you want them to store potentially incorrect information and go on a lot of aborted journeys.
Logged

Andir

  • Bay Watcher
    • View Profile
Re: The threaded pathfinding thread with the previously unhelpful title.
« Reply #96 on: January 21, 2009, 09:10:41 am »

Toady's concerns over dwarfs using the same "buffer" is a valid one, but there are several shared memory techniques used in threading that alleviate most of this.  The easiest way to solve this is resource locking, but you can also partition the data logically.  For example, if you have a group of dwarfs in one 16x16 block of the world (as it's been said before, he splits the map into 16x16 blocks) you could logically assign threads to those areas or assign a tread to handle one strip of zones in the map.  There are multiple methods to prevent race conditions as he describes.  It's all part of the learning curve though.
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."

Tormy

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

Toady's concerns over dwarfs using the same "buffer" is a valid one, but there are several shared memory techniques used in threading that alleviate most of this.  The easiest way to solve this is resource locking, but you can also partition the data logically.  For example, if you have a group of dwarfs in one 16x16 block of the world (as it's been said before, he splits the map into 16x16 blocks) you could logically assign threads to those areas or assign a tread to handle one strip of zones in the map.  There are multiple methods to prevent race conditions as he describes.  It's all part of the learning curve though.

Ok that is understandable, but changing to multi-threading would require an engine rewrite also I guess?
Logged

Andir

  • Bay Watcher
    • View Profile
Re: The threaded pathfinding thread with the previously unhelpful title.
« Reply #98 on: January 21, 2009, 11:50:24 am »

Toady's concerns over dwarfs using the same "buffer" is a valid one, but there are several shared memory techniques used in threading that alleviate most of this.  The easiest way to solve this is resource locking, but you can also partition the data logically.  For example, if you have a group of dwarfs in one 16x16 block of the world (as it's been said before, he splits the map into 16x16 blocks) you could logically assign threads to those areas or assign a tread to handle one strip of zones in the map.  There are multiple methods to prevent race conditions as he describes.  It's all part of the learning curve though.
Ok that is understandable, but changing to multi-threading would require an engine rewrite also I guess?
Parts of it... I assume.  I haven't seen enough of the code to determine how extensive it would be though.

Edit: format.  I accidentally replied inline with the quote.  ::)
« Last Edit: January 21, 2009, 12:43:07 pm by Andir »
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 #99 on: January 21, 2009, 12:31:32 pm »

Toady's concerns over dwarfs using the same "buffer" is a valid one, but there are several shared memory techniques used in threading that alleviate most of this.  The easiest way to solve this is resource locking, but you can also partition the data logically.  For example, if you have a group of dwarfs in one 16x16 block of the world (as it's been said before, he splits the map into 16x16 blocks) you could logically assign threads to those areas or assign a tread to handle one strip of zones in the map.  There are multiple methods to prevent race conditions as he describes.  It's all part of the learning curve though.

By my reading, the buffer is quite the smallest problem here.  My interpretation is that "a pathing dwarf needs to have XX kilobytes / megabytes to store stuff in", and possibly "Those XX bytes need to be set up properly ahead of time and cleaned afterwards".  In that case, having a buffer for every dwarf is problematic, but having a set number of buffers/threads is a trivial part of a basic implementation of threaded pathfinding.

It could get a little bit hairier in one way I can think of:  Some implementations use the map itself for pathfinding buffering, storing things like path cost and path origin in each individual tile.  If that's what DF does, we're a little hosed, because it'll take work to decouple that.  If DF doesn't do it that way though, I just don't see how adding a small number of buffers is a problem.
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 #100 on: January 21, 2009, 01:07:30 pm »

I'd hate to see the code if pathing was cached in the tile objects.   :o

I assume he's using one large array of dwarfs and storing the path in the dwarf item object.  I don't think it's generated each move of the dwarf.  I'm thinking he generates the path, saves it to the dwarf and cycles the next move each iteration of the movement part of the loop.  I also assume he's using a queue (maybe a dequeue) template container.  If this were the case, he could replace those with pointers to a path object to handle the threading with little problem.  For example he could be doing something like: path.next(destX, destY, destZ) where path() is instantiated with the origin and the destination could be used as a key.  You can replace that with dwarf.moveNext() that will spawn a new thread to see if the path exists, create it if needed, then step the dwarf.  moveNext() would return a boolean value if a thread was created telling the main loop if it needs to wait because all the threads are in use or if it can assume that the function will be handled and move to the next dwarf.  Of course, this can be an intensive method.  There are other ways to use threading to cache a bunch of common routes and use them within the path finding algorithm as well.  Most of it involves writing the main loops to "request" actions rather than execute a function and wait for that to finish before moving on.

Sorry, I'm rambling.
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."

Felblood

  • Bay Watcher
  • No, you don't.
    • View Profile
Re: The threaded pathfinding thread with the previously unhelpful title.
« Reply #101 on: January 21, 2009, 02:41:48 pm »

My own code is pretty crufty and I've never worked with threading, so I'll leave that aspect of the problem to more qualified persons.

However, I feel I should interject on the debate over how the pathing could be made more efficient.

It seems to my observations, that a Dwarf only recalculates his path if it becomes blocked, or another moving unit collides with him and grounds him. Until then some system just checks to be sure his existing path is still valid (since he changes routes before reaching a freshly locked door, and can go around other units, if the hallway is wide enough).

Somewhere in every fortress is a hallway one tile narrower than it should be, just waiting for the population to grow large enough for it to completely destroy your FPS with a continuous traffic jam. I can't count the number of times I've had a fortress humming along, only to have the latest litter of kittens or the new wave of migrants overload my road system and drive my FPS down between 3 and 9, from 35 to 50.

I can see "thinking" mark appear on the grounded dwarves, so I know they're re-pathing whenever they trip over a kitten. I believe that if they would just try their old path again they would reach their destinations without rendering my game unplayably slow. Surely whatever gains we get from discarding paths that result in collisions can't outweigh the cost of re-calculationf them everything time we bump into someone going the other way. Once a dwarf is caught in a traffic jam, the only way out is to keep pressing forward, anyway.

Dwarves might have to be given a way do differentiate between grounded by traffic and grounded by other means, and their old path should probably be re-checked; we don't have the code, so it's hard to say anything definite about how to actually do the thing.

Really, there's no way for anyone other than Toady to implement this, so the argument is pretty much academic, but it seems to me that eliminating all these pathings would be more effective than making each pathing slightly faster.

I'm a multithreaded, single core and unlikely to upgrade in the next few years, BTW.
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.

CobaltKobold

  • Bay Watcher
  • ☼HOOD☼ ☼ROBE☼ ☼DAGGER☼ [TAIL]
    • View Profile
Re: The threaded pathfinding thread with the previously unhelpful title.
« Reply #102 on: January 21, 2009, 07:07:48 pm »

It seems to my observations, that a Dwarf only recalculates his path if it becomes blocked, or another moving unit collides with him and grounds him. Until then some system just checks to be sure his existing path is still valid (since he changes routes before reaching a freshly locked door, and can go around other units, if the hallway is wide enough).
My dwarvesgoblins don't divert until they actually reach it and find "Huh, this door is locked now."
Logged
Neither whole, nor broken. Interpreting this post is left as an exercise for the reader.
OCEANCLIFF seeding, high z-var(40d)
Tilesets

Nesoo

  • Bay Watcher
    • View Profile
Re: The threaded pathfinding thread with the previously unhelpful title.
« Reply #103 on: January 23, 2009, 03:35:50 pm »

I don't know about locked doors, but I do know that they will recalculate a path if they run in to another dwarf. A recent test fortress (with lots of twisty passages so I can tweak my smooth wall tiles) had a hallway that split in two then rejoined. The dwarves kept pathing through one branch, but another dwarf would run in there to do some smoothing. Then the first dwarf would run in to my engraver and end up recalculating and zipping around the other hall. It was rather irritating. It was probably faster for the dwarf to take the other path than to just duck under the engraver... except that they invariably ran in to another dwarf in the other hall who was on his way somewhere, so they end up ducking anyway.
Logged
000508 □ [dwarf mode][flows] flooding over a full pond will kill the fish inside

Draco18s

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

I had a hallway like that once.  I had two dwarves in it who never left.  One was going west, the other east and they kept ping-ponging off each other until a third dwarf came along.
Logged
Pages: 1 ... 5 6 [7] 8 9