I was trying to make a simple random world generator for a geopolitical game yet to be done. I needed continent divided into territories and sea territories between them. I didn’t know at that point that I would solve a known mathematical problem.
The generator himself is divided into small elements. First not-so-random points are generated, spread evenly on the plane. After that, points are linked two by two with no overlapping. And then the real deal starts with polygon search in the produced graph.
The point generator
Not much to see here technically. To assure spreading, I implemented a minimum and a maximum distance between points. A new point needs to be farther than the minimum distance from every other point, and need to be closer than the maximum distance from the nearest point. For increased realism, the points are limited to a disk. Once there is more than 1000 misses (a new random point doesn’t fit in the rules) in a row, the point generation is complete.
The line generator
Since we had to calculate the distance between each new point and every other point, we do know the nearest points in the graph. That’s where we are going to draw lines, following a rule to limit the number of lines and allowing complex shapes : we only draw 2 lines from every point, even if the line has already been drawn. If the new line is overlapping another, we discard it and we draw a new one. We go on until we run out of points. At this point we have a nice little undirected graph with vertices and edges.
The polygon finder
For a human eye, finding all non-overlapping polygons in a graph is incredibly easy. But for a blind computer, it’s a little bit more complicated. But with a few simple rules, we can achieve what we want.
First of all, when we go through the graph, we always turn right. That way we always try to close the polygon we are in.
Then, when we found a cycle (e.g. during the course of the graph we fall back to a previous know vertice) we register it as a polygon of the graph. We now need a mean to know that we already found this polygon. We could check for polygon existence each time we find another one, but it would be terribly slow.
Instead, we rely on the fact that an edge of the graph can only belong to two contiguous polygons, and since we always go in circles the same direction, one edge can be traveled two ways, one for the polygon on one side, another for the contiguous polygon on the other side. Thus when we found a polygon, we forbid the algorithm to go through the edges in this direction again. But it still can (and will) go through them the other way, to find the contiguous polygons.
A problem remains : the outer edges of the graph don’t have contiguous polygons, and the algorithm may enter the outer edge circle looking for turning right, but since there would be no right, it will completely circle the graph counter-clockwise and believe that it is a polygon. It’s the only time where a found polygon can overlap the others. ((Of course, if the graph was concave, it would not work as easily as the center of the graph could be part of the outer polygon))
To circumvent this problem, we simply check that the point at the center of the graph is not included in the area of each found polygon. If it’s one of the point of the polygon, that’s not a problem, but if it is inside the area, that means that we found an overlapping polygon and discard it.
For each point of the graph, we try to find the contiguous polygons if they have not been already found. After all points have been tried, the polygon search is complete. We have a list of every non-overlapping polygon in the graph.
You can try it yourself at Worldgen v1 at Reactoweb Labs.
Feel free to play with the settings and post your best worlds !