How I implemented 2D collision detection in Pistol Slut

Re:How I implemented 2D collision detection in Pistol Slut by mrcharles on Wednesday January 19, 2011 @10:02AM (#2119888)

Another issue noticed with the algorithm is that you pick a grid square by the top left point, but then insert it in to the 8 surrounding squares. In reality, you only need to insert it in the right, bottom, and bottom right square. Because there is no chance your object can be higher or more left than it's top left point. So you can save yourself 5 grid inserts and a boatload of compares. Assuming you stick with the limitation of an object not being larger than an individual grid square, in which case this is still true, but you then need to expand further down and right.

(Also, a quadtree would be more efficient for this kind of solution).

(edit for another little thing I missed)

[ Parent | on HN ]

Re:How I implemented 2D collision detection in Pistol Slut by T-hawk on Wednesday January 19, 2011 @10:43AM (#2120037)

You can insert object A to just the 4 squares, but you still need to check with collisions with objects in all 8 surrounding squares. There could be an object B whose top-left point is in the square northwest of A's square but still collides with A.

edit: mrcharles in the child comment has it right, testing 4 squares is sufficient. In this case you will detect the collision from B's point of view instead of A's which is fine.

[ Parent | on HN ]

Re:How I implemented 2D collision detection in Pistol Slut by mrcharles on Wednesday January 19, 2011 @10:52AM (#2120080)

Unless I'm misunderstanding the algorithm, this is still handled with my suggestions, since you'd only test collisions against people in the same container as yourself, and someone who is northwest will be inserted in to my container regardless.

[ Parent | on HN ]