I’ve shared my tutorial “Using Grids For Collisions” on Google+ and there I’ve got a comment.
I wanna try it but I don’t understand it. Can anybody help me understanding it so that I can implement?
As far as I understand it:
(1) Sort all objects by their x-coordinate
(2) Take only all objects that have other objects with “nearby” x-coordinates
(3) Sort that list from #2 by their y-coordinate
(4) Take only all objects that have other objects with “nearby” y-coordinates
Thus, you have a list of objects that have potentially collided, and you work only with that filtered list of objects.
I just don’t know how to quantify “nearby” the way he uses it.
Sounds like a Sweep and prune. You check all AABBs for overlaps on first the x axis and then the y axis. Basically you check all points one dimension at a time. Then, if two objects overlap on both axes, there´s an intersection. Then you can keep an almost sorted list since an objects position change very little frame… It´s the basic idea, but google “Sweep and prune” and you will find a lot of better explanations. 
ps1. I actually came up with something like this idea a couple of months ago when thinking about how to solve collisions. “How come no one has come up with this idea before?”, I tought. Of course someone already did: David Baraff in 1992! I guess I wasn´t that groundbreaking after all…
ps2. “Nearby” should be “overlapping”.
Maybe like this
import java.util.*;;
interface Getter {
double get(GameObject go);
}
class GameObject {
public double x, y, sizeX, sizeY;
GameObject(double x, double y, double sizeX, double sizeY) {
this.x = x; this.y = y; this.sizeX = sizeX; this.sizeY = sizeY;
}
public double maxDistanceAtCollision(GameObject other) {
return Math.sqrt(sizeX*sizeX + sizeY*sizeY) +
Math.sqrt(other.sizeX*other.sizeX + other.sizeY*other.sizeY);
}
public final static Getter getX = new Getter() {
public double get(GameObject go) {
return go.x;
}
};
public final static Getter getY = new Getter() {
public double get(GameObject go) {
return go.y;
}
};
public String toString() {
return "pos = ("+x+", "+y+") - size = ("+sizeX+", "+sizeY+")";
}
}
public class Test {
static void sortAndFilter(List<GameObject> list, final Getter getter) {
if(list.isEmpty()) return;
Collections.sort(list, new Comparator<GameObject>() {
public int compare(GameObject go1, GameObject go2) {
double g1 = getter.get(go1);
double g2 = getter.get(go2);
if(g1 < g2) return -1;
else if(g1 > g2) return 1;
else return 0;
}
});
ArrayList<GameObject> newList = new ArrayList<>();
boolean foundAPairLastTime = false;
Iterator<GameObject> li = list.iterator();
GameObject last = li.next();
while(li.hasNext()) {
GameObject next = li.next();
boolean foundAPair = Math.abs(getter.get(last) - getter.get(next)) <= last.maxDistanceAtCollision(next);
if(foundAPair || foundAPairLastTime) newList.add(last);
last = next;
foundAPairLastTime = foundAPair;
}
if(foundAPairLastTime) newList.add(last);
list.clear();
list.addAll(newList);
}
public static void main(String[] args) {
List<GameObject> list = Arrays.asList(
new GameObject(100,100,20,20), new GameObject(110,110,20,20),
new GameObject(200,500,20,20), new GameObject(300,600,20,20),
new GameObject(400,700,20,20), new GameObject(310,810,20,20));
List<GameObject> newList = new ArrayList<>(list);
sortAndFilter(newList, GameObject.getX);
sortAndFilter(newList, GameObject.getY);
for(GameObject go: newList) System.out.println(go);
}
}
It’s called a “sweep and prune” collision. Limited to aabbs and very fast. requires a little sorting in realtime too.
Sweep-and-prune can be in any direction and number of dimensions, so a 2D systems can use 1 or 2. As I said in that other thread, nobody can tell you what’s fast without knowing (probably more information you can provide) information about your data set. It’ll be pretty common that a uniform grid will out-perform sweep-and-prune alone however and if your cells can contain a largest number of entities then sweep-and-prune inside the grid cells can be a win (there’s a closely related technique called SAP-trees). SAP can reduce the n(n-1)/2 by limiting how far forward your looking. A uniform grid can be viewed as SAP where your sorting along the axises and only sorting in discrete chunks.
EDIT: No AABB requirement…but if your using the coordinate frame as sort directions then you effectively using an AABB. Also note that for an arbitrary direction D, then choosing -D will be faster or slower.
@DrZoidberg, I’ve added benchmarking to your code.
long ts = System.nanoTime();
List<GameObject> newList = new ArrayList<>(list);
long te = System.nanoTime();
System.out.println("Time taken for creating new list: " + ((te-ts)*0.000001) + "ms");
ts = System.nanoTime();
sortAndFilter(newList, GameObject.getX);
te = System.nanoTime();
System.out.println("Time taken for sorting x-axis: " + ((te-ts)*0.000001) + "ms");
long ts2 = System.nanoTime();
sortAndFilter(newList, GameObject.getY);
te = System.nanoTime();
System.out.println("Time taken for sorting y-axis: " + ((te-ts2)*0.000001) + "ms");
System.out.println("Time taken for sorting both the axis: " + ((te-ts)*0.000001) + "ms");
for(GameObject go: newList) System.out.println(go);
Here’s the output
Time taken for creating new list: 0.054296ms
Time taken for sorting x-axis: 45.428871ms
Time taken for sorting y-axis: 0.023437ms
Time taken for sorting both the axis: 45.543712ms
pos = (100.0, 100.0) - size = (20.0, 20.0)
pos = (110.0, 110.0) - size = (20.0, 20.0)
Does this mean is this slow for a very few objects? I’ll try for adding more objects.
For ten objects,
Time taken for creating new list: 0.016796ms
Time taken for sorting x-axis: 3.447565ms
Time taken for sorting y-axis: 0.046874ms
Time taken for sorting both the axis: 3.580764ms
For 15 objects,
Time taken for creating new list: 0.009374ms
Time taken for sorting x-axis: 1.6327699999999998ms
Time taken for sorting y-axis: 0.061716999999999994ms
Time taken for sorting both the axis: 1.8187019999999998ms
It’s more for less number of objects.
Take care when doing micro benchmarks.
-> warm-up phase
-> dead code optimizations
-> cache sensitivity
-> timer accuracy
-> etc.
Would the performance of this be much better then something simple like this…
public static Point getClosest(Point start, ArrayList<Point> points) {
closest = null;
nearest = 9999;
for(Point p : points){
if(p != null && p.distance(start) < nearest){
nearest = (int) p.distance(start);
closest = p;
}
}
return closest;
}
Distance uses [icode]Math.sqrt()[/icode] which is slow.
Hmm… It really doesn’t seem slow at all…
Here is a little test I wrote up: http://pastebin.com/Yf5e3vst
And here are the results:
Average time TOTAL (10 loops of 100 loops): 0.016ms to find the closest point out of 100 points.
Average time TOTAL (10 loops of 100 loops): 0.124ms to find the closest point out of 10000 points.
Average time TOTAL (10 loops of 100 loops): 12.838999999999999ms to find the closest point out of 1000000 points.
Either I am testing this all wrong… or it really isn’t a problem using a simple method?
This thread is about collision detection. To find all collisions you’d have to call your method for every pair of objects in your game.
e.g. if you have 1000 objects you need to call that method 1,000.000 times. With 10l,000 objects 100,000,000 times. And that 60 times per second. So for a large number of objects it’s simply too slow. The sorting technique is orders of magnitude faster.
Ah that makes sense.
Thank you.
Well, the next step up from the naive n2 is n(n-1)/2 (still n2 in Big-O, but we don’t care). Collision detection is inherently an n2 problem. The worst case of SAP is still n(n-1)/2 checks plus the cost of whatever sorting scheme.