Yes, traces cut my fps in half too sometimes ... I've added a sleep in it as far as 'height tracing' goes for enemies ... My terrain are relatively flat, but I can imagine games in which this might be a very big problem indeed ... You can forget about constantly tracing, when having more than 5 enemies visible at once.

What did you do to fix the model dependant problem? I might have such a problem too, sometimes enemies get stuck in one particular model.

Cheers