A colleague mentioned the other day about creating a random world generator that starts from an icosahedron (20-sided polyhedron) and splits each face multiple times using discrete sets of Voronoi diagrams. The idea itself is quite unique, but was a lot of overhead to comprehend and even process as it would tessellate many times. Upon later reflection it was realized that the problem could be easily solved with a small modification to an existing algorithm: Binary Space Partitioning. The only constraint was to ensure that each face was always a triangle. Enter ternary space partitioning.

A flattened tetrahedron with four faces.

The smallest polyhedron that each face is walkable to the other is a tetrahedron, which has 4 sides - all of which triangles. While letting that be the starting point of the partitioning, when you think about splitting it up, you essentially look at the vertices and notice that 3 faces will always connect to each vertex.

Squishing the vertex at faces A, B & C.

Squishing the vertices down entirely of a tetrahedron will provide an octahedron. It's important to keep track of the connecting faces every time this partitioning occurs that way relationships can be established allowing pathing algorithms to traverse from one face to another. These relationships we establish will be a tree similar like binary space partitioning except instead of each node having two leaves, they will have three.

Now let us look at this from a relationship perspective to more easily understand how we would path from one face to another on just an octahedron for simplicity.

world has walkable children nodes: A, B, C & D
node A has 3 walkable children nodes: ABC, ACD & ABD
node B has 3 walkable children nodes: ABC, ABD & BCD
node C has 3 walkable children nodes: ABC, ACD & BCD
node D has 3 walkable children nodes: BAD, ACD & ACD

Before beginning, you may notice that children nodes will have three parents: that is correct! Unlike a traditional BSP, we need keep track of our neighbors so that we can path easily around. In order to get from C to BAD, we can easily see ourselves that you can do it many ways, an inefficient one is highlighted below.

Very inefficient way of pathing from C to BAD. 

A more efficient way would of course would be either of the following:


The code, however, is much more dumb. Because it's not a directed acyclic graph, we can't recursively call parents - it could happen forever. Instead we would do a pathfinding algorithm like Dijkstra's or Breadth First Search to look outward.