Procedural Map Creation for Crusader Kings II, Part 1: Voronoi Polygons

One of the greatest things about being alive in the 21st century is that other people provide source code on the internet for free. One such person calls himself BenDi, and he saved me the trouble of implementing an algorithm to compute Voronoi diagrams myself. Furthermore, one Maxim Barsuk¬†provided example client code for BenDi’s project, which I was able to modify to suit my needs.¬†

Specify a set of points, call them ‘seeds,’ and distribute them upon a plane. Given those points, we can make a Voronoi diagram, showing the plane divided into polygons in such a fashion that each polygon contains those points which are closer to a given seed than to any other. Each polygon will be a county for our random CKII map.

A Voronoi diagram. Seeds are the red circles.

A Voronoi diagram. Seeds are the red circles.

I still have some work to do to color the polygons as the CKII engine demands, but this is a good start.