2 min read

Runtime Procedural Map

Expanding the content created for Homeworld Mobile and using the star systems location used in the generation of background elements I also worked on creating a runtime procedurally generated galaxy map. This map represented the player’s clan’s territorial conquests.

Technical Bits

To keep things running smoothly, the map’s geometry was built as a single piece, cutting down on excessive draw calls. All the necessary data was baked right into the mesh, which fed into a shader that handled each faction colors and banners.

For the map generation the most important input was just point coordinates, with this in mind it was decided that the fastest way to create geometry was to use a Delaunay triangulation library ¹. This in turn imposed a look in the map that can be hard to shape from the perspective of an artist. For this purpose I created additional editor tools to manipulate the points and shape the look.

As the players claimed territories during the span of days, some territories in the map could become fractured and end up having concave shapes. To apply a clan’s banner in these shapes was an issue since finding the center of a concave shape fast is not a trivial task². To solve this problem I implemented an algorithm to find the center of any arbitrary polygon³

The map data structures were made up of only integers pointing to three different arrays an their indices (points, edges, triangles). Internally the delaunay graph (in this implementation) uses the half edges data structure⁴. This structure allows us to walk the geometry and to find relations between the two graphs easily. (delaunay and voronoi) and build a set of rules to solve the construction of the map geometry.

Footnotes