Simple, lightweight, general purpose collision detection

Showcase your libraries, tools and other projects that help your fellow love users.
Post Reply
User avatar
thelinx
The Strongest
Posts: 857
Joined: Fri Sep 26, 2008 3:56 pm
Location: Sweden

Re: Simple, lightweight, general purpose collision detection

Post by thelinx »

use box:move
chris
Prole
Posts: 17
Joined: Sat Sep 20, 2008 5:48 am

Re: Simple, lightweight, general purpose collision detection

Post by 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 :/
User avatar
vrld
Party member
Posts: 917
Joined: Sun Apr 04, 2010 9:14 pm
Location: Germany
Contact:

Re: Simple, lightweight, general purpose collision detection

Post by 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.
I have come here to chew bubblegum and kick ass... and I'm all out of bubblegum.

hump | HC | SUIT | moonshine
chris
Prole
Posts: 17
Joined: Sat Sep 20, 2008 5:48 am

Re: Simple, lightweight, general purpose collision detection

Post by chris »

Isnt it significantly inefficient to treat rectangles as polygons?
User avatar
vrld
Party member
Posts: 917
Joined: Sun Apr 04, 2010 9:14 pm
Location: Germany
Contact:

Re: Simple, lightweight, general purpose collision detection

Post by vrld »

No.
I have come here to chew bubblegum and kick ass... and I'm all out of bubblegum.

hump | HC | SUIT | moonshine
User avatar
slime
Solid Snayke
Posts: 3166
Joined: Mon Aug 23, 2010 6:45 am
Location: Nova Scotia, Canada
Contact:

Re: Simple, lightweight, general purpose collision detection

Post by slime »

Interesting article I read today... http://altdevblogaday.org/2011/02/21/sp ... solutions/
(bump :p)
User avatar
kikito
Inner party member
Posts: 3153
Joined: Sat Oct 03, 2009 5:22 pm
Location: Madrid, Spain
Contact:

Re: Simple, lightweight, general purpose collision detection

Post by 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.
When I write def I mean function.
User avatar
vrld
Party member
Posts: 917
Joined: Sun Apr 04, 2010 9:14 pm
Location: Germany
Contact:

Re: Simple, lightweight, general purpose collision detection

Post by 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.
I have come here to chew bubblegum and kick ass... and I'm all out of bubblegum.

hump | HC | SUIT | moonshine
User avatar
vrld
Party member
Posts: 917
Joined: Sun Apr 04, 2010 9:14 pm
Location: Germany
Contact:

Re: Simple, lightweight, general purpose collision detection

Post by 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/.
I have come here to chew bubblegum and kick ass... and I'm all out of bubblegum.

hump | HC | SUIT | moonshine
User avatar
TechnoCat
Inner party member
Posts: 1611
Joined: Thu Jul 30, 2009 12:31 am
Location: Milwaukee, WI
Contact:

Re: Simple, lightweight, general purpose collision detection

Post by TechnoCat »

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

Who is online

Users browsing this forum: No registered users and 5 guests