Collision detection on a 2D hexagonal grid
- by SundayMonday
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:
Calculate ij-coordinates of grid cell closest to moving cell using moving cell's xy-position
Get list of surrounding grid cells using ij-coordinates
Examine the surrounding cells. If they're all empty then no collision
If we have some non-empty surrounding cells then compare the distance between the disc centers to some minimum distance required for a collision
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?
