Island Project

This was a challenging project allowing the procedural generation of 2D islands, with features such as the following:

Various Island Shapes

We created some pre-defined shapes, and the code is designed such that new ones can be easily added, including irregular shapes.
The shores of the island will always be composed of beach tiles.

Elevation

Elevation profiles can easily be defined; we included a few examples such as a single large mountain, or a range of smaller mountains covering the island.

Rivers

Rivers start at a spring on a random tile and flow along tiles with decreasing or constant elevation.
They can merge with other rivers, forming a wider river which continues to flow.
A river ends either when it reaches the ocean, or when it can’t flow down any further.

Lakes

Lakes appear at random on the map in varying sizes.
They also form where rivers end if the river doesn’t reach the ocean, with the size of the lake determined by the flow of the river that formed it.

Moisture Absorption

Rivers and lakes cause surrounding water to absorb moisture, effecting greenery and habitability. This effect spreads outwards from the source.
Moisture is also produced by hidden underground aquifers at various points on the map.
The soil absorption coefficient can be configured.

Biomes

A tile’s biome is related to its moisture and elevation. For example, a low dry biome is a desert, whereas a high wet biome is a snowcapped peak.
Biomes each have their own colour, although they gradient based on how well they fit their criteria, allowing for a smooth colour transition across the island.
Biome criteria is determined by a Whittaker Diagram. New Whittaker Diagrams can be defined to change the face of an island.

Cities and Roads

City locations are chosen based on ideal conditions, based on an area’s moisture and distance to other cities. The capital city is placed first, in the optimal position on the map. Additional cities are then placed in the next best positions, while attempting to maintain a fair distance from other cities to prevent resource starvation.
Roads connect in a star network to the capital city.
Roads avoid lakes and rivers where possible but will create bridges over them if necessary. They also attempt to avoid mountainous terrain and will take the path that’s least steep if they have to go up a mountain to reach a city.

Generation Parameters

Shape, elevation profile, number of rivers lakes aquifers and cities, soil absorption, and the biome Whittaker diagram, can all be configured.

Object-Oriented Programming

Our code is heavily based around OOP principles, with emphasis on abstraction, inheritance, encapsulation, and polymorphism. Detailed UML diagrams can be found here:

Irregular Polygon Mesh Generation

First random points were added to the canvas, then a Voronoi diagram was calculated for each point, leaving a sharply angled mesh.
Lloyd Relaxations were then used to smooth out the polygons into their final shape.
Delauney Triangulation was used to find each tile’s neighbours for future use.

Breadth First Search (BFS)

Both elevation and moisture absorption were implemented through variations of the BFS algorithm to represent an expanding radius from a point.
Edits were made to the BFS algorithm when generating mountains in order to produce a more irregular shape.

Dijkstra’s Shortest Path

Road networks were calculated via use of this algorithm, with each tile as a node, and the difficulty of building a road across a tile due to steep elevation or blocking rivers used as a weight mapping for graph edges. This ensured the most efficient road networks were created.