Dan Kolbman About


Generative Maps


After seeing this post on Red Blob Games, I decided to give my own map generator a go.

Starting with some (N) random points

I’m going to construct a Voronoi diagram in a similiar way as done here1, minus the relaxation (I hope to get some more ‘chaotic’ terrain). I’m using the Voronoi implementation in Scipy2.

seed = 55555
np.random.seed(seed)
N = 5000
# x, y coordinate pairs
pts = np.random.rand(N,2)
vor = Voronoi(pts)
#voronoi_plot_2d(vor)
plt.show()

Determining Biomes and Coloring

To start filling in the Voronoi cells, I first define some different biome reigions using a sort of Whittaker classification, although I’ll use two dimensionless, normalized variables (I’ll call them height and humidity) in place of precipitation and temperature. I also map each biome onto its own hex color to use when coloring in the map.

To determine these two variables, I use two perlin noise maps. Here I show the two noise maps and how they combine to produce biomes.

I also turn it into closed landforms by applying a radial fourth order drop-off.

Adding Cities

Now that there’s a relatively nice looking topology, I’ll throw in some cities and provinces. I choose biome regions at random place cities according to a distribution that I’ve come up with (cities aren’t as likely to be on the top of a mountain as they are to be on a flat plain). Here’s that distribution as a probability as a function of the biome type:

class City:
    name = 'city'
    biomes = []
    roads = []
    
    def __init__(self, name, biomes):
        self.name = name
        self.biomes = biomes
        for b in biomes:
            b.owner = self
        self.connected = []
        
    def grow(self):
        for b in range(len(self.biomes)):
            for n in self.biomes[b].neighbors:
                if n.is_water() or n.outside:
                    continue
                if n.owner is None:
                    self.biomes.append(n)
                    n.owner = self
        
    def __repr__(self):
        return '< City {} >'.format(self.name)
    
def draw_cities(cities):
    c_xy = [c.biomes[0].center for c in cities.values()]
    plt.plot(*zip(*c_xy), 'o', ms=10, mew=2, mfc=None)

    for name, c in cities.items():
        plt.annotate(name, c.biomes[0].center, xytext=(0,10),
                     textcoords='offset points',
                    ha='center')
def search_city_BFS(v, w, mcount=500):
    Q = [ v ]
    prev = {}
    visited = [ v ]
    # Don't allow crazy stuff
    count = 0
    while Q and count < mcount:
        count += 1
        # Next node
        u = Q.pop(0)
        # If found end city in current path
        if u == w:
            return prev
        
        next_n = sorted(u.neighbors, key=lambda b: abs(b.height - u.height))

        for n in next_n:
            if not n in visited and not n.is_water():
                visited.append(n)
                prev[n] = u
                # Add a new path to the queue with next neighbor at end
                Q.append(n)
    
class Road:
    path = []
    
    def __init__(self, path):
        self.path = path
        
    def __repr__(self):
        return '< Road {} long >'.format(len(self.path))
def road_to(start, goal, biomes, mcount=1000):
    route = search_city_BFS(start, goal, mcount)
    if not route:
        return None
    path = [ route[goal]  ]
    while not path[-1] == start:
        path.append(route[path[-1]])

    path.insert(0,goal)
    return Road(path)
def draw_road(road):
    x = [ i.center[0] for i in road.path ]
    y = [ i.center[1] for i in road.path ]
    plt.plot(x,y, c=sns.xkcd_rgb['faded red'])
plt.figure(figsize=(7,7))

draw_biomes(biomes)
for i in range(len(cities)):
    for j in range(i):
        start = list(cities.values())[i].biomes[0]
        goal = list(cities.values())[j].biomes[0]
        r = road_to(start, goal, biomes, 600)
        if r:
            list(cities.values())[i].roads.append(r)
            list(cities.values())[j].roads.append(r)
            draw_road(r)
            
            
draw_cities(cities)

plt.gca().set_aspect(1)
plt.axis('off')
plt.xlim(0,1)
plt.ylim(0,1)
plt.show()

png

plt.figure(figsize=(7,7))



draw_biomes(biomes)
draw_provinces(cities)
draw_cities(cities)
plt.gca().set_aspect(1)
plt.axis('off')
plt.xlim(0,1)
plt.ylim(0,1)
plt.show()

png

  1. Polygon Generation from Voronoi Diagrams 

  2. scipy.spatial.Voronoi