I did test. All it takes is a door. Close the door, my system runs fine, open the door and it drops down to almost nothing.
Okay so there should have been little difference other than scope of search space between those two states.
Did the same test with a siege which has even more units and the door test produces far less of a change in FPS.
Of course I'm assuming it is because they are invisible. It could just be their red noses and big feet.
However this makes no sense at all if it was purely pathfinding a siege should be as bad. Unless the invisible demons where fliers? but even then they should probably be able to path to a dwarf before needing to fly much.
The answer is special cases. WE don't know and can't test the actual differences between "invisible" creatures and visible creatures. Only Toady knows. There is probably something in the code that a profiler(which Toady recently started using) would show is causing a performance bottleneck. The detect test could be the source of the slowdown for all we know. Kind of like how the way a forbidden door doesn't stop pets from trying to path through a door but does stop the pet from going through it with the end result being a pet that is constantly trying to repath through the door. That is a special case that we can understand because it is visible and obvious if you are paying attention. It is thought that the "invisible creature" slowdown cause might be similar to the pet/forbidden door problem.
That pathfinding is a major source of slowdowns is not an assumption. To test this, make a simple fort and turn weather, economy, temperature, and invaders off, grow the fort to 200 dwarfs then remove all jobs so they are all idle and set a 200+ item stockpile to be moved from one place to another. You will observe a significant difference in the FPS between 200 idle dwarfs and 200 dwarfs hauling things even a short distance, and people have recorded this. I personally did a similar test with assigning 80 dwarfs to stone detailing and ordered a large area smoothed and watched as my FPS dropped from the low 40's to below 20.
Additionally, there is a general observation that the more pathable creatures there are on a map the slow the game runs, this is one of the reasons why caging animals improves game performance. Historically, pathfinding is a non-trivial problem to code and, our own observations, along with Toady's admissions, indicate that there are problems related to the pathfinding code. Like how flying units won't fly to something unless there is a valid ground path to their destination, which is a problem related to the implementation of the connectivity map. Other behavior also causes slowdowns, like how off-duty dwarves check un-owned chests and cabinets for jewelry and trinkets, which can cause dwarfs to spam for paths as every idle dwarf checks and rechecks every empty and unclaimed chest repeatedly.
Sieges, specifically, are another special case, it is our understanding that the target of a siege is the dwarf closest to the siege when it spawns. But for invisible units, the target may be an item, the
closest child, or a random dwarf, which might be 15-z levels down and on the other side of the map AND may need to be repathed EVERY SINGLE frame because it has moved.
All of that said, there are
other major causes of slowdowns. The graphics code has historically been one, but it is being addressed. Another know source of slowdowns is the number of items/objects on a map. The assumption there is that the dynamic tables being used to keep track of each item and all it's details is big enough that accessing them invariably leads to multiple cache misses and multiple calls to main memory. A little math, some knowledge of computer architecture, and a few assumptions about how item information is stored supports this assumption.
-----
I couldn't find the current algorithm (is there one? Conversation seems to go in circles a lot) but anyway, an observation:
I think generating a complete path to your destination is a waste. You're too likely to have the path invalidated (by map changes, something getting in the way, Dwarf deciding he's thirsty and dropping his current task, etc.)
Generate zones (areas of limited size which are contiguous for the most limited movement type possible in them - i.e. a normal floor area would be part of a zone where the entire area is contiguous for a creature which can walk but not open doors, an area of water for one which can swim but not open doors, a tile with a door on it for creatures which can walk and open doors, etc) with connectivity links (not specific paths, just info that they zones are connected) to adjacent zones. Generate an initial path on this (comparatively very simple) zone network, and then just generate a path to reach the next adjacent zone as you need it.
You'll end up generating a lot more paths, but the cost will be diffused over time, (this doesn't seem so important in DF as in games that demand a smooth framerate - but caravans and sieges arriving can still cause huge, nasty hitches from the cost of the initial long pathfind for a bunch of new creatures entering the map all at once) and with relatively small zones the individual paths should be fairly trivial to solve. Additionally, as you know you are only pathing as far as the next adjacent zone, you can limit pathfinding to within your current zone - so in the worst case, of a failed pathfind, you'll only floodfill your current zone. (Though this should never happen if your connectivity info is good.) Shorter pathfinds also reduce the number of paths which are invalidated and have to be regenerated when the map changes (a map change would only affect creatures currently pathfinding in the same zone, and would only affect creatures pathfinding through the zone but not currently in it if the connectivity changes).
Also, I'd put aside multi-tile creatures for now. They're an edge-case, and even when they're there, there will generally be very few of them. It's not worth optimizing for this at the cost of a better algorithm for single-tile creatures. Not to mention the current lack of multi-tile creatures...
Toady has confirmed that the algorithm used in DF is a slight modification of A*. If you are asking about the implementation that Impaler[WrG] and shadow_slicer put together, read
this paper, this
power point, this
paper, and pages 23 through 26 of this thread.