Collision Detection Algorithm

This project was an experiment on optimizing collision detection and response. The video to the right shows the program (written in C# and WPF) running with 35,000 circular objects in a 30,000 square pixel environment running at 60 fps. My simulation is discrete, rather than continuous, and the well known caveat of a discrete system can be seen here: small, fast moving objects can ocassionally phase through other objects instead of being caught by the collision system.

My algorithm uses a variation of a two axis sweep and prune algorithm for broadphase collision detection. I only sweep on the x-axis (as y-axis collision is cheap enough to determine seperately once x-axis collision is assured). I also split the planes into a number of vertical and horizontal slices in hopes to lessen the number potential collisions found during the sweeping process.

The sweep and prune approach could also be easily extended to work for any number of dimensions, if needed.

Visit http:\\rtuckergameprogramming.com for more.

Category:

Science & Technology

Tags:

• 2D
• Collision
• Detection
• C#
• WPF