Print

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

[qwertyuiopas]

Except that, if I understand A* correctly, the diffrence between it and a flood-fill is that it adds the minimum, unimpeded straight-line cost to the goal to the weight of the tile itself to get the cost.

So if it got to a T junction, the path slightly towards the goal would get a bias, unless some other weighting factor made that tile cost slightly more.

So similar to that diagram except natually following fewer paths, I think.

[tylor]

A* adds heuristical minimum possible path cost from added tile to goal, which is not necessarily straight-line cost. More effective A*-based algorithms mostly works with other heuristics.

[PencilinHand]

A* adds heuristical minimum possible path cost from added tile to goal, which is not necessarily straight-line cost. More effective A*-based algorithms mostly works with other heuristics.

True, but they typically have a smaller node space(512^2 = 262k nodes is big in pathfinding, DF can be 50*288^2 = ~4.1 mill nodes)  and limited connectivity(mostly just the 4 cardinal directions, sometimes 6 x-y-z axis directions, sometimes 8 compass directions, DF has 10 + special cases such as doors, ramps, flying, and swimming).

This has all been discussed back in the thread.  The main conclusion of this thread was that the best course was to try and limit the ground pathable space by transforming it into a smaller and quicker to path node space(+95% of pathing is over ground so it makes sense to focus there).  Several white papers with different methods were put forward, and some other novel ideas were suggested towards this end.  A bit of code was written in the vein of one of the white papers and it was partly integrated with Khazad(there were pictures of paths posted), a few suggestions were put forward for how to make a benchmark for different methods but nothing was really put together.

Really, read the thread, or one of the dozen of other threads.  Many things have already been discussed and it is just not an easy problem to solve.  Significant concessions and game shaping choices may need to be made to really improve the pathfinding. 

Knowing one way or the other would require Toady who has indicated he isn't really interested in this, at least currently.  This is due to the necessity of waiting on/being pressured by other programmers and schedules which Toady has said repeatedly would steal the joy out of it for him.  It is something of a miracle that the graphics code is being revamped like it is.  Besides, Toady already feels like he may be looking into pathing related issues(siege improvements, multi-tile creatures, digging enemies, workshop and item hauling) in the "near future."

[qwertyuiopas]

From my understanding of the current system, you can probably get the game to run slightly faster by putting high-traffic zones along major corridors within the fortress, especially where it is the only route, and putting restricted zoning where dwarves rarely should go, like an occupied tomb.

The resulting improvement would be minimal, but it is a tactic that can be used *now* without modifications to the game itself, and if you already have 300 dwarves and assorted pets, a 0.5% gain per path may add up to a noticable speed gain.

The best solution, however, would require Toady to edit the game itself, and that must wait at least until the end of the current release, hopefully soon.

[ggeezz]

At least the thread has a good summary of what happened and the current state now.  Thanks.

[tylor]

I think, polished floor could work as a high-traffic lanes... Flat floor should be much easier to walk than rough, right?

[Shades]

Nope you need grip to move (also not exactly on topic)

[The Bismuth]

Gosh, this is a long thread. I've skimmed it and reckon I understand where you are at well enough not to be completely irrelevant.

I was thinking of Fuzzy Voroni Diagrams.

PencilinHand has been advocating a hierarchical structure. This makes a lot of sense to me given the size of the problem. I was thinking that you could do this by focusing on landmarks. A subnode would be in the vicinity of the landmark which is easiest to reach. It may also be fuzzily in the vicinity of another landmark if that were nearly as easy to reach. This dual status would help determine the connectedness and distance between two landmarks.

By definition these regions zones would be connected internally, though probably not convex if they form a warren of tunnels. In that case though, the point where paths to the local landmarks diverged should give you a good hint that it was time to find a more specific route.

The blocking and opening of paths would alter which neighbourhood a sub-node was in, but this change would be localised. Similarly the landmark nodes would gain or lose neighbours, but the numbers of connections made and broken would be small.

(So Now I say it) I am not a computer scientist, more like a mathematician. I am more used to dividing problems up so they will be easy for people to think about. I don't know enough about the computer algorithms you are using to know if there is any efficiency gain from this.

[Shades]

Search back through the thread for the trivially connected zones chatter.

However to be honest we don't have a very big search space so it is unlikely methods other than A* will be more optimal. Not that I think that should stop us looking of course.

[The Bismuth]

So that's what TCZ stands for! I did wonder. I was thinking 'terrible convex zones'  or something. If the idea is already in the mix then I'm happy to leave it to you. If you can make 250% efficiency savings on the standard routines then you have some good brains working on this.

[praguepride]

I haven't checked through the 35-page thread completely yet, but has anyone thought about just "cheating" it?

So instead of trying to create this super-advanced efficient algorithm, you instead create specialized algorithms for specific problem points.  Issues like:

Shutting down constant pathfinding when a unit gets trapped.
Creating seperate algorithms for flying/swimming/walking units that can bypass doors/walking units that are "dumb"
Quickly recalculating paths when disconnects happen.

I'm not an algorithm guy so I have no real clues to add, but it sounds like there are too many issues to deal with as a comprehensive system. So instead, try creating smaller systems that can join together to "fake" a comprehensive system...

For example (and again, forgive my ignorance). Certain actions could trigger different path-finding algorithms.

Take this scenario: The user switches a draw brdige that restructures the world. An algorithm that is very good at quick mapping new paths could be loaded to do a quick pass, then a different one that is better at continous path optimization could be restored to refine and control the more "normal" routes.

Perhapse the re-map could be triggered to certain major events: (seasonal changes for example) or could be triggered if X number of rejected paths crop up. So if a single door is locked and only one dwarf is effected by it, the whole map doesn't need to be redrawn just because one or two dwarves can't enter that room.

However, when the user floods the world and suddenly nobody can path, the huge number of "rejected" paths would trigger a remap. Perhaps a break should be put in so if flooding is progressing it doesn't continually redraw.

On that note, realism could cover some flaws. A dwarf trying to go to a draw bridge that's no longer passable might do so because he doesn't realize the bridge is closed. It's exusable for him to not have an instant knowledge of the entire map at all times.

During a massive event like a flood, perhaps pathfinding is heavily diminished to represent people in shock and awe at the coming tide of water/magma/goblins. Something could be put into place to recognize that a huge map-altering event is ongoing and that the map doesn't need to be re-calculated every second as it's just going to change again.

Perhaps activate a "safety" pathfinding that steers clear of flooding water/magma. So instead of constantly skirting close to it, the pathfinding just blocks off that whole section of map as inaccessible and encourages dwarves to go "the long route"

[PencilinHand]

Gosh, this is a long thread. I've skimmed it and reckon I understand where you are at well enough not to be completely irrelevant.

I was thinking of Fuzzy Voroni Diagrams.

PencilinHand has been advocating a hierarchical structure. This makes a lot of sense to me given the size of the problem. I was thinking that you could do this by focusing on landmarks. A subnode would be in the vicinity of the landmark which is easiest to reach. It may also be fuzzily in the vicinity of another landmark if that were nearly as easy to reach. This dual status would help determine the connectedness and distance between two landmarks.

By definition these regions zones would be connected internally, though probably not convex if they form a warren of tunnels. In that case though, the point where paths to the local landmarks diverged should give you a good hint that it was time to find a more specific route.

The blocking and opening of paths would alter which neighbourhood a sub-node was in, but this change would be localised. Similarly the landmark nodes would gain or lose neighbours, but the numbers of connections made and broken would be small.

(So Now I say it) I am not a computer scientist, more like a mathematician. I am more used to dividing problems up so they will be easy for people to think about. I don't know enough about the computer algorithms you are using to know if there is any efficiency gain from this.

What I was advocating and what was actually used by the code that was written are different.  Read the white papers.  Your idea about Voronoi diagram is interesting but it seems likely to be no less arbitrary and more likely to be less convenient than most of the other method of ambiguation listed in this thread.  My idea was partly inspired by a method for approximating the length of a non-trival curve. The simplest visual approximation is to use this java program to approximate the dimension of a Von Koch curve by iterating a series of boxes of decreasing size.  I was originally proposing a little more than just that but if you are really interested in my poor explanation of it you can go back and read it without much difficulty.

I haven't checked through the 35-page thread completely yet, but has anyone thought about just "cheating" it?

Spoiler (click to show/hide)

So instead of trying to create this super-advanced efficient algorithm, you instead create specialized algorithms for specific problem points.  Issues like:

Shutting down constant pathfinding when a unit gets trapped.
Creating seperate algorithms for flying/swimming/walking units that can bypass doors/walking units that are "dumb"
Quickly recalculating paths when disconnects happen.

I'm not an algorithm guy so I have no real clues to add, but it sounds like there are too many issues to deal with as a comprehensive system. So instead, try creating smaller systems that can join together to "fake" a comprehensive system...

For example (and again, forgive my ignorance). Certain actions could trigger different path-finding algorithms.

Take this scenario: The user switches a draw brdige that restructures the world. An algorithm that is very good at quick mapping new paths could be loaded to do a quick pass, then a different one that is better at continous path optimization could be restored to refine and control the more "normal" routes.

Perhapse the re-map could be triggered to certain major events: (seasonal changes for example) or could be triggered if X number of rejected paths crop up. So if a single door is locked and only one dwarf is effected by it, the whole map doesn't need to be redrawn just because one or two dwarves can't enter that room.

However, when the user floods the world and suddenly nobody can path, the huge number of "rejected" paths would trigger a remap. Perhaps a break should be put in so if flooding is progressing it doesn't continually redraw.

On that note, realism could cover some flaws. A dwarf trying to go to a draw bridge that's no longer passable might do so because he doesn't realize the bridge is closed. It's exusable for him to not have an instant knowledge of the entire map at all times.

During a massive event like a flood, perhaps pathfinding is heavily diminished to represent people in shock and awe at the coming tide of water/magma/goblins. Something could be put into place to recognize that a huge map-altering event is ongoing and that the map doesn't need to be re-calculated every second as it's just going to change again.

Perhaps activate a "safety" pathfinding that steers clear of flooding water/magma. So instead of constantly skirting close to it, the pathfinding just blocks off that whole section of map as inaccessible and encourages dwarves to go "the long route"

Almost all of your suggestions would require a level of interactivity with the "non-pathfinding" code that only Toady would be able to do any of it if he ever spun off the pathfinding code from DF.  A notable exception, however, is treating every movement model(swimming, flying, lava-passable, invader digging) as a special case, which is inevitable.  However, it would almost certainly be an overloaded function or pre-programed "dumb" AI behavior.

The "realism covering flaws" bit is already in place to an extent.  A dwarf will only repath once it runs into a block in its path.  The idea of a "safety" pathfinding would have very limited practical usage and may be more likely to cause frustration on the user's end than any kind of real speed improvement.

[qwertyuiopas]

I *still* retain my opinion that a background optimization thread might be a good thing.

First, it can be *paused* at any time without losing the current state/location in the function.

Second, that pause/unpause command could be handled directly by DF itself, so that, for example, if DF hits both the FPS cap and the grapthical FPS cap consistantly, it could activate the pathing optimizer during the delay. Furthermore, DF could let it run when the game is paused.

Also, it's existance could easily be controlled with an external setting.
(Recently finished a 7DRL where the AI was on a second thread from the interface, so you could quit even when it was not your turn, and even if the AI froze.)

[PencilinHand]

I *still* retain my opinion that a background optimization thread might be a good thing.

First, it can be *paused* at any time without losing the current state/location in the function.

Second, that pause/unpause command could be handled directly by DF itself, so that, for example, if DF hits both the FPS cap and the grapthical FPS cap consistantly, it could activate the pathing optimizer during the delay. Furthermore, DF could let it run when the game is paused.

Also, it's existance could easily be controlled with an external setting.
(Recently finished a 7DRL where the AI was on a second thread from the interface, so you could quit even when it was not your turn, and even if the AI froze.)

Except that there is nothing to optimize.  The project as it was proposed would update its nodes and connectivity map when it is told there is a change and only develop a path when one was called for.  There are limitless problems with trying to guess useful information before it is needed.  Organizing any kind of cache of recent paths is more likely to be done on an as needed basis anyway.  What could be optimized, or what work could be done that isn't already certain to be done as needed?

If what you are really pushing for is the library to function as an independent thread then that seems possible but likely that the benefits would be negligible most of the time.  The processes would run regardless of if DF was paused, locked up, or otherwise limited but there would be some performance overhead associated with it plus some other likely complications.

If the paths that were being generated required some sort of iterative post-processing smoothing to approach optimality then I might see a use for something like that.  A few of the white papers behaved something like that but nothing like that had been adopted.

[immibis]

If what you are really pushing for is the library to function as an independent thread then that seems possible but likely that the benefits would be negligible most of the time.  The processes would run regardless of if DF was paused, locked up, or otherwise limited but there would be some performance overhead associated with it plus some other likely complications.

Consider:
1. The rest of DF is single threaded (except PRINT_MODE:2DASYNC, I think, in 40d#)
2. A lot of people have multiple cores now.
3. Pathfinding is one of the slowest parts of DF.
If pathfinding ran in another thread it could use another core, greatly speeding up DF.