Trees for hyperbolic honeycombs

[tricosahedron]

This thread is about tree structures for hyperbolic (and maybe non-hyperbolic) honeycombs.

As a start, here is a tree structure for the order-5 cubic honeycomb {4,3,5}.[en.wikipedia.org]

-----------------------------------------------

First of all, the honeycomb is constructed by arranging 5 cubes around each edge, which results in 20 cubes around a vertex.
(yep, that's a lot)

I assume vertex adjacency, i.e. that two cube cells are adjacent when they have at least one vertex in common. Vertex adjacency includes edge adjacency (cells with a common edge are adjacent), which in turn includes face adjacency (cells with a common face are adjacent).
Initially, I assume there is a single root cell C at the center of the tree structure, but other setups are possible.

When refering to cell faces, I use the word 'top' if the face is next to a cell from a higher layer (-> more distant from the root cell), 'side' if it's next to a cell in the same layer, and 'bottom' if it's next to a cell from a layer below (-> closer to the root cell).
I also use the words 'top' and 'bottom' to refer to a unique edge or vertex at the top and bottom, respectively, if applicable.

There are 4 different cell types:

• C: The root cell at the center of the tree structure. All 6 faces are top faces.
  
• F: Has a bottom face, an opposite top face, and 4 side faces.
  
• E: Has a bottom edge, and an opposite top edge. The 2 faces connected by the top edge are top faces, and the 4 other faces are side faces.
  
• V: Has a bottom and an opposite top vertex. The 3 faces next to the top vertex are top faces, and the 3 faces next to the bottom vertex are side faces.

The following diagram shows the cell types F, E and V at the right, with yellow top faces, and green side faces:
https://steamcommunity.com/sharedfiles/filedetails/?id=1508058032
At the left, we see the root cell C, surrounded by 3 orbits, each of which has its own arbitrary direction.
(note: the orbit colors are completely arbitrary, and not related to the arrow colors on the right side of the diagram)

Let's start by attaching an F cell to each root cell face, and two E cells to each root cell edge, such that the top faces point away from the root cell, and the blue arrows on the F and E cells align with the respective orbits.
This gives us 1 C, 3 F and 6 E cells around each root cell vertex, for a total of 10 cells. Since there are 20 cells around each vertex, and all root cell faces and edges are occupied, all we need to do now is to add 10 V cells to each root cell vertex, with the three top faces pointing outwards.
This completes the first layer around C, with 3 circles described by the blue arrows on the F and E top faces, and several circles described by the red arrows on the E and V top faces. There are 6 F cells, 24 E cells, and 80 V cells in the first layer, for a total of 110 cells surrounding C.

For subsequent layers, we'll use the following transition rules:

	Basic	Blue Circle	Red Circle	Total
F →	F	2E 4V	-	F 2E 4V
E →	2F 2E 6V	E 2V	2E 4V	2F 5E 12V
V →	3F 6E 19V	-	3E 6V	3F 9E 25V

The basic transition rules generate cells that are closest to the parent cell, while ignoring cells that are equally close to another parent cell in the same layer. They can be summed up as following:

• Add an F cell on each top face.
  
• For each pair of added F cells, do the following: Put 2 E cells between them. Then add 4 V cells to the free side faces of the added E cells, and 1 more V cell between each pair of added V cells.
  (so in total: 2 E and 6 V cells per pair of added F cells)
  
• For a V parent cell, add an additional V cell to the top vertex to fill the gap.

Make sure that the blue arrows on the added F cells align with the arrows on their parent cell, and that the blue arrows from the added E cells point in the same circular direction as their added F neighbors.

Note that the first rule makes sure that each top face is covered with an F cell, and the second rule makes sure that each edge connecting two top faces is covered with 2 E cells.
The second and third rule make sure that the top vertex of a V parent cell is covered by 10 V cells. So in total, 3 F, 6 E, and 10 V will be added to the top vertex of a V parent cell.
This shows that there won't be any gaps directly above a parent cell.

The blue and red circle transition rules fill the gaps: For each top face arrow that points at an edge between a top and a side face, add an E cell to this edge. Then, add 1 V cell to each of the 2 free side faces of the added E cell (2 side faces are already covered after applying the basic transition rules).
Here again, make sure the blue arrows on the added E cells point in the same circular direction as the arrows on the neighboring added F cells.

Do the transition rules work as intended?

I am not absolutely certain, but so far it looks like it should work.

1) First of all, let's make sure that surface circles consisting of either red or blue arrows expand correctly. While it is not essential for the proof, it's good to see that this part works. Those circles correspond to circles in {4,5}, assuming vertex-adjacency:
https://steamcommunity.com/sharedfiles/filedetails/?id=1493020573
The circle with radius 1 has pattern [BAB]^4. I used bright colors (green, orange) for A cells, which share an edge with an inner neighbor, and darker colors (blue, red) for B cells, which only share a vertex with an inner neighbor. The transition rules are:

A → A(B)
B → ABBA(B)

A basically corresponds to F cells, and B to E cells along blue circles. This gives us:

F → F(2E)
E → FEEF(E)

The amount of generated E cells for F has to be doubled, because on F cells two blue circles intersect. The generated cells in brackets correspond to the blue circle transition rules, while the other generated cells correspond to the basic transition rules.
We can see that those transition rules correspond to the basic and blue circle transition rules, if we ignore V cells, which is enough to confirm that blue circles expand correctly.

If we start from a red circle, a blue circle consisting of F and E cells will be generated on top of it, and we already confirmed that blue circles expand correctly.


2) Earlier, we have confirmed that there are no gaps directly above a parent cell. But are the gaps between cells in the same layer filled correctly?

Well, the transition rules make sure that arrows on the surface form circles, pointing in the same circular direction. Placing an E cell at an edge pointed at by an arrow makes sure that this gap above the edge is filled.

But what about surface vertices? There are 3 different types of surface vertices that occur on the first layer:

• Single-cell vertex: The top vertex of a V cell.
  
• "Roof" vertex: The vertex connecting two cells of type E or V at their highest edges. The possible cases are 'EV' and 'VV'.
  
• 5-cell vertex: The vertex is part of an edge surrounded by 5 surface cells, either 'FEVVE', 'EEVVV', or 'VVVVV'.

The single-cell vertex type has already been covered.

Connecting two cells of type E or V results in 20 cells around the vertex:
- 2 parent cells
- 4 F cells (1 per top face adjacent to the vertex)
- 4 E cells, and 6 inwards V cells from the basic transition rules
- 2 E cells, and 2 inwards V cells from the red circle transition rules

There are also 20 cells around the 5-cell surface vertices:
- 5 parent cells
- 5 F cells (1 per top face adjacent to the vertex)
- 5 E cells (1 per surface edge between neighboring cells, placed in direction of blue or red arrow)
- 5 V cells (1 inward V cell per added E cell)

For a complete proof, we'd either have to show that those are the only surface vertex types that occur, or, if this is false, we'd have to make sure that the transition rules work correctly for any other vertex types.

Alternative root setups

We started with a single root cell, but there are alternative setups. For example:

1) Start with 20 V cells around a root vertex

2) Start with root cells whose centers correspond the the cell centers in a {4,5} plane. The two faces pointing away from the plane are the only top faces of a root cell.

In case 2), we have to draw a pair of crossing arrows on each top root face, making sure the arrows form unidirectional lines. Those lines could be generated based on the following pattern in {4,5}:
https://steamcommunity.com/sharedfiles/filedetails/?id=1493020932

• When standing on a white square above a white intersection square, draw a line through this square that points to the right.
  
• This results in the same rule for dark gray squares, except the line points to the left.
  
• Pure white or dark gray lines can point in any direction. For simplicity's sake, start with a white line pointing in any direction; then let all intersecting white lines point to the right, the same with white lines intersecting the intersecting lines, and so on (same for dark gray lines).

While this doesn't explain in detail how line directions can be managed, it shows a way to do it consistently, at least.

[tricosahedron]

Following is the missing part of the proof that the tree structure works as intended:

Originally posted by tricosahedron:

For a complete proof, we'd either have to show that those are the only surface vertex types that occur, or, if this is false, we'd have to make sure that the transition rules work correctly for any other vertex types.

To show whether or not other surface vertex types occur, all we have to do is to generate child cells for each known surface vertex, and then see if any new surface vertex types pop up.

Originally posted by tricosahedron:

There are 3 different types of surface vertices that occur on the first layer:

• Single-cell vertex: The top vertex of a V cell.
  
• "Roof" vertex: The vertex connecting two cells of type E or V at their highest edges. The possible cases are 'EV' and 'VV'.
  
• 5-cell vertex: The vertex is part of an edge surrounded by 5 surface cells, either 'FEVVE', 'EEVVV', or 'VVVVV'.

I generated the child cells for each surface vertex type that share this vertex; it turns out that in all cases, exactly all known surface vertices appear in the next layer, with the exception that starting with a 5-cell surface vertex doesn't result in 'EEVVV', since E cells are never added in pairs here.

Unless I made a mistake somewhere, this should proof the correctness of the transition rules. :)

[tricosahedron]

At the end of my opening post, I mentioned a way to arrange lines on a {4,5} grid, s.th. cubes in a plane can be used as root cells for the tree structure. However, I found a simpler way to arrange the lines:
https://steamcommunity.com/sharedfiles/filedetails/?id=1508930619
The idea is to start with a central cell in the plane, and generate concentric circles around it (assuming vertex-adjacency). Again, cell types A (green, yellow) share an edge with an inner neighbor, while cell types B (blue, orange) only share a vertex with an inner neighbor.

Black arrows only depend on the cell type, while purple arrows have to be determined from the parent cell.
(note: I only drew black arrows for radius 1 and 2, and purple arrows only for the top right quarter of the picture)

For B cells, one black arrow points towards the right circle neighbor, while the other black arrow points towards the right top edge.

For the root cell, Two purple arrows point in arbitrary directions (different axes).

For A cells, the black arrow points towards the right circle neighbor. The purple arrow direction has to be determined from the parent cell: If an arrow from the parent cell points towards this cell, then the purple arrow will point up, otherwise it will point down.

[tricosahedron]

I calculated the number of cells per layer, assuming that layer 0 is the root cell:

Layer                F                   E                     V                 total
--------------------------------------------------------------------------------------
 0                   -                   -                     -                     1
 1                   6                  24                    80                   110
 2                 294                 852                 2,312                 3,458
 3               8,934              25,656                69,200               103,790
 4             267,846             768,948             2,073,608             3,110,402
 5           8,026,566          23,042,904            62,138,960            93,208,430
 6         240,529,254         690,518,292         1,862,095,112         2,793,142,658
 7       7,207,851,174      20,692,505,976        55,800,714,320        83,701,071,470
 8     215,995,006,086     620,084,661,108     1,672,159,334,408     2,508,239,001,602
 9   6,472,642,331,526  18,581,847,327,384    50,108,979,317,840    75,163,468,976,750
10 193,963,274,939,814 556,835,335,160,532 1,501,597,220,200,712 2,252,395,830,301,058

Note: Those numbers are only for the specific layers. While there are 3458 cells in layer 2, the complete tree with 2 layers contains 1 + 110 + 3458 cells.

Here again, the transition rule:

F → {F, 2E, 4V}
E → {2F, 5E, 12V}
V → {3F, 9E, 25V}

I noticed that the ratio between cells in layer n+1, and cells in layer n seems to converge towards 15 + 4sqrt(14) ~ 29.97. This applies to general cells, as well as to cells of a specific type (F, E, V).

Also, the ratio #F : #E : #V seems to converge towards 1 : (1 + sqrt(14)/2) : (4 + sqrt(14)).

I tested the values, and it looks like they are correct:
If I start with an (irrational) number of F, E and V cells with this exact ratio, and use the transition rule to generate the next layer, the ratio remains the same, and the total number of cells for the next layer increases by said factor of 15 + 4sqrt(14).

[tricosahedron]

It can be difficult to imagine what the surface of a ball in this honeycomb looks like. Normally, the 3 cell types appear as following on the surface:

• F cells appear as a square
  
• E cells appear as 2 squares, connected by the top edge
  
• V cells appear as 3 squares around the top vertex

However, there's a way to simplify the surface structure, s.th. each cell type is represented by a single surface polygon:

• F cells remain unmodified, and still appear as a square on the surface.
  
• For E cells, take the 2 edges that connect them to other F or E cells, then make a cut through the plane that contains both edges. This cuts the cube into 2 triangular prisms with a rectangle* base. As we remove the top half, the bottom part of the cell appears as a rectangle on the surface.
  
• For V cells, take the 3 vertices that are next to the bottom vertex, and make a cut through the plane that contains them. After removing the top part, the remaining bottom part of the cell is a triangular pyramid that appears as a regular triangle on the surface.

* I define a non-Euclidean rectangle as a quadrilateral with 4 equal angles, and where opposite sides have the same length. If anyone knows a more appropriate term, please let me know. ;)

A side-effect of this simplified surface is that it's smoother, and the slopes are less extreme, making it easier to walk on the surface if gravity pulls towards the center.


Using this simplified representation, here's a diagram that shows the child cells derived from a parent cell of each type (F, E, V). I used red for F cells (square), green for E cells (rectangle), and blue for V cells (triangle).
Note that the polygons are distorted, and "rectangles" often have the shorter and longer side swapped. Also, only the child cells are shown, while the parent cells are only indicated with F, E, V.
https://steamcommunity.com/sharedfiles/filedetails/?id=1520260325
The blue arrows on the parent F cell here point up and left, and the blue arrow on the parent E cell here points up.

Note that V cell groups (blue triangles) are always arranged like icosahedron faces:

• The 10 V cells derived from a parent V cell are arranged like the 10 faces you see when looking at an icosahedron face.
  
• The 8 V cells that occur between V and E parent cells are arranged like the 8 faces you see when looking at an icosahedron edge.
  
• The 5 V cells that are surrounded by alternating F and E cells are arranged like 5 icosahedron faces around a vertex.

It could be interesting to analyze horosphere surface patterns in this honeycomb. Horospheres can be generated by starting with a single F, E or V cell, and extending a tree from it:

• From F cells, we get a central infinite line consisting of F cells that is orthogonal to the horospheres. Child cells only extend in a limited number of directions, but we can use the 4-fold symmetry around this line to extend the horospheres in all directions.
  
• From E cells, we get a central infinite line of alternating single and double E cells. So each other layer will generate a different horosphere pattern around the line center.
  
• From V cells, we get a central infinite line of V cells.

Note that actual hyperbolic distance per cell is small along the line of F cells, large along the line of V cells, and somewhere in-between along the line of E cells.
This will likely have an effect on the actual average curvature of the "horospheres", depending which base line is used to generate them. For example, "horospheres" generated using V lines have an above-average "distance" from the center, and should be more positively curved, while "horospheres" generated using F lines have a below-average "distance" from the center, and should be more negatively curved.

[tricosahedron]

I wonder how this pattern in {4,5} could be extended to a honeycomb in {4,3,5}:
https://steamcommunity.com/sharedfiles/filedetails/?id=1533399490
As a start, the grey cells can be interpreted as single cubes, and the lines could be implemented as planes that are attached to each face of those single cubes (so there would be 6 planes around each cube, not just 4).
However, if we start at the center of a single cube, and go in the direction of a cube vertex, the 3 planes diverge. Is there a way to complete the pattern in this direction, with the resulting tile size still being relatively small?

Such a pattern could be a nice basis for tunnel systems in a hyperbolic six-degrees-of-freedom game.


Also, I'd like to see patterns that use identical or different 3D tetrominos as tiles.
(Hint: In this honeycomb, the equivalent to the Euclidean 2x2 tetromino would have a gap. And there are two 3D tetrominos that don't have a 2D equivalent, or three if mirror versions count extra.)

[Fulgur14]

The problem I see here is that the colored lines have two distinct kinds of squares -- one adjacent to grey squares, one not.

But if you want to extend this to 3D, the lines become full {4,5} planes -- and you can't tile those with two different types of cubes that alternate.

[tricosahedron]

Yeah, it's not as simple as having 2 cell types, but not necessarily much more complicated. If we look at the grey cubes as centers of a sphere with radius 1 (vertex adjacency assumed), we can label some (or all?) of the plane cells as F, E, V, depending on their position relative to adjacent grey cubes, according to my cell type definition for the tree structure.

In the 2D picture, the line cells between 2 grey squares would correspond to F cells, and the other line cells would correspond to E cells.

If the lines are extended to planes, each F cell shares a face with 2 opposite grey cubes outside of the plane, and with 4 E cells within the same plane. The remaining 8 edge neighbors of an F cell within the same plane would be V cells.
E cells would share a face with 2 opposite E cells outside of the plane, and with 2 opposite F cells and 2 opposite V cells within the same plane. It follows that 4 of their other edge neighbors in the plane are E cells, and 4 are V cells.

The plane pattern could be continued in a simple way, but an arbitrary pattern may not work depending on how the pattern continues beyond the point where 3 nearby planes diverge.

[Fulgur14]

Yes, my research into tilings cannot be, sadly, easily extended into more than 2 dimensions.

[tricosahedron]

Originally posted by Fulgur14:

Yes, my research into tilings cannot be, sadly, easily extended into more than 2 dimensions.

This was basically the reason why I created this thread: Finding tree structures for hyperbolic honeycombs, which enable designers to create games / tools that implement those, which in turn allows users to experience or research those honeycombs.
But yeah, I currently don't know any useful tools that allow to mark cells in hyperbolic honeycombs etc., either.

I noticed that tree structures based on vertex adjacency are relatively simple to implement for honeycombs {p,3,4}, with p ≥ 3. They have 4 cells around each edge, and 8 cells around each vertex. That includes:

• The 16-cell {3,3,4}, for which the tree structure can be implemented in a minimalist way.
  
• The Euclidean cubic honeycomb {4,3,4}, which is useful as an easy way to understand how the tree structure works, before generalizing it for the hyperbolic honeycombs.
  
• The order-4 dodecahedral honeycomb {5,3,4}, which is the dual of the order-5 cubic honeycomb {4,3,5}. That means we now have tree structures for 2 out of the 4 compact regular honeycombs, with only {5,3,5} and {3,5,3} missing. :)
  
• The order-4 hexagonal tiling honeycomb {6,3,4}, which consists of hexagonal tiling cells whose vertices lie on a common horosphere, and which could be further subdivided.
  
• The order-4 heptagonal tiling honeycomb {7,3,4}, with heptagonal tiling cell borders, whose vertices lie on common equidistant planes. The cells could have two cell borders on opposite sides, with a heptagonal tiling plane in the middle. Each cell could contain a complete HyperRogue world (we already discussed this in another thread).
  
• The order-4 octagonal tiling honeycomb {8,3,4}. Similar to {7,3,4}, but with octagonal tilings as cell borders / central planes.

How the tree structure works

The cell types for a honeycomb {p,3,4} are defined similar to the ones in the {5,3,4} tree:

• A root cell R where all faces are top faces
  
• F cells have 1 bottom face, p side faces, and all other faces are top faces.
  
• E cells have 1 bottom edge, 2 side faces that have this edge in common, and 1 more side face at each bottom edge vertex (for a total of 4 side faces). All other faces are top faces.
  
• V cells have 1 bottom vertex, with 3 side faces around it. Again, all other faces are top faces.

Each cell has the following child cells:

• 1 F cell for each top face.
  
• 1 E cell for each edge between 2 top faces.
  
• 1 V cell for each vertex between 3 top faces.

...and that's it, mostly, because fortunately, no additional gaps have to be filled based on cell orientation. To illustrate:
Two face-adjacent cells in the same layer either have 2 or 3 surface vertices in common.
(A) If they have 2 surface vertices in common, there are 4 same-layer cells around both surface vertices, and each of those 4 cells per vertex generates an F child cell next to this vertex, resulting in 8 cells around both vertices.
(B) If they have 3 surface vertices in common, one of the vertices is only shared by both cells within this layer. Each cell has 2 top faces and 1 surface edge around this common surface vertex, and generates 2 F and 1 E cell around this vertex, for a total of 2 parent cells and 6 child cells around this vertex.

About the individual honeycombs:

{3,3,4} is a bit special here, since E cells have 2 bottom edges, each of which is shared with one of the two R cells (poles), and all 4 faces are side faces. And V cells are reinterpreted as F cells for the other pole, so the face that would normally be a top face is a bottom face instead, with the 3 remaining faces being side faces. As a result, only the poles have top faces, and the only transition rule we have is R → {4 F, 6 E, 4V} = {8 F, 6 E}, with 2 different types of F cells around each pole R.
(which is a bit messy, since each R cell shares its 14 child cells with the other R cell)

{4,3,4} and {5,3,4} are straightforward. For {4,3,4}, the transition rules are as following:
R → {6 F, 12 E, 8 V}
F → {1 F}
E → {2 F, 1 E}
V → {3 F, 3 E, 1 V}

...and for {5,3,4}:
R → {12 F, 30 E, 20 V}
F → {6 F, 10 E, 5 V}
E → {8 F, 15 E, 9 V}
V → {9 F, 18 E, 10 V}


For {p,3,4} with p ≥ 6, it doesn't make sense to list transition rules with the (infinite) number of child cells. But we can still describe how cells relate to each other.
Most importantly, the faces from each cell can be accessed by a tree structure for the {p,3} tiling, with face types A and B. With a single central face, the radius 1 pattern is {A}^p, and the transition rules are:
A → {A}^(p-5)B
B → {A}^(p-6)B
So for {6,3}, we have a starting pattern of A (repeated 6 times), and transition rules A → AB, B → B. And for {7,3}, the starting pattern is A (repeated 7 times), and the transition rules are A → AAB, B → AB.

Note: A faces have a bottom edge, and B faces have a bottom vertex that point towards the circle center.

We can use this to access child cells from R as following: The central face generates an F cell, its edges generate p E cells, and its vertices generate p V cells.
Each A face on a circle with radius > 0 generates an F cell, p-2 E cells (one for each edge except for the bottom and left side edge), and p-2 V cells (one for each non-bottom-edge vertex).
Each B face on a circle with radius > 0 generates an F cell, p-1 E cells (one for each edge except for the left side edge), and p-1 V cells (one for each non-bottom vertex).

For F, E and V cells we can generate circles around the bottom face, edge or vertex in a similar way. However, the first circle around those only contains side faces, and only starting with the circle around this child cells will be generated.


One thing that is also important for a software implementation of those trees is cell orientation, and how child cell orientation is determined based on parent cell orientation. But I don't think that it's very difficult to find a suitable implementation.

P.S.: I wonder how easy or difficult it is to find tree structures for the 3 bitruncations of the compact regular honeycombs 2t{5,3,4} = 2t{4,3,5}, 2t{3,5,3}, or 2t{5,3,5}, with order-4 vertices and at least one Archimedean cell type.

[tricosahedron]

I've already discussed this with Fulgur14:

There's a class of uniform hyperbolic honeycombs called borromeachoron, as defined here.[os2fan2.com]
It has cube and p-gonal prism cells, with a fixed p ≥ 3 for each specific honeycomb. Prisms meet at their base polygon, and cubes are attached to the prisms at their (non-base polygon) squares. To each cube face, a prism is attached with a (non-base polygon) square, according to pyritohedral symmetry, similar to how bilunabirotundae are attached to cube faces in this Euclidean honeycomb (see rightmost picture).[en.wikipedia.org]

For p = 4 we get a lower symmetry interpretation of {4,3,5}, where some cubes are interpreted as square prisms. If we look at {4,3,5} cells whose center lie in a common {4,5} plane with this interpretation, it will always look like this:
https://steamcommunity.com/sharedfiles/filedetails/?id=1543018703
The blue squares represent square prisms that form stacks that lie entirely in the plane. The green squares represent single cubes, with square prisms around them. And the red squares represent square prisms that form prism stacks that only have one cell in common with the displayed plane.
The dual of this interpretation is {5,3,4}, with the dodecahedron cells being interpreted as pyritohedra.

I am mentioning this here, because

• This interpretation of {4,3,5} could be used as a basis for a simple level structure in a game.
  
• Maybe it could be used as a basis for a tree structure for {4,3,5} that doesn't use vertex-adjacency.
  
• I am interested in the case p = 3 (i.e. cubes and triangular prisms), and in a tree structure for it, or for its dual, which is composed of 3 or 4 pyritohedra around an edge, depending on the edge type.

[tricosahedron]

Originally posted by tricosahedron:

I noticed that tree structures based on vertex adjacency are relatively simple to implement for honeycombs {p,3,4}, with p ≥ 3. They have 4 cells around each edge, and 8 cells around each vertex.

I noticed that this can be generalized further. I think it should be something like this:

If all cell faces lie in a plane that doesn't pass through other cells, and the honeycomb has a relatively simple symmetry, then there's a straightforward way to implement a tree structure based on vertex adjacency:

• Start with a root cell, root vertex, or root cells in a common plane etc.
  
• Build the first layer around the root cells manually, using cells of type F, E and V (includes subtypes if there are different cell, face, edge and/or vertex types).
  
• F cells have a bottom face, and all faces that are vertex-adjacent to the bottom face are side faces. Any remaining faces are top faces.
  
• E cells have a bottom edge, and all faces that are vertex-adjacent to the bottom edge are side faces. Any remaining faces are top faces.
  
• V cells have a bottom vertex, and all faces around it are side faces. Any remaining faces are top faces.
  
• Trivial child cells can be generated for each parent cell type like following: Add an F child for each top face, add E children for each edge between two top faces, and add V children for each vertex surrounded by top faces.
  
• To figure out how to generate the less trivial child cells, extend each side face of the parent cell to a plane. Consider the space enclosed by those planes and the top faces. Within this space, add E and V children to the edges and vertices that belong to top faces, but aren't enclosed by them.

I have successfully applied this approach to a somewhat exotic honeycomb, which takes the pyritohedron cells from the dual of the triangular borromeachoron honeycomb, and splits each pyritohedron into 2*4 mirror-symmetric asymmetric triangular trapezohedra.[en.wikipedia.org]
Each trapezohedron has 6 identical faces, which are Lambert quadrilaterals with an acute 60° angle.
A trapezohedron has 6 edges of type a, and 3 edges of type b and h, each. There are 4 cells around a or h edges, and 6 cells around b edges.
There are 2 vertices of type C where 3 a edges meet, and 6 vertices of type P where 3 edges of all types (a, b, h) meet. So there are 8 cells around each C vertex, and 12 cells around each P vertex.

If there is interest, I can go into more detail about this honeycomb, but for now I will focus on the transition rules, as an example for a tree structure for a honeycomb with different cell, edge and vertex types:

XF → {1 YF | 1 XB}
XA → {2 YF, 1 XA | 2 XB, 2 YP}
XB → {2 YF, 1 XH | 2 XB, 2 YP}
XH → {2 YF, 2 XB, 1 YB | -}
XC → {3 YF, 3 XA, 1 YC | 3 XB, 3 YP}
XP → {3 YF, 1 XA, 1 XH, 2 XB, 1 YB, 2 YP, 1 XP | 1 XB, 1 YP}

X and Y denote the two mutually mirror-symmetric cell types. The transition rules are only given for an X parent cell, but the rules for the mirror-symmetric Y cell look the same, except that X and Y are swapped.

XF is of cell type F.
XA, XB and XH are of cell type E (refering to different bottom edge types a, b and h).
XC and XP are of cell type V (refering to different bottom vertex types C and P).

In the {}, I listed the trivial child cells first, followed by the less trivial child cells after the '|'.

This example also illustrates how the cells in a honeycomb can be subdivided, s.th. this approach can be applied to the new cells.
(extending the pyritohedron faces to planes means that those planes pass through the centers of other pyritohedron cells, so this approach wouldn't work for the original honeycomb, and a subdivision was necessary for this approach)


Some open questions:

• Is there a simple approach for tree structures based on face- or edge-adjacency?
  
• Is there a simple way to assign non-trivial child cells to parent cells if the approach described in this post can't be applied?
  
• How simple or difficult is it in general to subdivide honeycombs s.th. the approach in this post can be applied to the modified honeycomb?

[zeno]

The simplest honeycomb to implement is the 3D analog of the binary tiling: https://youtu.be/625ZwpjtWZU

[tricosahedron]

I'm really impressed that the game now has hyperbolic honeycombs!

Out of curiosity: For [5,3,4} and {4,3,5}, do you use the tree structures from this thread? Or do you use the simpler {5,3,4} tree structure for both {5,3,4} and {4,3,5}? Or did you find trees where each cell only links to face-adjacent neighbors? In the latter case, I'd be interested about the tree structure.

Also, let me know if you want me to try to figure out certain tree structures. The ones for {4,3,8} or the runcinated order-5 cubic honeycomb should be quite simple. And I could provide absolute lengths and angles for the honeycomb from my last post, i.e. the one with the asymmetric triangular trapezohedron cells, which is related to the triangular borromeachoron honeycomb.

[zeno]

No, currently it uses a less elegant, but much simpler solution, which was also previously used for the Archimedean tilings: each vertex knows its position/orientation in the space, and when the game asks for the neighbor i of cell c, it computes its position and checks whether a vertex exists there, and connect them in yes. To prevent floating point errors, another tiling is built, and positions are computed relative to that (this is {7,3} tiling for Archimedean, and binary in 3D). (I believe floating point errors are still possible if you wander in weird ways.)