As promised, here’s that same image from the previous post (or very similar to it; fixed one or two minor bugs), converted into a Voronoi diagram.
Immediately, you can see that these sorts of shapes would work quite well for MMORPG regions; they’re irregular and somewhat chaotic, but still somehow look as though they’ve been carefully arranged. I love that these don’t look at all ‘boxy’, like the old region borders did; some of these regions have eight or more sides!
[warning: tech follows]
A Voronoi diagram is constructed by seeding the map with a certain number of “sites” (about 80 of them, in this image), and then figuring out for each point on the map, which “site” that point of the map is closest to. The shapes you see here are the regions which are closest to each randomly placed “site”. The sites in the Voronoi diagram aren’t being drawn here, but each of the points of the triangles in the Delaunay triangulation image from yesterday is a “Site” in today’s image. For example, one “Site” is near my cursor in this screenshot, and anything inside the border around it is closer that that one Site than to any other Site.
As it happens, the “Sites” in the Voronoi diagram are the same as the vertices in the Delaunay triangulation. Remember how yesterday I mentioned that rule about “in a correct Delaunay triangulation, if you drew a circle which touched all three corners of any triangle, there would be no other Delaunay triangle vertices inside that circle”? Well, it just so happens that if you made those circles for every triangle which used a particular vertex, and then found the center point of each of those circles, and then drew lines connecting those circle center points, you’d end up with a shape like one of the ones in today’s screenshot. Follow these instructions for every vertex in the Delaunay triangulation, and you’d have your Voronoi diagram, just like the one here. It’s math magic that doing this operation with circle centerpoints in the Delaunay triangulation happens to also define the regions which are nearer to one site than to any other site.
And I’ve explained it horribly; apologies! It makes my head spin, too, when I think about these algorithms, which is one of the reasons why it’s taken me so long to complete.
[end tech]
Anyhow. I haven’t connected these boundaries to the real game regions, yet; right now, this is just drawing an outline at about the right scale. Actually hooking it up will be a task for tomorrow. But compared to the maths that were required to generate the outline, that task should be trivial.
