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
show 3 more comments

3 Answers

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
add comment

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
add comment

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
add comment

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.