points vs. Rectangle Collision xxl

[LeechmasterB]

Just wanted to show some cool results with spacial partitioning, check out 100'000 points collision detection against a rectangle (only broad phase).

http://www.leechlabs.com/flash/quadtree/
quadtree.html

Wee this rocks! :)

[LeechmasterB]

At 7/1/09 05:34 AM, KaynSlamdyke wrote:

At 7/1/09 04:19 AM, LeechmasterB wrote: Wee this rocks! :)

This is not a senior programming forum. You're going to have to explain what this is in laymans terms why we should care and what we can learn from this.

Well if noone cares, thats not really my problem.

Anyhow... Quad Trees is a datatype to divide space up and place objects into clusters. Typical about this is subdivisions of four hence quad tree...

It is useful for collision detection, if you have many objects colliding against eachother or lots of collisions of a camera vs. terrain ect.

With this you can have collision detection between 1000 objects hittesting against eachother without problems.
Or like in the example test a "cam" against 100'000 points representing "objects". I have another version that works for rectangles, which is closer to real game use then simple points, but it looks way too cluttered as example.

Quad Trees come in several varations depending on what you want to use them for basically.

But yeah people here are not so ambitious with their games that they actually care i guess ^^.

cheers

[Bezman]

I don't see how you can call this collision detection - I mean I can't see any of the pixels moving, let along colliding. :-/

Despite your snide comments I'm sure folk - including myself - WOULD care if you bothered to clearly explain what's going on.

[LeechmasterB]

At 7/1/09 06:41 AM, Bezman wrote: I don't see how you can call this collision detection - I mean I can't see any of the pixels moving, let along colliding. :-/

Despite your snide comments I'm sure folk - including myself - WOULD care if you bothered to clearly explain what's going on.

Okay in the example you have a coordynate space of 400 x 400 pixels. 100'000 points (blue pixels) get created and spread randomly over that space.

The camera is represented by a darker blue square that is attached to the mouse. When you move the mouse the camera moves.

A collision detection between the camera rectangle and every point is performed by querying the quad tree. It returns all points that are in the camera area or that could be colliding with it.

So you go and try doing a hittest of 100'000 movieclips vs. another movieclip and see if it works. This approach here runs a lot faster by bypassing all objects that are too far away to collide and only gives you the objects that could be colliding to do hittests with.

The points that are colliding with the camera are drawn 4 times bigger and in red, to make them more visible.

No the points are not moving, but they could be! I just have not made such an example (yet).

Instead of testing 1 cam against points you could also be testing every point against every other point with just O(n log n) instead of O(n * n) if checking every object with brute force against every other object.

[LeechmasterB]

Here is another example checking rectangles against a rectangle.

If you think there are erros, be aware that rectangles that don't fit into a quad / bucket are contained within the next larger quad / bucket. So if there are objects on the middle lines they are also returned to check with additional hittests.

Anyhow this gives another perspective :)

[LeechmasterB]

At 7/1/09 07:14 AM, KaynSlamdyke wrote: A better example of the advantages of Quadtrees

Not trying to diminish what you've done Leech. The actual understanding of quad and kd trees is a little above my head (even if I understand the principle of what's happening, I lose grasp of the implementation), and I myself could do with a step by step algorithm to whats going on every pass.

Yeah I know that one too, like all others noone has actually released source code yet though. I ve gone through a couple of articles figuring out how they work. Basically it varies depending on what you want to do with it. The example on polygonal labs is a dynamic quad tree whereas mine is static at the moment. I might also have more examples with dynamic ones once its implemented.

The glorious part of it all is that it is really simple once you figure out which quad tree you should use for the problem you want to solve, the rest is mostly coding. :)

And visualisation of a quad tree is a pain to do if you just need to debug it, so sorry for nothing too fancy ui wise.

[UnknownFury]

At 7/1/09 07:43 AM, KaynSlamdyke wrote: Phew...
Someone needs to write this up for everyone...

This is the site a found when reading up on this stuff a few months ago. The source code itself is XNA but it gives a pretty detailed explanation along with the link at the top ('Quadtree Code Design').

There is also this video tutorial. It is C++ but the first ~5mins explain collision detection and octrees (3D quadtrees) but he does actually explain quadtrees using a 2D image. Not sure how useful other people will find this though.