Java-Gaming.org Hi !
Featured games (83)
games approved by the League of Dukes
Games in Showcase (513)
Games in Android Showcase (120)
games submitted by our members
Games in WIP (577)
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 1443 times)
0 Members and 1 Guest are viewing this topic.
Offline 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?

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

Offline Axeman

Senior Duke


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

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

ps2. "Nearby" should be "overlapping".
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline DrZoidberg

Senior Duke


Medals: 15



« 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<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);
    }
}
Offline 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.
Offline Roquen
« 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.
Offline 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<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

1  
2  
3  
4  
5  
6  
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,

1  
2  
3  
4  
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,

1  
2  
3  
4  
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.

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

Offline 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<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;
   }
Offline 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!
Legends of Yore - The Casual Retro Roguelike
Offline 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?
Offline DrZoidberg

Senior Duke


Medals: 15



« 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.
Offline 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.
Offline Roquen
« 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  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

Longarmx (52 views)
2014-10-17 03:59:02

Norakomi (43 views)
2014-10-16 15:22:06

Norakomi (33 views)
2014-10-16 15:20:20

lcass (37 views)
2014-10-15 16:18:58

TehJavaDev (68 views)
2014-10-14 00:39:48

TehJavaDev (66 views)
2014-10-14 00:35:47

TehJavaDev (59 views)
2014-10-14 00:32:37

BurntPizza (73 views)
2014-10-11 23:24:42

BurntPizza (45 views)
2014-10-11 23:10:45

BurntPizza (86 views)
2014-10-11 22:30:10
Understanding relations between setOrigin, setScale and setPosition in libGdx
by mbabuskov
2014-10-09 22:35:00

Definite guide to supporting multiple device resolutions on Android (2014)
by mbabuskov
2014-10-02 22:36:02

List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50

List of Learning Resources
by SilverTiger
2014-07-31 16:26:06
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
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!