Print

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

[random51]

Might have been mentioned before, but in terms of pathfinding performance in DF, pathfinding for invisible creatures applies a HUGE performance hit.

[Shades]

Might have been mentioned before, but in terms of pathfinding performance in DF, pathfinding for invisible creatures applies a HUGE performance hit.

Do we know that? I've not seen anything to show that. Why would a few extra units cause so much more pathfinding because they are invisible than a siege causes?

I agree the game slows down as there are more units (but it does with more rocks too).
Also I'll agree breaking into the fun stuff causes it to slow down as well.

But before we actually try and build all kinds of fun, paralleled processed, highly optimised and specialised super pathfinding system shouldn't we actually run some sort of test?

[random51]

Might have been mentioned before, but in terms of pathfinding performance in DF, pathfinding for invisible creatures applies a HUGE performance hit.

Do we know that? I've not seen anything to show that. Why would a few extra units cause so much more pathfinding because they are invisible than a siege causes?

I agree the game slows down as there are more units (but it does with more rocks too).
Also I'll agree breaking into the fun stuff causes it to slow down as well.

But before we actually try and build all kinds of fun, paralleled processed, highly optimised and specialised super pathfinding system shouldn't we actually run some sort of test?

I did test.  All it takes is a door. Close the door, my system runs fine, open the door and it drops down to almost nothing.

Did the same test with a siege which has even more units and the door test produces far  less of a change in FPS.

Of course I'm assuming it is because they are invisible. It could just be their red noses and big feet.

[Shades]

I did test.  All it takes is a door. Close the door, my system runs fine, open the door and it drops down to almost nothing.

Okay so there should have been little difference other than scope of search space between those two states.

Did the same test with a siege which has even more units and the door test produces far  less of a change in FPS.

Of course I'm assuming it is because they are invisible. It could just be their red noses and big feet.

However this makes no sense at all if it was purely pathfinding a siege should be as bad. Unless the invisible demons where fliers? but even then they should probably be able to path to a dwarf before needing to fly much.

[random51]

Yeah, they were fliers.  Perhaps it is the flying and not the invisibility, that would make more sense.

[PencilinHand]

I did test.  All it takes is a door. Close the door, my system runs fine, open the door and it drops down to almost nothing.

Okay so there should have been little difference other than scope of search space between those two states.

Did the same test with a siege which has even more units and the door test produces far  less of a change in FPS.

Of course I'm assuming it is because they are invisible. It could just be their red noses and big feet.

However this makes no sense at all if it was purely pathfinding a siege should be as bad. Unless the invisible demons where fliers? but even then they should probably be able to path to a dwarf before needing to fly much.

The answer is special cases.  WE don't know and can't test the actual differences between "invisible" creatures and visible creatures.  Only Toady knows.  There is probably something in the code that a profiler(which Toady recently started using) would show is causing a performance bottleneck.  The detect test could be the source of the slowdown for all we know.  Kind of like how the way a forbidden door doesn't stop pets from trying to path through a door but does stop the pet from going through it with the end result being a pet that is constantly trying to repath through the door.  That is a special case that we can understand because it is visible and obvious if you are paying attention.  It is thought that the "invisible creature" slowdown cause might be similar to the pet/forbidden door problem.

That pathfinding is a major source of slowdowns is not an assumption.  To test this, make a simple fort and turn weather, economy, temperature, and invaders off, grow the fort to 200 dwarfs then remove all jobs so they are all idle and set a 200+ item stockpile to be moved from one place to another.  You will observe a significant difference in the FPS between 200 idle dwarfs and 200 dwarfs hauling things even a short distance, and people have recorded this.  I personally did a similar test with assigning 80 dwarfs to stone detailing and ordered a large area smoothed and watched as my FPS dropped from the low 40's to below 20. 

Additionally, there is a general observation that the more pathable creatures there are on a map the slow the game runs, this is one of the reasons why caging animals improves game performance.  Historically, pathfinding is a non-trivial problem to code and, our own observations, along with Toady's admissions, indicate that there are problems related to the pathfinding code.  Like how flying units won't fly to something unless there is a valid ground path to their destination, which is a problem related to the implementation of the connectivity map.  Other behavior also causes slowdowns, like how off-duty dwarves check un-owned chests and cabinets for jewelry and trinkets, which can cause dwarfs to spam for paths as every idle dwarf checks and rechecks every empty and unclaimed chest repeatedly.

Sieges, specifically, are another special case, it is our understanding that the target of a siege is the dwarf closest to the siege when it spawns.  But for invisible units, the target may be an item, the closest child, or a random dwarf, which might be 15-z levels down and on the other side of the map AND may need to be repathed EVERY SINGLE frame because it has moved.

All of that said, there are other major causes of slowdowns.  The graphics code has historically been one, but it is being addressed.  Another know source of slowdowns is the number of items/objects on a map.  The assumption there is that the dynamic tables being used to keep track of each item and all it's details is big enough that accessing them invariably leads to multiple cache misses and multiple calls to main memory.  A little math, some knowledge of computer architecture, and a few assumptions about how item information is stored supports this assumption.

-----

I couldn't find the current algorithm (is there one? Conversation seems to go in circles a lot) but anyway, an observation:

Spoiler (click to show/hide)

I think generating a complete path to your destination is a waste. You're too likely to have the path invalidated (by map changes, something getting in the way, Dwarf deciding he's thirsty and dropping his current task, etc.)

Generate zones (areas of limited size which are contiguous for the most limited movement type possible in them - i.e. a normal floor area would be part of a zone where the entire area is contiguous for a creature which can walk but not open doors, an area of water for one which can swim but not open doors, a tile with a door on it for creatures which can walk and open doors, etc) with connectivity links (not specific paths, just info that they zones are connected) to adjacent zones. Generate an initial path on this (comparatively very simple) zone network, and then just generate a path to reach the next adjacent zone as you need it.

You'll end up generating a lot more paths, but the cost will be diffused over time, (this doesn't seem so important in DF as in games that demand a smooth framerate - but caravans and sieges arriving can still cause huge, nasty hitches from the cost of the initial long pathfind for a bunch of new creatures entering the map all at once) and with relatively small zones the individual paths should be fairly trivial to solve. Additionally, as you know you are only pathing as far as the next adjacent zone, you can limit pathfinding to within your current zone - so in the worst case, of a failed pathfind, you'll only floodfill your current zone. (Though this should never happen if your connectivity info is good.) Shorter pathfinds also reduce the number of paths which are invalidated and have to be regenerated when the map changes (a map change would only affect creatures currently pathfinding in the same zone, and would only affect creatures pathfinding through the zone but not currently in it if the connectivity changes).

Also, I'd put aside multi-tile creatures for now. They're an edge-case, and even when they're there, there will generally be very few of them. It's not worth optimizing for this at the cost of a better algorithm for single-tile creatures. Not to mention the current lack of multi-tile creatures...

Toady has confirmed that the algorithm used in DF is a slight modification of A*.  If you are asking about the implementation that Impaler[WrG] and shadow_slicer put together, read this paper, this power point, this paper, and pages 23 through 26 of this thread.

[Shades]

That pathfinding is a major source of slowdowns is not an assumption.  To test this, make a simple fort and turn weather, economy, temperature, and invaders off, grow the fort to 200 dwarfs then remove all jobs so they are all idle and set a 200+ item stockpile to be moved from one place to another.  You will observe a significant difference in the FPS between 200 idle dwarfs and 200 dwarfs hauling things even a short distance, and people have recorded this.  I personally did a similar test with assigning 80 dwarfs to stone detailing and ordered a large area smoothed and watched as my FPS dropped from the low 40's to below 20. 

Likewise take a new map, one dwarf and mine out a few thousand squares of rock, also watch the framerate drop. People have recorded this too.

To be honest my gut feeling is also that there is an issue with pathfinding (hence my posts towards the start of this thread), however I realised I couldn't prove it to myself so posed the question so see if anyone could. So far I'm not convinced we can show it is.

The main reason I want to prove that it is pathfinding is that I work with A* on a game with node spaces orders of magnitude larger than in DF and we don't have anything like this slowdown, we don't do quite so many calls but the time per call shows we could easily with a hundred or so units 50 times a second.

This leads me to wonder that assuming it is the pathfinding then maybe there is something bigger than mearly the algorithm used, such as pathfinding allocating node paths on the heap rather than the stack (which I know was an issue for our first implementation).

[Teiwaz]

The main reason I want to prove that it is pathfinding is that I work with A* on a game with node spaces orders of magnitude larger than in DF and we don't have anything like this slowdown, we don't do quite so many calls but the time per call shows we could easily with a hundred or so units 50 times a second.

I worked on a game which uses a variant of A*, with substantially fewer units (< 10) pathing over a much smaller network (< 2K nodes) than DF, and found pathfinding to be a huge expense when dealing with situations that basic A* doesn't handle very well. (Multi-story buildings, u-bends, etc. Anything which causes the heuristic to break down by forcing you to move substantially way from your objective to get there causes havoc with A*, as it quickly ends up flood-filling the network. DF is rife with these situations.)

[qwertyuiopas]

However, if you were to have it calculate places with only one reasonable path(Suggested SPZ(Single Path Zone)), or where the path can be accomplished by a move in a general direction(TCZ(I think? or was it TPZ?)), it could handle longer paths better. However, such calcuations would take time, and to achieve optimal zoning would require recalculation after any map update.

And if such recalculations turn out to take a lot of processing, then having a background thread do such processing and have the pathing in those areas temporarily revert to plain A* would suddenly seem more sensible.

Additionally, flagging each area with a general volatility rating, and only reclaculating for areas that generally don't change would keep recalculation to a minimum.

Most importantly, if optimization zone recalculation were a distinct thread, then pathing wouldn't totally halt during a long rezoning, it would merely be slower.

Now, if there were a very time-consuming way to further triple the speed of pathing in nonvolatile areas, wouldn't it make sense to calculate it when nothing else is happening?
And at the very least, specifying a framework where DF could signal the pather when to slow down or pause and when to go ahead with such background optimization would leave future decisions for the system more open.

[immibis]

3. Pathfinding is one of the slowest parts of DF.

Has anyone actually tested this? Because the pathfinding for a hundred or so critters on a map as small as we have should not be such a bottleneck, if it is a problem then simply improving the implementation of the A* used might be all that is needed.

Consider that every tile of a liquid under pressure needs to pathfind as well.

[Shades]

Anything which causes the heuristic to break down by forcing you to move substantially way from your objective to get there causes havoc with A*, as it quickly ends up flood-filling the network. DF is rife with these situations.

No it doesn't, no it's not. If you where getting these problems then either your implementation was broken or the heuristic you picked was flawed. A* is designed to solve exactly this problem, it's what it is good at, it's the one reason you use it.

Consider that every tile of a liquid under pressure needs to pathfind as well.

Actually only the top level (and pumps), and then it only needs to pathfind through a liquid, your node space is minimal in this case.

[Impaler[WrG]]

Generate zones (areas of limited size which are contiguous for the most limited movement type possible in them - i.e. a normal floor area would be part of a zone where the entire area is contiguous for a creature which can walk but not open doors, an area of water for one which can swim but not open doors, a tile with a door on it for creatures which can walk and open doors, etc) with connectivity links (not specific paths, just info that they zones are connected) to adjacent zones. Generate an initial path on this (comparatively very simple) zone network, and then just generate a path to reach the next adjacent zone as you need it.

The flaw with pathing only from zone to zone is that some arbitrary goal needs to be put in each zone which results in a "choppy" path in which the agent unnecessarily moves to that goal point.  My plan is to use a zone tree to both confirm connectivity and to progressively whittle-down a to a series of connected zones which will form a 'corridor' through witch an A* search will be confined.  That prevents most wasted node expansions but still gives the optimum path.

If you are asking about the implementation that Impaler[WrG] and shadow_slicer put together, read this paper, this power point, this paper, and pages 23 through 26 of this thread.

Unfortunately we never progressed to the point of zone implementation, currently were at a decent tile-level A* implementation, a test-suite that runs large batches of randomly generated searches and reports time efficiency and a path-following class that serves as the interface between the Path engine and the agent and will navigate for an agent.

[shadow_slicer]

Unfortunately we never progressed to the point of zone implementation, currently were at a decent tile-level A* implementation, a test-suite that runs large batches of randomly generated searches and reports time efficiency and a path-following class that serves as the interface between the Path engine and the agent and will navigate for an agent.

There was also a hierarchical A* implementation, but zones were statically determined square regions of size N by N. This method had some performance improvement over the tile-level A* for most maps, but wasn't significantly better. The framework should be general enough to use TCZs or other zones, but that wasn't implemented. It should even support multilevel hierarchies as well. It doesn't yet implement a breadth-first search or multi-item search or connectivity checking, but those could probably be added.

I had hoped to implement shortest path zones (zones that completely contain the shortest path between each of the nodes in the zone), but I haven't had so much time to work on it this year because of school. This is particularly difficult because the zones need to change appropriately in response to map changes. I haven't found a way to adjust the zones in such a way that I can guarantee they would achieve the same structure as if they were simply generated from the new map instead of simply being modified from the old one. This is not theoretically necessary, but it is sufficient for algorithm correctness and stability (preventing fragmentation) and would make it a whole lot easier to debug zone placement. It turns out this is actually a really difficult problem  .

tylor:  I already have something like that I call it 'interrupt-able' A*.  Each search and all of its nodes remain in memory until some kind of completion is reached (a full path or failure) only then are resources freed.  The actual node expansion loop is controllable, I can tell it to run for some number of expansions or until completion.  At any time I can query the search to get back the best partial-path found so far.

But I still need work out having an agent that started moving on that partial path smoothly transition to the final one if it turns out that the initial path was flawed and the agent was sent in the wrong direction, most likely I'd just request another path from scratch.

For those of you not in the know, the overall effect is simply to 'smooth' that 'hang' that occurs when a larger number of agents all start pathing simultaneously.  Though their are some potential side benifits, like terminating searches when they grow past a certain length but that get a bit more complex.

Why don't you instead use 'interrupt-able' A* to path from the destination to the current source position (or even the expected source position after N moves)? That way you don't have to request another path if the node went in the wrong direction -- they would just back track a bit. Since the dwarves already appear to do this anyway because of the delay assigning jobs, it probably wouldn't be that noticeable. You could even terminate early if the current source position becomes one of the explored nodes in the shortest path tree that you keep for A*.

[Teiwaz]

The flaw with pathing only from zone to zone is that some arbitrary goal needs to be put in each zone which results in a "choppy" path in which the agent unnecessarily moves to that goal point.  My plan is to use a zone tree to both confirm connectivity and to progressively whittle-down a to a series of connected zones which will form a 'corridor' through witch an A* search will be confined.  That prevents most wasted node expansions but still gives the optimum path.

Pathing to the arbitrary zone reference point is unnecessary. All you have to do is path into the zone. Depending on performance, you either path to the reference point, but stop as soon as you enter the zone and generate a path to the next one or you  generate a path to a "best guess" point which is nearest to you inside the target zone (and then generate a new path as soon as you enter the zone for whatever reason, in case your guess was wrong.) Obviously, which approach is more efficient depends on zone size.

You may not get a perfectly optimal path in all conditions (I expect most of the problems would exist outside) but in the normal environment of Dwarf Fortress - a series of rooms and corridors usually connected by only 1 or 2 tiles, which would generally be the boundary of a zone as they often have doors - there's not very much variation between a perfectly optimal path and one that works. (In fact, I'd bet there wouldn't be a difference at all in most cases.) In any case, we're dealing with a game with performance issues. Generating a path quickly and efficiently is *far* more important than generating the perfectly optimal path that saves a dwarf a tile or two of travel time.

While restricting the network over which you need to path will help, generating a complete path still means you're generating a LONG path, and also one that is likely to be discarded (the case of targeting something that is itself moving, like siegers going after a dwarf and having to regenerate their path every frame, for instance), and is therefore wasteful. Pathing between zones means that you only have to re-generate the path if the moving target is in the same or an adjacent zone as you, which means it's a short path by definition and therefore cheap. (If they're in a different zone, your path doesn't change. Even if the target moves to a new zone, you only have to regenerate the "high level" zone path, and even then, you just need to generate it from the second-last zone in your path, with a maximum path length of 2. Cheap!)

[Teiwaz]

No it doesn't, no it's not. If you where getting these problems then either your implementation was broken or the heuristic you picked was flawed. A* is designed to solve exactly this problem, it's what it is good at, it's the one reason you use it.

Yes, the heuristic was flawed for that particular path network, but it worked fine for 95% of the levels in the game. (It was the default implementation used by Unreal 3, I believe. I suspect the heuristic was based on straight-line distance between the node and the destination, just like 90% of A* implementations out there.) That's the problem with game environments - they aren't very predictable. And once you let players start screwing with the environment, (DF lets you do this a little ) things get worse.

Imagine the case of a dwarf standing on the floor immediately below the barrel of tasty Dwarven Wine he wants to get to. Somewhere on the level is a staircase leading up to the next floor. How do you avoid flood-filling the entire floor the dwarf is on until you find the staircase without doing some prior-to-runtime analysis of the map?