Print

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

[No1]

Well on the point to let the player designate paths I agree with you but they way that hierarchical path finding works is that it sort of make that for you but instead of a couple of player designated ways it has every possible way. To make it easy to understand it works by dividing the whole map in areas (might even be a cubes because DF is in 3D) and just save entrances between areas. So if you have a lot of rooms then they will be simplified down to just an entrance and that could make a (don't remember the size so this is just for the example) 100x100x100 tiles map into 10x10x10 areas that might have 10-20 entrances so instead of 1 000 000 tiles (nodes) you have 10 000 to 20 000 nodes. That's a factor 100 less nodes and I probably overestimated the number of entrances to an area.

[Lord Urist]

...ok. My suggestion has nothing to do with the hierachal thingamyjig though
idk, I'm no programmer.

[No1]

I'll bring this back the front as the Thread DF on an iPad got off topic into path finding and other FPS improvement ideas.

[Farmerbob]

One step in the right direction would probably be to at least slap the pathfinding (all of it) on a separate thread from the main DF process.  Like was already mentioned, however, tou end up needing to let creatures pause for a frame or two while they wait for pathfinding instructions, which might get annoying depending on the implementation. 

If the game is allowed to run at the same time as the pathing occurs then there will be consistency problem of the data for the threads. One way to make sure the pathing thread is not affected by the main thread is to make a complete copy of the map but that will be incredibly slow and memory inefficient. One approach could be to just ignore the fact that a node that already has been visited can be changed and let the entity handle the problem if it arise. I think it is how the pathing is now (ever seen a dwarf path to a locked door and just show a "?" and then path around it?)
The danger with multi-threading is that if something bad can happen it will happen and the result will be lots of angry people having crashes in their game and due to the fact that it is multi-threaded it is very hard (read almost impossible) to pinpoint the problem.

ONERR <locate nearest booze>

Can it not be made so that a potentially separate pathfinding thread be completely subordinate to the main game thread, and if it errors out, the pathfinding thread is simply terminated, data dumped, and rebuilt and fed destination data from the main thread again?

[Urist Da Vinci]

I'd suggest that, instead of having the game remember "high traffic nodes" on the map, that dwarves increment an extra variable on tiles that they walk over. The variable would decay over time. The variable would also be included into the pathfinding calculation as a preferred route or lower-cost tile. This would result in dwarves using ant-like navigation with the most common routes being heavily weighted. I don't know if the extra CPU cycles required to do this would be worth it.

Humor: http://df.magmawiki.com/index.php/File:Vomit_Trail.png

[No1]

Can it not be made so that a potentially separate pathfinding thread be completely subordinate to the main game thread, and if it errors out, the pathfinding thread is simply terminated, data dumped, and rebuilt and fed destination data from the main thread again?

I see what you are saying but it would not change anything, as it is now the main thread does everything and that includes the pathfinding that is done many times each turn. So what it would accomplish is pretty much nothing as the main thread would then have to wait for the pathfinder to do it works as they can not work parallel to each other, due to write collisions on data and the fact that the pathfinder thread would not know beforehand how the world looks.

I'd suggest that, instead of having the game remember "high traffic nodes" on the map, that dwarves increment an extra variable on tiles that they walk over. The variable would decay over time. The variable would also be included into the pathfinding calculation as a preferred route or lower-cost tile. This would result in dwarves using ant-like navigation with the most common routes being heavily weighted. I don't know if the extra CPU cycles required to do this would be worth it.

It's funny you mentioned ants as that is a well known machine learning algorithm to solve traveling salesman problem. However I'm not sure how much it would yield but it would be pretty easy to test, one could artificially create the trails by making traffic designations after where the dwarfs walk mostly and compare to a non-designated map.

I still think that the most benefit for pathfinding would come from a room based pathfinder, those that do not want to look through the thread it's basically a dynamic or manual(the player designates rooms for the pathfinder) heuristics that instead of searching through thousands of tiles only looks at the rooms, so say with a room size of about 25 tiles 1000 tiles(nodes) will become 40 nodes (of course there are some extra nodes in the end) with the only downside that the path will not be 100% of the optimal path.

[Starver]

Whoops, I didn't realise (didn't think to check) that this was a semi-necroed thread, and this is probably not relevant 4 pages down from the original reply I made, anyway...  Still, here you are.

I'd like to go ahead and request a crawling domain, so that entities can stick to walls like an insect. Oh yeah, and a configurable domain for jumping (flying short distances) several tiles.

Something I've mentioned in previous pathfinding threads is an extension of this...  Limited-resource using paths.  e.g., goblin squad comes on-screen with five ladders.  Can they find the best path that has no more than five 'use ladder' steps?  (Perhaps for bridging, as well as climbing.)  Merely using ladders at the first opportunity, along the various branches of the search tree, may not be as optimal as retaining the ladder (making a short detour around the obstacle) until it is useful to provide a much more vastly profitable short-cut (or even the only possible access opportunity) shortly thereafter.

This complicates the pathfinding algorithm, requiring an additional 'dimensionality' to the search-tree, with "n ladders left" (in this particular example, as it could include other used-as-resource items) branches 'overlapping' the same 3D space[1].  Perhaps less intrinsically complicated is an AI behaviour that allows emplacement of bridging-resources (temporary pathabilities) and then removal of same once the last unit is across, for re-use later on, but it requires a coordination of unit AIs (or at least an assumption of this, in the original path-finding, to be fulfilled as far as local conditions eventually allow).


Less controversially, in the multi-mode connectivity map, future possibilities of the presence of 'sappers' in a unit should allow (at a movement cost, at least insofar as time) pathing through solid rock (or at least soil), and building (or construction!) destroyers having a similar possibly biased-against possibility of pathing through other 'solid' areas.  But while this, also, should also be something to consider when designing the pathing from ground up, it of course does not apply to the current incarnation, so you may wish to hand-wave it away (or consider it, and reject it, in the initial write-up of the problem description)

Certainly, compared to these other examples, a connectivity map containing maps with "up to two 1 Z's climbed up, up to 2 Z's jumped down, and the ability to leap 1Z-wide channels/gaps", or however many can be done in a single move, is not overly complicated.

But if that linked-to thread is not the one of the ones in which I already mention all of this, I'm sure the various other threads can be found, as well.  For inspiration, only, as there's always a lot of different interpretation and ideas, in those, not all of which might be considered useful to you.

[1] You don't just forget that a tile is reached in 16 steps if an alternate path is found that reaches it in 8 steps.  If the former used one of the expendable 'bridges' and the latter used two of them, you'd have to retain both figures until you knew whether the lack/availability of the final bridge invalidated/validated an optimal path further down the lane.

[Starver]

Oh, and something else I was going to say, in case it hasn't already been mentioned:  Artificial Stupidity.  Omniscient (albeit without a sense of the differences to which paths will/will not be possible, sometime down the line[1]) pathfinding has regularly been denigrated.

Sometimes, of course,  it's actually a feature of the path-caching to have AS.  "Word of mouth" about discovered routes meaning that a small number of regular paths are used except where some other route is 'discovered', at least until somewhere not yet known to be pathable is actively searched for and such successes (or intermediate successes to other locations) are reported back to the other agents to add to their own usage-trees (or the shared hive-mind one).

(Reminds me of that pre-"Bug's Life" short where the leaf falls across the ant-trail.)


Not that this applies to the OP's project.  (Still to find out if anything more has been said about that.)  Just thought it worth saying, as I'm doubtless already not in line with the current state of this topic.


[1] And I didn't mention adding to the pathing algorithm the ability for the agents to understand and use lever-controls, in their travels, especially in the form of air-locks where pathing to a dead-end spot where they can activate a further stub, within which they can make this stub extend further still...

[No1]

Woah did not see those posts coming.

Anyhow there are very many nice ideas and additions to make this a more "complete" fantasy simulator. However to make it more complex before the performance issues has been solved or at least reduced there shouldn't be any additions.

The AS you mentioned would make the game more realistic on a good level, a goblin shouldn't know the way through the complex maze entrance some forts uses and it would enable a usage of multi paths that does not lead anywhere. It's not easy to make a computer stupid it is probably in the same class as making it smart, they often rely on partial omniscients and the less it knows the more it behaves stupidly adding random to choices but weighting them depending on some "knowledge".

[Farmerbob]

I mentioned this in a different thread a long time ago, but I believe that a lot of issues might be solved by implementing a new aspect of the bookkeeper's job.

At this time, the bookkeeper does nothing after they finish their first survey.  Give them something else to do.

Create a building type: Bookkeeper's Station

The bookkeeper builds it, and must maintain it from time to time.

The maintenance is the bookkeeper wandering around in nearby storage, going from station to station, and talking to miners, woodcutters, etc.

The game creates lookup tables.

Dwarves path to items by consulting Bookkeeper's Stations, and using the prebuilt lookup tables.

Dwarves would mark that they are going to take an item after they visit the bookkeeper station.  If they fail to move the item all the way to it's destination, the item will be off the list until the bookkeeper stops back by and maintains the station.

You would want to generate a lookup table for each Bookkeeper station, with a real shortest path, then also carry a table of path distances between Bookkeeper Stations.

This entire process other than the actions of the dwarves themselves might be handled in a separate CPU thread?