Print

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

[Draco18s]

##.|#..
##.|#..
##.|###
-------
###|...
..#|##.
...|...

Ah, thanks for the fix resulting in what I'd computed.  I'd originally had a distance of 7, that that too ignored diagonals.

[qwertyuiopas]

27 is numpad's 9 times 3(up, down, and same-z)

HOWEVER, 5 + same-level = unchanged, making the true number 26, or solving the "stay in place" question.

Clarification:
By
"solving the "stay in place" "

I meant that it would make not moving a "valid" direction, so such concerns wouldn't be a problem.

On the other hand, it might be a good idea that, if all 27 directions are included, you ensure it can't "explore" what happens if a creature doesn't move, how it affect's it's path. Some very possible infinite loops there, unless not moving is automatically discarded by the pathing, and that makes the pathing check for moving to the source tile from it utterly worthless...

[alway]

I haven't read through the whole thread, its a bit long... But have you tried this approach?
Start with your basic searching or whatever you decide is the fastest method. Then, record where dwarves move and create a seperate list for this. The first list will have all the world areas, and the second will have areas which dwarves have recently walked on. The second list will have some sort of counters assigned to the areas which will count down, and when the number reaches zero, the area will be removed from the list. This will make the list into a sort of short term memory for where dwarves have walked recently. This assumes your dwarves will move in relatively the same areas and pathways a majority of the time, which unless they are fleeing from goblins is a correct assumption. For example, most forts have a main hallway through which dwarves will walk. Using this method, the second list will very quickly acquire paths from common tasks, such as food stockpile to dining hall or storing mugs in their stockpile. This second list will be checked first for a path from point a to point b, and since it will be much smaller than the main world list it should take quite a bit less time to calculate a heuristic for. Another benefit is if you have dwarves running through a massive stockpile room. Take for example one of my forts which has a huge 1 z level room carved out which is probably about 100 by 100 in size and filled with stockpiles. Dwarves running from room entrance A to room entrance B will almost always take the same path or only 1 or 2 squares off the same path. So rather than generating a heuristic for the whole room, the path will be charted once, then followed by all further dwarves to come down that particular path with a much smaller list of areas over which the heuristic must be done. There are some problems with the method, such as the paths being potentially inefficient and doubling back as well as the extra processing done to make and maintain the 2nd list, and they may or may not cripple this technique.
Knowing C++ decently enough to try out this approach, I think I may start trying to implement such a search tommorow...

[Impaler[WrG]]

This assumes your dwarves will move in relatively the same areas and pathways a majority of the time, which unless they are fleeing from goblins is a correct assumption.

While it is generally true that new paths will be in the same areas as past paths this is  to use when finding a path.  We can't exclude low-traffic area from any search nor can we use it as a valid heuristic.

As for pathing across that large cavern this is what a hierarchical approach is designed to achieve.  Pathing is more efficient over the fewer number of nodes and its possible to store paths inside the zone and them link them up.  This is all covered in the HAA* paper at the start of the thread (I should copy it too the first post to make it more obvious.)

Now that the basic pathfinder is up and running I'll be working on the logging, profiling and creating a more full test suite.

[Starver]

On the other hand, it might be a good idea that, if all 27 directions are included, you ensure it can't "explore" what happens if a creature doesn't move, how it affect's it's path. Some very possible infinite loops there, unless not moving is automatically discarded by the pathing, and that makes the pathing check for moving to the source tile from it utterly worthless...

I would have thought that any state-sensitive (all of them?  by one means or another?) pathing algorithm would discount a movement of "no movement" on the same basis as moving back to a previously visited position is discounted.

i.e. on arrival at a tile (or simulated arrival, during a path-finding), the tile is marked as "visited", and while it might not yet have the "if you were to go here, it would be X paces to your destination" details (though it would have "Y paces from your origin" ones) attempts to revisit next turn or by moving onwards and back, or onwards, sideways and diagonally back, or any other combination would know it was an invalid new position.

Speaking generically for all algorithms, as there'd be different ways to implement this, e.g. pulling from a stack of unvisited locations all possible adjacent locations, or flagging the array of all locations, and those methods not strictly breadth-first (by cumulative weighted distance, if applicable) have the opportunity to interogate and re-allocate to themselves previously visited tiles with new, more optimal routing (and then have to worry about updating the visiting points following onwards from the original, longer, earlier discouvered route).  But the latter could never apply to 'same tile, no movement' moves, without some form of 'negative weighting' (which, transiently, could be used for certain very special circumstances, but is outside the scope of the DF pathing concerns, at least right now).

Of course, the caveat is the aforementioned (predictably) dynamic environment, where waiting for a door to open allows a quicker transit than keeping on moving around the longer route.  If standing still were still disallowed, then hopping between two or more nearby cells could be 'allowed' as a movement.  Either way, one has to assume that a state-sensitive system would essentially deal with this as "entire world, with 'gate' opening in N moves" state on one turn and "entire world, with 'gate' opening in N-1 moves" as the next (and differing) state, thus treating either standing still or movement as also moving to T+1 in the time dimension, regardless of overall effect.  And have to have some other rather more prosaic method of not emulating an XYZ loop/useless return even while progressing into infinite T, all of which would obviously mean resource hogging keeping track of an XYZT visited array compared to a simple XYZ array, roughly proportional to the total T allowed before a 'time out' limit is applied, or other solution found.

IYSWIM.

[shadow_slicer]

I would have thought that any state-sensitive (all of them?  by one means or another?) pathing algorithm would discount a movement of "no movement" on the same basis as moving back to a previously visited position is discounted.

As far as I know, this is correct.

Of course, the caveat is the aforementioned (predictably) dynamic environment, where waiting for a door to open allows a quicker transit than keeping on moving around the longer route.  If standing still were still disallowed, then hopping between two or more nearby cells could be 'allowed' as a movement.

Actually, I would probably not implement waiting in the pathfinder. I would adjust the cost function so that the cost of an edge was related to the traveling time. This means that traveling through a door that is about to open includes the time cost of waiting for it to open. Basically, if the cost of every tile is 1, and there's a door that will open in T steps from now, 5 tiles away from here, the cost of going through that door should be (T-5). This will add significant complexity to the cost function and will require doors and other predictable close-able things to be within their own zones (and carried all the way up the hierarchy). Anyway, we probably won't support anything like that for a while (if ever).

Also, Impaler has gotten the connectivity rendering working on the current Khazad svn head.

Spoiler: Screenshot (click to show/hide)

This shows roughly the same path as the previous image, only with the connectivity map displayed. It's pretty neat to play around with, though it probably doesn't look like much in the picture. On the left side it you can see diagonal lines, representing ramps going up to a higher level (not shown), and staircases with vertical lines, showing only vertical traversal. If you look closely you can see the 3x3 bedrooms on the mid-right side.

[Nadaka]

27 is numpad's 9 times 3(up, down, and same-z)

HOWEVER, 5 + same-level = unchanged, making the true number 26, or solving the "stay in place" question.

Clarification:
By
"solving the "stay in place" "

I meant that it would make not moving a "valid" direction, so such concerns wouldn't be a problem.

On the other hand, it might be a good idea that, if all 27 directions are included, you ensure it can't "explore" what happens if a creature doesn't move, how it affect's it's path. Some very possible infinite loops there, unless not moving is automatically discarded by the pathing, and that makes the pathing check for moving to the source tile from it utterly worthless...

no movement is not a valid concept in A* unless your algorithm is modified to predict the location of moving obstructions. However, dwarf fortress does not really have these kinds of moving obstructions.

[Starver]

Actually, I would probably not implement waiting in the pathfinder. I would adjust the cost function so that the cost of an edge was related to the traveling time. This means that traveling through a door that is about to open includes the time cost of waiting for it to open. Basically, if the cost of every tile is 1, and there's a door that will open in T steps from now, 5 tiles away from here, the cost of going through that door should be (T-5).

You'd need to modify the algorithm following the calculated path to avoid a juggernaut-like rush up to the not-yet-open pathway only for it to trigger on the current impassibility.

That is, if it doesn't use a locally suboptimal, but not actually looping, time-wasting path in order to not arrive there in time, but in my mind it's like arriving at a T-junction of 1-wide tiles, where travel to the left (+wait) would get through the door, but travel to the right is a (currently) guaranteed-but-lengthier route.  If it's a two-wide corridor, then you might be able to generate a saw-tooth traversal along it to 'spend the time', if you could get past the non-optimality of the journey up until the arrival at the transient obstruction.

(Of course, the model could be similar to that of the clustering of tame animals against pet-impassable doors.  Although that's a different "vague pathing" method, and I assume related to invader pathing in both "attack" and "flee" mode insofar as heading for "somewhere inside" and "virtually any map edge" respectively for said invaders.)

[...] Anyway, we probably won't support anything like that for a while (if ever).

Yes, I'm being a bit speculative in the above.  (A bit?  Typical English understatement, some might contend.

Also, Impaler has gotten the connectivity rendering working on the current Khazad svn head.

Because I haven't commented (I think...  If I have, I've slept since): Nice.


Oh, and @Nadaka: Some might say "Yes we have, bridges and floodgates and things", but I know you mean (as I've previously qualified) predictable bounding/unbounding features.

Spoiler: More speculative overimagination which has not much to do with the pathing situation, at least directly (click to show/hide)

You know, I'm still thinking (was it this thread, or another?) about the concept of a DF paternoster implementation.  Two tiles side-by-side, one up, one down, defined across multiple Z-levels, with power source fed in.  For balancing, 'cabs' or similarly defined rooms on nonadacent Z-levels up and down the chain (so that there isn't always a cab at any particular floor, maybe one-in-two, maybe one-in-five, maybe fixed maximum cabs, even when extending the shafts?) but give a transit speed between floors greater than a typical hauling dwarf.  If able to enter a car/wait for entry to a car then board, it's an assisted movement (at least while power is on) and an improvement to haulage, but the wait between the cars (and mechanics necessary to build) makes it an inefficient casual method.  Also can imagine a 'dunking paternoster' where it submerges an unsuspecting rider.  Possibly as an offshoot of one which is turned off to trap a rider in a cab (then prepare the flood an start them on their journey again).  In fact, imagine herding a set of beasties into cabs, one at a time, so as to redispense them out again (at source level or wherever else there is an exit) when the power goes on.  With a pressure-plate initiated power source linkage I could imagine a stock of War Elephants being steadily unleashed upon invaders, or untamed megabeasties let into the training pens.  Well, there are probably better ideas than that.

Back to the predictable location of moving obstructions, I'm also minded of the trap-laden routes of the kind most memorably parodied (to me, at this moment in time) in the film Galaxy Quest.  Also the Five Doctors-style "walk only on certain tiles" thingy, among various other versions of that trick.  Actually, I suppose the Indianna Jones And The Last Crusade examples are better, if you could imagine unifying the timing (Penitant Man) and positioning (In The Word Of God) problems.  But I waffle.  Again/More.

[Impaler[WrG]]

This will add significant complexity to the cost function and will require doors and other predictable close-able things to be within their own zones (and carried all the way up the hierarchy). Anyway, we probably won't support anything like that for a while (if ever).

Actually that's exactly what I was thinking of doing, The client would have to report these locations, then these would indeed be kept out of the zones.  But I don't think they can be carried all the way up, I'd merge normal nodes until a normal node has only a single link to a door node then allow merger.  This makes it really simple to later sever the connection and allows the high level graph to compress down as efficiently as possible.

[Footkerchief]

I couldn't find any mention in this thread, so apologies if the answer is blindingly obvious: would this client-server communication be synchronous or asynchronous?  The question came up in a performance-related thread.

[Impaler[WrG]]

Synchronous and single threaded currently, when the client sends a map change or a path request execution passes to the server (the pathfinder code) and has to return before the client can continue.  While multi-threading is interesting I'm not up too speed on it and I think a lot of performance can be squeezed out by optimizing the actual path finding code, perhaps far more then just multi-threading the old code.

[CobaltKobold]

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)

[Blacken]

Synchronous and single threaded currently, when the client sends a map change or a path request execution passes to the server (the pathfinder code) and has to return before the client can continue.  While multi-threading is interesting I'm not up too speed on it and I think a lot of performance can be squeezed out by optimizing the actual path finding code, perhaps far more then just multi-threading the old code.

Optimizing your proposed pathing doesn't mean it must remain single-threaded, though. I haven't looked at any of your code, just skimmed the thread, but it seems to me that the closer to shared-nothing you can get (minimizing any critical execution segments) in a single-threaded iteration that you can get, the easier you can take advantage of a multithreaded option later.

Talking about big-Oh when multithreaded stuff is involved gets weird, but in a perfectly shared-nothing system you can approach (never reach, of course, but approach) a 1/n multiplier to your entire execution time. That strikes me as being something that might be very, very useful down the line.

I'm not an algorithms guy, but it seems intuitively that you'll fairly quickly reach a point of diminishing returns in terms of the actual algorithm, whereas spreading it across multiple cores can reduce it further. It's not an either/or proposition.

(There's also graph knitting and all sorts of other stuff that can create a performance/accuracy tradeoff, but I'm sure that's already come up. )

[Nadaka]

Synchronous and single threaded currently, when the client sends a map change or a path request execution passes to the server (the pathfinder code) and has to return before the client can continue.  While multi-threading is interesting I'm not up too speed on it and I think a lot of performance can be squeezed out by optimizing the actual path finding code, perhaps far more then just multi-threading the old code.

Optimizing your proposed pathing doesn't mean it must remain single-threaded, though. I haven't looked at any of your code, just skimmed the thread, but it seems to me that the closer to shared-nothing you can get (minimizing any critical execution segments) in a single-threaded iteration that you can get, the easier you can take advantage of a multithreaded option later.

Talking about big-Oh when multithreaded stuff is involved gets weird, but in a perfectly shared-nothing system you can approach (never reach, of course, but approach) a 1/n multiplier to your entire execution time. That strikes me as being something that might be very, very useful down the line.

I'm not an algorithms guy, but it seems intuitively that you'll fairly quickly reach a point of diminishing returns in terms of the actual algorithm, whereas spreading it across multiple cores can reduce it further. It's not an either/or proposition.

(There's also graph knitting and all sorts of other stuff that can create a performance/accuracy tradeoff, but I'm sure that's already come up. )

I am an algorithm and optimization guy.

For A* each path needs to read edges from the map and store them in a queue, and that will be distinct for each path. The only potential conflict might be in the estimation algorithm and that will vary from implementation, but probably wont have any conflict anyway.

The overhead of multi-threading in this case will be minimal in terms of performance, resulting in a nearly 2 to 4 fold performance improvement on modern cpu's and negligible or avoidable performance cost on single core machines.

The overhead of multi-threading in terms of developer cost will also be minimal as almost no modification to the algorithm is required.

However, since the goal is to and optimize and measure the time to calculate each path, multi-threading in this way will be counterproductive to those stated goals.

A* can also use parallelism for a single path as the evaluation of each choice in its edge queue is independent. Each thread will be adding and removing from the queue, so that queue will need to be synchronized. Each task is relatively trivial, and so spawning one thread per task will not be efficient. Instead you would have a number of worker threads processing edges off the queue while your main thread waits for the workers to finish.

This will be less efficient that per path parallelization, but should give you somewhat less than linear speedup per core.

[numerobis]

You can often get important speedups by making part of the data stored for the search be stored permanently in the grid, rather than needing to store a mapping from the grid squares to the data you need for them in a given search.  But that does get in the way of parallelization.

Assuming you don't do that, then independent path queries are indeed perfectly independent -- just read-after-read dependences that don't count for much.  The parallel depth is the length of the longest path query, and everything is work-efficient.  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.

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.