A fantasy map generator based on Martin O'Leary's "Generating fantasy map" notes

Overview

Fantasy Map Generator

This program is an implementation of a fantasy map generator written in C++ based on the methods described in Martin O'Leary's "Generating fantasy map" notes (https://mewo2.com/notes/terrain/).

This project uses jsoncons for parsing JSON data, Argtable3 for parsing command line arguments, Python and PyCairo for drawing, and data from GeoNames for city name data.

The project page and generation notes are also available here: http://rlguy.com/map_generation

alt tag

alt tag

alt tag

alt tag

alt tag

alt tag

alt tag

Dependencies

There are three dependencies that are required to build this program:

  1. Python 2.7+
  2. PyCairo graphics library (https://cairographics.org/pycairo/)
  3. A compiler that supports C++11

Installing PyCairo on Windows

Prebuilt Windows binaries for PyCairo and its dependencies can be obtained by following this guide on installing igraph, which uses PyCairo for drawing. The relevant section is titled "Graph plotting in igraph on Windows".

To check if PyCairo was installed correctly, try importing the module within the Python interpretor:

import cairo

Installation

This program uses the CMake utility to generate the appropriate solution, project, or Makefiles for your system. The following commands can be executed in the root directory of the project to generate a build system for your machine:

mkdir build && cd build
cmake ..

The first line creates a new directory named build and changes the working directory to the newly created build directory. The second line runs the CMake utility and passes it the parent directory which contains the CMakeLists.txt file.

The type of build system generated by CMake can be specified with the -G [generator] parameter. For example:

cmake .. -G "MinGW Makefiles"

will generate Makefiles for the MinGW compiler which can then be built using the GNU Make utility with the command make. A list of CMake generators can be found here.

Once successfully built, the program will be located in the build/ directory.

Running the Map Generator

The map generator is a command line tool and can be invoked with the command:

./map_generator [OPTIONS]

Leaving the options blank will generate a high quality map with resolution 1920x1080 to the file output.png.

A set of options can be displayed with the --help flag:

>>> ./map_generator --help

Usage: map_generation [-hv] [-s <uint>] [--timeseed] [-r <float>] [-o filename] 
[<file>] [-e <float>] [--erosion-steps=<int>] [-c <int>] [-t <int>] 
[--size=<widthpx:heightpx>] [--draw-scale=<float>] [--no-slopes] [--no-rivers] 
[--no-contour] [--no-borders] [--no-cities] [--no-towns] [--no-labels] 
[--no-arealabels] [--drawing-supported]

Options:

 -h, --help                     display this help and exit
 -s, --seed=<uint>              set random generator seed
 --timeseed                     set seed from system time
 -r, --resolution=<float>       level of map detail
 -o, --output=filename          output file
 <file>                         output file
 -e, --erosion-amount=<float>   erosion amount
 --erosion-steps=<int>          number of erosion iterations
 -c, --cities=<int>             number of generated cities
 -t, --towns=<int>              number of generated towns
 --size=<widthpx:heightpx>      set output image size
 --draw-scale=<float>           set scale of drawn lines/points
 --no-slopes                    disable slope drawing
 --no-rivers                    disable river drawing
 --no-contour                   disable contour drawing
 --no-borders                   disable border drawing
 --no-cities                    disable city drawing
 --no-towns                     disable town drawing
 --no-labels                    disable label drawing
 --no-arealabels                disable area label drawing
 --drawing-supported            display whether drawing is supported and exit
 -v, --verbose                  output additional information to stdout

Example:

The following command will output program information to the screen (-v), will set the random generator seed to your current system time (--timeseed), will set the resolution to 0.08 (-r 0.08), and write the generated map to the file fantasy_map.png (-o fantasy_map.png).

./map_generation.exe -v --timeseed -r 0.08 -o fantasy_map.png

Map Generation Process

The map generation process involves the generation of irregular grids, the generation of terrain, the generation of city/town locations and their borders, and the generation of label placements.

Generating Irregular Grids

A Poisson disc sampler generates a set of random points with the property that no two points are within some set radius of eachother. alt tag

The set of points are triangulated in a Delaunay triangulation. The triangulation is stored in a doubly connected edge list (DCEL) data structure. alt tag

The dual of the Delaunay triangulation is computed to produce a Voronoi diagram, which is also stored as a DCEL. alt tag

Each vertex in the Delaunay triangulation becomes a face in the Voronoi diagram, and each triangle in the Delaunay triangulation becomes a vertex in the Voronoi diagram. A triangle is transformed into a vertex by fitting a circle to the three triangle vertices and setting the circle's center as the position of a Voronoi vertex. The following image displays the relationship between a Delaunay triangulation and a Voronoi diagram.

alt tag

The vertices of the Voronoi diagram will be used as the nodes in an irregular grid. Note that each node has exactly three neighbours.

Generating Terrain

An initial height map is generated using a set of primitives:

  • addHill - Create a rounded hill where height falls off smoothly
  • addCone - Create a cone where height falls off linearly
  • addSlope - Create a slope gradient that runs parallel to a line

and a set of operations:

  • normalize - Normalize the height map values to [0,1]
  • round - Round height map features by normalizing and taking the square root of the height values
  • relax - Replace height values with the average of their neighbours
  • setSeaLevel - Translate the height map so that the new sea level is at zero

alt tag

Contour lines are generated from the Voronoi edges. If a contour line is generated for some elevation h, a Voronoi edge will be included in the countour if one of its adjacent faces has a height less than h while the other has a height greater than or equal to h.

alt tag

A flow map is generated by tracing the route that water would flow over the map. At each point on the grid, a path must be traced downhill to the edge of the map. This means that there can be no sinks or depressions within the height map. Depressions are filled by using the Planchon-Darboux Algorithm to ensure that a path to the edge of the map exists for all grid points.

alt tag

The height map is then eroded by using the flow map data and terrain slope data.

alt tag

Paths representing rivers are generated at points where the amount of flux (river current) is above some threshold. The path of the river follows the flow map until it reaches a coastline or the edge of the map.

alt tag

The height map is shaded based upon the horizontal component of the slope. Short strokes are drawn at faces where the slope is above some threshold. Strokes pointing upwards from left to right are drawn if the height map is sloping upward from left to right, and strokes pointing downward from left to right are drawn if the height map is sloping downward from left to right.

alt tag

Generating Cities and Borders

City score values are computed to determine the location of a city and have a bonus at locations where there is a high flux value and a penalty at locations that are too close to other cities or too close to the edge of the map.

alt tag

Cities are placed at locations where the city score value is at a maximum.

alt tag

For each city, the movement cost is calculated at each tile (Voronoi face). Movement costs are based on horizontal and vertical distance, amount of flux (crossing rivers), and transitioning from land to sea (or sea to land).

alt tag

The tiles are then divided amongst the cities depending on who has the lowest movement cost for the tile.

alt tag

This method tends to create jagged borders and disjointed territories. The territories are cleaned up by smoothing the edges and by adding a rule that a city territory must contain the city and be a contiguous region.

alt tag

Borders are then generated around the city territories.

alt tag

Towns can be added to the map by using the same process that is used to generate city locations. Towns are contained within the city territories and are not involved in territory/border generation.

Generating Label Positions

The label placement system is based on methods described in this paper: A General Cartographic Labeling Algorithm.

There are two types of labels that will need to be generated: marker labels that label city and town markers, and area labels that label the city territories.

The labeling process begins by generating candidate label positions for the marker and area labels and calculating a base score for each label.

Marker label candidates are generated around a city or town marker. The calculated scores depend on orientation about the marker, how many river, border, and contour lines the label overlaps, whether the label overlaps another marker, and whether the marker is contained within the map.

alt tag

Area label candidates are generated within territory boundaries. The calculated scores are similar to the marker label scores except that the orientation score is based upon how much of the label is contained within the territory that it names.

alt tag

The number of area label candidates is then narrowed down by selecting only the candidates with the best scores.

alt tag

After all candidates for the marker and area labels have been generated, the final label candidates are selected by running the following algorithm:

1. Initialize the label configuration by selecting a candidate randomly for each label. 
2. Initialize the "temperature" T to an initial high value.
3. Repeat until the rate of improvement falls below some threshold:
  a) Decrease T according to an annealing schedule.
  b) Chose a label randomly and randomly select a new candidate.
  c) Compute ΔE, the change in label configuration score caused by selecting a new label candidate.
  d) If the new labeling is worse, undo the candidate change with a probability P = 1.0 - exp(ΔE/T).

The score of a label configuration is calculated by averaging the base scores of the selected candidates and adding an additional penalty for each set of overlapping candidates.

The initial high value of the temperature T is set to 1/log(3). This value is chosen so that P evaluates to 2/3 when ΔE is 1.

The loop in step three is terminated when no successful label repositionings are made after 20*n consecutive attempts, where n is the number of labels, or after some maximum number of temperature changes.

The temperature decreases by 10% after 20*n label repositioning attemps are made, or if 5*n successful repositioning attemps are made at the same temperature value.

The following set of images show the initial labeling, the labeling halfway through the algorithm, and the final labeling:

alt tag alt tag alt tag

References

M. O'Leary, "Generating fantasy maps", Mewo2.com, 2016. [Online]. Available: https://mewo2.com/notes/terrain/. [Accessed: 18- Oct- 2016].

R. Bridson, Fast Poisson Disk Sampling in Arbitrary Dimensions, ACM SIGGRAPH 2007 Sketches Program, 2007.

M. Berg, Computational geometry. Berlin: Springer, 2000.

O. Planchon and F. Darboux, "A fast, simple and versatile algorithm to fill the depressions of digital elevation models", CATENA, vol. 46, no. 2-3, pp. 159-176, 2002.

S. Edmondson, J. Christensen, J. Marks, and S. Shieber, "A General Cartographic Labeling Algorithm", Mitsubishi Electric Research Laboratories, 1996.

J. Christensen, J. Marks and S. Shieber, "An empirical study of algorithms for point-feature label placement", TOG, vol. 14, no. 3, pp. 203-232, 1995.

Comments
  • ‘PyString_FromString’ was not declared in this scope

    ‘PyString_FromString’ was not declared in this scope

    I was trying to install your package, but when running make I encountered the following.

    /my/path/FantasyMapGenerator/src/render.cpp: In function ‘void gen::render::drawMap(std::vector<char>&, std::__cxx11::string)’:
    /my/path/FantasyMapGenerator/src/render.cpp:17:75: error: ‘PyString_FromString’ was not declared in this scope
         PyObject *pFunctionName = PyString_FromString(drawFunctionName.c_str());
                                                                               ^
    CMakeFiles/objects.dir/build.make:254: recipe for target 'CMakeFiles/objects.dir/src/render.cpp.o' failed
    make[2]: *** [CMakeFiles/objects.dir/src/render.cpp.o] Error 1
    CMakeFiles/Makefile2:104: recipe for target 'CMakeFiles/objects.dir/all' failed
    make[1]: *** [CMakeFiles/objects.dir/all] Error 2
    Makefile:83: recipe for target 'all' failed
    make: *** [all] Error 2
    

    Any thoughts on resolving?

    opened by ahopkins 3
  • sys.path is not set to include the cwd

    sys.path is not set to include the cwd

    Thanks for fixing the string conversion bug. Now i bumped into another one that is probably 3.x specific. EDIT: Nope, that also happens on 2.7!

    I could build the binary now, but it couldn't import the render module:

    ModuleNotFoundError: No module named 'render'

    So, i searched a bit and i think it is related to the CWD not being in the current sys.path: Stackoverflow about sys.path with pyimport

    I tried adding it but failed because the _get_PyString_fromString function returns a bytes. So i did it via

    PyRun_SimpleString("sys.path.append('/home/riot/src/FantasyMapGenerator/build')");

    and it was able to import ther render module.

    Afterwards i ran into two problems:

    • 3.5 - "Error: function not in module dict"
    • 3.6 - couldn't import cairo, probably a cairo bug: ModuleNotFoundError: No module named 'cairo._cairo'

    I'd rather not open tickets for those, as i don't know whats going on with 3.5 and i think the 3.6-one is not related to this project. Help would be appreciated ;)

    opened by ri0t 2
  • can't import Cairo

    can't import Cairo

    (unity) [email protected]:~/unity/FantasyMapGenerator/build$ ./map_generation
    Error: module import
    Traceback (most recent call last):
      File "/Users/fred/bin/nimble/unity/FantasyMapGenerator/build/render/rendermap.py", line 2, in <module>
        import cairo
    
    Python 3.8.5
    (unity) [email protected]:~/unity/FantasyMapGenerator/build$ pip freeze | grep cairo
    cairocffi==1.3.0
    pycairo==1.21.0
    
    opened by fredzannarbor 0
  • Make a

    Make a "release" build

    I know this is an old repo, but in case someone still looks at it... Is it possible for someone to make a build and put it in the project "releases" That way people dont have to know how to get it all set up and running to build it themselves (i always get headaches when i try) and can just download the build.

    opened by GRhin 0
  • Export heightmap

    Export heightmap

    How do you achieve the shaded heightmap effect in the final image? (gallery04_large.jpg) I would love an --export-heightmap option, hoping to generate a 3d terrain with map.

    opened by haywirephoenix 0
  • Added initial support for output to SVG image format

    Added initial support for output to SVG image format

    Try it with commands like ./map_generation -v --with-svg or ./map_generation -v --with-svg --svg-colors It should produce both output.png and output.svg files, which you can then examine using your SVG editor of choice.

    opened by miilic 2
  • SVG output support

    SVG output support

    It would be rather convenient to have the ability to output in SVG format, since SVG files are much more friendly for editing and scaling. I tried adding that to Python rendering script (using svgwrite library), but it became painfully slow once I added the slope lines to output. In the end I hacked something together in C++, adding the MapGenerator::outputSvgData and a couple of small helper functions to MapGenerator class. SVG generation is pretty straight-forward, and it comes with an unexpected benefit of not having to calculate and pass label text extents for background covering, since SVG filtering can be employed to do that automagically. I used to a simple semi-opaque white to cover label backgrounds, but the specifics are easily editable. Patch and a couple of output SVG files (B&W vs color) are attached. I verified those SVG files by opening and editing them in Inkscape, in case your SVG viewer of choice is giving you trouble. Thanks for an awesome application and a great educational write-up on how it all works together! svg_output.zip

    opened by miilic 1
Owner
Ryan Guy
Developer of the FLIP Fluids addon for Blender
Ryan Guy
Procedural world generator written in C++. Uses SFML for map rendering.

World Generator Archived as the code is a big mess and it'd be easier to start from scratch than to clean up this code. A procedural world generator i

moneyl 32 Nov 22, 2022
A lightweight C++14 parsing library for tmx map files created with the Tiled map editor

tmxlite Description A lightweight C++14 parsing library for tmx map files created with the Tiled map editor. Requires no external linking, all depende

Matt Styles 323 Nov 26, 2022
An in-progress matching decompilation of Final Fantasy VII For the PSX.

FFVII An in-progress decompilation of the original US release of Final Fantasy VII on the PSX. Building (Linux) Install build dependencies The build p

null 16 Oct 4, 2022
Polybox - Late ninties, PS1 inspired fantasy console

Polybox Polybox is an in-development PS1 era fantasy console, a bit like Pico-8, but with simple 3D as well as 2D. It's still rather primitive and ear

David Colson 313 Nov 16, 2022
some notes on Xlib programming

XNOTES(1) X Notes NOTESO(1) NAME xnotes - some notes on Xlib programming DESCRIPTION

phillbush 23 Nov 26, 2022
Some hypervisor research notes. There is also a useful exploit template that you can use to verify / falsify any assumptions you may make while auditing code, and for exploit development.

Introduction Over the past few weeks, I've been doing some hypervisor research here and there, with most of my focus being on PCI device emulation cod

Faith 130 Nov 18, 2022
Notes and codes for Linux Kernel (SJTU-CS353)

Linux-Kernel-notes Notes and codes for Linux Kernel (SJTU-CS353) Lab 01: Module Programming 02: Process Management 03: Memory Management Notes Lec 1.

Zi-Han Liu 22 Oct 14, 2022
Contribute your handwritten PDF notes and help other students ✌ #DecodersCommunity 🖤

Contribute your handwritten PDF notes and help other students ✌ #DecodersCommunity ??

Decoders Community 37 Nov 22, 2022
learn skynet notes

skynet-notes 服务别名API local skynet = require "skynet" require "skynet.manager" -- 给当前服务取一个别名,可以是全局别名,也可以是本地别名 skynet.register(aliasname) -- 给指定service

null 3 Jul 5, 2022
CSAPP Notes

CSAPP-Notes 本群残酷 谨慎进群 ❗️ ❗ ❗️ 规则 【CSAPP阅读计划-0期】 欢迎对作业任务和群规提交建议; 若违反以下规则,请发金额为群人数2倍的红包,分群人数/2向下取整个包,否则请退群; 群友每天至少阅读5页 CSAPP ,并写100字读书笔记,上传至作业库当天作业目录; C

ArkTicketTech 40 Nov 20, 2022
Notes on optimizing the linux kernel function csum_partial

Intro Optimizing software for performance is fun. Loads of fun. And sometimes incredibly frustrating. It's also something to do on a long intercontine

Arjan van de Ven 5 Dec 2, 2021
This Repo would take notes for some OCW courses which I consider it is excellent.

Excellent OCW This Repo would take notes for some OCW courses which I consider it is excellent. Course Code HomePage Assignment&Note [Done] MIT 6.S096

PeterWrght 3 Apr 24, 2022
Northstar-dedicated - Docker container for the Northstar dedicated server. Also includes general notes on running the dedi on Linux. WIP.

northstar-dedicated Docker image for the Northstar dedicated server. Not ready yet (it'll probably be another day or two). Versioning Tentative. Stabl

null 82 Nov 27, 2022
Code and Notes for DSA practice before placement.

Code and Notes for DSA practice before placement

Kunal Tulsidasani 2 Jan 26, 2022
Write snippets of C code in your txt files for notes and skip the hassle of compiling and running

Write snippets of C code in your txt files for notes and skip the hassle of compiling and running. Greatly helps organization and note-taking to make sure you do not miss anything.

Seamus Walden 4 Jun 13, 2022
OpenScan is an open-source document scanner app that enables users to scan hard copies of documents or notes and convert it into a PDF file. No ads. No data collection. We respect your privacy.

OpenScan An open source app that enables users to scan hardcopies of documents or notes and convert it to a PDF file. No ads. No data collection. We r

Ethereal Developers Inc 1.2k Dec 1, 2022
Simple WPA-PSK default password candidates generator for mobile broadband WIFI routers, based on IMEI

IMEIgen Simple WPA-PSK default password candidates generator for mobile broadband WIFI routers, based on IMEI. Background In their conquest for more u

Alex Stanev 13 Nov 29, 2022
The v.st Colour Mod - a colour vector generator based on the original v.st

VSTCM - the v.st Colour Mod - a colour vector graphics generator The vstcm is a PCB which can generate colour vector graphics which can then be displa

Robin Champion 29 Nov 28, 2022
Single-header, ranges-compatible generator type built on C++20 coroutines

generator Single-header, ranges-compatible generator type built with C++20 coroutines. A generator allows implementing sequence producers which are te

Sy Brand 36 Nov 16, 2022