Collision detection, bruteforce -> Quadtree

[VoS]

Hey.
Im currently working on a little game to try out lwjgl and get my hands a bit dirtier with game development in general.
Ive got a little test-case going which has a bunch of random objects flying around, collisions are checked against other entities via brute force, ie O(n^n).
A collision exists if the bounding circles of two objects (rocks) intersect.

This works fine when ive only got a few objects on the screen 200-300 or so...
but when i increase the objects in the thousands it gets a little *choppy*

So my focus as of lately has been on trying to make this more effective, not that i really need to for the purpose of the end game i want to make but i want to

my first idea was to make a list for each entity containing all other 'collidable' entities ordered by the distance from the object.
This list would be updated every 1-2 seconds. The logic for testing would then be, if object 1 collides then check object 2, when no more are colliding i dont need to check the list anymore.

The memory usage for this was kinda evil though and it required Quite a bit of computatioal power once it updated.. so my next idea was to sort by grid where I would only need to check the objects in one square against each other, which brought me to quadtree's.

So my question is (as i dident find anything when searching this forum) is this a good way to go, are there better ways?
Has anyone done any examples using this?

For those wondering what a quadtree is: http://en.wikipedia.org/wiki/Quadtree

So what direction can i be pointed in, id love to see some example code, that usually helps me understand better than wordy explanations.

/V

[VoS]

So.. I took a crack at this using a grid based approach.. It seems to work decently. The most expensive operation seems to be when updating the positions of the entities in the grid.

When only doing updates every 30 ms ( each entity updates itself every 30 ms from when it entered the game ) it seems to be ok.

There is a performance improvement vs brute force, although its not huge.

The code:
The 'world' class which all the entities update to.

package berfenfeldt.spacer.world;

import java.util.ArrayList;
import java.util.Enumeration;
import java.util.Hashtable;

import berfenfeldt.spacer.entity.Entity;
/**
 * @author VoS
 */
public class World {
	/** pixel size of map */
	private int xsize;
	private int ysize;
	
	/** grid size of map */
	private int width;
	private int height;
	
	/** internal counter for globally unique id's */
	private long nextIdStepper;
	
	/** how often to divide map into a new grid i.e. xsize/resolution=gridsize */
	private int resolution;
	
	/** the 2d grid that keeps the list of what entities are where */
	private gridNode[][] gridArray;
	
	/** An array of all the entities in the world */
	private ArrayList<Entity> entityList;
	
	/** a list of all the gridnodes that have entities in them */
	private Hashtable<Integer, gridNode> nodesWithDataInThem;

	
	/** how many different grid nodes / cells does this world have */
	private int totalQuadrants = 0;
	
	/**
	 * Provides a world view divided into regions simplifying both 
	 * collision detection by only doing it on a subset of items as well
	 * as knowing easier what to render, by being able to figure out what  
	 * other grid's are near the users own grid
	 * 
	 * The resolution value should be bigger than the diameter of any entity in the game.
	 * 
	 * @param xsize the total x size of map
	 * @param ysize the total y size of map
	 * @param resolution what resolution to divide grid into (10 = every 10th units)
	 * @param entities the list of objects in the world
	 */
	public World(int xsize, int ysize, int resolution){
		this.xsize = xsize;
		this.ysize = ysize;
		this.resolution = resolution;
		
		nextIdStepper = 0;
		
		/**  
		 create a new grid to place entities  in 
		 and remove one value in each direction
		 because we will always round down, ie 
		 30x30 with resolution 10 = 3 units of
		 
		 0 0-10
		 1 11-20
		 2 21-30
		 
		 entity with x22 y12 -> 2,1
		 entity with x0 y30  -> 0,2
		 
		   x->
		 |-----|-----|-----|
		 | 0,0  | 1,0  | 2,0 |
		 |-----|-----|-----|
		 | 0,1  | 1,1  | 2,1 |
		 |-----|-----|-----|
		 | 0,2  | 1,2  | 2,2 |
		 |-----|-----|-----|
		
		My world is NOT centered around 0,0
		*/
		
		width =  (int) 	Math.ceil(xsize / resolution);
		height = (int) 	Math.ceil(ysize / resolution);
		
		gridArray = 	new gridNode[width][height];
		entityList = 	new ArrayList<Entity>();	
		nodesWithDataInThem = new Hashtable<Integer, gridNode>();
	
		for(int x = 0 ; x < width; x++){
			for(int y = 0 ; y < height; y++){
				gridArray[x][y] = new gridNode(50, x, y, totalQuadrants);
				totalQuadrants++;
				
			}
		}
		System.out.println(
				"World grid keeper\n" +
				"\tQuadrants (WxH): " + width + " x " + height+ " = "+ totalQuadrants +
				"");
	}

	/**
	 * Get the position of an element in the world 
	 * grid at the following x and y coordinates
	 * @param x the x position of the object
	 * @param y the y position of the object
	 * @return int[x, y]
	 */
	public int[] getPosition(float x, float y){
		return new int[] {
				(int) Math.floor(x/resolution),
				(int) Math.floor(y/resolution)};
	}
	/**
	 * Add an entity to the world
	 * @param the entity to add
	 */
	public void addEntity(Entity e){
		// the difference from this and update node is that we here
		// add it to the total list of entities so we know it exists ;)
		updatePosition(e);
		entityList.add(e);
	}
	/**
	 * Removes an entity from the world
	 * @param the entity to remove
	 */
	public void removeEntity(Entity e){
		removeAllCornersOfEntity(e, e.getRadius());
		entityList.remove(e);		
	}

	/**
	 * updates the entities position in the grid layout of the world
	 * @param Entity to update
	 */
	public void updatePosition(Entity e) {
		
		float oldPosition[] = e.getGridPosition();
		
		// check so its moved, does it need updating at all?
		// compare the position it was last saved into the system with the 
		// position its currently at
		if(oldPosition[0] != e.getX() || oldPosition[1] != e.getY()){
			
			// get the radius of this item.
			float r = e.getRadius();
			
			// if it has an old position of -1 it has never been added before
			// hence it does not need removing...
			if(oldPosition[0] != -1){
				removeAllCornersOfEntity(e, r);
			}
			
			// set the grid position of the entity to the current x and y location
			// so we can use this to know what to remove it from if we need to do that..
			e.setGridPosition(e.getX(), e.getY());
			
			// Calculate what grid locations the four corner points of entity are at.
			// Basically which different gridNodes the Entity needs to go into.
			// Then write the entity to this/these gridNode('s), even if its already there
			// Mostly because i can't think of anything faster then
			// O(nlogn) of adding it to the HashTable (which overwrites if it exists)
			int xNE = (int) Math.floor((e.getX()+r)/resolution);
			int yNE = (int) Math.floor((e.getY()+r)/resolution);
			addEntityToGridSection(e, xNE, yNE);
			
			int xSE = (int) Math.floor((e.getX()+r)/resolution);
			int ySE = (int) Math.floor((e.getY()-r)/resolution);
			addEntityToGridSection(e, xSE, ySE);
			
			int xSW = (int) Math.floor((e.getX()-r)/resolution);
			int ySW = (int) Math.floor((e.getY()-r)/resolution);
			addEntityToGridSection(e, xSW, ySW);
			
			int xNW = (int) Math.floor((e.getX()-r)/resolution);
			int yNW = (int) Math.floor((e.getY()+r)/resolution);
			addEntityToGridSection(e, xNW, yNW);
			
			// so all of the above is O(4 * n*log(n))
			// hope thats fast enough..
			
			// now update the list that knows which gridNodes has items in them
			// This is used so we only loop through nodes that has things that 
			// can crash in them once we collision detect..
		}
	}
	/** 
	 * This code is used in two places to pulled it out into a private method 
	 * Basically it just removes a entity from all its current grid positions 
	 * @param The entity to remove
	 * @param The radius of the item
	 */
	private void removeAllCornersOfEntity(Entity e, float r) {
		
		float[] gpxy = e.getGridPosition();
		
		int xNE = (int) Math.floor((gpxy[0]+r)/resolution);
		int yNE = (int) Math.floor((gpxy[1]+r)/resolution);
		removeEntityFromGridSection(e, xNE, yNE);
		
		int xSE = (int) Math.floor((gpxy[0]+r)/resolution);
		int ySE = (int) Math.floor((gpxy[1]-r)/resolution);
		removeEntityFromGridSection(e, xSE, ySE);
		
		int xSW = (int) Math.floor((gpxy[0]-r)/resolution);
		int ySW = (int) Math.floor((gpxy[1]-r)/resolution);
		removeEntityFromGridSection(e, xSW, ySW);
		
		int xNW = (int) Math.floor((gpxy[0]-r)/resolution);
		int yNW = (int) Math.floor((gpxy[1]+r)/resolution);
		removeEntityFromGridSection(e, xNW, yNW);
	}

	private void addEntityToGridSection(Entity e, int x, int y){
		// make sure we aren't under, below or beside the map
		// if we are wrap it around so entity gets added to the other
		// end of the world too
		if(x<0){ x = width - 1;	}
		if(y<0){ y = height - 1; }

		if(x>width-1){ x = 0;	}
		if(y>height-1){ y = 0; }
				
		gridNode n = gridArray[x][y];
		n.add(e);
		
		// if the node has more then 1 entity add it to the list of nodes with stuff to collision detect.
		if(n.size()>1){
			nodesWithDataInThem.put(n.getID(), n);
		}
		
	}
	/**
	 * removes any occurrence of a Entity from a gridNode
	 * Wants x and y coordiantes b/c they might be different from 
	 * where the Entity is at now
	 * @param Entity to remove
	 * @param X coordinate to use
	 * @param Y coordinate to use
	 */
	private void removeEntityFromGridSection(Entity e, int x, int y) {
		if(x<0){ x = width - 1;	}
		if(y<0){ y = height - 1; }

		if(x>width-1){ x = 0;	}
		if(y>height-1){ y = 0; }
			
		
		gridNode n = gridArray[x][y];
		n.remove(e);
		
		// if the node has less then 2 items no use collision detecting in it.
		if(n.size()<2){
			nodesWithDataInThem.remove(n.getID());
		}
	}

	/**
	 * get a list of all the nodes with entities in them
	 * @return ArrayList<int[]>
	 */
	public Enumeration<gridNode> getNodesWithDataInThem(){
		return nodesWithDataInThem.elements();
	}
	/** know the size of the world */
	public int getMaxXWidth(){
		return xsize;
	}
	public int getMaxYHeight(){
		return ysize;
	}
	/**
	 * get the next available global ID
	 * @return unique Long
	 */
	public long getNextID(){
		nextIdStepper++;
		return nextIdStepper;
	}
	
	/**
	 * Get a copy of the current entity list
	 * @return Entity[]
	 */
	public ArrayList<Entity> getEntityList(){
		return entityList;
	}
	/**
	 * get all entities in a specific grid location
	 * @param x
	 * @param y
	 * @return list of entities
	 */
	public Entity[] getEntitiesInGridLocation(int x, int y){
		return gridArray[x][y].getEntityList();
	}
	
	/** debugging */
		public int getTotalEntities(){
			Hashtable t = new Hashtable<Integer, Entity>();
			int r = 0;
			gridNode h = null;
			for(int x = 0 ; x < width; x++){
				for(int y = 0 ; y < height; y++){
					h = gridArray[x][y];
					for(Entity ee : h.getEntityList()){
						t.put(ee.getID(), ee);
					}
				}
			}
			return t.size();
		}
		public int getTotalEnt(){
			return entityList.size();
		}
}

The collision detection is then done by:

private void entityCollisionDetectGRID() {
		gridNode n ;
		Entity[] Ents;
		Enumeration<gridNode> d = world.getNodesWithDataInThem();
		while(d.hasMoreElements()){
			n = d.nextElement();
			Ents = n.getEntityList();
			for (int i=0;i<Ents.length;i++) {
				Entity entity = (Entity) Ents[i];
				for (int j=i+1;j<Ents.length;j++) {
					Entity other = (Entity) Ents[j];
					if(!(other instanceof WeaponBulletEntity && entity instanceof WeaponBulletEntity)){
						countCollisionsDetections++;
						if (entity.collides(other)) {
							entity.collide(this, other);
							other.collide(this, entity);
						}
					}
				}
			}
		}
	}

This was my first attempt at something like this... I Would REALLY like some feedback or pointers on where to improve.

[VoS]

also...
When comparing performance, for the Grid based collision detection this heavily relies on the correct grid size
To give you some idea of the performance of the code...

total entities in world: 807

With 400 different grid quadrants

BRUTE collisions tested: 807
GRID collisions tested: 447

With 4 Quadrants
BRUTE collisions tested: 807
GRID collisions tested: 88532

It dosent like big grids... =P

I originally started with Kev's tutorial so all collision detection is really radius tests.
Btw.. great tutorial =)

[princec]

Quadtrees have worked very nicely for me.

Cas

[indexunknown]

huh VoS?
with 807 entities the brute force takes 325221 tests to check if each entity pair collides.

int count = 0;
for(int i = 0;i < 807-1; i++){
   for(int j = i+1; j<807;j++){
      //test collision
      count++;
   }
}
System.out.println(count);