@Catsup
Play around with that pathfinding visualizer I linked.
http://qiao.github.io/PathFinding.js/visual/ Place start and goal on same y, different x. Place a big wall running up and down halfway between them, with a single hole right between them. Run the simulation (nodes expanded is linear with the path distance).
Add a second wall running parallel to the first, also with a single hole. Run the simulation multiple times with this hole in various places. (moving up one each simulation). You'll notice the further the path goes in between these two walls the more the search horizon (light green squares) extend past the start point in the
wrong way. Therefore the worst case search horizon is roughly proportional to path length times the
square of the inaccuracy of the heuristic... when on a simple 2d plane. Things get FUN in 3d if you set them up like this, as you get memory usage/running time proportional to the
cube of the inaccuracy.
This is a strong argument for highly connected fortresses. Try moving the start and/or goal up and down. You'll see this only increases the inefficiency, even though this is a simple and fairly realistic example.
I found an interview with Toady which said that the dorfs use a "streetcar distance" (which I take to mean Manhattan/taxicab metric), but isn't that an inadmissible heuristic for A* with diagonal movement due to overestimation? Perhaps he misspoke and meant Chebyshev metric. Try playing around with them, they are similar enough for the experiment I outlined above. Oh, and the wiki states that diagonal motion takes 1.4 as long as straight. Since dorfs prefer diagonal movement and 1.4 < sqrt(2), we can't rule out that they use the Euclidean metric either.
But he also hints that he is doing some sneaky stuff in the background (validating that paths from A to B exist before checking them) and gives almost no details. Probably not HPA*, but probably similar. (HPA* uses a pre-processed graph abstraction layer that can rapidly find if a path exists, and
a path, though perhaps not the best) A bug tracker post by him seems to indicate that locking a door causes this abstraction to be rebuilt, albeit inefficiently.
--
@UrbanGiraffe
Are we sure that items have a significant CPU impact? I though I had read that the current suspect for this was actually stockpiles, and that one of the quantum methods seemingly prevented a significant framerate decrease even with tens of thousands of items.
I have a small number of animals (caged), I embarked on 16x16 for testing purposes, aquifer/weather/temperature turned off, have the entire map revealed but no cavern access (those are uncontrolled variables).
Moreover, temperature would seem to be a constant CPU load. Pathfinding would seem to be roughly proportional to the number of actors moving around. Therefore if you half the amount of work it takes for the dorfs to go from A to B then you might not double framerate, but you could double the amount of dorfs [assuming pathfinding is the majority of a dorf's CPU impact].
--
@Victor6
So would just walling off the caverns with locked doors/hatches prevent that problem? Or molding the caverns into a more dwarven shape?
--
I've been looking at mechanical logic for controlling minecarts, but don't want to have to rely on waterwheels to power them (fluid sims being an unnecessary and uncontrolled variable in my experiment). How would I mod the game so either these things require 0 power, or a single water wheel / windmill provides an incredible amount of power?
