Simple, lightweight, general purpose collision detection

[thelinx]

use box:move

[chris]

Yes, I'm going to use that because it will make my code more efficient, but still it doesn't make sense to me that moveTo works this way :/

[vrld]

shape:moveTo(x,y) sets the shape's center to a new position. This is because shapes can not only be rectangles, but also circles and polygons (in fact, rectangles are internally treated as polygons), for which the notion of an upper left edge is somewhat unavailable. If you rotate the rectangle, the upper left edge may also not be where you want it to be (rotate it 180° and it becomes the lower right edge). I will clarify that in the documentation.

In your code you have to add an offset of 25 to x and y, which is half the width and height - (box.x + 25, box.y + 25) is the center point of the rectangle. Also, you can get the current shape's position with shape:center(), so you wont need to keep track of it yourself.

[chris]

Isnt it significantly inefficient to treat rectangles as polygons?

[vrld]

No.

[slime]

Interesting article I read today... http://altdevblogaday.org/2011/02/21/sp ... solutions/
(bump :p)

[kikito]

[In quadtrees, ] the nodes are partitioned based on object centers,

I don't agree with that on the article. That would be a very inefficient way to create a quadtrees. A more appropriate solution is building the nodes so they completely contain each object - for example using the object's bounding box.

[vrld]

A rather article.

HardonCollider uses the grid approach. And while it's true that it is possible for nearly all objects to fall inside the same cell, essentially destroying the whole purpose of the grid, this is a very unlikely scenario. It's also no problem to have variable sized objects in the grid - they just occupy more than one cell. In addition, HC only creates cells if there are actually objects occupying them, saving memory and giving you an infinite grid. I am not sure why the author thinks a hashtable would dramatically increase the lookup time; it's simply not true.

Quad Trees: As kikito already wrote, though the standard definition of a quad tree uses only points, you can (and should) use other things than the object's center to build the tree. And it's weird that the author didn't mention the IMO most pressing problems of quad trees:

• The square structure is not an optimal choice when objects are distributed other than in nearly square way. Think of platformers, where the distance of the leftmost to the rightmost object is usually much higher than the distance of the topmost to the bottommost one.
• The lookup time is high for objects down in the hirachy.
• They can degenerate to a list if you have many objects in the same range (a variation of the problem with grids he mentioned).

None of those problems are impossible to solve though.

KD trees: I'm not sure why he wants to use those for spatial partitioning. The problem they were introduced to tacke are range queries (e.g. "how many points lie in this rectangle") and nearest neighbor search and they excel at those only at high dimensions. I think I never saw a 2D or 3D tree other than for demonstration purposes.

[vrld]

Updates!

... and a major API change:

• The main module is now a class. This means you can have more than one collision detection system running at the same time.
• Added HC:setPassive() and HC:setActive() to flag shapes as active or passive. Can greatly improve the detection speed.
• Removed HC:setAutoUpdate()
• Tweaked vector class for speed.

The updated documentation and tutorial is available here: http://vrld.github.com/HardonCollider/.

[TechnoCat]

[*]The main module is now a class. This means you can have more than one collision detection system running at the same time.

yessss