Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

Probably the biggest advantage of a hex-based versus square-based map tiling is that the center of each hex has the same distance to all its neighboring hexes. Is there a similar shape that tiles this way in 3D, and an engine that supports such a model?

share|improve this question
    
You're actually asking two questions (not recommended). The first question, about 3D shapes (other than cubes I presume), really belongs on math.stackexchange.com. The second is more game-related, although I suspect the answer is no. :) –  Cyclops Oct 17 '11 at 12:22
    
Squares also have the same distance to all neighboring squares (assuming that a neighbor is a square that shares an edge) –  bummzack Oct 17 '11 at 12:30
1  
I did consider putting it on math, but I figured the topic might be too close to real world applicability ;) But I will try then. –  Hackworth Oct 17 '11 at 12:32
    
@bummzack If it wasn't obvious from the question, I did of course refer to the case where you count all 8 squares as neighboring, or 26 cubes in 3D. –  Hackworth Oct 17 '11 at 12:36
    
I edited your question a bit to downplay the "mathiness" of the first bit and put more focus on the engine aspect. –  Josh Petrie Oct 17 '11 at 14:59

4 Answers 4

I agree with @Cyclops that this is probably better asked on the math stack exchange, but in the mean time you may want to look into the Hexagonal Close Packing structure. It is the densest possible arrangement of spheres in 3D, and while the distance to all neighbours isn't uniform it may be the best you're going to get. The Diamond Cubic lattice has an equal distance to direct neighbours, but it's quite loosely packed, and each point only has four adjacent points.

share|improve this answer
    
HCP works fine indeed; you just have to "squish" the layers a bit so that the distance between the centres of the cells are the same in every direction. A cell thus has twelve neighbours - three up, three down and six on the same plane. –  Martin Sojka Oct 17 '11 at 13:40

Google and Wikipedia tag team to the rescue:

Tessellation and, more specific for 3D, Honeycomb is the term to look for. Cubes are indeed the only regular (all faces are congruent) AND space-filling (no gaps left as with sphere packing) polyhedra in 3D space. But they have the same problem as 2D squares - widely varying distances to its neighbors.

A Bitruncated cubic honeycomb made of truncated octahedra (quite a mouthful) comes very close to what I was asking for. The downsides are that the truncated octahedron is not regular (squares and hexes as faces) and has fewer neighbors than a cube (14 vs 26), but it fills space with a single, repeated solid and has (roughly) equal distance to all its neighbors.

share|improve this answer
    
+1 Interesting. Your cube neighbor count seems to be off though (should be 26 instead of 28?). –  bummzack Oct 17 '11 at 14:29
    
yes, 26 of course, thanks –  Hackworth Oct 17 '11 at 15:50
    
+1 Honeycomb, nice. I knew the structure, had forgotten the name. –  Nick Wiggill Oct 17 '11 at 17:47

There are two simple 3D analogues of the hexagonal lattice: Hexagonal Close Packing (HCP) and Cubic Close Packing, a.k.a. the Face-Centered Cubic (CCP / FCC) lattice.

Both of these lattices are quite similar: they have the same number of nearest neighbors per site (12) and the same sphere packing density (~74%), and they can both be decomposed into stacked 2D hex lattices.

Of the two, I would consider the CCP lattice somewhat "nicer": it's more symmetrical, having no preferred axis like the HCP lattice. In particular, if you were to sit inside one of the cells of the CCP lattice and looking at one of the nearest neighbor cells, the lattice would look the same regardless of which of the neighbor cells you were looking at. This does not hold true for the HCP lattice.

The cells of the CCP tiling are nice and symmetric rhombic dodecahedra, while those of the HPC are twisted into trapezo-rhombic dodecahedra. Here's a picture of some rhombic dodecahedra tiled to form a CCP lattice from Wikipedia:

Rhombic dodecahedral tiling

(Picture by Wikipedia user AndrewKepert, licensed under GFDL 1.2+ / CC-By-SA 3.0.)

Also note that, as the alternative name "face-centered cubic lattice" suggests, there's a very simple formula for finding the centers of the cells in a CCP lattice: start with a simple cubic lattice, with points at the corners of the cubes, and add new points at the centers of the faces of the cubes. The nearest neighbors of the points at the corners are those on the 12 adjacent faces, while the nearest neighbors of the points on the faces are the 4 on the adjacent corners plus the 8 on the adjacent faces of the two cubes sharing the face on which the center point lies. (With some geometry, you can show that the neighborhoods of all points in fact look the same, even though this construction makes it seem as if the "face points" were different from the "corner points".)

(Note: The MathWorld page I linked to above seems to contain a mistake, giving the density of the related, non-close-packed "Body-Centered Cubic" lattice also as 74% — it's actually about 68%.)

share|improve this answer

2D hexagonal maps are a representation of spheres packed in a flat (2D) tray, with each hex centred on the equivalent sphere, and allow distances between cells to be determined to workable (for gaming purposes anyway) accuracy, just by counting the number of hex cells through which you step.

The equivalent 3D representation is the face-centred cubic (FCC)/cubic close packing (CCP) tessalation mentioned above, using rhombic dodecahedra.

Face Centred Cubic tessellation in three dimensions

This Wikipedia article refers to FCC/CCP in particular and this other article compares it to hexagonal close packing (HCP) but the second article tends to be a bit more mathematical.

I have been investigating the use of these in RPG mapping, but although there is an appealing 'correctness' about them (the mathematical basis, the ability to pack space without gaps, the symmetry when slices are taken through the lattice etc), the real issues for gaming purposes seem to be the difficulty that players/GMs would face in visualising them, and the lack of an obvious coordinate system for referencing them.

Although it pains me, simple cubes with {x,y,z} coordinates look like a much simpler solution, allowing everyone to focus on the gameplay rather than being constantly baffled by the non-trivial choice of mapping standard.

Just my 2 cents, albeit a very late addition to this thread.

Oh, as an aside for space-themed settings, each cell has twelve adjacent cells (three above, three below, and six around the plane) and this allows a neat constellation/astrology link. Imagine a home sector in the starting cell, and then name each adjacent sector after one of the astrological constellations. Just as hex maps can be decomposed into smaller hexes, FCC cells could be decomposed into smaller cells, allowing each sector named after a constellation to be decomposed into sub-sectors. "Let's set a course for subsector 031 of the Gemini Sector"...

Stuart

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.