Islands and castles generation

Island generation
Castles placement
SDL pixel perfect rendering

Recently I decided to make a program that generates islands with linked castles.

This was made using SDL and C++ (which I’m both still learning), along with Reputeless’ Perlin Noise library. I used their example.cpp file as a starting point for the image generation part.

Island generation

I used perlin noise for the terrain generation. The perlin noise function assigns a value between 0.0 and 1.0 for each coordinate (i.e. pixel) on the image, and we can then assign a color to each pixel using their value. A base_height value acts as a threshold to color pixels either black or white. With base_height set to 0.4 we get:

I added an added_height value to only draw a contour of the island. So we now check if a pixel’s perlin noise value is between base_height and base_height + added_height. Notice how we get smaller islands when using a higher base_height value.

Then, each pixel that is over the ground now has a 0.02% chance of turning white, to make it look like grass. This makes differenciating the sea and the island much easier:

Now if we really want to make islands and not just a big continent, we need to shape it into a rounder shape. For this I smoothed the edges out by decreasing the perlin noise value exponentially: the further a point is to the center of the image, the more it is going to be decreased. Here’s a simplified sample from the code, where x and y are the coordinates of the pixel being sampled:

p_value = perlin.octave2D_01(x, y, octaves); // get the perlin noise value

dist_to_center = sqrt((x-center)*(x-center) + (y-center)*(y-center));
// max_dist is the highest distance possible
// it is computed using the top-left corner of the image
edge_smooth = dist_to_center / max_dist;
edge_smooth *= edge_smooth; // square it

p_value -= edge_smooth;

The island now looks like an island!

Castles placement

I started generating castles (little red boxes… not very architectural) all over the island at random. But as you can see on the second screenshot, they can generate way too close from each other… So I had to implement a Poisson Disc Sampling algorithm to make them spawn at even distances from each other. I won’t explain this in detail but here’s the original paper if you’re interested.

evenly placed using Poisson Disc Sampling

To generate each castle (which in the code are just points), I used a recursive function spawnNext(vec2 previous_point) that spawns another point from a previous one. This function tries to generate a candidate point until it has found one: it first generates a random radius and a random direction and uses them to calculate the candidate point’s position using the previous point’s one. This function also calls an bool isValid(vec2 point) function that checks if the candidate point is not out of bounds, and if it’s not too close from other points (using the Poisson Disc Sampling algorithm). When it has found a valid point, there is a 50% chance the function will call itself a second time. This creates a second “branch”, therefore two paths to choose from.

Since I wanted to interconnect the castles, I drew line segments between each point’s position and the position of their previous point. … which did not look very good, because segments were entangled. Here’s an extract from the code that resolves this using geometry:

vec2 p1 { origin_point.x, origin_point.y };
vec2 p2 { candidate.x, candidate.y };
vec2 p3, p4;
double m_1, m_2, b_1, b_2, x, y, w_min, w_max, h_min, h_max;

// get line equation of candidate segment (m and b parameters)
m_1 = (p2.y - p1.y) / (p2.x - p1.x);
b_1 = p1.y - m_1 * p1.x;

// paths are segments (two points p1 and p2)
// loop over each path to see if the current path intersects
for (auto path : paths)
{
    p3.x = path.p1.x;   p3.y = path.p1.y;
    p4.x = path.p2.x;   p4.y = path.p2.y;

    // get line equation of tested segment
    m_2 = (p4.y - p3.y) / (p4.x - p3.x);
    b_2 = p3.y - m_2 * p3.x;
    
    // get intersection point of the two lines (if not parallel they will intersect at some point)
    x = (b_1 - b_2) / (m_2 - m_1);
    y = m_1 * x + b_1;
    
    // get boundaries of the segments
    w_min = std::min(p1.x, p2.x);
    w_max = std::max(p1.x, p2.x);
    h_min = std::min(p3.y, p4.y);
    h_max = std::max(p3.y, p4.y);
    
    // check if the intersection point is in the segment or not
    if (x > w_min && x < w_max && y > h_min && y < h_max) {
        return false;
    }
}

return true;

Great! Now the castles and their paths generate nicely. I drew a little sprite for the castles and pasted it where the castle points were. Here are a few examples of generated islands:

This could definitely be used in the future as an overworld map for a game. Points could be randomized to either be castles, shops or something else.

SDL pixel perfect rendering

A little note on how I achieved scalable pixel perfect image rendering, thanks to this Stack Overflow answer by furious programming. I first defined a few macros:

// game space dimensions
#define IMG_WIDTH 512
#define IMG_HEIGHT 512

// upscaling factor (must be int for clean results)
#define UPSCALE 2

// window render dimensions
constexpr int R_WIDTH = IMG_WIDTH * UPSCALE;
constexpr int R_HEIGHT = IMG_HEIGHT * UPSCALE;

To resume things up, it copies everything that’s copied to a renderer to a texture. Then, only this texture is shown in the window. Here’s a simplified snippet that should be working:

SDL_Init(SDL_INIT_EVERYTHING);

SDL_Window *window = SDL_CreateWindow("pixel perfect", SDL_WINDOWPOS_UNDEFINED, SDL_WINDOWPOS_UNDEFINED, R_WIDTH, R_HEIGHT, SDL_WINDOW_ALLOW_HIGHDPI);
        
SDL_Renderer* renderer = NULL;
renderer = SDL_CreateRenderer(window, -1, SDL_RENDERER_TARGETTEXTURE);

SDL_SetHint(SDL_HINT_RENDER_SCALE_QUALITY, 0);
// create a texture to copy everything to
SDL_Texture *back_buffer = SDL_CreateTexture(renderer, SDL_PIXELFORMAT_RGBA8888, SDL_TEXTUREACCESS_TARGET, IMG_WIDTH, IMG_HEIGHT);
SDL_Rect back_buffer_rect { 0, 0, R_WIDTH, R_HEIGHT }; // size is the window size

// make a texture for the generated terrain
SDL_Texture *noise_terrain_tex = IMG_LoadTexture(renderer, path.c_str());
SDL_Rect noise_terrain_rect { 0, 0, IMG_WIDTH, IMG_HEIGHT }; // size is the image size

// main loop
while (true)
{
    // set the renderer's target to the back_buffer texture
    SDL_SetRenderTarget(renderer, back_buffer);

    // DRAW EVERYTHING
    SDL_SetRenderDrawColor(renderer, 0, 0, 0, 255);
    SDL_RenderClear(renderer);

    SDL_RenderCopy(renderer, noise_terrain_tex, NULL, &noise_terrain_rect);
    // END DRAW EVERYTHING

    SDL_SetRenderTarget(renderer, NULL); // back to window
    SDL_RenderCopy(renderer, back_buffer, NULL, &back_buffer_rect);
    SDL_RenderPresent(renderer);
}

I might try implementing more features later. Let me know if there are any errors!