253
« on: June 01, 2011, 11:35:33 am »
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 !
