Actually you'll have multiple objects inside one "sector" so when you can discard a sector you can already discard all objects inside it without checking them.

Typically you create some kind of tree hierarchy like a quadtree, octree, kdtree to do these things.

I don't know if it will help you, but this is my class for hash grid which I use in my game.

public class HashGrid {
	
	/*
	 * allGameObjects variable is used to store same objects as an gridObjects arraylist, execpt it is all in one place,
	 * and it is faster to return it, than adding all lists from gridObjects, and then returning them.
	 */
	private ArrayList<GameObject> allGameObjects;
	private ArrayList<GameObject> nearObjects;
	
	private ArrayList< ArrayList< ArrayList< GameObject> > > gridObjects; // two-dimentional ArrayList of ArrayList<GameObject>
	
	private ArrayList<Id> currentIds; 
	private Rectangle [][] gridBounds;
	private int gridSizeX, gridSizeY;
	
	class Id{
		public int x;
		public int y;
		
		public Id(int x, int y){
			this.x = x;
			this.y = y;
		}
	}
	
	public HashGrid(float worldWidth, float worldHeight, float squareWidth, float squareHeight){
		this.gridSizeX = (int) Math.ceil(worldWidth/squareWidth);
		this.gridSizeY = (int) Math.ceil(worldHeight/squareHeight);
		
		gridObjects = new ArrayList< ArrayList< ArrayList<GameObject> > >();
		
		
		for(int x = 0; x < gridSizeX; x++){
			gridObjects.add(new ArrayList<ArrayList<GameObject>>());
			for(int y = 0; y < gridSizeY; y++){
				gridObjects.get(x).add(new ArrayList<GameObject>());
			}
		}
		
		currentIds = new ArrayList<Id>();
		gridBounds = new Rectangle[gridSizeX][gridSizeY];
		allGameObjects = new ArrayList<GameObject>();
		nearObjects = new ArrayList<GameObject>();
	
		for(int i = 0; i < gridSizeX; i++){
			for(int j = 0; j < gridSizeY; j++){
				gridBounds[j] = new Rectangle(i*squareWidth,j*squareHeight,squareWidth,squareHeight);
			}
		}
	}
	
	public ArrayList<GameObject> getNearObjects(Rectangle bounds){
		nearObjects.clear();
		
		setTouchedSquaresIds(bounds);
		int size = currentIds.size();
		
		for(int i = 0; i < size; i++){
			Id id = currentIds.get(i);
			nearObjects.addAll(gridObjects.get(id.x).get(id.y));
		}
		
		return nearObjects;
	}
	
	/**
	 * 
	 * @param obj Game object to test with
	 * 
	 * @return which grid squares the object is touching
	 */
	private void setTouchedSquaresIds(Rectangle bounds){
		currentIds.clear();

		for(int x = 0; x < gridSizeX; x++){
			for(int y = 0; y < gridSizeY; y++){
				if(CollisionTester.rectsCollided(gridBounds[x][y], bounds)){
					currentIds.add(new Id(x,y));
				}
			}
		}
	}
	
	public ArrayList<GameObject> getAllObjects(){
		return allGameObjects;
	}
	
	/**
	 * Adds game object to hashgrid
	 * 
	 * @param obj
	 */
	public void add(GameObject obj){
		for(int x = 0; x < gridSizeX; x++){
			for(int y = 0; y < gridSizeY; y++){
				if(CollisionTester.rectsCollided(gridBounds[x][y], obj.bounds)){
					gridObjects.get(x).get(y).add(obj);
				}
			}
		}
		
		allGameObjects.add(obj);
	}
	
	/**
	 * Removes all instances of speicifed object
	 * 
	 * @param obj
	 */
	public void remove(GameObject obj){
		
		for(int x = 0; x < gridSizeX; x++){
			for(int y = 0; y < gridSizeY; y++){
				gridObjects.get(x).get(y).remove(obj);
			}
		}

		allGameObjects.remove(obj);
	}
	
	/**
	 * Only clears GameObjects.
	 * 
	 */
	public void clear(){
		for(int x = 0; x < gridSizeX; x++){
			for(int y = 0; y < gridSizeY; y++){
				gridObjects.get(x).get(y).clear();
			}
		}
		allGameObjects.clear();
	}
	
}

There are a number of ways to generate the sectors concept ranging from really simple to fairly complex. As LJ mentions, using a simplified concept such as a quad/octree can give you benefits in this area. Say with a quad tree you are simply looking for elements completely contained in a quad area (no overlap with other areas), interactions between one and another quad are completely ignored since there is no overlap. So, say you have 4 objects in quad 1, 4 objects in quad 2 and 4 objects straddling the division. Normally you have (n-1)*n interactions possible without the quad tree, i.e. (12-1)*12=132. With 4 objects in quad one, they have to consider themselves and the straddlers, but we leave the straddlers to check interactions between themselves so the equation is (n-1)*(n-s) where s is the straddler count, n is in quad 1 and the straddlers, or in this case: 7*4=28. The same for the second quad. And finally check the straddlers against each other for (4-1)*4=12. So, the total checks needed is down to 2*28+12=68 checks.

Something wrong with your calculations bruteforce of n objects will be n*(n-1)/2 12*11/2=66. == 11+10+...+1=66

So its the number checks in worst case.

I cant undertand why everyone suggest to use quadtrees, in my experience its always slower and harder to implement than properly implemented grid or hashgrid.

Maybe it was good algorith in the past, but now its much slower becouse of cache missings.

And if you want even to speedup your grid , you can use sweap and prune inside each cell.

I don't know if it will help you, but this is my class for hash grid which I use in my game.

Sveiks,

I think its a simle grid implementation becouse there is no hash function

Sveiks,

I think its a simle grid implementation becouse there is no hash function

I still need to learn many things :)

All found grid implementations I found, even in book are damw far away from perfectness

After lots of optimizations and experiments I found routine that works finiest and its stil on optimizations

but main loop would look like this:

loop
{

//objects update
for(all objects)  //dead,alive, and waiting to be inserted in game world
{
     if(obj.is_dead()){delete obj;continue;}
     if(obj.mut_insert())obj.set_acative();
     if(obj.active)
     {	
        obj.move_object();
        obj.find_bounding_box();
        bool update = obj.find_out_does_it_needs_to_be_updated_in_grid(); //not accessing grid data, maybe tricky or very easy, it depends
        if(update)
        {
            obj.update_id++;
            grid.add(obj);
        }
    }
}
//grid update and collisions
for(all cells in grid)
{
     for(all objects in cell)
     {
          if(cell_obj->obj->update_id!=cell_obj->update_id)delete cell_obj; //delete all elements with old id's
          
     }
     sort_cell_objects_by_box_left_up_corner_x(cell);
     do_collision_like_sweep_and_prune(cell);//with some tricks its easy to avoid dublicate checks so we dont need to check neighbur cells so even object size differences do not mater
}

}

So its main simple main loop.

Some of optimization could be done for example:

do cell objects delete sort and check for collision in one loop (possible allmost done)

find bounding box without resuming all object vectors (done with only 2 vectors)

object insertation could be done in grid.collision routine() becouse on insert you must check if it lands on free space