#delaunaytriangulation

[nulldividedbyzero]

Connecting the rooms

The most popular way I’ve found to link the rooms to each other is using a Delaunay Triangulation. 

After reading on what it does I got in a little trouble since maths isn’t an area I’m a lot comfortable with, luckily I found a neat site that doesn’t only explain it simply it has many examples in several languages, including c#.

So I got ready to work on that and after some time I did it! 

The red lines represent the connections between the rooms, but as you can see that could be a problem since I didn’t want every room connecting to it’s neighbors, making the dungeon  easy and taking away that “dungeony” feeling. The solution? Making a Minimum Spawning Tree! To put it simply, basically it finds the links to connect every room in an optimal way, making a simple path that still can create some interesting dungeons, but to guarantee that it gets a little more complex we add a random part of the remaining links so there isn’t always only the optimal path to get to every room.

I found a site with the code that worked nicely to do what I wanted and implemented it in my game-to-be. 

The green lines represent the path that’s going to be placed in the dungeon creating halls from them, and that’s what I was focusing now, making halls that looked nice and were efficient to find their path between rooms.

[vizual-statistix]

These are Voronoi maps of the contiguous USA, using the 48 capital cities as the set of input points. The two maps are identical with one exception – in the lower map, I added the original state borders to provide geographic context.

Voronoi maps/diagrams, for those unfamiliar, represent the portioning of a plane into polygons based on a set of points. This is done such that each polygon contains exactly one point, and the area within the polygon is necessarily closer to the point it contains than it is to any other point.  In other words, each point translates into a polygon of all the space closer to that point than any other point. The polygons are referred to as Voronoi cells (or sometimes Thiessen polygons or Dirichlet cells). For those who have encountered Delaunay triangulation, a Voronoi diagram is simply the dual graph of a Delaunay triangulation.

So for the purposes of this map, the state you live in would be determined by which capital city is closest to your home. If you originally lived in Manhattan, you would be a New Jerseyan because you are closer to Trenton than Albany (and Hartford). If you were a proud Chicagoan, you would reside in Wisconsin because you are closer to Madison than Springfield.

As can be seen on the map, some states would barely change shape (e.g., Maine), but most would be unrecognizable. I calculated the revised areas of the states to see which were most affected. Those losing the most area percentagewise are Massachusetts (37% of original size), California (42%), and Kansas (53%). Benefactors would include Delaware (342% of original size), Rhode Island (319%), and West Virginia (202%). Mississippi and New Hampshire would both be with 1.5% of their original sizes. On the basis of area, Utah and New Mexico are the biggest gainers, each adding over 60,000 square miles. Texas ends up as the biggest loser, shedding ~98,000 square miles.