Seven years ago I worked on an terrain generator for a game called Realm of the Mad God. We had started out using Perlin Noise for height maps but found that most of the maps we generated weren't a good fit for the game. I spent the summer trying out ideas for making the maps, and discovered that Voronoi Diagrams could form a good “skeleton” for making maps. The combination of Voronoi polygons and Delaunay triangles gave me places for quests, towns, rivers, and roads. I used Perlin Noise for the coastlines instead of for the height map. The resulting maps were unrealistic and inflexible but they were just what we needed for our game.