2D Procedural Map Generation
With Pascal & SwinGame
Jacob Milligan
Student ID - 100660682
Contents
1 Procedural Generation 2
1.1 Procedural over Manual . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Diamonds & Squares . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
2 Coding Terrain Generation 5
2.1 Setting Up . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2.2 Implementing Diamond-Square . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
2.3 Testing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
2.4 Generating Terrain and Features . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3 Drawing, Input, and Collision 22
3.1 Drawing the map . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
3.2 Handling Input & Collision . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
3.3 Finishing Up . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27
4 Extending & Investigating Deeper 32
Source Code & Repository 33
1
1 Procedural Generation
1.1 Procedural over Manual
Very broadly speaking, in game development there are two primary ways to generate content for a project. The
most common and controllable way is to produce each piece of content by hand. The consequences, in the case
of this article, would be the production of a large 2D tile map by a manual process.
For smaller content sizes this isn’t a problem; it’s a relatively straight-forward process to declare each tile as an
element of a statically-sized 2D array and just draw those tiles to the screen in a single pass alongside, perhaps,
the drawing of different sprites layered on top of each tile to represent NPC’s or the player. But what happens
as a map grows in size? As it increases from a 32 × 32 map to a 256 × 256 sized map, or even larger? Even if
the programmer had created a time-saving, high-level system for creating maps as text files to be read in by the
program, it can very quickly become time-consuming and tedious. Although this is a valid way of generating con-
tent, in fact the developers on CD Projekt Red’s The Witcher 3: Wild Hunt did just that (Klepek 2015), most
programmers don’t possess the resources or manpower of a AAA game studio and therefore often must create
a better solution. So what’s the appropriate solution?
Procedural Generation algorithms are the solution
Indie game title such as Minecraft, Dwarf Fortress, and the upcoming No Mans Sky all make use of procedural
content generation to build enormous, beautiful, but seemingly random and unique worlds. We say seemingly
random for two reasons:
1. Computers can only produce pseudo-random numbers as the only truly random processes are analog, phys-
ically occurring phenomena, such as the measurement of cosmic radiation or noise signals in hardware cir-
cuits (Güneysu 2010).
2. These procedural generation algorithms are designed so that, with the same starting point, it will produce
the same result.
What is the starting point for this process?
The answer to that question is wide and varied and many games, such as in indie title Dwarf Corp., begin by sim-
ulating tectonic plate activity (Klingensmith 2013), erosion, or river formation to carve out their terrain - in a
similar fashion to how terrain forms in the real world (Huggett 2007, pp. 46). However, this article will be tak-
ing a different route and begin by generating a realistic height map stored in a 2D array of elements that each
hold a generated elevation value which will be used to base the remaining generation procedures off. We will use
this initial information to procedurally generate a 512×512 sized 2D continent-like map that can be navigated
by a player character. Furthermore, we will make heavy use of the SwinGame API to handle all graphics-related
functionality and briefly touch on other interesting concepts such as basic collision detection and drawing algo-
rithms, all of which will be coded using the Pascal programming language.
1.2 Diamonds & Squares
To generate a heightmap, it would be possible to design an algorithm from scratch, however that would take a
long time, would need to be rigorously tested, and the result probably wouldn’t be very effective, so the core of
our program will be based off a very well-known and well-tested one named Random Midpoint Displacement
(Fournier, Fussell, and Carpenter 1982), also known as the Diamond-Square Algorithm. At its core, the pur-
pose of this algorithm is to generate pseudo-random noise in a desirable pattern, i.e. one that resembles a re-
alistic spread of terrain height values. Each point of noise is stored in a data structure, in our case a 2D array,
and holds a single value - a number representing its elevation. The resulting map will look something like this:
2
Example 1: A map generated using Diamond-Square
The basic concept behind Diamond-Square can be summed up like so:
Take an empty grid, which must be of size 2
n
+1 in order for the following steps to function correctly. Then
assign the corners a seed value, a number that all other calculations are based off. This will mean that with
the same seed, the same result should be produced. Then iterate the following two steps:
The Sqaure Step - Take the grids four corners, average their total, find their mid point and assign
that point the average plus a random value up to the maximum defined height of the map.
The Diamond Step - Given the previous step, we now have a diamond shape of four points surround-
ing a new mid point. Take the average of all points in the diamond and assign the new midpoint that
value plus a random amount up to the maximum defined height value.
Use a nextStep variable to determine which point in each diamond and square step to calculate.
Iterate until nextStep is less than zero.
This process can be best visualized using graphs, seen in the example pictured below.
3
Step 1. Begin with a blank 2D array which
represents a map. It can be viewed as a
graph with each node representing a single tile
Step 2. Take the four corner nodes of the map
and assign them a given seed value (in our
case -1500 to force a continent-like map)
which will inuence the rest of the map
Step 3. Take the mid point between all
four
nodes and assign it the average of the four
corner nodes plus another random
value. This gives us a square shape with
a middle point.
Step 4. Take the middle of each corner-to-
corner edge from the previous square step
(the pink nodes above) and assign them
the average of all surrounding nodes in a
diamond shape (in the above graph, the
red and green dotted lines represent half-
diamonds) plus a random value.
Step 5. The result of the previous step is
another square (the orange nodes above).
Therefore we now do the square step again.
Step 6. As before, the result of the previous
step is a diamond shape surrounding each of
the pink nodes. Therefore we complete the
diamond step one more time.
Step 7. We have our complete tile grid!
The Square step
The Diamond step
Example 2: Summary of the Diamond-Square algorithm
Using this algorithm provides the ability to generate a starting point. However, before beginning an
implementation, as with all software development, it would be wise to define the requirements for the final pro-
gram - the functions, procedures, data structures, and features that should be included:
4
First, we’ll need a Tile record to hold data related to each tile in the map such as collision value, its
associated bitmap, it’s terrain type, and elevation. We’ll also need a MapData record to contain our tile
grid, the players sprite and location data, and its total size.
We’ll need two primary terrain generation procedures - DiamondSquare() & GenerateTerrain().
DiamondSquare() will be responsible for creating a new heightmap for a given MapData() parame-
ter, whereas GenerateTerrain() will be responsible for deciding how each tile should be rendered based
off the heightmap, alongside generating trees on the new MapData’s tile grid.
Now that the terrain generation functions and data structures are defined, we’ll also need a CreateMap()
function to call both of the above procedures and to search for an appropriate place on the map to spawn
the player.
Finally, we’ll need both a HandleInput() procedure and a DrawMap() procedure to move the player
around while detecting collision tiles and to draw the tile grid to the screen respectively.
There will also be several functions and resources referenced later on that we won’t be building as they aren’t
directly related to procedural generation and are just utilities for allowing our map to render properly. This code
sits in the MapUtils.pas file and can be downloaded from github, as part of the source for the finished project,
alongside the bitmap resources we’ll be using (if you don’t have git installed you can just click the ’clone or down-
load’ link and download as a zip file). These extra files are important for loading bitmaps, updating the cam-
era position relative to the edge of the map, and drawing a map overview to the screen.
2 Coding Terrain Generation
2.1 Setting Up
The primary goal of this article is to implement Diamond-Square and must be done prior to any
other terrain generation. First, download and install the latest version of FPC (Free Pascal Compiler) and
a Pascal SwinGame template from the SwinGame Website (see each websites installation section for instructions
on how to do this). Once this is complete, copy your downloaded SwinGame template to wherever you normally
store your code, i.e. /Users/Jacob/Dev/Repos/. All of the programming will take place in the /src/ folder
and whenever the game needs to be built and run, type the command ./build.sh && ./run.sh (drop the
./ on Windows machines). Rename the GameMain.pas file to something a bit more descriptive, such as Pro-
ceduralGeneration.pas and open it up in your favourite text editor.
The first thing we need to do is to replace the code in the stock Main() procedure with the following:
procedure Main();
var
map: MapData;
begin
DiamondSquare(map, 100, 20);
PrintMapToConsole(map);
end;
Before we render anything to a graphics window, we should first implement our algorithm and ensure that it func-
tions correctly by printing it to the console, both procedures that will be called from Main(). We’ve also de-
clared a new MapData variable which we’ll be creating soon.
Next, create a new file in the /src/ directory called Terrain.pas, open it up and write a new Unit file skele-
ton:
5