Bay 12 Games Forum

Please login or register.

Login with username, password and session length
Advanced search  
Pages: 1 2 3 [4] 5 6 ... 9

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

Ogantai

  • Bay Watcher
    • View Profile
Re: The threaded pathfinding thread with the previously unhelpful title.
« Reply #45 on: January 13, 2009, 07:18:32 pm »

Trying to multithread DF's pathfinding isn't going to work without almost a complete rewrite of how DF works, I'm afraid. That's something for T1 to attempt in DF 2.0, what we need now is route caching. Not only is it easier to implement, but it will provide a greater performance increase for all but a few trivial cases.
Logged

Andir

  • Bay Watcher
    • View Profile
Re: The threaded pathfinding thread with the previously unhelpful title.
« Reply #46 on: January 13, 2009, 07:30:52 pm »

Trying to multithread DF's pathfinding isn't going to work without almost a complete rewrite of how DF works, I'm afraid. That's something for T1 to attempt in DF 2.0, what we need now is route caching. Not only is it easier to implement, but it will provide a greater performance increase for all but a few trivial cases.
If DF was written with any semblance of OO programming in mind, it would be very little time from the old method to the new and you wouldn't have to recode the entire thing.  You just point the material request functions, pathing requests, and others to the new pathing objects.
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."

Ogantai

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

Trying to multithread DF's pathfinding isn't going to work without almost a complete rewrite of how DF works, I'm afraid. That's something for T1 to attempt in DF 2.0, what we need now is route caching. Not only is it easier to implement, but it will provide a greater performance increase for all but a few trivial cases.
If DF was written with any semblance of OO programming in mind, it would be very little time from the old method to the new and you wouldn't have to recode the entire thing.  You just point the material request functions, pathing requests, and others to the new pathing objects.
True or not, T1 doesn't seem to be interested in doing that, and since he's the only one with the source I don't think we'll be seeing anyone else do it either. A rewrite on that scale would require the whole kit and kaboodle, whereas route caching could be added with just the pathing code. The way DF works now just running parallelized pathfinding would result in all sort of locking/conflict issues.
Logged

Ampersand

  • Bay Watcher
    • View Profile
Re: The threaded pathfinding thread with the previously unhelpful title.
« Reply #48 on: January 13, 2009, 08:12:25 pm »

The most important routes are from the bedroom to the meeting hall. Then, maybe from the meeting hall to a given point on stockpiles. I don't think pathing to specific objects could be much improved meaningfully.
Logged
!!&!!

Ogantai

  • Bay Watcher
    • View Profile
Re: The threaded pathfinding thread with the previously unhelpful title.
« Reply #49 on: January 13, 2009, 10:24:08 pm »

The most important routes are from the bedroom to the meeting hall. Then, maybe from the meeting hall to a given point on stockpiles. I don't think pathing to specific objects could be much improved meaningfully.
From the finishing goods workshop(s) to the finished goods stockpile :D (This is about 25% of my forts pathfinding.)
Logged

CobaltKobold

  • Bay Watcher
  • ☼HOOD☼ ☼ROBE☼ ☼DAGGER☼ [TAIL]
    • View Profile
Re: The threaded pathfinding thread with the previously unhelpful title.
« Reply #50 on: January 13, 2009, 10:36:32 pm »

From an ore vein to the ore stockpile(or smelter, as case may be)
From any workshop to its input or output stockpile
Butcher to Tanner
From glass forge to sand collection area (and back)
From food stockpile to dining hall(s)
Logged
Neither whole, nor broken. Interpreting this post is left as an exercise for the reader.
OCEANCLIFF seeding, high z-var(40d)
Tilesets

Optimizt

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

Trying to multithread DF's pathfinding isn't going to work without almost a complete rewrite of how DF works, I'm afraid. That's something for T1 to attempt in DF 2.0, what we need now is route caching. Not only is it easier to implement, but it will provide a greater performance increase for all but a few trivial cases.
Multithreading isn't as hard as you think. In many cases, making an algorithm run parallel is as simple as a few function calls to the appropriate library.

If A* pathfinding is implemented in DF like I think, it would not be hard at all to spread the pathfinding load between processors with little effort. That's what I'm working on right now ;)

Also, I was thinking of splitting the map into a quadtree.  The quadtree algorithm can be summarized as follows:
  • Take a region with dimensions 2^n x 2^n, where n is any integer
  • If contents of that region are not uniform, divide it into four new regions and repeat for each of the four regions.
Since the map is already represented as 16x16 blocks, it is possible to split up a block like this:

The red shaded areas are regions that are blocked, and the green shaded areas can be walked on. The red outline denotes the four regions under the central node, the green outlines denote the regions under that region, etc. The good thing is that giant expanses of similar regions can be stored as a single node in a tree, saving memory and processing time.
Logged

Draco18s

  • Bay Watcher
    • View Profile
Re: The threaded pathfinding thread with the previously unhelpful title.
« Reply #52 on: January 14, 2009, 11:14:33 am »

And then what?
Logged

Kardos

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

What about adding a blue square for transient squares such as doors where properties for walking change?  Or would the benefit be to small in terms of computing speed?
Logged

Sowelu

  • Bay Watcher
  • I am offishially a penguin.
    • View Profile
Re: The threaded pathfinding thread with the previously unhelpful title.
« Reply #54 on: January 14, 2009, 02:18:59 pm »

If DF was written with any semblance of OO programming in mind, it would be very little time from the old method to the new and you wouldn't have to recode the entire thing.  You just point the material request functions, pathing requests, and others to the new pathing objects.

Yyyyeeeeahh...I'm going to have to say you never had to move a program from "single thread" to "multiple threads" in your professional career, nor from "one memory management system" to "another memory management system".  Being OO has very little to do with being threadsafe!  Single threaded applications can make a lot of very, very convenient assumptions!

They also tend to block on things that are very obvious for a single threaded application, but remarkably unhelpful for a threaded one.

DF might not even make sense in parallel, right now.  See, it's fairly easy to multithread chess with "white AI" and "black AI".  It's a bit harder to multithread chess with, say, "white pawn" and "white knight".  It's a concept that just doesn't make any sense.  For all we know, one dwarf moving can catastrophically change the state for the next dwarf, right now.

Moving from single thread to multithread is easy if you code with OO in mind?  Do your programs crash a lot, mysteriously, every few hours, and you can never quite track down why?  Yeah.

Sorry if that came off as mean, but honestly, your implication was too.  :)
« Last Edit: January 14, 2009, 02:21:42 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!

Thndr

  • Bay Watcher
    • View Profile
Re: The threaded pathfinding thread with the previously unhelpful title.
« Reply #55 on: January 14, 2009, 03:36:59 pm »

Is it going to be as basic as GREEN and RED blocks?
Because for some things it seems more complicated. Like water level (maybe VS swimming skill? Not sure how toady handles that), and ramps that can only be entered from specific directions (although downramps only block one direction from Z movement, and the square I assume is registered as some sort of channel)

Or am I just once again overthinking what exactly you have to do.
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 #56 on: January 14, 2009, 03:41:03 pm »

^^^ No, you're more or less right -- DF already has problems of this kind, in that the "connected components" system used for pathfinding feasibility checks (needed because the algorithm chokes on impossible pathing requests) assumes a particular mobility system, breaking fliers and swimmers.
Logged

Gertack

  • Bay Watcher
    • View Profile
Re: The threaded pathfinding thread with the previously unhelpful title.
« Reply #57 on: January 14, 2009, 07:32:51 pm »

I've moved programs from single- to multi-threaded before and it really depends on the application.  Some already have "boundaries" across which different parts of the system don't interact and so if one side suddenly goes multi-threaded the other sides doesn't give a whit.

There's also different approaches to multi-threading.  Some people in this thread have been talking about making CPU_COUNT-1 extra threads for pathing, but what if you gave each dwarf their own thread?  How coarse or fine do you want to make the locking? 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.
Logged

Andir

  • Bay Watcher
    • View Profile
Re: The threaded pathfinding thread with the previously unhelpful title.
« Reply #58 on: January 14, 2009, 07:43:03 pm »

If DF was written with any semblance of OO programming in mind, it would be very little time from the old method to the new and you wouldn't have to recode the entire thing.  You just point the material request functions, pathing requests, and others to the new pathing objects.

Yyyyeeeeahh...I'm going to have to say you never had to move a program from "single thread" to "multiple threads" in your professional career, nor from "one memory management system" to "another memory management system".
I have actually, for a multi-billion dollar companies payroll processing.  Many times over actually for different check processing routines.

But we aren't really talking about memory management schemes here.  I doubt he did from the little code I did see (in BC) because he barely even covers RAII.  It's nothing to be joked at though.  I don't have the time to do what he does, so I try to help when I can.
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."

Andir

  • Bay Watcher
    • View Profile
Re: The threaded pathfinding thread with the previously unhelpful title.
« Reply #59 on: January 14, 2009, 07:50:32 pm »

Some people in this thread have been talking about making CPU_COUNT-1 extra threads for pathing, but what if you gave each dwarf their own thread?  How coarse or fine do you want to make the locking? 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.
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."
Pages: 1 2 3 [4] 5 6 ... 9