Procedural Island Generation for Ludum Dare 24

  • I spent the first 8 hours of Ludum Dare 24 creating a random island generator. Unfortunately due to a series of disasters, I wasn’t actually able to finish the gameplay in time for the deadline and didn’t submit my game, so this is the one good thing that came out of the whole experience!

    It was my first ever attempt at something like this… I always shied away from anything procedural in the past because I thought it would be more complicated than it is. But I decided it was time to try and overcome those fears and try to generate islands that:

    1. Look natural (= not computer generated)
    2. Look unqiue
    3. But still similar enough that the gameplay experience is comparable

    All things considered I’m reasonably happy with the result. I wish I had more time to add features (lakes, river, mountains, deserts, etc) but most of the time it creates something that looks convincing enough. What do you think? Did I achieve my goals? Here’s a couple examples that it generated.

    Procedural Island Examples

    So how is it done? Here’s a quick step by step.

    1. I start off with a 16×16 grid of water.

    2.. I mark half the middle 1/3rd of tiles as land.

    3. Then I go around in circles for the next 1/3 of tiles, growing the circle each time and marking random tiles as land. The more land a water tile is touching, the higher the random chance of it becoming land. This causes the land to become less as I move away further from the center while still mostly staying connected (but with the occasional island here and there).

    4. The tiles get subdivided into 8×8 smaller tiles each.

    5. Only the middle 50% of the newly subdivided tiles are kept as land, the rest becomes water again.

    6. I connect all the land centers with each other.

    7. And fill in the between connections. The basic shape of the island is now complete and it is time to make it more detailed.

    8. To add detail, I use a similar method as before. I just go around in circles on each individual 8×8 tile that has land on it, randomly changing some water to land. Again, the chance of a tile becoming land is proportional to the amount of other land tiles it is touching.

    (At this point I’m going to stop using the hand-drawn diagram I have been so far because it’s getting too tedious and switch to actual generated images, so that’s why the island shape suddenly looks different.)

    9. With the shape detail added, it’s time to start modifying the terrain types. First, every tile touching water is turned into sand.

    10. I go around the entire map twice, randomly changing some grass tiles that are touching sand into sand. As always, the chance of a tile changing is proportional to how many other tiles of the same type it is touching.

    11. Now for some forest! I go back to the 16×16 grid I was using earlier and count how much grass each 8×8 tile in the grid has. If it is at least 25% grass, it gets marked as a potential forest starting point.

    12. From the valid tiles, I pick 40% at random. Then I randomly choose a spot on each remaining 8×8 tile as a starting spot.

    13. To grow the forest, I go in circles between 2 and 8 times around each starting spot, randomly turning tiles into forest. As always, touching more forest = greater chance to become forest.

    14. For the final step, I pick 15-30 random tiles on the map as rock starting spots, and go in circles 0-5 times to grow them.

    And that’s it! The island is complete.

    Bonus: this is what it looks like in-game at gameplay resolution with trees, berry bushes, and bugs.

    I think there’s a lot of room for improvement here. What you see took me 8 hours, and if I had more time I would:

    • Add a a step between 7 and 8 that curves the angular sections to look more natural.
    • Add features such as lakes, rivers, etc.
    • Add terrain variety: deserts, snow etc.

    Anyways, if you’re looking for a quick and easy way to generate some okay-looking islands I hope this helps you. I hard a hard time finding good articles on the subject and didn’t have time to do a lot of research. The article that probably helped me the most is Procedural Level Generation for Artists. It made me realize that the easiest way to exert some control over what the island would look like, while retaining a good amount of randomness, would be to fix and hand-tweak a couple variables (eg my 16×16 starting grid, filling the center 33% with land, etc). Other 100% randomized methods (for example) don’t look or play as well, but I did learn to subdivide a large grid into a smaller one from it. I also decided against fancier algorithms like perlin noise (as Notch famously uses in MineCraft) due to time constraints.

    Questions? Suggestions? How would you have done it? Leave me a comment!

    September 2nd, 2012 | Wolfgang | 14 Comments | Tags: , , , ,

About The Author

Wolfgang Graebner

I'm half of Funstorm - I do the programming and business stuff.

14 Responses and Counting...

  • Thank you for this excellent article. As I mentioned in the Flixel Forum. You guys have a great blog. Please continue posting. :)

  • Step 4 says “The tiles get subdivided into 8×8 smaller tiles each.”. Can you explain that further? The images provided don’t give much detail to that.

  • I started off with a map 12 tiles wide, and 12 tiles tall. But with just 12×12 tiles, that doesn’t give me a lot of options to add detail. So I turn each tile into 8×8 smaller ones. That gives me a total of 12 * 8 = 96×96 tiles to work with. Which allows me to add finer detail in the later steps. The image shows one tile subdivided into 8×8 smaller ones.

    Hope that explains it better!

  • Very interesting article Wolfgang, thanks for sharing :)

    By the way, that last screenshot looks great… Are there any plans to continue developing the game?

    Thanks, Paulo

  • Thanks man!
    I don’t think I’ll take it further… too busy with other projects :) I tend to look at gamejams as a time to learn and experiment with something new. But I’m sure the procedural stuff I learned doing it will eventually find it’s way into another game!!

  • As you’re not planning(at the moment) on doing anything else with this, is there any chance that we’d be able to see some snippets of the code? I’m learning AS3 and procedural generation! Ideally I’d just want to have a peak at the generation bit I’m interested in… :D

    If not, this post is still really helpful – Thanks a lot for writing it :) It really does help to be lead through the logic in plain English!

  • Sorry, but I can’t do that. It’s really long, and really badly written since I was rushing all the way while doing the game jam. It does silly things that are bad and I don’t want to teach others to do bad things :P I would have to clean it up, and fix too many things to feel comfortable releasing it. But if you have a specific question I’ll try my best to help.

  • Ok! That’s fine :) I don’t really have any specific questions at the moment. I’ve just been trying to read up on it whilst attempting to do some basic stuff. The language and programming techniques feel so over my head in most of the articles/threads/anything I read on procedural stuff though.

    Like I said before though, seeing the steps in plain English is incredibly helpful – So thanks!

  • Just a heads up on something you may or may not want to consider fixing – your 16×16 grid is actually 18×18 and you are definitely are using all of this space because your “thirds” are 6 tiles to a side.

    I know the algorithm is the same otherwise but I found it confusing when following along to see my implementation produce two rows of random tiles at step 3 instead of the three rows you have. I thought I was doing something wrong until I discovered you had us all fooled!

    Great write up altogether though. Great work!

  • Usually I do not learn article on blogs, but I would like to say that this write-up very forced me to take a look at and do so! Your writing style has been surprised me. Thank you, quite nice post. discount soccer jerseys

  • [...] I am developing my first island generator (in c#). I am using this algorithm as my basic idea : [...]

  • [...] Procedural Island Generation [...]

  • Very cool swirl idea! I like that a lot. I think for the beaches it would have been cool if you raycast out in the direction of the water and if you hit a lot of land the chances of becoming sand increase whereas if you hit a lot of water (border) then it would become rock. That way you get beach coves and straight ends but rocky peninsulas. I’m no expert but I think that’s how it really works… the turbulence of water being pushed into a socket creates sand but a peninsula creates very little unless it’s part of a bay system…

    Not sure! But lots of food for thought. I know its an old article now but thanks for sharing.

  • I love the ideas presented here! Can I ask… how best to split the grid into smaller tiles and then back again? How are you storing your map data?

Leave a Reply