For a real-time strategy game, I use a grid to calculate collision. Units don't have a rigid body, they only occupy a cell of the physics grid and if a unit is trying to move on a cell that is occupied, a collision is triggered. The performance is pretty good.

To detect if an enemy is close enough to do a melee attack, I use the same physics grid and I parse the 8 cells around a unit to find any enemies. The problem is that 8 cell scan per unit is too slow. The biggest bottleneck in my game is that units are constantly scanning the cells around them to detect enemies. This might not seem like a lot at a first glance, but it adds up really fast when this process is repeated tens of thousands of times.

How can I improve my physical detection? Would running a rigid body simulation be faster than scanning cells?

I think you should show your existing implementation first, because what you have should, in theory, be lightning fast.

It's hard to tell as you didn't post your implementation.
You're right in that GPU is generally faster than CPU. But I wouldn't implement rigidbody just for the sake of that.
So, if you have grid, why not simply cache which cells are occupied? Would that help?

Yeah, I think you need to post your current implementation, directly indexing to see if something is in a grid should be very cheap.  ObjCells[myX +1 + (myY+1) * mapWidth].indexToObjArray != -1 or what have you.

Though, uh, one cheesy speed-up already comes to mind, maybe only do 4 directions instead of 8 =P

And considering you want to do a Total War-alike, with lots and lots of units, you really want to approach things as a struct of arrays.

Just looking for around cells shouldn't be expensive. But you can do some logical optimizations.

If you find an enemy for current unit, you can inform the enemy about current unit as an enemy. This reduce cost by %50.

Also, check only moving units, stationary unit doesn't need to check for enemy, moving enemy will inform itself...

1 hour ago, ptietz said:

So, if you have grid, why not simply cache which cells are occupied? Would that help?

This might help a lot because I realised I might have a very serious case of cache misses.

45 minutes ago, ferrous said:

Though, uh, one cheesy speed-up already comes to mind, maybe only do 4 directions instead of 8 =P

I'm not sure that would work because my units can move diagonally. I imagine if two units are in diagonal neighbour cells, they might ignore each other. Or not because they'd keep moving in their adjacent cells ? I'm definitely going to try that!

33 minutes ago, wisecode said:

If you find an enemy for current unit, you can inform the enemy about current unit as an enemy. This reduce cost by %50.

Also, check only moving units, stationary unit doesn't need to check for enemy, moving enemy will inform itself...

This sounds incredibly simple and ingenious at the same time.

5 hours ago, Kylotan said:

I think you should show your existing implementation first, because what you have should, in theory, be lightning fast.

This is pseudo code of my enemy detection function. I think I would rather not post the real thing because it might be offensive to some (it's not very pretty).

Entity detect_enemy(Entity me) 
{
        for each cell in 8 cells around me
        {   
                if (cell.is_empty())
                        continue;

                Entity other = cell.get_entity();
                if (other.isEnemy(me))
                        return other;
        }   
        return no one;
}

I'll try all of your advice and let you know of the result.

7 hours ago, Michael Aganier said:

To detect if an enemy is close enough to do a melee attack, I use the same physics grid and I parse the 8 cells around a unit to find any enemies. The problem is that 8 cell scan per unit is too slow. The biggest bottleneck in my game is that units are constantly scanning the cells around them to detect enemies. This might not seem like a lot at a first glance, but it adds up really fast when this process is repeated tens of thousands of times.

This makes me wonder about a few things.

Why is every unit constantly scanning? Shouldn't they only scan when their current action is complete, which typically means once every 1-2 seconds?

How many units have you got in order for this to be repeated tens of thousands of times?  Each unit doing the scan should only scan the four neighboring cells for a list, and choose one from the list if the list is not empty. Even if you had a relatively high number of 1000 characters in the world, with roughly 1-2 second actions only about 10 would be scanning their neighbors any given frame, and 10 queries of either 5 cells or 9 cells should complete in under a microsecond. 

If you're doing those things already and still have "tens of thousands of times" every second, it would mean you've got 20,000+ units out there all looking for actions.   At that point you're talking about perhaps a full frame of 15 or 20 milliseconds doing that work, but you're going to have other serious bottlenecks with that many objects in the world.

2 hours ago, Michael Aganier said:

This is pseudo code of my enemy detection function. I think I would rather not post the real thing because it might be offensive to some (it's not very pretty).

You say it's not pretty, so maybe that's the problem? I think you should show the mess  Maybe bad memory layout or too much indirection. Maybe you should sort entities so they match grid memory order to improve caching.

2 hours ago, Michael Aganier said:

3 hours ago, wisecode said:

If you find an enemy for current unit, you can inform the enemy about current unit as an enemy. This reduce cost by %50.

Also, check only moving units, stationary unit doesn't need to check for enemy, moving enemy will inform itself...

This sounds incredibly simple and ingenious at the same time.

With your current code, each entity would detect the top left neighbour first (if there is one and top left is first cell to look for). So using the suggestion would break this behavior. (Maybe that does not matter, just to mention. Maybe you want this more random anyways.)

15 hours ago, Michael Aganier said:

This is pseudo code of my enemy detection function.

The problem with the pseudo code is that it leaves out all the important information:

• How do you determine which the 8 surrounding grid squares are? These should be O(1) operations but it's possible to get this wrong.
• How is cell.get_entity implemented? If there's only one entity possible there, this too should be O(1), but again, maybe this is wrong.
• How is isEnemy implemented? Again, see above.