Print

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

[deek0146]

This is more of an open letter to Toady rather than a discussion thread, but please post thoughts and remarks.

A preface:
I love dwarf fortress, its a game that I have singularly played more than any other. But the slowdown caused by pathfinding causes me no end of despair, as the game slows down incredibly once you have about 60 dwarves, or less with uncaged animals.

I am a third year Computer Game Applications Development student at the University of Abertay Dundee, and for my dissertation project I am considering researching pathfinding methods, and I would like to write a pathfinding system to integrate into dwarf fortress (in the same way that the graphics system was replaced by an SDL version).
Obviously this sounds overly ambitious, and presentation of this idea would be better delayed until I have managed to write something worthwhile, but if from the start I could have an understanding of what kind of requirements such a system would have, it would make it easier to write a system that could be tested in dwarf fortress without rewriting significant parts of it.

Technical details:
The system would be based on Dynamic Heirarchical A*, many essays on which can be found with a google search, but with a concentration on massive parallelization and scalability.

[Thief^]

Requirements I can think of for DF:
Dynamic map (this screws with your ability to do async pathfinding you realise) which you could read from a live DF using DF hack if you really want
Hundreds of moving units
Variable tile cost
Different kinds of unit movement (walk/fly/swim/amphibious (can be ignored for your dissertation really))
Liquids pathfinder (probably needs a separate approach, so I'd ignore it for now)

I would guess that the current code assumes pathfinding is calculated synchronously.

You'd need Toady's help if you need specifics, and I wouldn't expect you to get them (Toady is understandably wary of sharing the code for DF).

EDIT: My final project for my BSc was an A* pathfinder and simple AI state machine, so I have some idea what you're about to attempt. Good luck

[Cyntrox]

It'd also have to be able to handle 3D, and different paths for different entities - a pet might not be able to pass a door that a dwarf could.

[Fieari]

See: This Thread.  Long, but likely very useful for you.

[Dae]

First of all, you should probably make it with DF in mind, but don't expect Toady to implement it; instead, make it as versatile as possible, make it easy to implement with ANY pre-existing framework, and then perhaps Toady will consider the hassle of migrating his code to accomodate yours.
That sets up two goals : make it fast and efficient concerning processing power, AND make it easy to integrate.
Moreover, it has to be modular enough that you can simply add new information to nodes and new ways to pathfind.

The first thing to notice is that you'll have to sacrifice memory for CPU, but it's really okay. RAM is cheap whereas DF sets the CPU as a rare resource. Don't be afraid to cache. In fact, I would suggest you build different maps for each type of move (walk/fly/swim). For amphibious, you can either do it brute force and build a totally different map OR check the union of walk and swim. Your call, but don't forget you have to keep your API user-friendly, so if you go that path, you'll have to enable unions of whatever map with any number of different maps.

Concerning the API, the most modular would be the simplest : one node can be created, attached to other nodes, it can be passable or impassable and its cost can be changed. It has 3 coordinates. Let the user handle the map building and the cost setting, there are too many variables in DF for you to take into account. Also, Toady won't have to ask you everytime he wants to add a new parameter to the algorithm.

Z-levels are easily handled, they're just a node with a different Z coordinate. If they are attached to a node with a different Z-coordinate, good for it.

Cache every path taken, on every level, separately. I mean if one dwarf wants to path to a place and another dwarf 3 tiles away wants to go to the same destination, if only for 4 tiles of distance, their path through the upper levels should be mainly the same and so the second could reuse most of the calculations of the first. Only the lower levels at the beggining and the end should differ.

Clean the cache when a node is updated, and the cache of every level above it. Wait for someone to ask for information before re-building this section of the map, or else you'd have consequent lag when mining, or with water flowing. Imagine you flood a valley, but there is no one in it. The cache will be cleaned but if you compute it again as soon as the cache is emptied, you'd have hundreds of updates each second. If you wait for someone to ask "what if I tried to go through the area that is being flooded ?", then you only compute it once.

Also, if you use C++ (which I highly recommend for pathfinding), make the objects that you want to be thread-protected mutexable in themselves by inheritting from a class that allows it to be mutexed in reading and writing, separately.
By putting the mutex on the object rather than on a list, you'll have significant gain. By separating the lock in reading and writing, you allow many users to check a tile simultaneously while a write is pending. Note though, that it leads to a HUGE amount of mutexes and I'm not sure all OS handle that correctly.
Make the updates of a node non-blocking so Toady's update code doesn't wait for client to have finished pathing before the information is updated, as it would let many dwarves take the wrong path.
For the same reason, give updates high priority over pathfinding, meaning if you want to update a tile and 3 dwarves are checking it, wait for them to finish BUT don't let any other read it.

I think I'm done with miscellaneous recommandations. Good luck !

[deek0146]

Cheers for all of the input, and I agree with most of the recommendations.

As for making the API user friendly, thats my biggest priority. I was thinking having it as simple as requesting pathing from A(x,y,z) to B(x,y,z) and it would return a path object with some kind of follow routine.

Thief^ mentioned that the current pathfinding is done synchronously, which I had thought of and is a big concern. The most optimal solution is for Toady to modify his code slightly so as a pathing request can be sent and then retreived, however this puts a decent bit of work on him.
 What I was thinking instead is that the path object (which is returned immediately) would internally be waiting on a pathing task asynchronously, and the follow routine would do nothing the first time it was used (next frame the task has to be finished and then it will start).
 Obviously this entails dwarves pausing slightly (for the length of one frame) before they move off anywhere, but this is actually a common method used in games and isn't noticeable.

Dae: thats an interesting point you bring up about making node information modular, so for example you would have a list of modifiers and in that list would be the user-definable pathing cost, effect of liquids or whatever (I don't actually know if dwarves wade slower than they walk) but its a better idea than I had, I was thinking just making the map information pluggable so that it could be replaced with a wrapper around toady's existing map implementation.

Thief^ what you said about dynamic maps messing with asynchronous work is definately a concern - its the biggest internal issue with this method, but I think I know how I'm going to deal with it.
Also on the different types on pathing (those which can swim etc), thats not too much effort, they would just have a bitmask of their capabilities and nodes in the graph would have a correspending bitmask for what types can pass through it.

A few notes on my planned implementation however:
Thief^ you are correct in that this would not be a liquid pathfinder - bear in the mind that liquids don't use A* they use Dijkstra so theres no way to use heuristics to optimise it.

As to the mentioned of caching - thats not the way that this will work.
If you think about the kind of pathfinding done by dwarf fortress, caching would not be optimal as the miss rate would most likely be below 10% which would actually make it slower than a standard implementation.
My method is based on heirarchical node graphs - that is, nodes that represent large areas, split up internally into nodes that represent smaller areas and so on. This can cause the final output paths to be slightly sub optimal (within 5% however). Here is an interesting paper on the subject http://aigamedev.com/open/reviews/near-optimal-hierarchical-pathfinding/

Obviously this generated node graph algorithm could not work in adventure mode, it would only be suitable for fortress mode as it depends on having a finite space to work in.

[Thief^]

Actually, if you want a research-style project, it IS theoretically possible to make a hierarchical pathfinder for an expandable finite space... calculate and stitch on the node graph for the new area when it's added.

Extending the hierarchical pathfinder to 3 dimensions to make it suitable for swimming and flying would be a good project too. It wouldn't just be adding nodes with a Z to the pathfinder, you'd also need to split on the Z axis to generate a 3d hierarchy, and bitmask the hierarchy edges for walk/swim/fly caps.

[No1]

As mentioned many times the need to make the game run on several cores should be the focus of a new path-finding algorithm.
I've not done much parallel working algorithms but if the main thread could work as a consumer and path-finding algorithms works as producers of paths, I imagine the main thread making a number of requests for paths in a given game-tick. Because the game is "paused" in that moment the map would only be in read mode which makes it easier to make it thread safe. Although it would only improve performance if two or more requests was made at the same instant I think this is not a problem as there are always lots of entities pathing.

Do anyone know the current used algorithm is it just a Dijkstra's or some A* implementation?

[Thief^]

AFAIK the game is not paused during pathfinding at the moment, dwarves finish digging or constructions as part of their own AI tick, in between of other dwarves' AI updates (which could be doing pathfinding). I could be wrong about this but I doubt it.

EDIT: I believe DF currently minimizes the number of pathfinding requests it has to make, for proof see the lag you could get when a single unit started spamming pathfinding attempts every frame. There are likely very few pathfinding attempts per frame.

[deek0146]

Thief^: Well thats an interesting idea, but if you think about it a straight A* method is probably the best for adventure mode - outdoor maps (very few collisions), infrequent use, large areas, as opposed to fortress mode, which is why optimization of a fortress mode is needed.
Using a precalculation method like heirarchical A* would actually slow performance I beleive, because pathing isn't beig done in real time or particularly frequently, and the generation algorithm for the node graph is going to take a while.

No1: Toady explicity said at one point that he uses A*, if you check the wiki there is fort building advice based on reducing heuristic mishits.

[cephalo]

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.

You might also see if you can do something with the massively parallel architecture of modern video cards. I believe there are some algorithms for extremely fast seed fills, (like the paint bucket in a paint program), which is strongly related to A*. You could use such a technique for updating your top hierarchy perhaps.

[deek0146]

cephalo:
I was indeed considering graphics cards, although I have thought of a few issues:
An A* calculation is a rather non-trivial operation, and graphics processors are designed for extremely small operations (the best graphics cards you can get have a limit of 1024 instructions).
Another problem is the type of processors they are. Graphics processors are good at executing multiple, multi-component/dimensional floating point operations, and memory input and output streams with extremely small caches. A* however, involves no floating point operations, which is a large part of the power of a graphics processor lost, it involves complicated logic flow with a high instruction count, and data structure manipulation. The operation of a pathfinding algorithm could not be further removed from the domain of graphics processors if they tried.

Another issue is the south bridge bandwidth. If pathfinding were to operate on a graphics card it would require a lot of data going in and coming out of the graphics card:
The node graph if its being calculated on the CPU (a rather large task in itself)
The level data to calculate the node graph from (absolutely massive, quite unfeasible to transfer I beleive)
Path data being sent back (very small compared to textures and vertex buffers, but still hogging bus bandwidth)

I don't see it as being particularly optimal, although as this is a research project, one of my ideas was to try and conclusively prove it either way.

[ferok]

All the above being said, going the CUDA/graphics card route is unnecessary.  Threading would be nice (and would certainly be a goal of mine if I were doing this), however DF isn't recalculating routes for every dwarf each frame as far as I can tell - it's either doing it at incremental intervals and/or at task completion for each dwarf.  This can be seen plainly when you issue a kill order on a fleeing enemy.  Your military paths to where they were, and when they get there, they find a new path to where the enemy is now.  Therefore, while a handful of dwarves / enemies are pathfinding may be pathfinding on a given frame, it's not really an issue of 50 dwarves pathfinding on a given frame - which is the order of magnitude you'd be looking for.

The A* algorithm itself is procedural in nature, which doesn't really lend itself to multithreading.  Perhaps an excellent dissertation would be research into an extensible multithreaded pathfinding heuristic.  I'm sure there's some research already done there, but I'm certainly not familiar with it.

[No1]

I looked at the report on HPA*, I didn't read the whole document but I think I understood the main idea. The main point I think would help DF alot is the use of predefined(read cached) paths between two commonly used areas(the nodes in the graph, see the document linked above). Although the optimal would be to let the program define these "areas" by itself I think a shortcut would be to make it player defined, I mean the player rather spend a couple of minutes to gain 10% FPS or something then what we have now.

So basically what I mean is that the same way as you define burrows (or zones) you define a node for a graph. When you have defined two zones you can link them with a "path", I guess this could be generated on the time you try to link them. These paths will be prio one to use when a friendly (to avoid abuse) entity tries to move from one defined area to another. Example to these areas are the bedrooms, meeting area, food stockpile etc.

[Niseg]

you should check my pathfinding simulator. I got path caching and a room system. my room system needs an update scheme and some other improvements but it works well. it gets rid of the tunnel vision and reduce the number of visited nodes it also have low inaccessibility penalty but it needs a second pass after generation to get full coverage and reduce the number of rooms.

I'm. thinking about adding mesh generation but I havn't worked on on my simulator at all recently.