Print

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

[Shades]

Within an invocation of A*, I don't see how you're going to get any parallelism at all though.  You're going through a priority queue one element at a time; you can't get much more sequential than that.  With a hierarchy I suppose you could do something, but it wouldn't be entirely straightforward.

There isn't much point doing it within the A* invocation if you ask me. Better to leave is as just able to calculate multiple routes at a time.

The problem is figuring out how to write the code that calls the pathing code so that it knows to do lots of path queries at once.

You don't actually have to worry about this either, in fact it's more likely to be included by Toady if he doesn't have to refactor a lot of his code to do it. The trick here is to take advantage of the fact a single creature will request it's path multiple times before it gets to it's target.

On the first request you return a quick, possibly wrong, where to go next style path and spawn off your A*. Later requests the A* will have hopefully finished and you can pass the remaining route (and spawn off the recalculation for next time). It's not perfect as technically the dwarf will follow a blocked route for a short time, we return the last route not a current one, but it's probably good enough. If not then validating a route is very quick to do.

[Footkerchief]

Within an invocation of A*, I don't see how you're going to get any parallelism at all though.  You're going through a priority queue one element at a time; you can't get much more sequential than that.  With a hierarchy I suppose you could do something, but it wouldn't be entirely straightforward.

Well, you can go bidirectional at least, right?

edit: here we go.

Here's a PDF of the second paper mentioned, couldn't find a free copy of the first.

[Starver]

could gain lots by pathing in background of queued but not yet chosen jobs...the relevant portion anyway (from material to workshop, say, and leaving the dwarf-to-material until a dwarf takes on the job)

Possibly, but unless there's a minimal number/closely packed set of raw material items, what's the probability that the precalculated material-to-workshop path is relevent to the best accessible raw material for whatever worker picks up that task?

Yes, if there's just one worker, currently in the workshop, then its likely that the closest raw item to the workshop is the closest to the worker when they pick it up, but you have to consider drink/food/socialising/complaining breaks, other workers taking over production just after wandering out into the wilderness for a game of hide-and-seek, etc.  And we know the little buggers tend to mess us around enough with that sort of thing already.

[Rose]

this is all fascinating, but I have nothing to contribute.

I'm just posting here so I get updates.

[qwertyuiopas]

Perhaps have a single low-priority thread running searches for pathing optimizations by seeking out areas where an abstract zone may be placed, like a TCZ, SPZ, or anything else that anyone theorizes may help?

[Shades]

Perhaps have a single low-priority thread running searches for pathing optimizations by seeking out areas where an abstract zone may be placed, like a TCZ, SPZ, or anything else that anyone theorizes may help?

To be honest the really simple change of allowing pathing in the 'background' to the main DF thread would improve performance significantly for the majority of players without being a major amount of work. I'd suggest do that first then improve later. (following the "there is always time to improve later" mantra)

[Starver]

To be honest the really simple change of allowing pathing in the 'background' to the main DF thread would improve performance significantly for the majority of players without being a major amount of work. I'd suggest do that first then improve later. (following the "there is always time to improve later" mantra)

My doubts about this are related to the fact that when I run DF, it's machine speed rather than framerate capping that limits the timely progression.  Maybe if the routing could be optimised to the extent that it doesn't freeze the world when  immigrants or invaders are about to enter the world (for example... I've always assumed that the mass path-calculation is what's caused the freeze, just before the relevent notification comes up) then maybe I would have free cycles to spare to do some speculative "just in case" path searching as opposed to the "just in time" that takes exactly as long as it needs to, anyway, because the world can't help but wait[1].

But unless you have got that luxury, adding the overhead of a management process for multithreading[2] and adding in the pursuit of speculative not-necessarily-usable calculations (rather than the not-eventually-usable calculations already inherant in nature of path searching, and which caching/etc should help to avoid or keep to avoid later unnecessary redoing) seems to me to be a less than optimal approach, overall.

But that's an impression, only.  I'm probably misrepresenting the process.


[1] The exception to this general rule is the occasional notification of things that should only be happening while the world is running (e.g. strange moods and births) that interupt the world-frozen resource management phases.  Of course, these are rare enough events that it's hard to replicate and properly analyse.  I've always assumed that there's already a multithreading queue for some things, that initiated an enquiry just before changing to the management mode and continue for a second or two in the background to give the new baby its character, etc, and then announcing the arrival.  But then I'm not too familiar with Toady's code.

[2] Noting my comment in the above footnote that there may already be one in place... Could that be used for minimal extra overheading?

[Thief^]

this is all fascinating, but I have nothing to contribute.

I'm just posting here so I get updates.

You can just press the "notify" button instead of "reply" and you get updates without having to have a post in the thread. Try that in future.

[Shades]

stuff

I think you misunderstood my post, I wasn't talking about doing any extra/speculative pathfinding, only to 'background' the current pathfinding so it doesn't tie up main game thread. Like you say when a number of new dwarfs enter the map there is no reason for the game to freeze.

You can just press the "notify" button instead of "reply" and you get updates without having to have a post in the thread. Try that in future.

I have to say I don't find the notify display of threads anywhere near as nice as the one you get for threads you have replied to.

[Nadaka]

I have done an optimization job on a real time P2P live video streaming service that transformed its startup time from more than half a minute to about 4 seconds, 2 of those were buffering by the media player. Thats a 15 fold or more performance increase. That was difficult, but we didn't have to go to assembly or c, and we only did a few dirty tricks, most of it was organization to work less but still get results.


There are a couple important things you can do to optimize performance.
1: work less.
2: work smart.
3: do more work at a time.

From what I have seen, you guys are trying to work smart, improve on A*. Unfortunately there are only 3 ways to do this from an algorithmic perspective. 1: produce an estimation heuristic closer to the shortest path using domain specific knowledge. 2: reduce your search space by combining nodes. 3: accept paths that are less than ideal, typically done by having an estimation heuristic higher than the shortest path.

Parallelization is doing more work at a time, its maximum performance multiplier is a little less than your number of cpu cores. However, it is low hanging fruit, its minimum performance multiplier is also a little less than your number of cpu cores. Parallelization can provide a benifit more than your number of cores with special planning. For instance, you don't need to wait for all paths to be calculated to move on to the next step, you can keep calculating new paths while you are consuming the first paths generated.

Working less usually produces the greatest returns. Here is an example, in a 2x2 single level map, hypothesize a path 40 tiles long ( a little less than half the maps width) for each step taken the path is recalculated. For each step taken one tile somewhere on the map becomes blocked (that is a fairly high rate of construction imo). Each tile has a 1 / (9216 - step) chance of becoming blocked. The chance that that tile is in the remaining path is (40 - step) / (9216 - step). There is only an 8.9% chance of the path becoming blocked while the path is being run. Caching that path will save you 39 path calculations 91.1% of the time, It will also save you 38 path calculations more than 99% of the time.

For paths with an average length as short as 5 or 6 tiles, caching should produce at least equal gains compared to improved algorithm or multi-threading, and if the average length is longer, it will become progressively more effective.

[numerobis]

I also make stuff fast for a living, and I have to say, parallelizing the solution to one problem is rarely low-hanging fruit.  If you can rewrite things to that you need to solve the same problem repeatedly, and you can spawn off a bunch of threads to do it, then it can be pretty easy -- assuming that "rewrite things" is itself easy.

Your idea for a massive speedup is how A* is pretty much always implemented in a "real-time" game, and even in a number of turn-based games.

[numerobis]

Within an invocation of A*, I don't see how you're going to get any parallelism at all though.  You're going through a priority queue one element at a time; you can't get much more sequential than that.  With a hierarchy I suppose you could do something, but it wouldn't be entirely straightforward.

Well, you can go bidirectional at least, right?

Bidirectional, true.  There's a common issue that your two paths may not usefully link up (e.g. the shortest path through a rectangle -- do you first go diagonally, then up, or first up, then diagonally?  Making sure both paths meet somewhere is not necessarily easy, but maybe there's tricks.)

Here's a many-processor A* paper much more recent than that vintage one you found, with a bunch of references: http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.50.6224&rep=rep1&type=pdf
I have to note wryly that the authors have searched far and wide, and discovered that they have written half of the important papers on the topic.

[Nadaka]

I also make stuff fast for a living, and I have to say, parallelizing the solution to one problem is rarely low-hanging fruit.  If you can rewrite things to that you need to solve the same problem repeatedly, and you can spawn off a bunch of threads to do it, then it can be pretty easy -- assuming that "rewrite things" is itself easy.

Your idea for a massive speedup is how A* is pretty much always implemented in a "real-time" game, and even in a number of turn-based games.

Generally I agree with you about parallelization rarely being low hanging fruit if you don't start developing a solution with it in mind. However, for the problem "produce a lot of paths quickly, using a standard implementation of A*" it is pretty low fruit.

[Footkerchief]

Bidirectional, true.  There's a common issue that your two paths may not usefully link up (e.g. the shortest path through a rectangle -- do you first go diagonally, then up, or first up, then diagonally?  Making sure both paths meet somewhere is not necessarily easy, but maybe there's tricks.)

It appears someone found a way of handling it.  Can't find a free version of the article as usual.

[Impaler[WrG]]

Most home multi-core systems are around 2 or 4 cores and though a jump to 8 cores is inevitable it's not going to happen for a while.  This means your maximum performance gain is around a factor of 4, realistically a factor of 3. 

Better algorithms utterly blows that out of the water, improvement can be factors of 10 for an optimized hierarchical pathfinder vs an optimized non-hierarchical approach, all the papers I've read confirm this.  Add a cache on top of that and we can probably get another factor of 10 improvement. 

I'm going to focus on algorithms for now but will try to keep each path search isolated so the potential exists for parallelization in the future.  One thing in particular that were already doing is storing the parent node data produced in each search outside of the grid.  Most pathfinders just write this to the grid their searching on in a 'throw away' layer that overwritten with each search, clearly a solution which will fail if multiple searches are occurring over the same space.  Theirs also the issue of modifying the grid, as the current implementation will never be modifying the grid and searching at the same time theirs no issue.  But if multi-threaded theirs would need to be a signaling system to keep searches and grid modifications from colliding, grid modifications would probably need to be handled singularly as well.