Pathfinding takes almost no processor time at all (it's really just basic addition and comparison - absurdly easy math for a processor). The entire reason why pathfinding takes up time is because it has to access several megs of map data from memory, one tile at a time. And most of that data is contained through a complex series of vectors with difficult-to-guess points in memory. That means that the game is slowed down by memory access speed, and the processor speed has almost nothing to do with it.
I'd like to see a bit more testing done before I believe this. If no one else already has, I'll do a few benchmarks with my RAM clocked slower/faster. Anyone else interested in seeing the results of that?
I see you've already gone ahead and done a test (and good for you for doing so), but I'd explain my reasoning for saying what I said, anyway...
This link is a (fairly easy-to-read) description of how A* pathfinding works.
Now, A* pathfinding is actually fairly simple - you just add the traffic weight of a given tile plus what the heuristic says is the distance from the tile you are about to test pathing onto, and compare that to all the other tiles. That's just simple addition and comparison.
The thing that makes A* pathfinding take so long is that in a maze like the sort of thing that most player forts become, A* will often run into a dead end, and wind up going through every single tile in the entire area before finding its way around a given wall - that means it's accessing the data of every single tile in the entire area. That's potentially thousands of checks to memory - per unit pathfinding - and because we are dealing with a series of vectors storing the map data, it is very difficult to make a guess as to what parts of memory you need to access next.
What's behind pathfinding in tying up system resources? Temperature checks on every single item on the map - tens of thousands of items on some maps, all need to be checked for their temperatures every frame, which is up to 100 frames per second. Most temperature checks don't even DO anything, and the few that do only change a small amount of data per frame. You're just iterating through pieces of data, performing a few simple comparisons, then dumping that data, and fetching the next from memory.
So, to go back to pathfinding, the problem with pathfinding, and the reason why people want to improve the pathfinding algorithm isn't that the current A* pathfinding requires crunching way too many numbers, it's that it requires accessing memory far too often looking up bad paths that turn out to be looking for a way to get to the central staircase by going into someone's bedroom, only to find out it's a dead end, then going into the next bedroom, finding out THAT'S a dead end, going to the next bedroom, etc. etc. etc.
It's a problem of the game checking a huge number of individual tiles that it doesn't need to check, and each one of those checks forcing the CPU to queue up another call on the memory for the next set of tiles.
Now, if memory bandwidth isn't being fully used, as Profit says, my best guess is it's because the computer can't speculate on what data it will need to access next (at least as far as pathfinding goes), so it can't take up all the memory bandwidth in one access of memory, and is waiting on what's actually in the memory that the game reads to tell it where to look next in memory. (Which is something that can be helped by multithreading if you just make more than one creature pathfind at the same time, but it still is also something where just making memory access faster results in faster performance.)
The bottleneck is still the processor reading one piece of data, realizing it needs to fetch a new piece of data, and putting the process on hold until the fetch is complete. (Slicing to another thread at that point.) It has to go to RAM because you're never going to have a cache big enough for the sorts of things DF is going to process every frame, and because we are dealing with vectors, it's just plain going to be slower to access RAM. (And RAM access speeds are laughably slower than CPU speeds.)
Author
Topic: Multhreading Dwarf fortress (Read 13451 times)