Menu
I'm designing a collision detection game tutorial for young adults, so I want this to be as simple as possible to make it easier to explain.
The requirements are very simple. The world is 2D and contains only rectangles (of arbitrary sizes). BSP and even quadtrees seems like it would be overkill (again, the emphasis is on simplicity) but I would like something more efficient than brute forcing through all n(n-1)/2 possible collisions.
2D, rectangles only, and simple.
Can anyone point to an algorithm I can look up? Is a quadtree algorithm what I'm looking for?
EDIT: Also, the rectangles will never be rotated (I'm keeping it simple). And to give you an idea of what scale I'm working at, there will be on the order of a few hundred rectangles running on your typical user's laptop/desktop (less than 5 years old) implemented in Python with Pygame.
902
Axis-Aligned Bounding Box One of the simpler forms of collision detection is between two rectangles that are axis aligned — meaning no rotation. The algorithm works by ensuring there is no gap between any of the 4 sides of the rectangles. Any gap means a collision does not exist.
As with 2D collision detection, axis-aligned bounding boxes (AABB) are the quickest algorithm to determine whether the two game entities are overlapping or not.
A hitbox is an invisible shape commonly used in video games for real-time collision detection; it is a type of bounding box.
In solving 2 dimensional collision problems, a good approach usually follows a general procedure: Identify all the bodies in the system. Assign clear symbols to each and draw a simple diagram if necessary. Write down all the values you know and decide exactly what you need to find out to solve the problem.
In my experience, all broadphase collision-detection algorithms are relatively subtle and hard to understand. Given how cheap rectangle-collision testing is, I'd structure the lesson using the n^2 algorithm, then as bonus material, maybe introduce the idea of spatial indexing. With fewer than hundreds of rectangles, I'll bet the dumb way is fast enough.
A quadtree would be fine for your purposes, but remember that when you're dealing with non-points, you have to put the rectangle in a node that contains all of the quadrants it intersects. Then, when testing something that's in a low node, you have to test against all the rects in that node and in all of its ancestors!
You might also consider a sort and sweep algorithm, since what you've already got are axis-aligned bounding boxes.
196
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
