Recent investigation of slowdowns in D2X-XL have led to the insight that path finding contributes quite a bit to the issue, with massive levels massively increasing that contribution. D2X-XL does path finding for each sound playing, trying to determine the distance to the listener, i.e. the player, and for each robot that is looking for a target (usually the player as well ). Robots do not contribute too much, since there are only so many robots aware of the player in almost all instances. If a level contains a lot of ambient sound, this can really impact performance though, particularly if the level is huge. It didn't help much that I had turned off the cache ages ago that was keeping the most recently computed routes through the level because it had more misses than hits.

Dijkstra is too slow

The first thing I tried was to replace Parallax Software's brute force breadth-first search with a Dijkstra Address Calculation Sort based algorithm. That worked very well and elegantly, but data buffer management overhead was so massive compared to the path finding that it slowed down the search inacceptably. DACS is good for huge networks where so many network nodes have to be expanded that management overhead doesn't play a role.

Bi-directional search does the trick

So I got back to the breadth-first search. First thing was to streamline it quite a bit, since Parallax' implementation somewhat lacked elegance and simplicity (isn't simplicity always elegant?). The essential step however was to make the search bi-directional, i.e. start from both the start and the destination segment and find the segment where both searches would meet. The performance increase achieved by this was to be expected, but most pleasurable none the less: Bi-directional search only touched roughly 1/3 of the data the uni-directional search did, about doubling the performance of the search (the additional data management consumed some time, too). This will work with all but the weirdest of level topologies (i.e. very linear, stretched out levels), and won't hurt much with those either.

Multi-Threading doesn't help

The final thing I tried was to make both searches concurrent by putting them in threads. It turned out that the search was so fast that the additional thread management degraded its performance by quite a margin below the sequential bi-directional search.

Caching does though

Turning the caching on again (and using different caches for sound and robot path finding) increased performance by another 65%.

Having explored every option here and found the best one leaves me pretty satisfied about this corner of D2X-XL.