Collision detection on a 2D hexagonal grid

Question

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.

Answer 1

You could treat circles (balls) as hexagons, and calculate exact position of a circle mathematically, but I suggest you use a grid, as in these answers:

Making an efficient collision detection system

Fast, accurate 2d collision

Then get balls registered on a cell under mouse cursor and iterate through them to see which is in shortest distance to the cursor.

Answer 2

I don't know what is the actual issue with this algorithm, since you didn't provide any explanation, but assuming you get false negatives for collision, I would suggest running your check not for the nearest grid cell but for all the grid cells that the moving disc collides with.