I'm working on a sketch that needs to do collision detection for hundreds (or possibly thousands) of particles, so in an effort to optimize it I decided to try a spatial partitioning algorithm.  I was surprised that I couldn't find any good (simple) examples; everything was either O(n^2) collision detection or jumped straight to Quadtrees.  I thought that something in the middle would be a good place to start, and hopefully a good example for others to learn from.

Here's the code:

1. class Grid {
2.   float binSize;
3.   int noBinsX;
4.   int noBinsY;
5.   ArrayList[] particleBuckets = new ArrayList[noBinsY];
6.  
7.   Grid(float _binSize, int windowWidth, int windowHeight) {
8.     binSize = _binSize;
9.     noBinsX = ceil(windowWidth / _binSize);
10.     noBinsY = ceil(windowHeight / _binSize);
11.     //Setup the 2D ArrayList for the grid
12.     for(int i = 0; i < noBinsY; i++) {
13.       particleBuckets[i].add(new ArrayList<Particle>(noBinsX));;    }
14.   }
15.  
16.  void getParticles(int binX, int binY) {
17.     ArrayList subList = particleBuckets.get(binY);
18.     return subList.get(binX);
19.  }
20.  
21.  int[] getBinNumber(float pos_x, float pos_y) {
22.    //given a particle's position, return the bin number that it is currently in.
23.    int indexX = floor(pos_x / binSize);
24.    int indexY = floor(pos_y / binSize);
25.    int[] binNumbers = {indexX,indexY};
26.    return binNumbers;
27.  }
28.  
29.  void addParticle(Particle particle) {
30.    //Add a new particle to the grid.
31.    int indexX = floor(particle.pos_x / binSize);
32.    int indexY = floor(particle.pos_y / binSize);
33.    particleBuckets[clamp(indexY,0,noBinsY - 1)][clamp(indexX,0,noBinsX - 1)].add(particle);
34.  }
35.  
36. }
37. int clamp(int value, int minVal, int maxVal) {
38.   return max(minVal, min(value,maxVal));
39. }

However, getting things to work with the 2D ArrayList is a bit tricky.  I'm currently stumped with an error occuring at line 33:

"The type of expression must be an array type but it resolved to ArrayList"

This seems to be because I can't use double indices for ArrayLists.  Do I need to get() a sublist and then place the element in the subList?  If that's the case, then do I need to replace the list with the new one also?

Is there a way to add a particle to a bin in-place, or is the only way to do it by copying the subarray and copying it back in?

thanks!