Java-Gaming.org Hi !
 Featured games (90) games approved by the League of Dukes Games in Showcase (769) Games in Android Showcase (230) games submitted by our members Games in WIP (855) games currently in development
 News: Read the Java Gaming Resources, or peek at the official Java tutorials
 Home Help Search Login Register
Pages: [1]
 ignore  |  Print
 Finding nearest objects  (Read 4739 times) 0 Members and 1 Guest are viewing this topic.
SHC
 « Posted 2013-05-05 14:07:49 »

I've shared my tutorial "Using Grids For Collisions" on Google+ and there I've got a comment.

Quote
I use a different, very fast algorithm: First, sort all objects by their x-coordinate. Then calculate abs(x(n)-x(n-1)) to filter out those objects, which are nearby each other on x (can be done during sort), and only those you have to insert into a list, sort again by their y-coordinate. And if those left are also nearby on y, you have sorted out then all candidates for a more intense collision detection. The advantage is, if you use a sort algorithm, which likes pre-sorted data, its incredibly fast. Works for several hundred thousands of object coordinates (means polygons) in near real-time. No need to differentiate between unmovable and moving objects! And - because of the simplicity of the algorithm, it is typically translated into very fast machine code, avoiding cache - misses. And if you need to detect z-axis collisions, just add one more sorter. Works perfectly in fully dynamic worlds, where all objects move. Have fun!﻿

I wanna try it but I don't understand it. Can anybody help me understanding it so that I can implement?

heisenbergman

JGO Coder

Medals: 14

L___ o_ G___ a__ P___

 « Reply #1 - Posted 2013-05-05 14:52:55 »

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.

Axeman

Senior Devvie

Medals: 7

 « Reply #2 - Posted 2013-05-05 16:29:18 »

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".
 Games published by our own members! Check 'em out!
DrZoidberg

JGO Coder

Medals: 21

 « Reply #3 - Posted 2013-05-05 16:35:51 »

Maybe like this

 1  2  3  4  5  6  7  8  9  10  11  12  13  14  15  16  17  18  19  20  21  22  23  24  25  26  27  28  29  30  31  32  33  34  35  36  37  38  39  40  41  42  43  44  45  46  47  48  49  50  51  52  53  54  55  56  57  58  59  60  61  62  63  64  65  66  67  68  69  70  71  72  73 `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 list, final Getter getter) {        if(list.isEmpty()) return;        Collections.sort(list, new Comparator() {            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 newList = new ArrayList<>();        boolean foundAPairLastTime = false;        Iterator 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 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 newList = new ArrayList<>(list);        sortAndFilter(newList, GameObject.getX);        sortAndFilter(newList, GameObject.getY);        for(GameObject go: newList) System.out.println(go);    }}`
relminator
 « Reply #4 - Posted 2013-05-06 00:32:16 »

It's called a "sweep and prune" collision.  Limited to aabbs and very fast. requires a little sorting in realtime too.
Roquen

JGO Kernel

Medals: 518

 « Reply #5 - Posted 2013-05-06 06:12:34 »

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.
SHC
 « Reply #6 - Posted 2013-05-06 07:05:02 »

@DrZoidberg, I've added benchmarking to your code.

 1  2  3  4  5  6  7  8  9  10  11  12  13  14 `long ts = System.nanoTime();List 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

 1  2  3  4  5  6 `Time taken for creating new list: 0.054296msTime taken for sorting x-axis: 45.428871msTime taken for sorting y-axis: 0.023437msTime taken for sorting both the axis: 45.543712mspos = (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,

 1  2  3  4 `Time taken for creating new list: 0.016796msTime taken for sorting x-axis: 3.447565msTime taken for sorting y-axis: 0.046874msTime taken for sorting both the axis: 3.580764ms`

For 15 objects,

 1  2  3  4 `Time taken for creating new list: 0.009374msTime taken for sorting x-axis: 1.6327699999999998msTime taken for sorting y-axis: 0.061716999999999994msTime taken for sorting both the axis: 1.8187019999999998ms`

It's more for less number of objects.

65K
 « Reply #7 - Posted 2013-05-06 07:47:14 »

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.

Lethal Running - a RPG about a deadly game show held in a futuristic dystopian society.
Fsig

Senior Newbie

 « Reply #8 - Posted 2013-05-09 05:52:30 »

Would the performance of this be much better then something simple like this...

 1  2  3  4  5  6  7  8  9  10  11  12  13  14 `   public static Point getClosest(Point start, ArrayList 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;   }`
SHC
 « Reply #9 - Posted 2013-05-09 05:54:47 »

Would the performance of this be much better then something simple like this...

 1 `p.distance(start)`

Distance uses
 `Math.sqrt()`
which is slow.

 Games published by our own members! Check 'em out!
Fsig

Senior Newbie

 « Reply #10 - Posted 2013-05-09 06:45:20 »

Distance uses
 `Math.sqrt()`
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:
 1  2  3 `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?
DrZoidberg

JGO Coder

Medals: 21

 « Reply #11 - Posted 2013-05-09 08:23:27 »

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.
Fsig

Senior Newbie

 « Reply #12 - Posted 2013-05-09 12:20:29 »

100,000,000 times. And that 60 times per second

Ah that makes sense.

Thank you.
Roquen

JGO Kernel

Medals: 518

 « Reply #13 - Posted 2013-05-14 12:54:15 »

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.
Pages: [1]
 ignore  |  Print

 EgonOlsen (1594 views) 2018-06-10 19:43:48 EgonOlsen (1695 views) 2018-06-10 19:43:44 EgonOlsen (1150 views) 2018-06-10 19:43:20 DesertCoockie (1578 views) 2018-05-13 18:23:11 nelsongames (1178 views) 2018-04-24 18:15:36 nelsongames (1701 views) 2018-04-24 18:14:32 ivj94 (2467 views) 2018-03-24 14:47:39 ivj94 (1683 views) 2018-03-24 14:46:31 ivj94 (2767 views) 2018-03-24 14:43:53 Solater (905 views) 2018-03-17 05:04:08
 Deployment and Packagingby mudlee2018-08-22 18:09:50Java Gaming Resourcesby gouessej2018-08-22 08:19:41Deployment and Packagingby gouessej2018-08-22 08:04:08Deployment and Packagingby gouessej2018-08-22 08:03:45Deployment and Packagingby philfrei2018-08-20 02:33:38Deployment and Packagingby philfrei2018-08-20 02:29:55Deployment and Packagingby philfrei2018-08-19 23:56:20Deployment and Packagingby philfrei2018-08-19 23:54:46
 java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org