Bay 12 Games Forum

Please login or register.

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

Author Topic: Spin the pathfinding off to other threads.  (Read 6989 times)

612DwarfAvenue

  • Bay Watcher
  • Voice actor.
    • View Profile
    • TESnexus profile, has my voice acting portfolio.
Re: Spin the pathfinding off to other threads.
« Reply #15 on: June 28, 2012, 08:05:16 pm »

Alright, first off, Aha you're coming across as a condescending asshole.

Secondly, DF has been built from the ground up as a single-threaded application. In order to introduce multi-threading, Toady will have to redo the entire code. He's said that himself, so before you go claiming it'd be an easy task, listen to what the man who actually makes the game is saying.


Multi-threading has been discussed so many times, more than it needs to because people like you just do not use the damn search function.
Logged
My voice acting portfolio.
Centration. Similar to Spacestation 13, but in 3D and first-person. Sounds damn awesome.
NanoTrasen Exploratory Team: SS13 in DF.

aha

  • Bay Watcher
    • View Profile
Re: Spin the pathfinding off to other threads.
« Reply #16 on: June 29, 2012, 06:06:34 am »

Alright, first off, Aha you're coming across as a condescending asshole.

Secondly, DF has been built from the ground up as a single-threaded application. In order to introduce multi-threading, Toady will have to redo the entire code. He's said that himself, so before you go claiming it'd be an easy task, listen to what the man who actually makes the game is saying.


Multi-threading has been discussed so many times, more than it needs to because people like you just do not use the damn search function.

Nonsense, Please reread my first post - nothing suggested requires the full rewrite. I do have experience with multithreaded apps and thus am more qualified to comment on this than you, or in fact Toady:)
Your comments are not helpful at all - I believe that its been put off for so long just because people without a clue shooting down the idea in all these previous posts.
Considering that more and more features are being added to the game its really inevitable that the game will keep getting slower - gradual spin off of the tasks will help A LOT without a need for major rewrite.

Logged
tail -f -n 10 df_27_176_38a/gamelog.txt

helmacon

  • Bay Watcher
  • Spirit sanguine, delicious
    • View Profile
Re: Spin the pathfinding off to other threads.
« Reply #17 on: June 29, 2012, 12:02:10 pm »

1. Simply stating the same thing again does not make it right
Quote
Nonsense, Please reread my first post - nothing suggested requires the full rewrite. I do have experience with multithreaded apps and thus am more qualified to comment on this than you, or in fact Toady:)

2. Because there are other threads about this doesn't mean you cant post about it, it means that instead of starting another fucking thread about it, post in one of the former threads.

thank you
Logged
Science is Meta gaming IRL. Humans are cheating fucks.

helmacon

  • Bay Watcher
  • Spirit sanguine, delicious
    • View Profile
Re: Spin the pathfinding off to other threads.
« Reply #18 on: June 29, 2012, 12:03:23 pm »

sorry, it posted twice for some reason.
« Last Edit: June 29, 2012, 04:09:06 pm by helmacon »
Logged
Science is Meta gaming IRL. Humans are cheating fucks.

612DwarfAvenue

  • Bay Watcher
  • Voice actor.
    • View Profile
    • TESnexus profile, has my voice acting portfolio.
Re: Spin the pathfinding off to other threads.
« Reply #19 on: June 29, 2012, 07:49:27 pm »

Your comments are not helpful at all - I believe that its been put off for so long just because people without a clue shooting down the idea in all these previous posts.

Speak for yourself, dude. Plenty of people here do have a clue, and you seem to have ignored the part where i pointed out that ToadyOne said it would require a full re-write. Now, i'm willing to go on faith he said that because spinning it off would be a no-go for whatever reason. If you can prove him wrong and successfully make this game decently multithreaded, i'll be glad to mea culpa all you want, but until then i remain skeptical.

In addition, what Helmacon said.
Logged
My voice acting portfolio.
Centration. Similar to Spacestation 13, but in 3D and first-person. Sounds damn awesome.
NanoTrasen Exploratory Team: SS13 in DF.

thisisjimmy

  • Bay Watcher
    • View Profile
Re: Spin the pathfinding off to other threads.
« Reply #20 on: June 29, 2012, 08:48:15 pm »

you seem to have ignored the part where i pointed out that ToadyOne said it would require a full re-write. Now, i'm willing to go on faith he said that because spinning it off would be a no-go for whatever reason.

I don't recall Toady ever saying that.  He did say this in DF Talk #9:
Quote
It is my understanding that the SDL stuff is now multicored, with the graphics and the graphics display and so on. Now obviously people, when they're asking about it, that's one important point but people are curious like 'why can't I have seventeen dwarves pathing at once' or 'why can't you take that stupid ass weather simulation and make that go happen on some core, preferably not at all'. It's complicated, and from what I gather it would be a really difficult long project and it's probably not going to happen. That's what I gather. Now there are some things, like these micro multithreading of a smaller process just to get through one loop faster, it can break it up and then come back without it being a case of running path finding at the same time as you're running a fluid simulation, and that stuff, the more I know about that the better, probably, and maybe that's feasible. As for splitting up the path finding and stuff: some people have discussed about how that might work, but as for whether anything is actually going to come of that, I wouldn't bet on it anyway.
Logged

crazysheep

  • Bay Watcher
  • [PREFSTRING:fluffy wool]
    • View Profile
Re: Spin the pathfinding off to other threads.
« Reply #21 on: June 30, 2012, 05:07:31 am »

Before this gets derailed, may I suggest that Aha do the following: Contact Toady (via email or PM) and ask to volunteer with multithreading the pathfinding loops? As he's pointed out, he feels that he is more qualified than most of us to discuss multithreading, and that he might be able to do a decent job with it. So why not contact Toady directly to see how Aha can help?
Logged
"Don't be in such a hurry to grow up, for there's nothing a kid can't do."

aha

  • Bay Watcher
    • View Profile
Re: Spin the pathfinding off to other threads.
« Reply #22 on: June 30, 2012, 02:16:18 pm »

Before this gets derailed, may I suggest that Aha do the following: Contact Toady (via email or PM) and ask to volunteer with multithreading the pathfinding loops? As he's pointed out, he feels that he is more qualified than most of us to discuss multithreading, and that he might be able to do a decent job with it. So why not contact Toady directly to see how Aha can help?

I have started on a proof of concept project. Since I will be working on it mostly on weekends it will be some time before I have something to show.
Logged
tail -f -n 10 df_27_176_38a/gamelog.txt

crazysheep

  • Bay Watcher
  • [PREFSTRING:fluffy wool]
    • View Profile
Re: Spin the pathfinding off to other threads.
« Reply #23 on: June 30, 2012, 09:05:09 pm »

In that case, you might want to update this thread once you get the proof of concept ready :)
Logged
"Don't be in such a hurry to grow up, for there's nothing a kid can't do."

bombzero

  • Bay Watcher
    • View Profile
Re: Spin the pathfinding off to other threads.
« Reply #24 on: June 30, 2012, 09:11:28 pm »

Yeah I would strongly suggest having something to show for it any time you imply something is easier and you can do it better then toady around here for a few reasons.

1) you sounded pretty condescending.
2) whether or not anyone admits it, there are a lot of fanboys here.
3) it makes you look like 'that guy', you say you can do something better but you have no evidence of that claim.
Logged

aha

  • Bay Watcher
    • View Profile
Re: Spin the pathfinding off to other threads.
« Reply #25 on: July 02, 2012, 08:21:11 am »

1) you sounded pretty condescending.
Thanks:)

I have finished implementing a version of a* pathfinder that can find a single path from opposite corner of a 300^3 cube in about 5ms - on one thread. 5 threads(my rig has 6 cores) running simultaneously reduce the speed to 6-7ms, so the worst case scenario with this map size(6x6 embark) is about ~  1.2 ms per path.
I know that it's not great, but it's a first time I've done path finding of any kind and there is still some room for optimisation:
a) I don't have a very efficient implementation of a double-linked list for maintaining sort order of F in A* open list at the moment and seek times in closed/open lists are not great.
b) still testing the appropriate heuristic functions for calculating the H value. Manhattan is ok. Diagonal a bit better, but I haven't turned on the area restrictions yet (variable G for a step) - this will change H - G balance and will need to rerun all the tests with these on. Also need to implement that Quake fast sqrt for Euclidian and see if it fares any better.
c) I have some problems maintaining a very large map in the memory, I have implemented a partitioned sparse vector (index = x + y<<10 + z<<20, partition = index/((maxindex/partitionCount +1))) for holding the data, but it will need more improvements before I can realistically maintain the  maximum size local area map ( (48*16)^3). Good thing is that random and neighbouring cell access is very fast.

Now its time to do the caching. There is no reason to recalculate paths all the time. I will reuse as much of the pre-calculated paths as possible. Path calculation will also use the cache, so if its gets to a point where the path can be completed with a pre-cached one it will do so.

Next steps
caching
  a) Cache full path and all its subcomponents. Idea is that entities will reuse cached paths. Paths will be cached with the usability flags (flier, walker, jumper, climber) so a dwarf wouldn't try take the same one an eagle does.
  b) Invalidate cached paths when a set amount of ticks have elapsed (f(path length) - longer paths decay faster). Probably read repair consistency check, unless memory or seek times prove problematic.
  c) Invalidate paths on node and adjacent node update. Path should be invalidated when a node on it becomes unpassable/passable. It won't account for a shorter route suddenly becoming available, but those will be taken care by tick based invalidation unless I think of something better. Async repair.
  d) Entity movement feedback - should entity find that path can't be followed any more, the path will be cleared from cache. Write/Async repair.

visualiser/simulator
  Simple visualiser for simulating movement of entities on a map.

df hookup step 1 - live map data from df
    a) Will likely expose the map from dfhack via a memory mapped file for start.
    b) map block update events tied into the path cache to invalidate calculated paths where appropriate.

df hookup step 2
  h2xor DF to
    a) change the pathfinding loop to wait for paths from the external pathfinder <-Will need help with this one.
    b) give feedback on the path (entity can't use path/completed the path, etc.)
 

future
  local avoidance
    fast checks for a 3-step path bypassing the node blocked by another entity.
    right-of-way
       nobles newer give way to others
       dwarf might elect to wait a tick or 2 if way is blocked
       pets might be kicked aside
    climbing
      nimble dwarves who don't carry stuff might climb a zlevel
    jumping
      nimble dwarves not carrying crap might jump down a zlevel
    swimming
      swimmers will go through deep water

Logged
tail -f -n 10 df_27_176_38a/gamelog.txt

JanusTwoface

  • Bay Watcher
  • murbleblarg
    • View Profile
    • jverkamp.com
Re: Spin the pathfinding off to other threads.
« Reply #26 on: July 02, 2012, 05:52:52 pm »

Now its time to do the caching. There is no reason to recalculate paths all the time. I will reuse as much of the pre-calculated paths as possible. Path calculation will also use the cache, so if its gets to a point where the path can be completed with a pre-cached one it will do so.
If you're trying to prove that pushing pathfinding onto a seperate thread pool will speed up Dwarf Fortress, I would suggest only doing that (at least at first). Otherwise it's uncertain whether any speedup you gain is due to what you're suggesting or another factor.

df hookup step 2
  h2xor DF to
    a) change the pathfinding loop to wait for paths from the external pathfinder <-Will need help with this one.
    b) give feedback on the path (entity can't use path/completed the path, etc.)
I'm about 80% sure that you're just not going to be able to do this without actually decompiling DF (at least not easily). Utilities like DFHack that already exist to interface with DF are not capable of modifying running code on the fly nor redirecting code flow, at least so far as I'm aware. And that's pretty much the state of the art so far as hacking DF goes.



If you really want to prove that this idea is feasible for DF (and that's the most important bit right there), I think that your best bet would be to write a parallel program that can more or less mimic what DF has to do so far as path finding goes in a completely single threaded manner. Then rewrite your code from there to deal with handing off control to the thread pool.

Because, realistically, that's what's going to have to happen. DF has almost a decade (if not more, I think work started around 2004?) of work put into it. Retrofitting a new system, particularly one that deals with concepts the programmer hasn't dealt with before (multithreading) is not at all a trivial task. That's the main problem people are having it.
Logged
You may think I'm crazy / And I think you may be right
But life is ever so much more fun / If you are the crazy one

My blog: Photography, Programming, Writing
Novels: A Sea of Stars, Confession

thisisjimmy

  • Bay Watcher
    • View Profile
Re: Spin the pathfinding off to other threads.
« Reply #27 on: July 03, 2012, 12:36:05 am »

I have finished implementing a version of a* pathfinder that can find a single path from opposite corner of a 300^3 cube in about 5ms - on one thread.
[...]
I know that it's not great

Actually, without knowing more details about the tests, we have no way of knowing how good that is.  For one, the speed of A* pathfinding will vary drastically depending on what kind of obstacles are on the map.  A worst case scenario would look something like this:
Spoiler (click to show/hide)

In a map like that, A* will search almost every open tile before finding the path.  On the other hand, if there's a direct, straight-line path between the start and goal, A* will be super fast.  Also, if you have something like this:
Spoiler (click to show/hide)
A* will again be super fast.  That's because most of the map is filled in and there are so few open tiles for it to search.

a) I don't have a very efficient implementation of a double-linked list for maintaining sort order of F in A* open list at the moment and seek times in closed/open lists are not great.

Usually you would use a heap for the open list.  This will let you pop the minimum value in O(log(n)) time.  I'm not sure what your current system is, but if it takes linear time, then using a heap should give you a much better performance boost than any of the micro-optimizations.

Now its time to do the caching.

Caching is a whole other topic.  I would expect making a good caching system is a lot harder than just multithreading pathfinding.  On the other hand, the potential performance improvements are likely greater. 

In the caching system you described, would a dwarf be able to use a cached path if the start and end tiles weren't exactly the same as what's in the cache?

In any case, back to multithreaded pathfinding.  Measuring the performance characteristics of multithreading pathfinding in your demo will not tell you much about how it will perform in DF.  While I agree that pathfinding is something that would probably be easy to parallelize in DF, we don't know whether it would actually improve performance.  There are a lot of factors to consider, such as:
  • Is pathfinding largely responsible for slowing DF down?
  • Are there usually multiple pathfinding tasks per step?  If you had 100 dwarves, and each one, on average, had to pathfind every 10 seconds, DF would only have to compute about 10 paths per seconds.  At 100 FPS, that's one path every 10 frames.  If there aren't multiple paths required per frame, you have nothing to parallelize.
  • Of those pathfinding tasks, how many are long running? A* will find easy paths almost instantly.  There's no benefit to parallelizing these.  Only the roundabout paths will be slow enough to benefit.
  • Is the algorithm limited by CPU cycles or something else?  Maybe memory access is taking most of the time.

The only sure way to see if parallelizing pathfinding would improve performance would be to actually implement it in DF and measure the results.
Logged

Maklak

  • Bay Watcher
    • View Profile
Re: Spin the pathfinding off to other threads.
« Reply #28 on: July 03, 2012, 04:18:58 am »

When people say there were other pathfinding threads, they were serious. There was at least one 20+pages long with links to articles. Someone even wrote a webpage that demonstrated various techniques for path finding. Seriously, go look for that stuff. I believe there was a (failed?) DF pathfinding project already.

You don't need sqrt for euclidean metrics. Just compare the sums of squares. For arg>=0, sqrt(arg) is strictly increasing, therefore:
Let a, b, c > 0
sqrt(a*dx1^2 + b*dy1^2 + c*dz1^2) > sqrt(a*dx2^2 + b*dy2^2 + c*dz2^2) if and only if:
a*dx1^2 + b*dy1^2 + c*dz1^2 > a*dx2^2 + b*dy2^2 + c*dz2^2

Toady One said that there are some places where fork - join multithreading could help. I believe it is on his to-do list, along with x86-64 version, a long list of planned features, all those bug fixes on mantis and most of the things in ESV. It is just that it is a lot to do and DF's programmer has a strong preference for dealing with things that are fun to him first, such as adding new stuff, then doing some low hanging fruit bugfixes and only occasionally doing something else.

The pathfinding itself could likely benefit much more from further optimisations than multi-threading. Like thisisjimmy said, there is no guarantee that multiple instances of pathfinding run every frame. There are, however, some clever methods to accelerate A*. There were some articles linked on this forum about hierarchical pathfinding and some method that marks some tiles as hot-spots, then works on a graph of 'line-of-sight' visible hotspots.
Logged
Quote from: Omnicega
Since you seem to criticize most things harsher than concentrated acid, I'll take that as a compliment.
On mining Organics
Military guide for FoE mod.
Research: Crossbow with axe and shield.
Dropbox referral

Abysium

  • Bay Watcher
    • View Profile
Re: Spin the pathfinding off to other threads.
« Reply #29 on: July 03, 2012, 05:09:06 am »

external program to make it run on cores? do it, I dare you!
:D
Logged
Pages: 1 [2] 3 4