Print

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

[Carp McDwarfEater]

If main hallways with a lot of dwarves passing through were to eventually get automatically designated as high-traffic, and irrigation tunnels that no sane dwarf enters get marked as low trafficafter a while, I can see this improving FPS. Traffic designations you make would never be changed, though, and there should be an option to turn this off for people who find it annoying or whatever.

Another somewhat related suggestion is that there be a "Forbidden" traffic designation, that would essentially be considered a wall in the pathfinding. Dwarves would not pass through a tile designated as forbidden, no matter what. That would make it easy for you to prevent them from walking into waterfalls, or in your irrigation tunnel, or whatever.

Thoughts?

[Itsdavyjones]

This doesn't sound that bad actually.

[NW_Kohaku]

The problem with suggesting optimizations like the original one about starting in high traffic and then going to low traffic as you play is that you have to build a system for determining how often dwarves have passed through those tiles (so-called "ant trail" pathfinding optimizations), and that, in turn, is a rather complex set of computations and requires a rewriting of the map code in order to carry data on traffic that would create overhead for the computer that eats into FPS. 

The current pathfinding algorithm also doesn't respect any pathfinding method other than the ones dwarves use, with the exception of a few fliers that only pathfind via floodfill short-range.  This means that a bird that is tamed by dwarves will lose its ability to fly, and fish their ability to swim because the game doesn't support more than one connectivity map currently. 

Because goblins and other invaders shouldn't respect what you forbid, that precludes easy "forbidden" zones, no matter how much sense it would make in fortress organization. 

Forbidden zones makes more sense than the first one when Toady eventually does get around to eventually, hopefully, implementing a much better pathfinding system, however.  What we really need is something, at the very least, a little like jump point search, and at best, we need to have the connectivity maps work through hierarchical pathfinding routines that are capable of reacting to map changes as quickly as current connectivity updates take place. 

[King Mir]

Forbidden zones make sense because it should be possible to mark off a dangerous area. It's kind of like an anti-burrow.

As for the rest of the idea, I'm unsure it would actually lead to a speed up. It's good to have good traffic designations, and high traffic areas are often but not always good candidates for the high traffic designation. On the other hand, gathering data on how many dwarves pass through a tile is a new burden.

[Carp McDwarfEater]

Not every tile in the game would necessarily have to be constantly checked for passing dwarves. Couldn't it just check different places at different intervals, and decide which traffic designation to give based on how many dwarves are nearby on average when the game checks for that location? But I do see the problem. Still, I think Toady could find a way to make this work.

[King Mir]

It would also mean that dwarves will take suboptimal paths more often. Not sure if that's good or bad though.

I mean, people will often prefer to take the path they know well to the short cut they don't.

[NW_Kohaku]

Not every tile in the game would necessarily have to be constantly checked for passing dwarves. Couldn't it just check different places at different intervals, and decide which traffic designation to give based on how many dwarves are nearby on average when the game checks for that location? But I do see the problem. Still, I think Toady could find a way to make this work.

It doesn't have to check, no - the original ant trail theories are all based upon an at-stepping update, although you need to have a timestamp on those tiles, as well, so that you know how much time there has been to average those tiles over (so that you don't compare a piece of tile that has been in your fort's front yard forever to a newly-carved but still high-traffic hallway as you expanded your fort without reflecting the time spent).

Even this is going to take at least two new units of data on every single map tile. 

Worse, for this to really make sense in dynamic forts (where I might wall off an old entrance entirely, and set up new traffic patterns I want respected), you will need to way for the game to eventually forget old data, and that means timestamping every single step, which gets horribly complex.

Again, it's not that it isn't doable, but the thing is, you might as well spend the effort it would take to do this to just go to the effort of making a system that's wholly better than A* and make a significant improvement on pathfinding times instead of the marginal one that you would get from trying to make ant trails work with A* would do. 

Jump point search isn't that hard, and it makes for significant improvements in rectangular areas that most players make quite often.  (It simply searches for large rectangular rooms, and assumes symmetry through them, consolidating searches through rooms into very quick searches instead of having to pathfind through every tile to find the ones that are fastest.) 

Again, the ideal solution is some sort of modular Hierarchical pathfinding system, where paths for long-distance travel is stored and updated modularly, so that there is as little overhead in changes to the map causing connectivity updates as possible, since that allows you to simply cut pathfinding entirely down to local searches to the nearest "hierarchical highway". 

The main problem with pathfinding is that in a long-range pathfind, as much as 79% of the fortress is searched in a single pathfind... and fortresses contain potentially millions of tiles to search.  Even weighting A* heavily does nothing if you are pathfinding far enough away that a 25-point weight will be overcome after 25 tiles of searching, even with weight 1 tiles. 

But hey, we've beaten this horse well past death in this thread already.  Oh, and here's one specifically on jump point search.

[Bohandas]

I definitely support the forbidden zone suggestion