Darwinia isn't 10 years old, it's from 2005.
Anyway, to answer the major question about "why are other games faster at pathfinding", there are several reasons.
First, Darwinia and other games like that make for fairly easy pathfinding since they have mostly large open areas with nothing to pathfind around. Just look at what happens when you try to tell Darwinians to go to a point where they have to go around a bend to avoid the water - they walk straight up to the water, then get confused. That isn't pathfinding, that's just going in a straight line.
Second, most games "cheat" at pathfinding. They don't generate their own pathfinding maps, they rely upon a designer-created set of waypoints which, in turn, relies upon the fact that maps are mostly static. You can especially see this in various "cover shooter" games, where every piece of cover or wall has to be "painted" with the parts of the map you can crouch behind, while other pieces of wall refuse to allow you to hide behind them. AI units will walk from one hand-painted waypoint to another along the predefined routes they have to access various parts of the map.
Third, most games use some tricks to hide the time it takes them to pathfind. Often, they'll only allow one unit to pathfind per frame, and all the other units will stand and idle until they get a turn - this prevents a large number of pathfinding units from causing notable spikes in lag, but involves making several units that are commanded simultaniously to move just burn some turns.
Finally (and this is somewhat related to the first), pathfinding isn't as good as it really should be in many games... See the video here -
http://www.ai-blog.net/archives/000152.html (That was linked by Mohican in the most recent pathfinding thread.) (That article also covers things like waypoint pathfinding and talks about why it's time to get rid of it, too...)
The thing is, most of the crutches and cheats that other games rely upon don't work in DF.
The other thing is, basically, Toady knows A* alone isn't as efficient as some of the algorithms that are in the suggestions threads, but he's been hesitant to impliment them. (He also wants to conserve on memory consumption and the algorithm has to react to dynamically changing map statuses.) We've been arguing about how to make an ideal system, but a hierarchical system of almost any sort would make pathfinding run potentially one or two orders of magnitude faster in virtually every common situation, (and no worse than standard A* in the worst cases,) and also allow for multiple forms of locomotion, such as having fliers or swimmers or multi-tile vehicles becoming able to pathfind properly.
Basically, there's a reason why people have been saying that rewriting pathfinding would be easier and far more fruitful a way to speed up the game than multithreading. Multithreading would MAYBE produce a doubling of speed in return for months of programming and probably a year of lingering bugs, but pathfinding rewrites would make the game run ten times as fast for a fraction of the time spent rewriting the code.
Author
Topic: Multhreading Dwarf fortress (Read 13450 times)