Island generator?

I’m trying to make a game involving a bunch of islands. I’ve searched high and low for a vector-based island generator that can restrict the width, height, and area of an island. Possible lakes, forests, etc. could occur, but there must be reasonable room for the player to place buildings, troops and vehicles. I tried getting the outline of the island using the fractal terrain algorithm, but I ended up with a very quadrilateral island. Any ideas?

You can use an image height map, with readimage you get the color and this value represent the height of the whole land, building only from a height…

I’d like the island to be randomly generated in the game, so it’s different each time. And I want it to be vector-based, so it look neat and simple. This means that the border of the island has to be generated as a list of points, so height-mapping wouldn’t work.

I think heightmappin can still work as a tool to get the location and shape of the islands.
in short:

  1. generate a random noise heightmap.
  2. smooth it out to get a nice landscape
  3. assing water to pixels below a level, the rest is land.
  4. trace out the borders of the islands, use those coordinates to get the border vectors you need

part 4 may be hard, depending on how many border points an island may have. The less points, the smarter your selection of these points needs to be.
Perhaps Bezier curves?

Picking up on that last, there’s a nice algorithm for producing piecewise cubic bezier curves through a given set of points. So you could generate a random set of points and then use this algorithm to generate the coastline from them.

I’ve already implemented the algorithm in Codea, by the way.

Thanks for the help @PTN and @Andrew_Stacey. I’ve got a nice island generator going using height maps.

However, I’m stuck on finding the border of not just the main island, but all surrounding mini-islands and lakes as well.

Gaah, Lua is too slow. I have a feeling that if I wrote this in C, I could supersample the image instead of vectorizing it, and it would still be much faster.

Maybe I’ll make the lua prototype without antialiasing, and add it if I port it to a faster platform.


-- Island Generator

-- This function generates the height values of the terrain.
-- Width and height specify the map size, although the land will be much
-- smaller.
-- Smoothness sets how smooth the terrain is. A bigger value means
-- smoother terrain. Suggested value is around 10.
function generate(width, height, smoothness, iterations)
    local n, amplitude
    local smoothnessx = smoothness*width/30
    local smoothnessy = smoothness*height/30
    
    -- Create the map array
    local map = {}
    for y = 1, height do
        map[y] = {}
    end
    
    local seed = math.random()*50000
    for y = 1, height do
        for x = 1, width do -- This never repeats
            n = 0
            amplitude = 2
            -- Generate the terrain
            -- 'n' is the height value of the terrain
            for i = 1, iterations do
                n = n + (noise(x/(smoothnessx)*amplitude,
                               y/(smoothnessy)*amplitude,
                               seed)+1)/amplitude
                amplitude = amplitude * 2
            end
            -- Make the height value go to 0 near the edge
            n = n * (1-math.abs((x/width*2)-1))
                  * (1-math.abs((y/height*2)-1))
            map[y][x] = n
        end
    end
    return map
end

function drawIsland(map)
    img = image(#map[1], #map)
    for y = 1, #map do
        for x = 1, #map[1] do
            if map[y][x] > 0.5 then
                if map[y][x] < 0.57 then
                    img:set(x, y, color(214, 192, 132, 255))
                else
                    img:set(x, y, color(34, 140-map[y][x]*90, 10))
                end
            end
        end
    end
    return img
end

-- Use this function to perform your initial setup
function setup()
    island = generate(200, 200, 10, 4)
    img = drawIsland(island)
end

-- This function gets called once every frame
function draw()
    background(46, 91, 173, 255)
    
    sprite(img, WIDTH/2, HEIGHT/2)
end

If you have a map with islands from a heightmap, why do you still need to convert to a system with islands based on borders.
I’m not questioning your method, just need to know where you’re going.

Getting from a heightmap to a set of borders would involve some hefty ridge detection, and then grouping those ridges into islands. I fear this may be the long way to do things.
Faster would be to either stick with the heightmap system throughout the game, or never use a heigtmap and generate the borders directly

Epic :open_mouth:

To do make it 3d and add trees.

@floppy_gunk Are you making an RTS?

@PTN I wanted the border to be vector-based so it could have anti-aliasing. However, it seems that it would be too inefficient do so, and none of my island border generators worked well, so I’ll stick with this for now.

@Connorbot999 I’m planning on adding some forest if I can, but 3D isn’t quite where I’m going with this. Feel free to use my code though if you want to make something from it.

@MizB My game is going to be turn-based.

Tight loops in lua can certainly slow things down. I would recommend using a one dimensional array (i.e. a single table, instead of a table for each row). Also using locals instead of table loops where possible may also help.

Here’s an excellent tutorial on map generation.

http://www-cs-students.stanford.edu/~amitp/game-programming/polygon-map-generation/

It’s very thorough, but really informative.
I think using Voronoi diagrams to generate a mesh for each island may give you the result you need.

I.ve messed around with Bezier curves and they don’t produce natural looking islands. It’s possible to generate smooth irragular shapes, but they’re too smooth looking, or intersect themselves.

No promises, but this does look quite fun.

@floppy_gunk but RTS games are turn based aren’t they?

You do realize when I asked if it was an RTS I meant Real-Time Strategy

.@MizB I think if it was turn based it would not be real time. It would just be a turn-based strategy game.

@PTN Now that looks interesting. It’s a bit intimidating, but I’ll try to work my way through it.

@MizB according to Wikipedia ‘Real-time strategy (RTS) is a sub-genre of strategy video game which does not progress incrementally in turns.’

@floppy_gunk I hope your brain is better than mine, I’m already stuck at the voronoi diagrams. I found some c++ examples, but lame-a$$ me can read no c++… :frowning:
Trying to build the Fortune’s Sweep-line implementation from scratch is smacking my brain around.
Help anyone?