Saturday 19 July 2014

Crucible XXV 19/07/2014

So sorry for the lack of an update yesterday. I was very close to finishing off my current task so I thought it would be worth the wait. I've 'finished' the Voronoi diagram generation! I can't speak much of it's efficiency, and there are still a couple of bugs that need ironing out, but I'll be sure to improve it in the future. I've included a few screenshots of it in game at a number of different map sizes. The smallest shown is a 30 star map that generates in 2-3 seconds (including the time Unity takes to start up- which is a similar time). Next is a 60 star map that takes around 6 seconds to generate. Finally I have included a 90 star map (the largest map) which takes a whopping 15 seconds to generate. However I can't say that the Voronoi generation is responsible much for the longer loading time since the 90 star system has always taken a fair while to generate, and I suspect it is more to do with the map constructor code (line intersections are expensive on that scale!).

 30 Star System. Placeholder graphics just to show off the regions

60 Star System. Region shape becomes more interesting and smaller.

90 Star System, many, many regions!

This week I'll be bugfixing and doing minor changes. I'm on holiday for two weeks afterwards with the family. And then back for the final 2 months before uni! Exciting times!

Friday 11 July 2014

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!