Around The World, Part 25: Placing ports
In the previous post, I promised to start placing some ports in our procedurally generated world. That turned out to be a bit more work than I expected.
First off, what are our requirements?
- Ports must be on a coast.
- Two ports must not be too close to each other.
- Ports must be distributed around the world, according to some distribution that I can configure.
- Ports must be reachable by sea (do not put them on the shore of a lake).
As with terrain generation, my approach has two “levels”: the global and the local. The code decides the location of all ports in the world on the global map first, so that we can later create quests that involve ports that are very far away.
(By the way, right now I’m talking only about ports, but besides harbour towns there could also be other points-of-interest on the coast, such as shipwrecks and buried treasure. Those have the same requirements, so they will be a straightforward extension later.)
Global placement
Recall that we previously figured out where the coasts are in our global map. We know the height of the terrain at each grid point, which can be either above or below sea level. We say that a grid cell is “coast” if some of its corners are above, and some are below sea level, coloured light blue here:
Those cells will be candidates for containing a port. (Lakes have already been detected and filtered out at this point; they are classified as land instead.)
To guarantee an even distribution of ports around the world, you might think that we could just put all coast cells in a list, and randomly pick elements from that list. However, that would only guarantee even distribution along coastlines, not spatially. If we have a very wrinkly coastline (think fjords), it will contain a much higher density of ports than straight coastlines!
The solution I came up with is to divide the global map up into grid squares:
Each of these squares will contain at most one port. For each square, we first check if it contains any coast at all; if not, we skip this square. If it does contain some coast cells, we pick the most “desirable” one; desirability is measured as the number of land cells within some radius of the port. This promotes spawning of ports at the end of sheltered bays, and discourages spawning of ports on tiny islands. The most desirable coast cell becomes the candidate port for that grid square.
Next, all candidates are assigned a sample weight according to their latitude, fed through a curve that I can specify:
So ports at the equator have a weight of 0.5, around 30° latitude the weight goes up to 1.0, sloping all the way down to 0.0 in the polar regions. The shape of the curve is my best guess at realism, considering habitability, but I might well need to tweak it for gameplay balancing purposes later. We then select a fixed number of candidates according to this weight:
(The icons are very small; zoom in to see them.)
For each of these ports, we also randomly select a population, also according to some distribution. I think I’ll later replace this by discrete size classes (hamlet, village, town, city, metropolis) but this’ll do for now.
Smooth sailing so far!
Local placement
In the previous post, I was very happy because I’d found a solution to the port placement problem, by using a modified diamond-square algorithm. In short, if all four corners of a diamond or square are below sea level, the center is assigned a value below sea level as well, and vice versa.
This works perfectly to preserve the “nature” of each cell in the global map: land, sea or coast. However, it does not guarantee that all coast is reachable – I encountered fun situations like this:
The red and green lines here mark out the edges of global map cells, whose corners have their heights taken from the global height map; everything in between is generated using diamond-square. As you can see, the cell containing (most of) the port has one corner that’s ever so slightly below water, so this cell is a coast cell, and the algorithm correctly decided to spawn a port there.
However, the cells connecting it to the sea are also coast cells, so there are no constraints on the heights inside those cells, apart from the corners. In this case that terrain is fairly high, creating a tiny lake completely surrounded by hills; not a great spawn point for our intrepid fleet of player ships.
At first I thought I could solve this by forcibly lowering the center of the port’s cell, pulling the neighbouring cells down along with it. But no:
This created a second tiny lake, but diamond-square still decided to block off the route to the sea.
A second attempt had me force the height of the entire quadrant connected to the sea corner, and you can guess how that worked out:
This problem took me way too long to figure out, but once I did, the solution seems obvious: we need to enforce connectivity between grid points. To be precise: if two adjacent corners of a cell are both below sea level, the local terrain generator must ensure that there is a path by sea between the two. So I ended up forcing the terrain to be sea along entire edges, and that works great:
(For now, I’m ignoring both the width and the depth of this forced “channel”. The depth does not currently matter to gameplay; any place where the terrain is below sea level is accessible. The width can easily be extended by also forcing a minimum depth on cells adjacent to the edge.)
Now that I had this functionality of forcing minimum and maximum height of particular points, I also used it to force the height of the middle point to be at least zero. Usually this will cause some of the adjacent terrain to be above zero, creating some land for the port buildings to spawn on. The port is then always spawned right in the middle of the cell, without any local adjustments needed. Much simpler!
The player’s ship will also need to be spawned near one of these ports. I previously had a complex dance at game startup to figure out where to spawn it, because even corner points wouldn’t necessarily be connected to open sea, but we couldn’t know until we started generating local terrain around the player, which we couldn’t do until we had placed the player. Now that chicken-and-egg problem is gone too: we simply pick a corner of the port’s cell that is below sea level, and the local terrain generator will guarantee a path from there to open sea.
Spawning buildings
You’ve already seen how the ports currently look, using this placeholder absolutely stunning model of a building I created in Blender:
The radius in which buildings are spawned depends on the port’s population. Right now, the algorithm simply picks a uniformly random angle and distance from the center, and plops a building down at that point. This causes the building density in the centre to be greater, which is actually a feature – but really, this entire algorithm is a placeholder as well, until I have time to come up with something better.
That’s it for port placement… for now. I’m sure I’ll revisit this topic in the future, because there are more things I want to implement: a fair spatial distribution of small vs. large ports (larger ones having more services), a local language and culture, proper building placement in sensibly-looking districts, influence on the local vegetation, and maybe even non-placeholder building models as well. For now though, I should be turning to gameplay, but I might actually tackle some eyecandy first. We’ll see.