   tracing point within a grid...
  Hi,I have a game environment(2D), which i have segmented into a 10 by 10 grid, with the idea of making collision detection more efficient. In the environment i have maybe 100's possible a 1000 small circles moving about the environment.I am looking for method to trace which grid these circles are in. Short of comparing the position of each circle to each grid square every frame I'm not really sure what approach to take.I'd appreciate any help or techniques anyone can suggestThanks   
  Assuming that you're already updating each circle's position each loop, you could add a check to see if a circle's grid cell is the same after moving than it was before moving.If it's the same cell, then there's nothing to do.  If it has moved into a different cell, then it should be removed from the old cell's list-o-circles and added to the new cell's list-o-circles.If your circles are big enough to warrant recording them as being in multiple cells at a time as they near a border, then you'll need to separate out the checking for moving into new cells from the moving out of old cells.-Matt;  If they are moving fast or across multiple grids look into 3DDDA. This will help you to do checks in the cells along the path of the point.   ;  hey thanks for replying, I've been working on this for while now, without really getting the results i require.The first approach i took was to compare each vehicles position, which each grid position as below.each grid partition holds a vector list of vehicles, so its basically recalculating this list every frame for every partition// loop through all vehicles in environment and note which partition they are infor(int b = 0; b < 10; b++){for(int c = 0; c < 10; c++){grid[c].vehicles.clear();for(int a = 0; a < vehicles.size(); a++){if((vehicles.at(a).getPosition().x > grid[c].bottom_left.x) &&(vehicles.at(a).getPosition().x < grid[c].bottom_left.x + cell_width) &&(vehicles.at(a).getPosition().y > grid[c].bottom_left.y) &&(vehicles.at(a).getPosition().y < grid[c].bottom_left.y + cell_height)){// vehicles centre is inside partition so add pointer to vehicle in// partitions listgrid[c].vehicles.push_back(vehicles.at(a));}}}}as expected the frame rate went from 60fps to 4 fpsas suggested by MattWorden I've tried to implement a more efficient solution where every frame I will test every vehicles to see if it has changed partitions, if it hasnt then i do nothing, if it has, i perform test on teh eight surrounding partitions becuase it must be in one of those 8, then simply move the object from one vector list to anotherfor(int i = 0; i < 10; i++){for(int j = 0; j < 10; j++){for(int k = 0; k < grid[j].vehicles.size(); k++){// check to see if vehicled is still inside grid index, if it is then nothing needs to be done, if it isnt then// we need to find which partition it is inif(!isVehicleInPartition(i, j, &grid[j].vehicles.at(k))){Vehicle temp = grid[j].vehicles.at(k);// vehicle is no longer in this grid partition so it needs to be erasedgrid[j].vehicles.erase(grid[j].vehicles.begin() + (k));// as the vehicle is not in the same partition as it was the last frame// we need to check teh 8 surrounding partitions because it will be in one of those// check [i+1][j+1]if(isVehicleInPartition(i+1, j+1, &temp)){grid[i+1][j+1].vehicles.push_back(temp);}// check [i+1][j]else if(isVehicleInPartition(i+1, j, &temp)){grid[i+1][j].vehicles.push_back(temp);}// check [i+1][j-1]else if(isVehicleInPartition(i+1, j-1, &temp)){grid[i+1][j-1].vehicles.push_back(temp);}// check [j-1]else if(isVehicleInPartition(i, j-1, &temp)){grid[j-1].vehicles.push_back(temp);}// check [i-1][j-1]else if(isVehicleInPartition(i-1, j-1, &temp)){grid[i-1][j-1].vehicles.push_back(temp);}// check [i-1][j]else if(isVehicleInPartition(i-1, j, &temp)){grid[i-1][j].vehicles.push_back(temp);}// check [i-1][j+1]else if(isVehicleInPartition(i-1, j+1, &temp)){grid[i-1][j+1].vehicles.push_back(temp);}// check [j+1]else if(isVehicleInPartition(i, j+1, &temp)){grid[j+1].vehicles.push_back(temp);}}}}}while the first solution works perfectly(i know because I'm outputting the number of vehicles in each partition) the second method always outputs 0's as the number of vehicles in the partition.I've been trying to correct this for a while now, and probably something simple as usual lol!I'd appreciate any help, and thank for the posts so far thanks   ;  If your grid is rectangular and uniform, finding which grid cell you are in is trivial. For example imagine a 10x10 grid, each cell of which is 20x20 game coordinates.Partition[,] grid = new Partition[10,10];Partition getPartition(float x, float y){ return grid[((int)x)/20, ((int)y)/20];}then something likeforeach(Partition p in grid) p.vehicles.Clear();foreach(Vehicle v in vehicles) getPartition(v.x, v.y).vehicles.Add(v);Okay, it's pseudocode but with a well arranged grid it is that simple.Don't forget that objects in adjacent grid cells can interact in a collision though.   