The hexagonal tilesets for my first experiments in board game design, Advaya and Atreya, were developed by explorative programming and that process was explained in a different article.

Here, I will discuss some theoretical aspects that are not really relevant for playing the games, but are interesting questions from a theoretical point of view and for implementation purposes. We will completely forget about the pieces drawn on the tiles and just consider the game arenas as abstract objects made from equivalent tiles, without edge-matching constraints imposed by the colors.

From a mathematical point of view, the arenas of tabletop games like Hive, Advaya and Atreya are nothing but dynamically changing polyhexes, and more specifically for the latter two, biconnected holefree polyhexes. I would argue that this is an interesting combination of properties. While simple connectedness can be understood geometrically, biconnectedness is an inherently graph-theoretic property that is combined with otherwise geometric restrictions.

Summarizing the relevant rules of Advaya and Atreya, an arena consisting of hexagonal game pieces is valid if its graph is biconnected and it has no holes (in the geometric sense). Furthermore, this validity is to be maintained throughout any tile movement. From Hive I have borrowed the additional restriction that tiles may only be moved from one position to another if, besides upholding arena validity, the movement can be performed without lifting the tile up, purely by sliding it on the table and without needing to move any other tiles (assuming perfect precision and tile placement).

This combination of properties has some interesting non-obvious consequences and I have not found a paper looking at the interaction of these properties before, so here I want to present my not too difficult, but still interesting findings.

Preliminaries

Some finite non-empty set $A \subseteq \mathcal{H}$ of cells (or positions) of an infinite regular hexagonal grid $\mathcal{H}$ is called a polyhex. By $\overline{A}$ we denote the set of cells $\mathcal{H}\setminus A$ that do not belong to $A$. We say that cells $c\not\in A$ are empty, whereas cells $c\in A$ are occupied. A tile is a cell-shaped position marker and it is implied that each occupied cell is covered by a tile. The connectivity graph of $G(\mathcal{H})$ is the 6-regular triangular grid graph with cells as vertices and shared cell boundaries as edges. The connectivity graph of the polyhex $G(A)$ is just the restriction of $G(\mathcal{H})$ to the polyhex cells, whereas the connectivity of empty space is captured by $G(\overline{A})$.

A polyhex is biconnected if removing a cell from the set does not disconnect any pair of other cells and it is holefree if there is no empty area of cells fully surrounded by cells of the polyhex. A polyhex is valid if it is biconnected and holefree, which formally means that $G(A)$ is biconnected and $G(\overline{A})$ is connected. A hole is a finite connected component of $G(\overline{A})$ that is disconnected from the rest. An almost-hole is a maximal connected area of empty cells that becomes a hole by making one more tile occupied.

We can also treat $A$ as a characteristic function $A : \mathcal{H} \to {0,1}$ mapping cells of the polyhex to 1 and all others to 0. The 6 neighbor cells of $c$ are denoted by the set $N(c)$. To describe the relative layout of the neighbors, start with any neighbor, traverse them in counter-clockwise order, and write down $A(c)$ for each of them. Next, take the lexicographically smallest out of the 6 cyclic shifts as the connectivity profile $P(c) \in {0,1}^6$ of $c$ (illustrated e.g. here). For example, if every other neighbor cell is occupied, then the profile is 010101. If $P(c) \in 0^{6-k}1^k$ for $k\in[1..6]$, we say that $P(c)$ is $k$-simple and also call it a $k$-gap if $c\not\in A$. The notation $[n..m]$-gap or $[n..m]$-simple denotes that a cell is a $k$-gap or $k$-simple with $k\in[n..m]$. Notice that $P(c) = 1^6$ means the cell is completely surrounded by polyhex cells, and dually, if $P(c) = 0^6$ means then it is completely surrounded by empty cells.

We will mostly care about boundary cells, i.e. $$B = \{ c\in\mathcal{H} \mid \exists c’\in N(c): A(c) \neq A(c’) \}$$ and distinguish boundary cells $B_A = B \cap A$ inside the polyhex and $B_{\overline{A}} = B \cap \overline{A}$ outside the polyhex. Notice that there are 14 different profiles and one of the 12 nontrivial ones can apply to a boundary cell.

The profile of each cell describes the sides of the cell, which are the consecutive edges shared with neighbors along the profile with the same status (empty or occupied). The endpoints of sides are the two cell corners at the start and end of a side. Sides consisting of empty neighbors are called open. If there are more than one non-open sides, we call the side a tunnel, which can be narrow, if consisting of one edge, or wide otherwise. For example, the profile 001101 consists of four sides, and two of them are open, one is a narrow tunnel and one a wide tunnel.

Efficient validity update exploiting restricted cell connectivity

First we will see that the inside boundary of biconnected holefree polyhexes has very restricted connectivity options and use this to get efficient algorithms to check validity in a dynamic setting. We start by testing validity of an unknown polyhex, and then proceed with the case where a cell is added or removed.

Proposition. Deciding whether a connected polyhex is holefree is possible in linear time.

Proof. Given a cell $c$ of a polyhex $A$, explore the polyhex starting from $c$ as follows. In addition to the BFS exploration queue, maintain a queue of open sides (e.g. as pair of cell coordinates and the side endpoints) for which the boundary cycle they belong to is not known (we call such sides orphans). The algorithm computes all boundary cycles and the open sides that belong to them and prioritizes tracing the boundary of orphans by closing a cycle they belong to over exploring of the graph. When tracing, there is an active boundary id to identify this cycle later.

Whenever a cell is visited, proceed as follows. If there is an active boundary id, assign the id to the traced open side. If the cell is visited for the first time, add each newly discovered but unvisited neighbor to the exploration queue and mark them as discovered. Next, add each open side without assigned boundary id to the orphan queue and mark the cell as visited. If currently tracing a cycle (i.e., there exists an active boundary id), check the neighbor cell along the traced open side. If its traced open side has no id yet, proceed to this neighbor. Otherwise, the cycle is completed, hence unset the active boundary id and check the orphan queue.

If it is empty and no unvisited neighbors exist, the algorithm terminates. Otherwise, explore the unvisited neighbors by BFS using the exploration queue. If the tracing queue is not empty, take an open side from the queue, and check that it is still has no boundary id. If it has an assigned id, just discard it and proceed to the next one, because its cycle has been already traced after adding it to the queue. Otherwise, set a fresh active boundary id and proceed by jumping to the cell with the orphan side (i.e., visit it again to trace the unknown boundary cycle).

Notice that each cell of the polyhex is visited at least once due to the BFS exploration queue. As on the first visit the boundary segments are registered for exploration, so every boundary segment is eventually discovered and assigned to a cycle due to the tracing queue. As a cell can have at most 3 different open sides, each cell is visited at most three times (once for each cycle, if they are different). $\blacksquare$

Remark. If you only want to know whether there are holes, you can abort the algorithm after finding two different boundary cycles. Also, this algorithm works with triangular and square grids (and also e.g. triangulated polygons) with the obvious required adaptations concerning neighbor connectivity. If you need to know which cycle is the outside boundary of the polyhex, just compute the bounding box of the polyhex and pick a boundary cell that touches the bounding box, its cycle must be outside.

The following observation is the key for simple and efficient updates:

Lemma. Let $A$ be a polyhex.

1. $A$ is valid and $|A|\geq 3 \Rightarrow \forall c \in B_A,$ $P(c)$ is $[2..5]$-simple.

2. $A$ is connected, holefree and ($|A| \leq 2$ or $\forall c \in B_A,$ $P(c)$ is $[2..5]$-simple) $\Rightarrow A$ is valid.

Proof. (1.) The profiles $0^6, 1^6$ and $0^5 1$ are impossible for an inside boundary cell of a valid polyhex of size greater than 2. Specifically in the case of $0^5 1$, removing the single neighbor of a cell $c$ with $P(c)=0^5 1$ would separate $c$ from the other polyhex cells, violating biconnectedness.

Now assume that a cell $c\in B_A$ has two open sides, i.e., $P(c) \in 0^+ 1^+ 0^+ 1^+$. Let the two non-open sides (here meaning the corresponding neighbor cells, not the edges) be denoted by $l$ and $r$, the two open sides by $u$ and $d$. As $A$ has no holes, $u$ and $d$ must be both on the outside and hence be connected by a path using only empty cells. This implies that either $l$ or $r$ are completely enclosed by a cycle of cells where all cells except for $c$ are empty. It follows that removing $c$ from the polyhex disconnects polyhex cells in $l$ from polyhex in $r$, violating biconnectedness. The remaining case of $P(c) = 010101$ is shown similarly.

(2.) Connected polyhexes of size $\leq 2$ are trivially biconnected and holefree, and thus valid. Assume that $A$ is connected, holefree, $|A|\geq 3$, but not valid. This is only possible if $A$ is not biconnected. In this case, there must exist a $c\in A$ such that removing $c$ disconnects two neighbor cells $a,b$ of the polyhex, so the only path using polyhex cells from one side to the other use $c$. It is easy to see that in this case $c$ must have at least two open sides, because with only one open side it means that there is a path from $a$ to $b$ directly around $c$. Hence we conclude that $c\in B_A$ (because it has open and non-open sides) and $P(c)$ cannot be $k$-simple. $\blacksquare$

Theorem. Deciding whether a single cell update of a polyhex is valid can be done in $\mathcal{O}(1)$.

Proof. We assume that the size $n$ of the polyhex is known, so it does not need to be calculated by exploration. We can only add or remove boundary cells of the polyhex, as otherwise the polyhex immediately either gets a hole or becomes disconnected, therefore $c\in B$ must hold, excluding the profiles $0^6$ and $1^6$. Any empty neighbor cell can be added to a singleton polyhex and any cell can be removed from an polyhex with size at most 3. Next we analyze the remaining cases. By assumption that the polyhex was valid before, we know that the polyhex can only become invalid locally, and changing the state of a single boundary cell can only change the profiles of its neighbors.

First, consider adding a cell $c\in B_\overline{A}$ to an polyhex of size at least 2. When adding $c$ to the polyhex, the connectivity of neighbor cells only increases. So $c$ only can violate biconnectedness if it is an 1-gap, as removing its single neighbor would disconnect the polyhex. Also, adding a cell at a $k$-gap position can not introduce a hole, so the only way to create a hole by adding a single cell is by picking a cell that has (at least) two open sides, i.e. $P(c) \in 0^+ 1^+ 0^+ 1^+ + 010101$. By an argument like in the previous lemma, we have at least one path of occupied cells between the two non-open polyhex sides and this path does not use $c$. Hence the two open sides with empty cells must become disconnected by adding $c$, making one of the open sides part of hole. So a cell $c \in B_\overline{A}$ that can validly be added to $A$ must be a $[2..5]$-gap.

Next, consider removing an polyhex cell $c\in B_A$. By assumption the polyhex was biconnected before, so removing $c$ keeps it connected. Furthermore, removing $c$ clearly cannot increase the number of holes. By the previous lemma and the fact that only the neighbor profiles changed, we conclude that for determining whether the polyhex is still valid it suffices to check whether the profiles of all relevant neighbor cells in $B_{A\setminus {c}} \cap N(c)$ are $[2..5]$-simple or the arena size decreased below $3$. $\blacksquare$

Corollary. Deciding whether a connected polyhex is valid is possible in linear time.

Proof. Use the presented algorithm to find holes in the polyhex $A$ and compute its size. If there are no holes, by the lemma it suffices to check whether If the size is less than $3$ (then $A$ is trivially valid) or otherwise check whether all $c\in B_A$ have $[2..5]$-simple profiles. Alternatively, one could use a generic algorithm to compute biconnected components and check that the polyhex is a single component, which also is possible in linear time, but more involved.$\blacksquare$

Tile dynamics: continuous vs. discrete sliding

These are very useful results to be used as subroutines to determine whether a move is valid, i.e., not violating the validity of the arena. But until now, the tiles located at the cells can just appear and disappear, not taking the geometric restriction on the arena dynamics into account that allows only tile movements possible by sliding without interfering with other tiles. Thinking discretely, moving a tile means temporarily removing it from the arena and then adding it at some different place. But sliding is intuitively understood in a continuous way that refers to the smooth process of actually moving the tile.

There are at least two problematic aspects with a continuous interpretation when combined with the validity invariance of the arena. While biconnectedness can hardly be understood in any other way than discretely, there are problems arising due to a continuous interpretation of a hole that become visible in the following situations:

1. moving a tile out from a position that leaves a 4-gap, and

2. moving a tile through a position with profile 001001.

The first issue arises due to the fact that an actual, geometric hole in the arena appears as soon as you start sliding a tile out. The hole will have at most the area of $\frac{2}{3}$ of a single cell at the point where the hexagon with radius $r$ smoothly slided a distance $r$ into the open direction, barely touching two of its previous neighbors in single points. Moving the tile further opens up this hole again, but a strict reading of the movement constraints would require us to disallow such a move under continuous interpretation. The same situation arises dually whenever we want to slide a tile into a 4-gap, introducing a temporary hole until the tile is in the final position. As this kind of hole is clearly not what is meant by the rules, this issue could be solved by saying that considered holes have at least the size of a full cell, but this would clutter the rules with more technicalities.

The second issue arises from the fact that the two tiles touching a 001001 position must be connected, so one open side of the cell necessarily is inside of some almost-hole that lacks a single tile at that position to become an actual hole. But this means, that sliding a tile through this position does create a temporary hole in the arena of possibly significant size.

One could decide that this is perfectly fine and thus it is simply forbidden to cross such a position with a tile, but allowing to use 4-gaps by adding a specific clarification, because it fits there, and at the same time prohibiting to move a tile through such a position even though it fits is a questionable decision. So instead of accepting the continuous interpretation of moving a tile, a better solution is to allow both of those things and formalize a purely discrete and graph-theoretic definition of allowed movements that captures what is meant by the intuitive geometrical definition via sliding.

Sliding components of a polyhex

For a tile to be able to slide in or out, it is obvious that we need two adjacent empty cells, as a tile cannot fit through a narrow tunnel consisting of just one boundary edge. When we consider the connectivity graph of empty cells $G(\overline{A})$, it is easy to see that we can slide a tile between any neighboring cells where both cells are part of a triangle of empty cells, and we cannot move a tile between empty cells connected just by a narrow tunnel.

Remark. An important observation is that once you have a triangle of empty cells, you can rotate the tile into any orientation by first moving it to the center of that triangle, and then you can continue to slide it through or into any of those three cells. So whenever a tile can be slided, it can also be rotated. While this does not matter as long we ignore the tile textures, this is important to know for the application in the game.

Maximal empty regions where a tile can freely move by sliding are called sliding components of the polyhex that form a sliding component graph where sliding components are nodes and narrow tunnels are the edges.

Proposition. Given a boundary cell of a connected polyhex, its sliding component can be determined in time linear in the polyhex boundary length.

Proof. For each cell $c\in B_A$ we can compute its sliding component using a BFS on $G(\overline{A}\cup {c})$, i.e. the empty cells, but starting from the non-empty boundary cell of the tile to be moved. For each visited $a$, only queue a unexplored neighbor cell $b\in N(a)$ for exploration if a common neighbor $c\in N(a)\cup N(b)$ is also empty, so that $a,b,c$ form a triangle. Notice that for each neighboring pair $a,b$ there are only two shared neighbors $c\neq c’$ that can form such a triangle. As we cannot place a tile away from the boundary and because the polyhex is connected, we do not need to explore empty cells that touch no polyhex cell, but those cells do count for the triangles. This way, the exploration will only proceed along the boundary. Intuitively, we do not require the whole open space, because we know that it is possible to slide tiles to any reachable position along the discovered boundary chain of triangles, even if it might be not the shortest path. $\blacksquare$

Proposition. The boundary of a connected polyhex can be decomposed into sliding components, each marked as hole, almost-hole or outside, in linear time.

Proof. First, use the algorithm to compute all holes and find the outside boundary of the polyhex. For each boundary, pick a cell and apply the previous algorithm to find its sliding component, with a slight modification. Queue empty neighbors that are not reachable for sliding (due to narrow tunnels) for later exploration, and then successively explore the other sliding components in the queue. $\blacksquare$

One can also show the following about the sliding component graph:

Proposition. Let $A$ be some polyhex. Then the sliding component graph is:

1. a tree rooted at the outside component iff $A$ has no holes, or

2. a forest iff $A$ has holes and is either connected, or is disconnected without nesting, or

3. any planar graph otherwise.

Proof. (1.) When holes are forbidden, there is no way for two sliding components to be disconnected, so all components are parts of and reachable by narrow gaps in the outside boundary.

(2.) There cannot be any cycles in the sliding component graph if connectedness of the polyhex is required, because a cycle of such components implies that the dual unbounded polyhex $\overline{A}$ has a hole of polyhex cells in $A$ and must itself be surrounded by cells in $A$, because if it these sliding components were are not surrounded by arena cells, there would be no narrow tunnels to restrict the tile movement, which is a contradiction.

If this happens inside a hole (holes are required to get disconnected graphs), then the non-empty area would be a nested shape, so having no nesting inside holes implies that the sliding component graphs inside of holes form trees. Hence, the sliding component graph must form a forest, each tree representing a set of connected sliding components inside a hole or the outside boundary.

(3.) Planarity trivially follows from planarity of the grid.

For the other direction, consider following procedure to map a finite planar graph $G$ and embed it on a hexagonal grid. Map each vertex to a sliding component of a suffiently large polyhex and each each edge to a narrow tunnel. Any vertex $v$ of the graph $G$ can be taken to be the outside component in the grid, as we can project $G \setminus {v}$ into the polygon defined by the previous neighbors of $v$, so that the outside sliding component connects to reachable vertices by narrow tunnels that lead into an almost-hole, whereas each other connected component of G is mapped into an actual hole. Notice that nesting of just depth 2 (areas inside holes) of occupied areas is required. The same procedure can be used for forests and trees and it is easy to see that the resulting polyhex must have the claimed properties. $\blacksquare$

Remark. In case of a valid polyhex, closing one of the narrow gaps would separate the empty space into two disconnected parts, because the sliding components form a tree. Hence, the non-triangle edges (i.e., narrow tunnels) of $G(\overline{A})$ are bridges and sliding components are in fact the biconnected components of the empty area. Also, one can apply the same approach to compute sliding components of the polyhex, if it is just required to be connected and we care about components on top of the tiles.

Existence of outside 2- and 3-gaps

Now we know how to check arena validity efficiently, both from scratch and throughout single-tile movements, and we can also check for a tile whether a certain movement is permitted, using the grid-based charactization of sliding using sliding components. The only thing missing is to check the edge-matching constraints that we abstracted away at the beginning, which is trivial.

One interesting question concerning tile movement remains—how likely is that a tile that we want to place or move will fit? There are multiple ways to make this question more concrete and the variant we will consider is: given an additional tile, how likely is that we can extend the arena with that tile? Clearly, this depends on the connectivity profile of the boundary positions and the possibilities and requirements imposed by the tile textures. In any case, the less edges to match, the more probable it is that a uniformly chosen random tile fits, so it would be good to know whether we can give any guarantees about the kind of boundary the arena always offers and which a tile should be able to match (here we only care about whether the tile fits somewhere validly).

According to the game rules, we can not move the new tile into almost-holes separated from the outside by narrow tunnels, so we are specifically interested in finding a position on the outside. We already know that biconnected holefree polyhexes have a nice inner boundary consisting of [2..5]-simple profiles and now we look for good positions on the outside to add a tile. We cannot use 1-gaps because this violates biconnectedness and we cannot use 5-gaps or any positions inside an almost-hole, because this violates the sliding rule, so we are interested in [2..4]-gaps in the outside sliding component of the outside boundary of the arena.

One can easily see that there are polyhexes with no 3-gaps (take the triangle polyhex), and also ones without 2-gaps (build a flattened “snowflake” of 21 cells). But in fact is impossible that there are neither 2-gaps nor 3-gaps somewhere on the outside:

Theorem. Every connected polyhex has a 2- or 3-gap in its outside sliding component.

Proof.

It is a known fact that the sum of directed exterior angles for all pairs of edges of a simple polygon is 360 degrees, and the outside boundary of a connected polyhex forms such a polygon. Instead of looking at the angles between edges directly, we can accumulate the change in angle in some direction (w.l.o.g. counterclockwise) along the polyhex boundary that each cell contributes, which means that we sum the angles between adjacent edges from the first boundary edge of the current cell to the first boundary of the next. One can easily see that $k$-gap cells contribute an exterior angle of $180-k\cdot 60$ degrees. We will first pretend that almost-holes are filled up with cells, to get an almost equivalent polyhex $A’$ without narrow tunnels and will take care of the possible problems later. This gives us the advantage that each $c\in B_\overline{A’}$ can only consist of $k$-gaps and the outside sliding component coincides with the actual outside boundary.

Notice that 5-gaps are trivial almost-holes and not reachable by sliding, so there are no 5-gaps in $B_\overline{A’}$. Also, the only positive angle change is possible due to $1$-gaps on the boundary, because $2$-gaps are angle-neutral and $[3..4]$-gaps angle-negative, so clearly there must exist $1$-gaps along the outside boundary. Observe that those 1-gaps can come only alone or in pairs, because three successive 1-gaps imply that their common shared neighbor is $1$-simple, violating polyhex validity. But this means that the positions before and after these single or paired 1-gaps (we call them flanking positions) must be $k$-gaps with $k\geq 2$.

Assume that for all $1$-gap sequences both the position before and after are $4$-gaps. Notice that a single $4$-gap neutralizes two $1$-gaps. But this contradicts the required positive angle sum obtained along the boundary, because the sum of angles of those leading and trailing positions, counted only once, would still be more negative that can be balanced out by summing all 1-gaps. Therefore, there must exist some 1-gap $c\in B_\overline{A’}$ where at most one flanking position is a $4$-gap and the other position is a $2$- or $3$-gap.

Next, we need to check that those positions are in fact usable and are not narrow tunnels in the original polyhex $A$. Notice that the outside position of a narrow tunnel cannot be a 1-gap or 2-gap of $A’$, because a narrow tunnel can only arise when there are two non-open sides with a single-edge open side between them. It also cannot be a 5-gap, as this would mean that the position itself is on the inside, but we consider only positions reachable on the outside. Hence, only $3$- or $4$-gap positions of $A’$ could have been narrow tunnels.

Hence, if one flanking position of some 1-gap is a 2-gap, then we are done immedately, because the 2-gap is also existing and valid in $A$. So now we assume that there are no flanking 2-gaps. As at most two 1-gaps can follow each other, the only way for the angle sum to increase are paired 1-gaps, because they are always followed by a 3-gap or 4-gap, so the angle sum could not be positive if only single 1-gaps were present. Hence, there must be 3-1-1-3, 3-1-1-4 and 4-1-1-3 gap sequences along the outside boundary. Now observe that if any of the flanking 3-gaps in these sequences is a narrow tunnel in $A$, it means that the polyhex tile neighboring the pair of 1-gaps is $1$-simple in $A$, violating the validity of the polyhex. We conclude that there must exist a 3-gap in $B_A$ that can be used to add a cell if there does not exist a usable $2$-gap in $B_A$. $\blacksquare$

Using this result, we can see that for estimating the probability that a tile can fit anywhere on the outside, it really suffices to check the 2-gap and 3-gap situation. This is an enormous restriction compared to checking all 12 connectivity possibilities and another advantage of biconnected polyhexes.

Even higher connectivity

We only looked at biconnected polyhexes, but one could consider even stronger connectivity constraints? A polyhex is $k$-connected if removing a tile keeps it $(k-1)$-connected. A natural question is what consequences $k$-connectedness for $k>2$ has on polyhexes.

Consider polyhexes that have only 1-gaps and 2-gaps on the outside. Such polyhexes do not have a negative exterior angle, so we call them convex. Notice that the this convexity coincides with convexity in the usual sense if you smooth out the zig-zagging edges along the outside boundary of the polyhex or consider only central points. Notice that all convex polyhexes have outside boundary profile of the form $(12^*)^6$. Convex polyhexes require the addition of at least 2 adjacent tiles to be 3-connected again, so in general this is not a useful restriction if we want to be able to uphold the property with every single tile movement.

Furthermore, not every cell of a connected polyhex can be 4- or 5-connected, because we have seen that there are always 1-gaps on the outside which imply that the neighboring polyhex cell has at most 3 neighbors. Finally, $k$-connectedness with $k\geq 6$ is impossible on a hexagonal grid except for the trivial case of $|A|\leq 2$.

One could also restrict the empty space by imposing stricter connectedness constraints, but if we restrict the empty space to be biconnected, then we prohibit placing tiles so that narrow tunnels are introduced and thereby immediately lose the whole concept of almost-holes and sliding components. From a game mechanics point of view, this means to lose an interesting mechanism while introducing a rather unintuitive restriction about the minimal size of gaps. So the slightly more asymmetric definition of validity offers more interesting possibilities, even though a symmetric constraint seems to be more elegant.