Short Version
What is a performance friendly way of detecting collisions in a large, open map where objects are generated on the fly?
Long Version
I'm currently working on recreating the first Android game I've ever made (https://play.google.com/store/apps/details?id=com.Joey_Ant.Lite&feature=search_result#?t=W251bGwsMSwyLDEsImNvbS5Kb2V5X0FudC5MaXRlIl0.)
I am rebuilding it from the ground up and adding about a hundred new features.
Description of the game: User will be in control of an ant colony that has an underground, grid based map, and an above ground open playing field. The ants will have AI and there may be a large number of ants. (Which means I need to optimize the crap out of everything.) The maps will be highly variable. (I plan on making a map creator and letting users create and download maps online.)
So, in a map full of a large number of objects and other ants / creatures, what is the optimal way to detect collisions? I can't be looping through all other objects to detect collisions, as this would have to happen for each creature and would hog too much cpu time.
What I have considered
Grid: Creating an arbitrary grid object. The grid object would create sub regions (the actual grid) and everytime a creature "thinks". it would update the grid object with a reference to itself. Then, the creature will ask the grid object for other objects within it's grid. This would hopefully greatly reduce the number of checks that need to be made. But the overhead for this might be more. This grid may be beneficial for allowing creatures to detect other creatures in its general area as well, as AI decisions will be effected by other objects and creatures in the area.
Occupied Grids: Essentially the same as the above grid option, only the grid object is created by objects. Say I have 3 Objects (A, B, and C). When I initialize Object A, it creates a grid cell with a specified width and height. Object B is initialized, but is in the same area as object A, so it adds itself to that grid area. Object C initializes outside of the area, so it creates a grid cell for it's location. If Object C enters the cell object A is in, its previous cell is destroyed. I guess you could picture this as blowing bubbles.
Any ideas of a better way to do this?
This is quite an old question, i don't know if you came to a solution, but why not using one of the already developed collision detection and physics engines, instead of inventing the hot water. Here are some possibilities:
There are good examples how to use them also.