A couple of things make Annexation stand out from other filler-like games (see this for details). One of them is the awesome AI that I'll write about in the future. The other is the game board itself. In annexation you get to choose between a number of board types.
In the original game, the board cells were hexagons. In Annexation you can choose to use hexagons, squares, rhombs, florets or random:
Technically all these tilings can be constructed using Voronoi diagrams.
Given a set of points on a plane (called sites). For each site we construct a tile, such that all the points on a tile are closer to that site then to any other site on the plane.
This means that given a correct algorithm for creating sites, all sorts of tilings can be created.
The algorithm needs to create additional sites along the edge of the board so that border cells do not extend into infinity.
In Annexation players take turn choosing a color and taking over any neighboring cells of the chosen color. This means that we need to turn the Voronoi diagram into a graph, where neighboring tiles are connected. As luck would have it, each Voronoi diagram has a corresponding (dual) graph called Delaunay triangulation. Overloaded over the Voronoi graph it looks like this.
This gives us the connections between individual voronoi tiles. It is hard for a player to tell if some tiles are touching, especially if they share a very small border. So next we eliminate connections between tiles that have a very short common border.
The last step in board creation is an optimization one. In Annexation, by choosing a color you annex all the neighboring cells of the chosen color. But this also includes the neighboring cells of those cells. Example:
If player (the white cell), chooses dark green as his color, he will not only annex the neighboring green cell, but the one next to it as well!
This means that game engine calculating the board position after a move needs to recursively check cells and their neighbors. This is not very efficient. We can take advantage of the fact that cell colors don't change throughout the game (well apart from being annexed by a player). We can search for cells that share border and color and merge them into larger cells. In the game engine, we can consider those as cells that are simply worth more. So our diagram of connections now reflects that.
This also means that the difference between different tilings is not purely visual. Some tilings will create boards where cells have few neighbors. Here choosing colors that will extend your influence over the board is important. So your strategy might change depending on the tiling. This also means that we need to create an ai, that will be able to handle all these different board types. But that's the subject of the next post.