Bay 12 Games Forum

Please login or register.

Login with username, password and session length
Advanced search  

Show Posts

This section allows you to view all posts made by this member. Note that you can only see posts made in areas you currently have access to.

Messages - Sunken

Pages: 1 ... 10 11 [12] 13 14 ... 20
166
DF General Discussion / Re: Anouncing The PathFinder Project
« on: October 21, 2009, 06:37:02 am »
Quote from: sir monko on October 21, 2009, 05:00:43 am

i assume that most movements are not between quasi-random destinations (e.g. a hunter wandering around until he finds game) but few highly frequented locations.
Sure, but "frequented locations" will be whole stockpiles, farm plots and other multi-tile regions, not single tiles. The restriction of one log or stone per stockpile tile, for example, ensures that you will never get a single cache hit when pathing to get logs or stones from a stockpile.
I still conclude that abstract locations will be absolutely crucial for path caching to have any utility. But feel free to prove me wrong!

167
DF General Discussion / Re: Anouncing The PathFinder Project
« on: October 21, 2009, 03:39:08 am »
I doubt if you'd see many cache hits for DF on a tile-by-tile level, but it might be more practical on a higher abstraction level such as rooms or zones. The cached path might be suboptimal in that case, but one could live with that.

168
DF General Discussion / Re: Anouncing The PathFinder Project
« on: October 20, 2009, 02:53:21 pm »
Quote from: Starver on October 20, 2009, 09:21:35 am
BTW, not that my own ideas are going in this direction, but could you see a major problem with taking a roughly calculated route, far from optimal (e.g. could easily be /\/\/\/\/\), subdividing it into segments and then assessing the optimal pathing between the centres of each segments as mini challenges (all of them resource-light, even combined) rinsing and repeating for a loop or three until the inefficiences of the route are smoothed out (becoming __________, in this stupidly simple example).  On a 100-step-line cycle, 49 quite trivial "two steps at a time" tests highlighting kinks in an unecessarily bendy route (but necessarily and unavoidable bendy around obstacles), and then paying attention to the areas around that route neighbouring that 'betterment' might help.  (Of course, the ultimate counter-example is where, from the start point, one has a choice of stepping left to go through one obstacle course or right through another, the exit to each being straight onto the finish-point.  The 'shrinking' algorithm would never have chance to 'snap' the route from one side to another, to see if that were more optimal.  Or even not an obstacle course at all.  Which is a bit of a downer.  God job that's not my chosen approach, eh? :))
I think you put your finger on it. In formal terms: a simulated annealing approach; sensitive to local minima

169
DF General Discussion / Re: Anouncing The PathFinder Project
« on: October 19, 2009, 11:50:48 am »
It depends. Mostly A, I think, at least if the errors are "human" in nature. People don't do optimal pathfinding, after all.
I'm counting on that with my TCZ suggestion, because "silly-move" navigation inside TCZs is not optimal. In extremely contrived circumstances it can be as much as 50% inefficient.

That's on the small scale, however. On that scale, one could even get by with having dwarfs use different pathfinding locally depending on whether the player is looking at them or not... if it is visually displeasing. Large-scale pathing should be acceptable.

170
DF General Discussion / Re: Anouncing The PathFinder Project
« on: October 19, 2009, 11:21:35 am »
Quote from: Jifodus on October 19, 2009, 10:52:30 am
Thank you for the clarification.  Most of what I could got from all the previous posts was that "We'll optimize the algorithm," which didn't make any sense since A* is already optimal assuming that the heuristic is >= actual cost.  I still would like to know though, what is the algorithm are you planning on using to discover areas, since an idea is one thing, but an implementation is something else.

Well... "A* is optimal" means that A* finds the optimal path - not that it does it in the least possible time!

The time taken is given by the shape of the search space we give to A* (which in our case comes from the zones we use, the limitations imposed by movement types, and the use of a connectivity map), and the heuristic function we use (absolutely crucial), and also by the low-level programmatical implementation (such as which language to use). I'm just claiming the two former are vastly superior targets for optimization efforts than the latter.

171
DF General Discussion / Re: Anouncing The PathFinder Project
« on: October 19, 2009, 10:47:31 am »
Quote from: Slogo on October 19, 2009, 10:37:09 am
Designations like Indoor/Outdoor could also be solved easily if we use a Type->Subtype allowance flag system like I described earlier. If a creature is designated to only be allowed indoors then they can check the sub tile of any tiles during A* to see if its of a valid type much like they might with water or magma.
More importantly, subtyping can make for efficient representation of the connectivity map. For example, a dwarf with access to a certain room is also a dwarf with general dwarf access; thus, if a goal is reachable in the general-access connectivity map he doesn't need to check (or create) a connectivity map that uses his special room.

172
DF General Discussion / Re: Anouncing The PathFinder Project
« on: October 19, 2009, 10:42:10 am »
Quote from: Shades on October 19, 2009, 10:06:19 am
I would recommend sticking to the basic bit array for things like magma and water and looking into expanding it if and when it's required. As long as the check functions are isolated and well tested its easy to refactor and the basic system should allow duplication of the DF system without overly complicating the problem.

Quite, but it's important to remember not to circumscribe ourselves while coding. No optimizations based on the knowledge that capabilities will be bitmasks of a certain size! No optimizations based on the knowledge that the goal is a single tile!

173
DF General Discussion / Re: Anouncing The PathFinder Project
« on: October 19, 2009, 09:49:15 am »
I think we must keep all channels open when it comes to the number of movement types we can deal with. We don't just have to cope with walkers, fliers, swimmers, jumpers, water walkers and lava-resistant creatures, but actually with a potentially infinite set. Pathing doesn't care whether a space is untraversable because it is impassable to the creature, or because it is passable but otherwise forbidden by the AI.

For example, we have the pets-and-doors issue, but in general this may be much more complex: different castes of creature may be allowed through different sets of doors (guards, workers, guests, nobles, the owner of a given room).
Then there's the issue of knowledge of spaces - an invader might not be allowed to path through spaces he doesn't know about.
Then there's traffic limitations - "dwarfs don't go outdoors", "absolutely forbidden zones" and other player-imposed restrictions, possibly applying differently to different agents.
Also, you might envision situation-dependent limitations - disallowing civilian dwarfs from moving through "enemy held territory", automatically maintained (rather than user-specified in detail).

What all this adds up to, I think, is that each path search is in principle unique, and we should have a system that permits arbitrary limitations to be placed on any individual path search. A path request could be as general as:
"Find a way from tile A to any tile with a limestone block; staying indoors at all times; going through no restricted doors except my personal room; walking, or jumping down no more than 1 z-level at a time; staying out of dangerous areas"

It's not as hard as it sounds, in principle: as has been stated already, A* can do all this - we just place custom limitations on which search nodes we are allowed to open. Whatever zone types we choose need to be annotated with the data we use for the limitations, naturally, but that will be obvious once we get there.

The tricky bit is that A* needs a connectivity map to be efficient. We can't maintain a connectivity map for each such custom request so we must find some way of cache the most commonly used ones, and compute an exact or approximate variation of the connectivity map when a special path request needs it. Requests for unusual restrictions are just that - unusual, so maybe we can get by with a flood fill every time for them. The more common ones ("general indoor worker dwarf walking through any unlocked door") will stay cached and updated constantly.
It's not a trivial problem but should be possible to solve, and with big dividends.

Finding good heuristics will be another challenge.

174
DF General Discussion / Re: Anouncing The PathFinder Project
« on: October 18, 2009, 07:55:47 am »
Quote from: Jifodus on October 17, 2009, 11:00:04 pm
I highly doubt you'll be able to optimize the algorithms any more than what they currently are now.  For the most part, I believe that the only way to optimize pathing is to allow players to be able to place waypoints instead of dreaming up a magical computer algorithm for figuring out rooms/halls or a TCZ that players already do naturally.

Apart from the arrogant tone, I agree with the potential of letting the players help. TCZs can already utilize what is already in place - doors - to let the player influence the shape of zones. Waypoints is one possibility, surely. But would players bother?

175
DF General Discussion / Re: Anouncing The PathFinder Project
« on: October 17, 2009, 07:10:02 pm »
Agree with Shades on the above: all effort should be spent on improving the algorithms rather than low-level optimization such as re-writing things in C. Until the algorithms are perfect it will yield more bang for the buck, and using C means making the code harder to change and maintain, meaning that Dwarf Fortress will take longer to arrive - which is even more important than the dorfs arriving at their destinations quickly :)

176
DF General Discussion / Re: Anouncing The PathFinder Project
« on: October 17, 2009, 01:44:05 am »
Here's something y'all may have thought of but that I hadn't. In the "stockpiling pathfinding" thread (and many others previously) it is pointed out that dwarfs often select startin points and destinations stupidly - getting the "closest" stone from 30 Z-levels away for example.
I think no pathfinding scheme will be complete unless it can help deal with this problem as well.

The bottom line is, we won't always be given "go from this tile A to this tile B", but will sometimes be asked to "go from this tile A to any tile B that has these properties P".

I'm sure what we've been talking about could be tailored to deal with this. For example, each TCZ (or convex or rectangular zone) can have a cache containing its stored items. A* would simply search until the topmost open node is any node in a TCZ with the desired items in it, instead of one with the desired goal tile in it.
So it's not a huge conundrum; We'd just do well to have this in the back of our minds.

177
DF Suggestions / Re: Stockpile Pathfinding
« on: October 17, 2009, 01:37:56 am »
It's not so much about pathing itself as about choosing your destination in the first place. Pathing, once the destination is picked, is optimal (though not necessarily optimized!) AFAIK.

I think the discussions about hierarchical pathfinding will have as a spin-off effect that it will become cheap enough to actually search for the best destination at the same time as pathing. At least, I hope so.

178
DF General Discussion / Re: Anouncing The PathFinder Project
« on: October 17, 2009, 01:30:40 am »
Are you talking about learning a specific map, or do you want to apply the learned information more generally?

179
DF General Discussion / Re: Anouncing The PathFinder Project
« on: October 16, 2009, 06:02:03 pm »
Quote from: chmod on October 16, 2009, 12:24:03 pm
I apologize for not reading the whole thread, but has anyone suggested simple machine-learning for pathfinding? I would start simple, as that's all you need in the beginning of a fort. Random movement coupled with reward/punishment for finding good paths. The whole thing would be a bit organic. But you could save a general routine to use with all dwarfs. So it would be like a hive-mind. I've seen some success with things this simple before, although it was just a proof on concept on a simple Cartesian plane.

I'm all for learning and Toady likes the idea too, I've heard, but I think it is just too hard. You need an appropriate representation to learn things in, and that is the most difficult part to set up. What are the abstract features that you are going to feed into the trained system? And how will you get them? Very interesting issues, and the subject of my ever procrastinated Ph.D., and also immensely complicated. Even in a "toy" world.

180
DF General Discussion / Re: Anouncing The PathFinder Project
« on: October 16, 2009, 09:34:57 am »
Quote from: Slogo on October 16, 2009, 09:12:07 am
Digging creatures probably isn't really a concern of ours. If a creature is digging through rock then I'd imagine their ideal route would be a straight line down the tunnel. I'd expect any path finding algorithm to simply get the location of the next hole to dig and we'd be responsible for moving them to the appropriate dig location.
I assume he was talking about tunneling creatures, not just digging straight down. Still, since a tunneler has such great freedom of movement, raw A* will probably be plenty fast for that.

Quote
Dodging and falling really isn't a concern of path finding either but rather an issue of locomotion. A creature dodges to a specified location or falls down based on gravity and dodging, not some pre-planned path.
Jumping down a low cliff or hole is very much a valid choice of deliberate pathing in some situations. Some creatures may be impervious to the effects of a fall and it would be silly of them not to use gravity to get to where they want to go.

Quote
As for having preference for certain types of routes, well that's easy! All you need to do is allow for our methods to accept a set of weights for different types/sub-types of tiles. These weights would factor into the A* heuristic causing the optimal path to 'bend' towards prefered methods of movement when possible.
You can't factor them into the A* heuristic, only the exact cost.

Pages: 1 ... 10 11 [12] 13 14 ... 20