Hex Grid - Custom Layout

General Grid graph
1

Hi,

I would like to use a hex grid graph in my game. I’ve noticed that the default hex grid generated from A* produces a ‘parallelogram’ shaped grid layout. This is generating a lot of wasted nodes for me as I would like to use a rectangular grid layout.

How would I go about modifying the default hex grid layout to produce a rectangular grid layout instead of the parallelogram layout? I imagine I’m going to have to create a custom grid. If anyone has produced a custom rectangular shaped hex grid and can help me out, it would be much appreciated.

Thanks guys.

2

Hi

There is currently no way to avoid that. It is laid out as a parallelogram since it is backed by a 2D array which makes the code a lot simpler. Yes, you could create your own graph type, but I think it would end up being less efficient since it does not have all the optimizations that the grid graph contains (like storing node connections in a bitfield instead of an array, efficient lookups of the nearest node, etc.).
For the most part I think you can safely ignore the wasted nodes unless you profile and the extra memory usage turns out to be a problem.

3

Hi Aron,

Thanks for the quick response. Based on what you said I’ll leave the layout as is for the performance benefits you mentioned.

Do you have a rough figure of the numbers of nodes you should try and limit your grid graph to before performance starts to become an issue? I’m looking at around 90,000 nodes at the moment. Performance and memory usage seem to be okay (although the project is in its early stages). I guess it is highly dependent on what the game is and how many path finding operations need to be performed at a time, but for a simplistic example such as one object try to get from a to b, would 100,000 nodes sound excessive?

4

Hi

I am limiting the grid graph to 1000*1000 as if you go higher than that, then you probably should be using another graph type. 90000 nodes is not extreme, but it is not that low either, it depends on the game if that will turn out to be too much or not.

5

Thanks for the feedback Aron. It has proved helpful.