Sunday, December 18, 2016

Procedurally Generated Island Overworld Map

I've had a mild interest in procedurally generated worlds for video games for a while now. I recently found this article by Amit Patel from Red Blob Games on building procedurally-generated game worlds using randomized voronoi diagrams and a graph-based approach to defining spatial attributes. I had played a bit previously using Perlin noise to define world elevations, and then basing spatial attributes on elevation contours, which is cool but always ends up with pretty random, unrealistic looking landscapes. This graph-based approach seemed to provide a bit more flexibility in how the landscape looked and how to add additional objects into the world (like rivers, roads etc) in a way that seemed to provide a bit more control. I also found this 8x8 pixel micro tileset, which sparked my interest to try and build up a random island overworld generator, based on the tiles here.

I wanted to generate landscapes that could form the overworld of an adventure style game. Basically something where the player has a constrained world to explore that contains a variety of different biomes (provided by the tileset), villages, roads and locations representing the entrance to caves or dungeons that would form the basis of the objective of the game (enter caves, defeat monsters, recover treasure etc).

Working in python, I started by defining random points in a 2D space using stratified random sampling, to make sure points were not too 'clumpy'. Instead of using voronoi diagrams to generate polygons, I went straight to using a Delaunay triangulation to define the local connectivity of points (using this nice pure-python implementation). The triangulations would later be used to rasterise landscape tiles and define paths and distances between locations. Following from Amit's approach, I created a series of points regularly spaced around the border of the map and defined them as water. I then selected a fixed number of the other random points and defined them as land. I then performed flood fills along the triangulated network to define all remaining points as land or water based on whichever predefined node is closest. I then incremented through triangles, and those that contained a majority of land nodes were rasterised into land tiles, where the remaining tiles were labelled as water/ocean.

This gave me a bulk of land surrounded by water, usually as one island but some times split into two. Each node on land is then labelled by it's distance to the closest water/ocean node, which helps define what type of tile is used (light/dark grass, light/dark dirt) and the probability it will be occupied by a trees or mountains. I then added a few lakes by defining random starting locations on land and seeded some water patches using region growing. I added some villages: one that appears on a random mountain tile, one in a forest (distance layer with probability of tree being 1.0) and two on the coast (distance to water less than one edge on the triangulated network). I then finally drew roads between the mountain village and the forest village and biggest coastal village using A* paths along the triangulated network.

The micro tileset has tiles for a temperate landscape and for mid-winter, as well as one devoid of trees (like a desert or devastated terrain). Originally I had wanted to integrate all of them into one map with different biomes, but they didn't really look that good together. So in the end I decided to make the rendering of the map seasonal, so for every map there is one rendering for summer and one for winter. For the winter rendering I also add in a few icebergs in the surrounding waters.

I'm not sure exactly what I'm going to do with this yet, but I'll probably end up expanding upon it to make an adventure game. I was thinking about also making a random dungeon generator that utilises the dungeon portion of the micro tileset.

For now, source code available here: mit-mit-randomprojectlab/RandomOverworldGenerator

No comments:

Post a Comment