Print

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

[MrWiggles]

Path finding calculations are the one thing that seem to slow time to a grinding halt. I would love to see Toady work on better methods of calculating paths as my FPS is at an average of 2 FPS...
j

Just after embark screen... 

My old computer used to have 10fps just after embark.

Any I never really understood why its the common beliefe that Pathfiding is the major source of FPS death. When as your fortress grows larger, the number of pathing creatures, remains extremely small, compared to the number of tiles revealed, number of objects to keep tract of, the number of interactions to work, the number of jobs being generated. Ect ect ect.

[SuicideJunkie]

For a method that uses the existing mechanics, why not have tiles with many dwarves walking them be reduced in cost?

Because changing the preference for one path over another doesn't affect the computational cost of running the algorithm.

There's no advantage in having dwarves always use the same path, as such; the advantage is in not having to calculate the entire path. They can't just blindly follow the ant trail because they don't know if it leads to their destination or not.

Why would you think that?
Dwarves don't just blindly wander the existing high traffic tiles and hope they get to their destination.

Its the algorithm that looks at the high traffic tiles first, so in this case the tiles most used by the most common destinations will be considered first.
Since you're quite likely to be going to (or near) a frequently used destination, the algorithm finds a path earlier most of the time.
It won't necessarily be the shortest path, but it will be quick to find and well-traveled.

Just like the current high traffic designations!  Except automagic!

[czolus]

Except that the low-weight regions will cause the pathing system to prefer said regions, even if that results in excess tracking in the wrong direction.  This is an old problem in pathing: making sure the weights are relevant.

Now, the counter is to simply state, "Then people should keep their high traffic regions always up-to-date."  People are forgetful, and A*, despite being the best known general pathing algorithm, is far from cheap, averaging O(p*log(p)) with a worst case around O(p^2), where p is the length of the optimal path.  Said path can be hundreds (or thousands, in the case of some siege engine traps) of tiles long, and to avoid getting trapped in local minima (of which there are many in typical fortress layouts), you can't really afford to perform the pathing piece-wise in DF. It appears also that Toady doesn't try to do it piece-wise, and the frame-rate hit can be seen if one elects to enable some large number of jobs for which the vast majority of the fortress population goes from idle to working.  Sieges are also a case where the pathing system is heavily used---especially for those of us using "mazes" of opening and closing doors.  Lastly, broken paths (pet-restricted/locked doors/any obstruction that prevents pathing) always result in worst-case performance for A*, as every tile that may be reached from the start node will be considered (and rejected) before the search is exhausted w/ no valid path.

Now, choosing to use weighted tiles can reduce the runtime cost of the resulting A*, but not enough to change the expected complexity behavior; its still dependent on the number of tiles that make up the path, and the complexity of the path---remember also, a more complex path will be predicted less optimally by A*.

The only real solution to reduce the cost of A* is to reduce the number of nodes that can be considered, which is the approach I've taken.  I look at points where you have to deflect from the ideal (straight-line) path for some arbitrary path.  From those nodes (and so far, my empirical testing results in only ~1-5% of nodes being "special"---more complex layouts result in more special tiles), A* is now guaranteed to not consider more nodes than that subset, and the speedup is noticeable, especially in worst-case scenarios (which are unfortunately common in DF).  For example, I have ~21k ground pathable tiles (3x3 world tiles), resulting in an expected worst case of ~21k tiles if its a broken path.  I think there's ~300 special tiles, which results in a worst-case of ~300 tiles considered for a broken path---fewer tiles considered in total that for a typical complete A* path.  To generate the actual path needed (since my algo results in an ordered list of special tiles), simply draw the straight-line path between each item in the list (which can be done piece-meal, something A* can't do).

The devil is in the details, as additional time (and space) are used to track which tiles are special.  Thankfully, restricting the algo to only considering ground tiles results in a very manageable amount of time (and space) used in overhead (a few milliseconds per 100 special tiles, last I checked).  At present, I have 2 improvements that I'm working in: Tile coalescing (to further reduce the number of special tiles by eliminating redundant ones), and magma-/water-sensitive special tiles (to handle other ground-pathers, that might not care if a tile has too much water and/or magma---skeletal critters come to mind).

I do completely agree that there are other things eating up far to much computation time in DF, but pathing is at least something that can be reduced (significantly).

[catenate]

For a method that uses the existing mechanics, why not have tiles with many dwarves walking them be reduced in cost?

Because changing the preference for one path over another doesn't affect the computational cost of running the algorithm.

There's no advantage in having dwarves always use the same path, as such; the advantage is in not having to calculate the entire path. They can't just blindly follow the ant trail because they don't know if it leads to their destination or not.

Wikipedia sez: In species that forage in groups, a forager that finds food marks a trail on the way back to the colony; this trail is followed by other ants, these ants then reinforce the trail when they head back with food to the colony. When the food source is exhausted, no new trails are marked by returning ants and the scent slowly dissipates. This behaviour helps ants deal with changes in their environment. For instance, when an established path to a food source is blocked by an obstacle, the foragers leave the path to explore new routes. If an ant is successful, it leaves a new trail marking the shortest route on its return. Successful trails are followed by more ants, reinforcing better routes and gradually finding the best path.

Ant pathing seems to be for connecting a two specific types of location, for example food and the nest.  The benefit to other ants comes from the ants coming in the opposite direction, from the nest to food.

Dwarves, being more clever, could have many more types of trails than this-way-to-food and that-way-to-nest and other-way-to-enemies.  For example, a newly designated area to cut trees could have a this-way-to-cut-trees marker deposited on the way back to some point (a meeting hall by default; a carpenter workshop, to trees; barracks, to beseigers), so some dwarf needing to go cut trees could follow the trail out to the tree area, with no pathing calculation (just follow the most strongly laid trail).

This kind of only works well with resource areas though (stockpiles, trees, plants, types of stone, gem clusters, metal veins, water, magma, herds of animals, mobile goblinite vendors, megabeasts that take many hits).  For single, isolated items it's not useful, since such a trail is obsolete once it's laid.

One difficulty with proposing pathing improvements is generality, and the cost of maintaining two methods and knowing when to switch between them without running them both.  If only dwarves used this trail typing, then A* might still be used for individual items, and by every creature other than dwarves.  Accept this cost, though, and work out where to switch, and common cases could be made faster.

[czolus]

The key to making the any pheromone system work is the volatility of said pheromones.  To quote the wiki quoted text, "and the scent slowly dissipates".  These five words are what enable ant pathing algorithms to function, and are ultimately the greatest (hidden) cost in using them.

In the real world, this dissipation is ever-present, and thus why ants must be actively using a trail to maintain its value.  To the ants, this volatility is "free" (beyond the energy needed to manufacture said pheromone).  By comparison, to the universe, it is not as some energy is exchanged.  In our case, to a dwarf it may be "free" in the same sense as the ant.  But by comparison, the DF program is in effect playing the role of the universe, and must maintain pheromone count for all tiles.  This comes at a cost to both time (touching---at a minimum---every pheromone'd tile), and space (tracking the pheromone count of any given tile, and---optionally---which tiles have pheromones and which don't to speed up the time component).

Many things right in your suggestion ("this-way-to-trees marker") that improves pathing's context-sensitivity (and thus, selectivity), but the devil is in the details waiting to murder you in the face.

In the case of many creatures wanting to head to the same general area (from the same general area), there are other options to simplify pathing.  For example, in StarCraft 2, the reason that clusters of units retain their shape when moving as a group (bio-ball is an obvious case) as opposed to deforming the group shape as they move (StarCraft 1) has to do with the entire group behaves as 1 pathing entity, as opposed to each unit performing its own pathing.  Works well in that case, since you are defining a single destination point (which is where the group will center itself), whereas DF will likely be defining multiple destinations (1 tree per harvesting dwarf, et cetera).

[catenate]

The key to making the any pheromone system work is the volatility of said pheromones.  To quote the wiki quoted text, "and the scent slowly dissipates".  These five words are what enable ant pathing algorithms to function, and are ultimately the greatest (hidden) cost in using them.

In the real world, this dissipation is ever-present, and thus why ants must be actively using a trail to maintain its value.  To the ants, this volatility is "free" (beyond the energy needed to manufacture said pheromone).  By comparison, to the universe, it is not as some energy is exchanged.  In our case, to a dwarf it may be "free" in the same sense as the ant.  But by comparison, the DF program is in effect playing the role of the universe, and must maintain pheromone count for all tiles.  This comes at a cost to both time (touching---at a minimum---every pheromone'd tile), and space (tracking the pheromone count of any given tile, and---optionally---which tiles have pheromones and which don't to speed up the time component).

Since we only need to lazily model dwarven expectations, not the actual state of the universe, each dwarf could store a rough order of magnitude marker (like the bookkeeper's lowest-precision number-and-magnitude), along with the type of trail they lay down, as they return from the resource to the consumer.  This still allows relevance: a path to 100? will be preferred to a path to 60?, which will be preferred to a path to 10?; two tracks to 160 and 190 will be treated the same, as 200?; and a path to 120 will round to 100? and a path to 180 will round to 200?, so be treated differently.  If a dwarf finds nothing at the end of a trail, which has been counting down from 10 by ones, then the dwarf erases the marks on the way back, so they're no longer overhead.  If the resource disappears on its own, then the next dwarf to go looking for it also removes the marks on its way back.

So instead of the universe decaying at some arbitrary rate, the dwarves do it themselves, only at the time they actually make changes to the resource.  This models real-world expectations and lack of information--it bugs me a little (as a simulationist, not as a gamer) that dwarves always know precisely where to go to get stuff. 

At the end of the trail, there's still a need to A*, to find a particular item, but it's usually a localized search, within the same location bounds the last trailmaking dwarf used to get its number-and-magnitude estimate.  Or, to prevent another search if there are no resources in those bounds, always do an unlimited A* from the end of the trail to a resource of the desired type.

[Niseg]

I admit I didn't go through the whole thread but I did work on the subject in the path trying to get a working demo and I managed to get a few models done. I created a javascript simulator and posted it on this thread (in my sig too).

I've tested a few models :
waypoints - with path cache to every other waypoint. To get from A to B find closest waypoint to A , Wa and the closest waypoint to B Wb . then find a path A->Wa, use path Wa->Wb and then find a path Wb->B.

this saves time but you have to somehow select waypoint poistion and keep them updated when you change things because the cached path can change. the no path penalty can still be high.

-automatically placed waypoints - this is kind of a room placement . This uniformly places waypoints and find paths to their neighbors . this way you save a lot of short path and when changing an area you'll have less updating to do. it works similarly to the waypoint system.

- room based navigation - this is a divide a conquer method it's generally ideal and scalable . The idea is to scatter points like in automatically placed points but then create rooms out of them and save them somehow. The way the room are created is by using a modified breadth first search with many starting point and collision detection. When a collision happens  it's saved as an access point between rooms and it signifies a path between rooms .

To navigate point A to  B you  need to do is figure out which room , Ra,  point A is in.This is generally easily found mathematically and using elimination (it's generally fast). Then you have to find which room , Rb , B is in using the same process.  After finding the rooms you look for a path using A* on the room map from room Ra to room Rb this way you get a list of rooms. Now all you need to do is find a path from access point to access point.

This turn a potential k^(xa) to a *k^x problems . You can use a path cache but it's not really necessary. The room method visit less nodes on the map and have a clear dirrection unless an aimless A*. The many smaller A* also make it easier to deal with changing conditions. The main problem with this system is that I didn't figure out the update scheme for the rooms yet and didn't touch this project for a while.

you can try this maze . If you scroll down you can see the room I generated.The room pathing method I described above is done by pressing "advanced rooms no path cache ".  Because there are no update schemes then if you change the maze you have to click on "recreate wp rooms "(if I remember correctly) to regenerate the room. I recommend you use chrome because it's the fastest in JS.

A system like this can be implemented with periodic update or something like this but the update scheme isn't this complicated . All I have to do is figure out which room I'm in/near to update it but I didn't point my mind into it. the simple alternative is make all neighboring rooms fight over territory again. I know how to solve it but I haven't found the will to continue. I can go back to this if you guys really want  .

I still think that a key part of every pathfinding suggestion is always a working demo or clear methodology! Pathfinding is not a trivial subject and people who are involved in this should know a thing or two about writing code or the algorithms involved .

[irmo]

Since we only need to lazily model dwarven expectations, not the actual state of the universe, each dwarf could store a rough order of magnitude marker (like the bookkeeper's lowest-precision number-and-magnitude), along with the type of trail they lay down, as they return from the resource to the consumer.  This still allows relevance: a path to 100? will be preferred to a path to 60?, which will be preferred to a path to 10?; two tracks to 160 and 190 will be treated the same, as 200?; and a path to 120 will round to 100? and a path to 180 will round to 200?, so be treated differently.  If a dwarf finds nothing at the end of a trail, which has been counting down from 10 by ones, then the dwarf erases the marks on the way back, so they're no longer overhead.  If the resource disappears on its own, then the next dwarf to go looking for it also removes the marks on its way back.

I'm not sure what these numbers represent or what you mean by "counting down".

It sounds like you're still talking about some kind of group resource collection scenario, which is not really very common. Mostly, dwarves have distinct jobs taking them to different destinations.

So instead of the universe decaying at some arbitrary rate, the dwarves do it themselves, only at the time they actually make changes to the resource.  This models real-world expectations and lack of information--it bugs me a little (as a simulationist, not as a gamer) that dwarves always know precisely where to go to get stuff. 

I think that's our real disagreement, then: you're talking about removing the job queue, and instead giving each dwarf a vague idea of what sort of thing it should be doing now (like 'mine ore') which tells it which trail to follow. I'm not convinced that that will actually be any faster, because they have to be scanning continuously along the path for the object they're interested in, and I'm not sure what you'd do in any of the cases where the dwarf really has to find one specific object, like "recover wounded".

My larger concern is that since there's no job queue, and laying down trails is an automatic process, the player has basically no control.

[catenate]

I suggested ant pathing supplement, not replace, A*, for cases where resources go to places they're used, which I gave common examples of. I don't see why the job queue needs to change, so that's not my argument. The numbers refer to how many of the resource/reagent is at the source end of the trail.

[thisisjimmy]

I suggested ant pathing supplement, not replace, A*, for cases where resources go to places they're used, which I gave common examples of. I don't see why the job queue needs to change, so that's not my argument. The numbers refer to how many of the resource/reagent is at the source end of the trail.

If you think this will work, the best thing you can do is code up a demo.  Then we can try it and see for ourselves if it's faster or better.

[Niseg]

I suggested ant pathing supplement, not replace, A*, for cases where resources go to places they're used, which I gave common examples of. I don't see why the job queue needs to change, so that's not my argument. The numbers refer to how many of the resource/reagent is at the source end of the trail.

If you think this will work, the best thing you can do is code up a demo.  Then we can try it and see for ourselves if it's faster or better.

I tend to agree I can add this thing to my simulator if i knew the exact algorithm. My simulator isn't really designed for dynamic algorithm but it can be added.

I still think a room base system would be a lot better because it simplifies a lot of things. Items can be marked with their room ID and then finding an item closest to you would be easier . With a room system you can find the closest item with ease and you can find the closest job. What's really killing performance is the fact the game is dynamic  and every collision can cause the dwarf to search for a new path. With a room system all he'll need to do is check if he's room path is valid and find an alternate path to the next room's access point. This would also spread the load because you might be looking for more paths but they would be very short one which also helps caching performance.

In order to attack an algorithm you have to attack it's complexity and look at worst and avg case. The worst case of A* happens when there is no path to the target and then the algorithm will search through every single accessible node . A path caching scheme still has the worst case of A* . While the room system is no different it has a much smaller N there is a big difference between going through 200 nodes compared to going through 100000 nodes. This is why a room system is a better solution and I already know how to generate them  automatically    .

[catenate]

I suggested ant pathing supplement, not replace, A*, for cases where resources go to places they're used, which I gave common examples of. I don't see why the job queue needs to change, so that's not my argument. The numbers refer to how many of the resource/reagent is at the source end of the trail.

If you think this will work, the best thing you can do is code up a demo.  Then we can try it and see for ourselves if it's faster or better.

I tend to agree I can add this thing to my simulator if i knew the exact algorithm. My simulator isn't really designed for dynamic algorithm but it can be added.

That's generous of you, thanks.

I've honestly not thought through it in detail much more than my posts here.  To maximize the use of a trail, a dwarf should probably not lay one until there is 10 or more resources of the same type "near" the resource it's gathering.

The dwarf would have to decide between (1) pathing to a resource, and then pathing back to the consumer of the resource, or (2) path to a trail of the right type, follow it in the right direction to a resource, and follow it back to the consumer of the resource.  I tend to think that pathing to the trail would usually be quicker, on a stable map.

But there are no doubt pathological cases, such as a new, significantly quicker path opening up.  In this case, A* would find , and force dwarves to use, the new path more quickly, since it is computing the path from scratch.  So, this may be an argument for yet another piece of data on the trail markings: the number of steps (again, a lowest-precision number-and-magnitude would probably suffice) to the resource.  In this case, the first dwarf to wander back from the resource area without using the trail would lay a trail with a much lower distance-to-resource.

This of course begs the question of why a dwarf would use A* to path back, when a trail is sitting there waiting for him.  The answer to this is to either go back to the environment decaying the path (which only addresses the point indirectly), or having every tenth or twentieth or hundredth dwarf use A* instead to see if it can find a much better trail.  As soon as this dwarf does, the lower-cost path would exclusively be used, until the resource runs out, then the lower-cost trail would be cleared.  At this point the higher-cost trail is still around, so it would be used once, found to be useless, and cleared.

There's overhead introduced in this post, but I still think that saving, say, a path and a half might be worth it.  I'd try replacing (always "A*-to-resource and then A*-to-consumer") with ("A* to trail, follow trail to resource, follow trail back to consumer" plus the rare "A*-to-resource and then A*-to-consumer" to find a better path).

[czolus]

In order to attack an algorithm you have to attack it's complexity and look at worst and avg case. The worst case of A* happens when there is no path to the target and then the algorithm will search through every single accessible node . A path caching scheme still has the worst case of A* . While the room system is no different it has a much smaller N there is a big difference between going through 200 nodes compared to going through 100000 nodes. This is why a room system is a better solution and I already know how to generate them  automatically    .

How costly is your system to calculate your room nodes, as it sounds loosely like your overarching change is like mine: Reduce the size of the set of nodes that A* must iterate over.  I'd toyed around with a system to partition the world into rooms (I'd called them regions, but meh), but found the setup cost was too great to run well in real-time.  Moreso, are you able to get it to scale well into 3D pathing?

[Niseg]

How costly is your system to calculate your room nodes, as it sounds loosely like your overarching change is like mine: Reduce the size of the set of nodes that A* must iterate over.  I'd toyed around with a system to partition the world into rooms (I'd called them regions, but meh), but found the setup cost was too great to run well in real-time.  Moreso, are you able to get it to scale well into 3D pathing?

Room generation uses a modified breadth first search and it go through every open node on the map. I think generating it would be about 3 times more costly than no path penalty of A* because I'm considering 3 sets :overground, caves,HFS. It uses 2 points and a bit vector + room connection vector . I did the math once and it won't consume that much memory but for JS it's a little excessive( I also pushed some optimization to A* to reduce complexity because JS is slow).

Converting it to 3d isn't really a big deal. I think it goes through a coordinate array so all it needs to do is add a few points and another dimension . It's possible to keep it 2d by not allowing it to move on the Z axis and just find access point.

The thing is with this method is that you should build it once and then the update scheme takes over to maintain it. It only need to update when something is built or/dag. It can also update when finding those nodes not in room and merge them into the closest one.

But as I said I didn't touch the update scheme because it's not simple. I kinda abandoned the project at some point. My HDD also died  but I have a few backups.

[czolus]

Sounds quite a bit like the system I'm using wrt setup/maintenance costs, which I found to not scale efficiently into 3D.