Flash procedural map generation example: land and water

Today we’ll draw a simple random map with land and water using some kind of procedural map generation.

Using this technique, we can draw infinite (not really “infinite” to tell the truth… let’s say “more than you can play”) maps with no hassle.

In this post, we’ll cover the basics of procedural map making, building a random map.

First, we divide the map in large tiles (32×32 pixels tiles in a 640×480 map are large enough) and we define a land/water ratio. With

we say every tile has the same probability of being land or water. So with a simple random function assign each tile a land/water state.

At the end of this first, simple step we have something like this:

Now we reduce tile size by an half, having 16×16 pixels tiles. This way, every original tile will be replaced by four smaller tiles.

New tiles will be drawn with this rule: when a tile is going to be created over a water tile, it has the 80% of probability for being a water tile. If it’s created over a land tile, it has the 80& of probability for being a land tile.

There are better ways to determine if a tile over a land/water tile will be a land/water tile… you can also look at its surrounding tiles for example… but at the moment we are keeping things simple.

After this step, the previous map looks this way:

You can repat the previous step until you get 1×1 pixel tiles, or simply another time like I am doing. This is the map after the 3rd step:

Once you are done with tiling, the map could look a bit scattered, so the last step consists in removing any land tile without any adjacent land tile (just looking horizontally and vertically, not in diagonal), turning it into a water tile, and removing any water tile withoud any adjacent water tile, turning it into a land tile.

This is the map at the end of this step:

And this is the script which generate such kind of map:

Playing with these variables:

you can get very different results. This is what you get with the above settings:

it may seem a bit slow because I am rendering a tile at each frame, to show you the process.

Download the source code. Next time, we’ll see how to merge procedural map generation with the generation of pseudorandom numbers with Blum Blum Shub method to create pseudorandom maps.

  • I like the idea of having random/pseudoRandom parts in a game, you can ensure a degree of “novelty” with each play through. If for example…in Zelda Ocarina of time the lost woods part were random…that would have been GREAT :).

    I’ll try to make a game based on your posts…I hope soon :p

  • (random) Procedural creations are always very nice and can be usefull – the biggest problem there is the predictability :D

  • Perlin noise might give you a more realistic pattern, with continents and islands.

    See: http://devmag.org.za/2009/04/25/perlin-noise/

    and

    http://josephknight.com/2d-cave-generator-looking-good/

    and maybe this would apply, do you see how the cave walls can be re-imagined as top down land-masses in an ocean? :

    http://josephknight.com/lonely-alien-in-an-erie-cave/

    Hope this helps. Was easy to implement and lot’s of fun.

  • Kaustav

    JosephKnight is right, Perlin noise will get an even more realistic map with smooth edges.

    Perlin noise can also be used in so many other areas, from textures to clouds, but i think the most beautiful use of Perlin noise can be found over here:

    http://www.nulldesign.de/2008/01/21/war-of-the-fireflies/

    Each firefly’s path is determined by Perlin noise, and it simulates smooth flocking behavior extremely well, check it out! The method that was used is described here:

    http://www.mikethenderson.com/2008/09/moving-particles-with-perlin-noise-v01/

  • Emanuele Feronato

    @JosephKnight: your cave map is interesting, unfortunately it does not generate a perfect cave since there may be cases with unreachable spots. I’ll publish a cave generator next week, hope we can sort out the perfect cave generator

  • I tried making one of these a short while back, where tiles are randomly chosen a thousand or so times to change their type to whatever is popular with their neighbors. The clumping effect turned out nice, but there must have been a more efficient way.

    http://www.kevindoesart.com/WorldGenerate.html

  • Ben

    Real cool stuff here!

    I actually just got really motivated by this idea and after replicating the land/water thing I thought I’d give the Perlin noise a try. It seems to have a lot of applications for game development without hogging a lot of computer resources. Well after a full Sunday at the computer, I got it! And I decided not to let all this work go to waste so I wrote up a quick as3 guide to Perlin noise generation! http://www.bendeitch.com/blog/perlin-noise/

  • @Emanuele: It depends on the game mechanics as to whether or not all areas are reachable. Since you can dig or explode areas in my game concept, having initially unreachable areas is great because then I can have the generator put extra special treasures and items there, giving the player incentive to explore and push to reach obscure areas. Breaking through into a sealed off cavern to find a large ancient temple is likely to inspire the player to emotion.

    I’m still interested in your version of what a perfect cave generator is. However, “perfect” will likely depend on whether it meets the need of a particular game.

    Here’s the latest image complete with textures, lightning bugs, and an ancient relic.

    http://josephknight.com/the-lonely-alien-stumbles-onto-an-ancient-relic/

    Thanks for the tuts, keep it up!

  • Roger Hudson

    Hi.

    Great tut like always :)

    What about simulation cracked ice on the river or ocean?
    for example
    http://image.shutterstock.com/display_pic_with_logo/189514/189514,1236329864,3/stock-photo-cracked-ice-on-river-in-spring-26141074.jpg

    I can’t get the idea where i shoud start…
    There is a Voronoi_diagram
    http://en.wikipedia.org/wiki/Voronoi_diagram

    But i think there is a simple decision…

    Thanks

  • h_seldon

    Nice work (as always at this blog – thanks for your great posts). As JosephKnight said, perlin noise might give a somewhat more smoother result esepcially if you want to use more than just two tiles. Also, when combined with paletteMap or copyPixels (hypso color palette) you might get a nice top down view on terrain. In that case you don’t need tiles anymore, of course.

    @Ben, tried to post at bendeitch, but it doesn’t work for some reason. So here is my question to your http://bendeitch.com/blog/perlin-noise/ post: why do you write your own perlin noise algo instead of trying Flash’s built-in one? Is it faster? Emanuele, if it is not ok to ask that question here, delete this part of the post please. Sorry for the inconvenience.

  • Emanuele Feronato

    @JosephKnight: when I said “perfect” I did not mean “better than the rest”, but I meant the definition of a perfect maze (or cave), where all spots are reachable. Obviously if you are working at a “drill” game, you don’t want to use perfect levels.

    @roger and h_seldon: I’ll try to build some examples built upon Voronoi and perlin noise.

  • h_seldon

    Just for fun a kind of b/w transition effect with perlin noise:

    //——————- import ———————-
    import flash.display.BitmapData;
    import flash.display.Bitmap;
    import flash.geom.Rectangle;
    import flash.geom.Point;
    import flash.events.Event;
    //——————- vars ———————-
    var bm_someNoise:Bitmap;
    var someNoise:BitmapData;
    var frequX:Number = 100;
    var frequY:Number = 100;
    var octs:Number = 4;
    var seed:Number = Math.floor(Math.random() * 1000);
    var stitch:Boolean = false;
    var fractal:Boolean = true;
    var channels:Number = 1;
    var gray:Boolean = true;
    var switchCol:Boolean = false;
    var myIndex:Number = 0;
    var red:Array = new Array(256);
    var green:Array = new Array(256);
    var blue:Array = new Array(256);
    var cols:Array = [0x00000000,0x00ffffff];
    var step:Number = 1;
    //——————- functions ———————-
    function changePalette(e:Event) { someNoise.perlinNoise(frequX,frequY,octs,seed,stitch,fractal,channels,gray);
    myIndex += step;
    if (myIndex >= 256 || myIndex <= 0) {
    switchCol = ! switchCol;
    step *= -1;
    }
    red[myIndex] = green[myIndex] = blue[myIndex] = cols[Number(switchCol)];
    someNoise.paletteMap(someNoise,new Rectangle(0,0,someNoise.width,someNoise.height),new Point(0,0),red,green,blue);
    }
    function init() {
    someNoise = new BitmapData(400,300,false);
    someNoise.perlinNoise(frequX,frequY,octs,seed,stitch,fractal,channels,gray);
    bm_someNoise = new Bitmap(someNoise);
    addChild(bm_someNoise);
    for (var i:uint = 0; i myIndex; i < 256; i++) {
    red[i] = green[i] = blue[i] = cols[1];
    }
    someNoise.paletteMap(someNoise,new Rectangle(0,0,someNoise.width,someNoise.height),new Point(0,0),red,green,blue);
    stage.addEventListener(Event.ENTER_FRAME,changePalette);
    }
    //——————- start ———————-
    init();

    to get a landscape throw out the enterframe, load a hypso (gradient 256 px) and fill the arrays for paletteMap by getPixel32 in the gradient from pixel 0,0 to pixel 255,0. That allows for loading different gradients as bitmaps and change the terrain easily.

  • I was not familiar with that usage of perfect. I just learned something new.

  • Pingback: Using cellular automata to generate random land and water maps with Flash()