Crucible XXIV 11/07/2014

Back from my holiday! Feeling thoroughly relaxed and ready for work. This week I've just been working on the Voronoi diagram for the empire map and all the issues associated with it. Happily it has also resulted in some good optimisation of the map generator and geometry related methods. On the other hand it has turned out to be quite complicated. There are 3 main steps to the process- Triangulation of the map of star systems, turning the Triangulation into a Delaunay Triangulation (writing a straight up Delaunay Triangulation algorithm is HARD), and then turning the Delaunay Triangulation into a Voronoi Diagram. The last two steps are easy, but the initial triangulation is proving to be rather complicated (but I reckon I'm close to success). Anyway I've provided a quick overview of how this works;

Step 1: Create a Delaunay Triangulation of the points. In this case I have just provided the triangulation of the stars near Nephthys.

Step 2: Create Circumcircles for each triangle. These are circles that pass through all three points of a triangle.

Step 3: Create a polygon by linking up all the centres of the Circumcircles. This creates the Voronoi cell, with the system as the central points. All locations within the cell are closed to Nephthys than any other system.

Step 4: Roughly how the final cell would look. In-game this will be seen by zooming the map out. It will allow the player to see all the territory they own, and the territory controlled by each star system. All the cells in a Voronoi diagram link up like a jigsaw, so the map will have no holes in it (unless I want it to!).

As I said I am having trouble with the initial triangulation, but as soon as I crack that problem I can put up some real screenshots and move onto some other aspect of the game (probably go back to invasions and finish that up). See you next week!