# Collision detection on a 2D hexagonal grid

I'm making a casual grid-based 2D iPhone game using Cocos2D. The grid is a "staggered" hex-like grid consisting of uniformly sized and spaced discs. It looks something like this:

I've stored the grid in a 2D array. Also, I have a concept of "surrounding" grid cells. Namely the six grid cells surrounding a particular cell (except those on the boundries which can have less than six).

Anyways, I'm testing some collision detection and it's not working out as well as I had planned. Here's how I currently do collision detection for a moving disc that's approaching the stationary group of discs:

1. Calculate ij-coordinates of grid cell closest to moving cell using moving cell's xy-position
2. Get list of surrounding grid cells using ij-coordinates
3. Examine the surrounding cells. If they're all empty then no collision
4. If we have some non-empty surrounding cells then compare the distance between the disc centers to some minimum distance required for a collision
5. If there's a collision then place the moving disc in grid cell ij

So this works but not too well. I've considered a potentially simpler brute force approach where I just compare the moving disc to all stationary discs at each step of the game loop. This is probably feasible in terms of performance since the stationary disc count is 300 max. If not then some space-partitioning data structure could be used, however that feels too complex.

What are some common approaches and best practices to collision detection in a game like this?

Edit - More info: This current implementation has a few bugs like discs will sometimes stick over an occupied grid slot. Also it's too difficult to get discs into small spaces. These are all fixable. I asked here just to learn about alternative approaches.

• Why doesn't it work so well? Or what problems do you have with this implementation.
– Ken
Commented Oct 19, 2012 at 6:58
• @Ken there's a few bugs here and there like occasionally a disc will stick over an existing disc. Also the collisions seem too generous so it's difficult to get into smaller spaces. I can just fix these of course. However I wanted to see if there's a better general approach. Commented Oct 19, 2012 at 14:03