## Dec 11: 3D Hexagonal-Like Geometry 1

Category: Methodology

Posted by: Aaron

The dominant discrete geometry for 2D simulation environments is the square grid; mostly because it's the default and conceptually and methodologically simple. There are, however, some advantages to using a hexagonal grid in 2D: hexes also tessellate (tile) in two dimensions and the centers of all six neighboring hexes are equidistant (see Hex in Netlogo). In three dimensions, however, only the cube tessellates and hence the corner effects are inescapable…until now! By considering discrete geometries as networks of connections, it is possible to build a 3D hexagonal-like (actually dodecahedral) geometry in which all neighbors are equidistant.

The problem with square grids in 2D is that the corner spaces (in a Moore neighborhood) are sqrt 2 (1.41421356) further away than the horizontal and vertical spaces. In the hex grid all the immediate neighboring cells are the same distance apart. However, the more general problem doesn't completely go away, it just gets pushed back one step. The reason that it's only delayed is that the hex grid preserves neighbor distances only up to distance one. The diagram shows that neighbors two steps away can be either distance 2 or sqrt 3 (1.73205081) depending on the path. This is exactly the right thing if interaction can only happen with immediate neighbors (as is often the case, for example in cellular automata), and it's still an improvement overall. Now we can extend this benefit to 3D worlds.

The 3D version of the hex-like geometry creates a 2D hexagonal grid along three axes, but those axes are not orthogonal. Each space has 12 neighboring spaces (see figure). The generated tiling uses irregular polygons, but they are equal volume and repeat with periods 1, 2, and 3 depending on the axis (for example, along one direction they just repeat, in another direction they repeat every other space, and in the third axis direction they repeat every three spaces). Thus, to get a wrapping space to tile properly one has to build it out of 1x2x3 sized blocks in the appropriate way...which is quite easily done, but restricts the viable world dimensions.

You get a closer look at the top example image I generated of a 6x6x6 wrapping 3D hex world here. My next step is to create all the necessary helper functions so that agents can move around such a world and refer to neighbors in an intuitive (for the programmer) way. If you have any particular application for which you think this helpful, let me know and I can create a demo of the technique for that purpose as part of the 3DHex code example. Advice for a better name for the dodecahedral geometry than "dodecahedral" or "3D Hex-like" is welcome too.

The problem with square grids in 2D is that the corner spaces (in a Moore neighborhood) are sqrt 2 (1.41421356) further away than the horizontal and vertical spaces. In the hex grid all the immediate neighboring cells are the same distance apart. However, the more general problem doesn't completely go away, it just gets pushed back one step. The reason that it's only delayed is that the hex grid preserves neighbor distances only up to distance one. The diagram shows that neighbors two steps away can be either distance 2 or sqrt 3 (1.73205081) depending on the path. This is exactly the right thing if interaction can only happen with immediate neighbors (as is often the case, for example in cellular automata), and it's still an improvement overall. Now we can extend this benefit to 3D worlds.

The 3D version of the hex-like geometry creates a 2D hexagonal grid along three axes, but those axes are not orthogonal. Each space has 12 neighboring spaces (see figure). The generated tiling uses irregular polygons, but they are equal volume and repeat with periods 1, 2, and 3 depending on the axis (for example, along one direction they just repeat, in another direction they repeat every other space, and in the third axis direction they repeat every three spaces). Thus, to get a wrapping space to tile properly one has to build it out of 1x2x3 sized blocks in the appropriate way...which is quite easily done, but restricts the viable world dimensions.

You get a closer look at the top example image I generated of a 6x6x6 wrapping 3D hex world here. My next step is to create all the necessary helper functions so that agents can move around such a world and refer to neighbors in an intuitive (for the programmer) way. If you have any particular application for which you think this helpful, let me know and I can create a demo of the technique for that purpose as part of the 3DHex code example. Advice for a better name for the dodecahedral geometry than "dodecahedral" or "3D Hex-like" is welcome too.