Ben's Busy Blog
My personal online journal of daily accomplishments and setbacks
Collision and The Big OWednesday, April 01, 2009
I was getting hung up in SpaceHook because I felt it was time to start implementing collision, which I then realized was something I'd never done before. I had absolutely no idea how to deal with it. I decided that I would try to create a much more simple test game that focused heavily on collision. I sat down and tried doing a code jam and see how that rolled out. The basic concept was to have walls, immobile gun turret type enemies, and a mobile protagonist. Everything would have simple flat shaded geometric representation. Along the way I thought of a fun twist that could be a cool hook... but we'll wait and see if I put that mechanic in. Unfortunately the idea of just powering through focused a collision mechanic didn't work out. I hit the point where I had the basics, but I still didn't know how to implement collision. It didn't seem to be something I could just blunder through.
So I started looking around for XNA collision tutorials. I came across this article on polygonal collision detection by Nick Gravelyn. This was refactored by another person into an object oriented solution. Neat stuff, but I bookmarked it for later as being advanced beyond what I was looking for.
Instead I've been working my way through a series of tutorials on creators.xna.com. There are multiple parts and each part builds upon the previous: 2D rectangle collisions, then 2D per-pixel collisions, and then 2d collisions with transformed objects. It's interesting stuff, but it also feels very remedial. I have to suck up my pride and accept that although I can program already, I have to be patient and take baby steps to learn this new stuff.
I'm intrigued about the extensions of this though. What really is the best way to efficiently handle 2D collisions? Per-pixel is the most accurate, but very resource intensive as it requires stepping through each pixel of each bitmap. You can cut down on that by gating each per pixel collision with a weaker form of collision detection. In this case, assigning each object a bounding sphere (or series of spheres) allows you to do a relatively cheap comparison. You still have to compare each object against each other object, which if I'm recalling my big O notation correctly, it's O(!n). How do you reduce after that? Binary space partitioning? Or am I overthinking this and I can just trust blindly and safely in the computing power at hand?
So I started looking around for XNA collision tutorials. I came across this article on polygonal collision detection by Nick Gravelyn. This was refactored by another person into an object oriented solution. Neat stuff, but I bookmarked it for later as being advanced beyond what I was looking for.
Instead I've been working my way through a series of tutorials on creators.xna.com. There are multiple parts and each part builds upon the previous: 2D rectangle collisions, then 2D per-pixel collisions, and then 2d collisions with transformed objects. It's interesting stuff, but it also feels very remedial. I have to suck up my pride and accept that although I can program already, I have to be patient and take baby steps to learn this new stuff.
I'm intrigued about the extensions of this though. What really is the best way to efficiently handle 2D collisions? Per-pixel is the most accurate, but very resource intensive as it requires stepping through each pixel of each bitmap. You can cut down on that by gating each per pixel collision with a weaker form of collision detection. In this case, assigning each object a bounding sphere (or series of spheres) allows you to do a relatively cheap comparison. You still have to compare each object against each other object, which if I'm recalling my big O notation correctly, it's O(!n). How do you reduce after that? Binary space partitioning? Or am I overthinking this and I can just trust blindly and safely in the computing power at hand?
Labels: programming
