I'd suggest giving up on SAP, because it seems like a completely unhelpful algorithm for this problem . There may be some things it's good at, but it sounds like this isn't one of them, and trying to twist it to work non-terribly is unlikely to result in something that actually works well. CCmpRangeManager deals with points rather than bounding boxes, so it only has to put entities into a single cell (except for the rare cases where an entity is precisely on the edge between cells, which we could avoid by being more careful about the edge conditions). We have to sort the results so that we can do std::set_difference to see which entities have entered/left the range (there's no way to avoid putting an O(n log n) operation somewhere, when we're doing set comparison), and once we've sorted them it doesn't cost much to do a std::unique. (CCmpObstructionManager does deal with bounding boxes, but that's all tied in with the pathfinder design and needs to be changed anyway.) Agreed (I said similar things on IRC yesterday) . Moving self-contained latency-tolerant things like the AI and pathfinder into separate threads should give much greater benefit, with much less pain than will come from uncontrolled access to the entire simulation state from multiple threads. On Combat Demo Huge? That's a fairly unrealistic extreme case, and if we were running at full speed then 24ms/turn would still only be about 10% of total CPU time. I had assumed it was worse than that...