Data Structure for a hex grid questions

Hi, I am currently working on a little project to bring myself back up to speed with C++ and Unreal after a few years of C# and Unity, so I’m working on a project to recreate a board game I am fond of.

The board for the game is a hex grid with a slightly abnormal shape, with another version an even more abnormal shape.

I am currently working on a data structure to efficiently store the grid and have two ideas for now.

First is a simple 2D Array of HexObjects, each containing coords of their neighbours and a boolean to show if it’s a valid grid location or not. This means I can just use normal (X,Y) coords and if I need a specific location I can select that location in the grid. If I’m correct, this has the drawback of a lot of wasted memory, especially in the second version I mentioned.

The other is a linked list type of structure, having each hex object hold pointers to its neighbours, using square coordinates (explained here), which would have the benefit of only containing valid hexes.

To me, both of these have considerable downsides in terms of traversal, memory usage and efficiency, I was wondering if anyone else would have any tips or pointers to put me on the right path? I’m leaning towards the 2D array and potentially incorporating the pointers to neighbours.

How large are you envisioning your game board being? I’ve played around with a few hex games in the past, and have actually tried both approaches. I would highly suggest a simple 2D array.

If you go with a simple 2D array approach, you can still think of it as a square grid, but offset the y coordinate when the x coordinate is odd while rendering. Internally, you can think of pulling the rows apart vertically then shifting the odd columns half their distance to the left.

The reference approach is definitely neat, but it creates a lot of headache in generating the nodes and references. Just my two cents, but I’m curious to hear more.

Best of luck!

But hex array is just normal square array, with every other row (or column) moved by 1/2 of its width (height).
Instead of keeping all that easy to calculate data, make function that calculates neighbors in runtime.
And store only type of hex tile in 2d array.

Thanks for the thoughts! The basic version would only be 23x11, complex board would be a 27x27.

I worked on a bubble shooter game (think bubble witch, panda pop etc.) which used a hex grid layout using the 2D Array and did it how you recommended. There were a lot of things problems I had, but I think you’re probably right and the pros I can think of outweigh the cons. I imagine the reference approach would become slightly painful having to constantly traverse to find specific cells, I was just wondering if I was thinking too lazy!

My reason for doubting my original idea was the problems I ran into using it, but I think they were more to do with the fact I just expanded the prototype as opposed to rebuilding it with my exact requirements in mind

I think I’ll go ahead with the 2D Array, keep it straight forward! Cheers!

Yeah Nawrot, I know it probably sounds daft, I’ve probably just been overthinking the problem. Cheers for the input!