I experimented with making the navgrid generation code multithreaded. My first implementation actually made things ~25% slower. It wasn't as straightforward to thread-ify b/c the navgrid algorithm is recursive - basically a fancy flood fill, which takes the initial start positions of all chars as the seeds. The simplest way to try to add threads was to spawn 8 threads for the 8 search directions, wait for them all to complete, and then kill the threads, and so on.
Another approach I may try some other time would be to have 8 work queues, one for each thread. Each queue would have a critical section for updates, and also an event that is signaled when there is more work to do. I could still have 8 threads, and every time I wanted to check a node to the east, I would stick it on the east work thread, and set the signal. The worker threads would then wake up via the signal, and then proceed to handle everything in the queue, then sleep on the signal again.
The confusing thing is to figure out when to quit. Each search of a node can potentially bring in other nodes to test. I suppose when all 8 queues are empty, then it's done. But how to be sure that they are really empty for good, and you didn't just check it at the wrong time? hmmm...
I changed the way the smoke particle system works. I used to issue many smoke particles at once, like 8-12 or so, when a laser bolt hit something. This was faster than making each its own object, because I could cull and draw them as a group. Once the enemies started shooting more, and we changed to the burst fire system, this became overkill and slowed things down, as the smoke performs collision detection with the world and other objects in the game, so I changed it to issue a single puff instead. I made all bullet firing weapons make smoke come out of the muzzle, which slowed down things a bit.
Yesterday I made only a single smoke particle cluster object for the whole game. It tracks and renders all puffs, and an entire object is not being constructed every time a bullet comes out, so it's noticeable faster in firefights.
Just made another change - if a puff is ever out of the view frustum, I kill it. I may add some slop to this later, but I think this will help even more. Alternately, I could add a time it's been invisible and kill it after a timeout.
regarding the smoke being killed when off-screen... what happens in a fire-fight where I suddenly move the camera around (lots of smoke gets killed for being off-screen) and then move it back to where I previously was looking - all the smoke is gone. I guess it might not be noticeable, but i've found myself noticing odd little things like that in games (Grand Theft Auto has always been an offender here!)...
As for MT'ing the navigation code... surely theres a stopping condition in your current code that can be adapted? Once a worker thread has hit the end of its search it could signal back to the manager/core thread and everything is complete when all 8 threads say they've got nothing else to do.
Or, alternatively, maybe just cap the number of levels down the search tree it can go - say 100 iterations (or whatever testing reveals)...
I dunno - just guesses given I don't really know that much about how your code works [grin]
Keep up the good work,
Jack