GM:S 1.4 Randomly generated terrain using tile runners

Discussion in 'Tutorials' started by Simon Gust, Sep 17, 2018.

  1. Simon Gust

    Simon Gust Member

    Joined:
    Nov 15, 2016
    Posts:
    2,967
    GM Version: GM:S 1.4
    Target Platform: All
    Download: N/A
    Links: N/A

    Summary:
    This tutorial is about randomly generated terrain. It shows you what the purpose and effectiveness of tile runners are and how to use them.

    Heads up:
    This tutorial requires you to know at least the following terms
    - arrays
    - for loops
    - while loops
    - basic math

    Tutorial:
    PART 1, your basic twisted line:
    Tile runners are used to make randomly generated terrain and are extremely wide in their use, ranging from caves to rivers.
    Almost anything can be generated with a tile runner if you use it right. Think of it as a worm that eats anything in it’s path.

    First, you must understand how they work.
    Imagine your terrain as an array where «1» in a cell means that there is solid terrain and «0» meaning that there is nothing but thin air.
    Something like seen in this tutorial: https://forum.yoyogames.com/index.php?threads/cellular-automata-cave-generation.37895/
    The outcomes are similar but the methods are two different worlds.
    upload_2018-9-17_14-6-20.png
    Example of a simple generated terrain that shows caves going all over the place like spaghetti

    The most basic tilerunner is simple, it starts somewhere, eats some tiles and moves somewhere else,
    just to repeat it’s process over and over, until either the compiler crashes due to many recursions or you set it a limit / goal.

    Let’s start by setting up a template.
    CREATE
    Code:
    Randomize(); // call this so the outcome is different every compile
    wdt = 300; // width of the terrain
    hgt = 300; // height of the terrain
    for (var i = wdt-1; i >= 0; i--)
    {
        for (var j = hgt-1; j >= 0; j--)
        {
            global.tile[i, j] = 1; // 1 being solid terrain
        }
    }
    
    Now, apply the tile runner to that array
    Code:
    // tile_runner(array name, start x, start y, runner strength, runner life)
       tile_runner(global.tile, 150, 150, 5, 100);
    
    Also create a surface so we can see the results pasted to the screen
    Code:
    surface = surface_create(wdt, hgt); // create the surface
    surface_set_target(surface); // set the surface as the current render target
    draw_clear(c_white); // clear the surface with a white color
    draw_set_color(c_black); // set the terrain color
    
    var array = global.tile; // shortcut refrence (var is faster than global.)
    for (var i = 0; i < wdt; i++)
    {
        for (var j = 0; j < hgt; j++)
        {
            if (array[@ i, j] > 0)
            {
                draw_point(i, j); // draw a pixel if there is solid terrain
            }
        }
    }
    
    surface_reset_target(); // reset the render target
    
    The draw event simply looks like this
    Code:
    draw_surface(surface, 0, 0);
    
    And finally, the tile runner script
    Code:
    /// tile_runner(array name, start x, start y, runner strength, runner life)
    var array = argument0;
    var X = argument1;
    var Y = argument2;
    var str = argument3;
    var sps = argument4;
    var dir = random(360);
    
    while (sps > 0) // run this as long as sps (steps i.e. the lifetime) is above 0
    {
        // reduce runner lifetime
        sps--;
    
        // keeping the runner inbounds to avoid out-of-bounds errors
        var x1 = max(X - 0.5 * str, 0);
        var y1 = max(Y - 0.5 * str, 0);
        var x2 = min(X + 0.5 * str, wdt);
        var y2 = min(Y + 0.5 * str, hgt);
    
        // eat away at the terrain
        for (var i = x1; i < x2; i++)
        {
            for (var j = y1; j < y2; j++)
            {
                if (array[i, j] > 0) // if there isn’t already nothing, reduce it to nothing
                {
                    if (point_distance(X, Y, i, j) < 0.5 * str) // this line is explained below
                    {
                        array[@ i, j] = 0;
                    }
                }
            }
        }
    
        // move the runner in a random direction
        if (!random(3))
        {
            dir += random_range(45, -45); // don’t allow the runner to make sharp corners by limiting it to 45° degree turns
        }
    
        // move the runner
        X += lengthdir_x(1.00, dir);
        Y += lengthdir_y(1.00, dir);
    }
    
    The strength of the runner acts as a diameter the runner will eat the terrain.
    If the strength is 5, you can expect a 5 wide / tall tunnel to be made.

    Now to this code snippet
    Code:
    if (point_distance(X, Y, i, j) < 0.5 * str)
    
    It’s only purpose right now is to make the cave have rounded edges if so desired.
    Without it, you would get box tunnels which can work but don’t look really natural.
    The math behind this is simple:
    It checks the distance to every cell it’s going to eat, then it asks them if they’re in the radius of the center.
    upload_2018-9-18_22-49-54.png
    The strength suggests to eat away the whole box, but the code snippet sees the distance of the orange cells as too far and doesn’t eat them.
    The green cells are in the radius from the center and are eaten away correctly.
    No matter how great the strength of your runner, the rounding of the edges is always ultra-precise.

    So lets see the result: https://imgur.com/a/dGoAwMZ
    Pretty cool huh?

    PART 2, the tile brush:

    In the first part you were shown how to make the roundness in the runner for smooth endings in caves.
    This time, you get to see what other (geometry) brushes can have.

    First, welcome the diamond brush:
    upload_2018-9-18_22-52-1.png
    This brush eats the terrain in a diamond shape and it even needs less time to do so, there are 2 reasons for this:
    1. There are fewer green cells than with the circle brush.
    2. The geometry requires a different distance check which is more efficient.
    For this to work, the only thing you need to do is replace this line
    Code:
    if (point_distance(X, Y, i, j) < str * 0.5)
    
    with this one
    Code:
    if (abs(i-X) + abs(j-Y) < str * 0.5)
    
    This new calculation is explained here https://en.wikipedia.org/wiki/Taxicab_geometry
    I like to call it "Manhattan distance".
    Let's test it with a greater strength to better notice the difference.
    https://imgur.com/a/dBRpwOh

    The most simplest brush though is the one where you don't use a brush at all.
    If you leave out that line of code, your brush is simply rectangular.
    This works well for corridors or dungeons.

    Of course, you can always invent your own brush. But do so at your own risk.
    You may have to change the radius to not get flat edges when you try something like this
    Code:
    if (sqrt(sqr(i-X) + 6 * sqr(j-Y)) < 0.50 * num1)
    
    in which case you'll get an elipse for example.

    As a base to making your own brush, use the point_distance math:
    Code:
    sqrt(sqr(i-X) + sqr(j-Y))
    
    You can alter this code and see what happens to your brush shape.

    The next thing that might serve usefulness to you is random brush imprecision.
    Instead of taking the radius of the brush for granted, you can patch it with a
    random_range function. Try this:
    Code:
    if (point_distance(X, Y, i, j) < str * random_range(0.2, 0.8))
    
    This is the result: https://imgur.com/a/AUYlMgW

    Fast brush (kept for refrence)
    And finally, there is the fast brush.
    This brush works a little different as it no longer serves the purpose as a brush to shape your caves
    but rather as an optimization.
    The old brush code line now checks if the array cells of the new position of the runner don't touch the old positions. It only writes the array on the green cells and leaves out the yellow cells.
    upload_2018-9-18_22-56-15.png
    Red being the old runner position and Green the new runner position.
    Since this is a geometry type of check, it's going to be faster than asking every cell if they've been overwritten.
    To get this to work, you need to do some code adding:
    You need to save and update the last position of the runner each iteration.
    initialize XL and YL to 0 at the start.
    Then at the bottom in the while loop BEFORE you've moved the runner, update the last position to the new position.
    Code:
    /// tile_runner(array name, start x, start y, runner strength, runner life)
    var array = argument0;
    var X = argument1;
    var Y = argument2;
    var XL = 0;
    var YL = 0;
    var str = argument3;
    var sps = argument4;
    var dir = random(360);
    
    while (sps > 0) // run this as long as sps (steps i.e. the lifetime) is above 0
    {
        // reduce runner lifetime
        sps--;
    
        // keeping the runner inbounds to avoid out-of-bounds errors
        var x1 = max(X - 0.5 * str, 0);
        var y1 = max(Y - 0.5 * str, 0);
        var x2 = min(X + 0.5 * str, wdt);
        var y2 = min(Y + 0.5 * str, hgt);
    
        // eat away at the terrain
        for (var i = x1; i < x2; i++)
        {
            for (var j = y1; j < y2; j++)
            {
                if (point_distance(XL, YL, i, j) > 0.40 * str)
                {
                    array[@ i, j] = 0;
                }
            }
        }
    
        // move the runner in a random direction
        if (!random(3))
        {
            dir += random_range(45, -45); // don’t allow the runner to make sharp corners by limiting it to 45° degree turns
        }
    
        // now update the last position
        XL = X;
        YL = Y;
     
        // move the runner
        X += lengthdir_x(1.00, dir);
        Y += lengthdir_y(1.00, dir);
    }
    
    You can see that the > has been changed to a < on the brush line.
    A problem arises when you choose the number to check the distance for.
    Best case scenario would be 0.50 x strength (exactly outside the old radius).
    But because array indexes don't work on decimals, the imprecision makes it not work reliably.
    A safer number, that I've chosen is 0.40 just to make sure every cell is eaten.
    The more strength your runner has, the preciser you can go, up to 0.50.

    This also causes the brush to lose it's shape and you end up with a rectangular brush again.
    To fix this you can add another bit of code to that line if you want.
    Code:
    var dis = point_distance(XL, YL, i, j); // or abs(i-XL) + abs(j-YL);
    if (dis > 0.40 * str && dis > 0.5 * str)
    
    Whether you remove the read-write check (if (array[i, j] > 0) is up to you.
    The more runners you call, the more use you get out of this line.
    Because the brush checks the cells only on it's last position and only on it's own runner.
    Octagon brush
    You can get a semi-round brush if you combine the rectangular brush with the diamon brush.
    The code is the same for the diamond brush except the radius to check is greater.
    Code:
    if (abs(i-X) + abs(j-Y) < str * 0.75)
    
    I changed the 0.5 to a 0.75 and your brush should look something like this
    upload_2018-11-9_16-47-22.png
    Technically, it is just a bigger diamond shape, but the edges are cut due to the double for loop range limitation.

    PART 3: setting runner properties
    To make your caves / rivers / dugeons or whatever more interesting you can add certain rules to your runner.
    These rules can be soley math or random chance of something happening.
    The setup is quite easy, so I'll show some examples.

    the strength over steps property makes it so that the runner starts at 100% strength and ends at 0% when it's life has ran out.
    The math involved looks like this
    Code:
    real_strength = strength * (current_step / step_amount);
    
    You need to define a current_step and current_strength variable to keep track of your brush size.
    Code:
    var array = argument0;
    var X = argument1;
    var Y = argument2;
    var str = argument3;
    var sps = argument4;
    var str_ = str;
    var sps_ = sps;
    var dir = random(360);
    
    while (sps_ > 0)
    {
        // calc real strength
        str_ = str * (sps_ / sps);
     
        // reduce runner lifetime
        sps_--;
    
        // keeping the runner inbounds to avoid out-of-bounds errors
        var x1 = max(X - 0.5 * str_, 0);
        var y1 = max(Y - 0.5 * str_, 0);
        var x2 = min(X + 0.5 * str_, wdt);
        var y2 = min(Y + 0.5 * str_, hgt);
    
        // eat away at the terrain
        for (var i = x1; i < x2; i++)
        {
            for (var j = y1; j < y2; j++)
            {
                if (abs(i-X) + abs(j-Y) < 0.50 * str_)
                {
                    array[@ i, j] = 0;
                }
            }
        }
    
        // move the runner in a random direction
        if (!random(3))
        {
            dir += random_range(45, -45); // don’t allow the runner to make sharp corners by limiting it to 45° degree turns
        }
     
        // move the runner
        X += lengthdir_x(1.00, dir);
        Y += lengthdir_y(1.00, dir);
    }
    
    The result can look like this https://imgur.com/a/4qqIJwz

    You can also make some variation happen in your runner like this:
    Code:
    if (!random(10))
    {
        str_ += 10;
        sps_ += 10;
        dir = -dir;
    }
    
    Put them anywhere in the while loop. Just make sure not to create an infinite loop.
    This example procs on a 5 percent chance to increase str_ by 10, sps_ by 10 and reverse the direction.

    You can add "wind" to your runner. You want to have your runner go into a set direction.
    Add some speed variables and if you want, also let them be arguments for your script.
    Code:
    var array = argument0;
    var X = argument1;
    var Y = argument2;
    var str = argument3;
    var sps = argument4;
    var xspd = argument5;
    var yspd = argument6;
    var str_ = str;
    var sps_ = sps;
    var dir = random(360);
    
    while (sps_ > 0)
    {
        // calc real strength
        str_ = str * (sps_ / sps);
     
        // reduce runner lifetime
        sps_--;
    
        // keeping the runner inbounds to avoid out-of-bounds errors
        var x1 = max(X - 0.5 * str_, 0);
        var y1 = max(Y - 0.5 * str_, 0);
        var x2 = min(X + 0.5 * str_, wdt);
        var y2 = min(Y + 0.5 * str_, hgt);
    
        // eat away at the terrain
        for (var i = x1; i < x2; i++)
        {
            for (var j = y1; j < y2; j++)
            {
                if (abs(i-X) + abs(j-Y) < 0.50 * str_)
                {
                    array[@ i, j] = 0;
                }
            }
        }
    
        // move the runner in a random direction
        if (!random(3))
        {
            dir += random_range(45, -45); // don’t allow the runner to make sharp corners by limiting it to 45° degree turns
        }
     
        // move the runner
        X += xspd + lengthdir_x(1.00, dir);
        Y += yspd + lengthdir_y(1.00, dir);
    }
    
    The last 2 lines now always make the position move by your speed on top of the random direction the runner takes.
    Code:
    repeat (10)
    {
        tile_runner(global.tile, 150, 50, 10, 100, 0, 2);
     // tile_runner(array, startx, starty, strength, steps, xspd, yspd)
    }
    
    https://imgur.com/a/7lSTm5u

    Of course, you can also make events happen like splitting a runner into 2 shorter runners or
    reverse the direction of a runner at the end of it's lifetime and recurse it.
    This is dangerous though as now you're giving the runner the ability to live forever and freezing your generation process.
    It's important to add a check or a fail save that keeps track of recursions.
    This tracker must be an instance variable as it should not be reset inside the runner script as a local variable.
    Example:
    Code:
    recursions = 10;
       tile_runner(global.tile, 150, 50, 10, 100, 340);
    // tile_runner(array, startx, starty, strength, steps, dir)
    
    Code:
    var array = argument0;
    var X = argument1;
    var Y = argument2;
    var str = argument3;
    var sps = argument4;
    var dir = argument5;
    
    while (sps > 0)
    {
        // reduce runner lifetime
        sps--;
    
        // keeping the runner inbounds to avoid out-of-bounds errors
        var x1 = max(X - 0.5 * str, 0);
        var y1 = max(Y - 0.5 * str, 0);
        var x2 = min(X + 0.5 * str, wdt);
        var y2 = min(Y + 0.5 * str, hgt);
    
        // eat away at the terrain
        for (var i = x1; i < x2; i++)
        {
            for (var j = y1; j < y2; j++)
            {
                if (abs(i-X) + abs(j-Y) < 0.50 * str)
                {
                    array[@ i, j] = 0;
                }
            }
        }
     
        // slight path alterations
        dir += random_range(1, -1);
     
        // move the runner
        X += lengthdir_x(1.00, dir);
        Y += lengthdir_y(1.00, dir);
    }
    
    if (recursions-- > 0)
    {
        tile_runner(global.tile, X, Y, str, random_range(30, 50), choose(200, 340));
    }
    
    If there are recursions left, the runner starts from where the old runner died.
    https://imgur.com/a/9xiI3ar

    Selection Runners
    Selection runners are tile runners that work less on math and more on user input.
    The runner chooses from several patterns that are set by the user.

    I've prepared 5 patterns for this example
    0: go straight
    1: make a slow turn clockwise
    2: make a slow turn anti clockwise
    3: make a sharp turn clockwise
    4: make a sharp turn anti clockwise

    The runner will choose one of these but not entirely random.
    A chance variable will keep track of how likely the runner is to switch off from a pattern.

    In code form it looks like this
    Code:
    // select 1 of 5 curve types
    if (!random(chance))
    {
        curve = irandom(4);
    }
    
    // evaluate new direction via curve type
    switch (curve)
    {
        case 0: chance--; break;
        case 1: dir += 1.00; chance = 15; break;
        case 2: dir -= 1.00; chance = 15; break;
        case 3: dir += 2.00; chance = 8; break;
        case 4: dir -= 2.00; chance = 8; break;
    }
    
    It is simply put inside the runner though it doesn't go unnoticed in time cost to execute this every step of the runner.

    I've put some thinking in the curve types aswell.
    Notice how the sharper turns have a higher chance to be rerolled, this is to prevent revolutions.
    The first curve type makes sure that straight paths don't get to long by increasing the chance to change the curve type every step.

    The outcome is this:
    https://imgur.com/a/8PbPwBl

    Wave Runners
    Wave runners are tile runners that curve in a sinus wave.
    The user can determine how many revolutions the wave makes and how high the waves get.
    Code:
    wave_runner(global.tile, 500, 500, 10, 1000, 4, 80);
    
    Code:
    /// wave_runner(array, x, y, str, sps, revs, hgt)
    var array = argument0;
    var X = argument1;
    var Y = argument2;
    var str = argument3;
    var sps = argument4;
    var revs = argument5;
    var hgt = argument6;
    var dir = random(360);
    var dps = (360 / sps) * revs;
    
    while (sps > 0)
    {
        // runner aging
        sps--;
     
        // limit
        var x1 = max(X - 0.5 * str, 0);
        var y1 = max(Y - 0.5 * str, 0);
        var x2 = min(X + 0.5 * str, w);
        var y2 = min(Y + 0.5 * str, h);
     
        // run
        for (var i = x1; i < x2; i++) {
        for (var j = y1; j < y2; j++) {
            if (array[i, j] > 0)
            {
                if (abs(i-X) + abs(j-Y) < 0.50 * str)
                {
                    array[@ i, j] = 0;
                }
            }
        }}
     
        // random dir
        if (!random(5)) {
            dir += random_range(15, -15);
        }
     
        // sinus curve
        var sinus = sps * dps;
        var real_dir = dir + lengthdir_x(hgt, sinus);
     
        // move the runner
        X += lengthdir_x(1.00, real_dir);
        Y += lengthdir_y(1.00, real_dir);
    }
    
    dps stands for degrees per step and is required for the runner to know how many degrees
    it has to change so that all sinus wave revolutions can be done until the runner dies.

    I've included certain randomness to the main path so that it wouldn't look too unrealistic.

    The outcome
    https://imgur.com/a/la1tfG5

    Community tricks
    by GMWolf:
    A faster way to achieve alteration tothe circular brush is using
    Code:
    if (sqr(i - X) + sqr(j - Y) < sqr(0.5 * str))
    
    over
    Code:
    if (sqrt(sqr(i - X) + sqr(j - Y)) < 0.5 * str)
    
    as now, it is no longer necessary to calculate the square root of one if we can square the other instead.
    Important is however, that you include the 0.5 as well inside the square function.

    by GMWolf:
    It is faster to first check for the tile's existence before doing heavier distance calculation with them.

    by Me:
    Apparently, doing the limit checks with if-statements is faster than doing them with the max and min functions. This is unfortunate because I really like the format of min and max.
    Code:
    if (x1 < 0) x1 = 0;
    if (y1 < 0) y1 = 0;
    if (x2 > w) x2 = w;
    if (y2 > h) y2 = h;
    
     
    Last edited: Nov 9, 2018
    ROK, chamaeleon, Posh Indie and 6 others like this.
  2. Bentley

    Bentley Member

    Joined:
    Jun 18, 2017
    Posts:
    609
    This looks very cool. The comments and diagram help a lot. I like how you round the edges of the area the worm is eating.
     
    Last edited: Sep 18, 2018
    Simon Gust likes this.
  3. Simon Gust

    Simon Gust Member

    Joined:
    Nov 15, 2016
    Posts:
    2,967
    Part 2 added! Get to know your tile brushes and bring shape into your caves.
     
  4. NightFrost

    NightFrost Member

    Joined:
    Jun 24, 2016
    Posts:
    1,456
    Reminds me about drunkard walk method, as the movement method is the same (randomized). Having lifetime for the runner is an interesting idea, the guidance I used on my implementation just had them die if everything around them had been dug out. It also had a low chance (5% I recall) of spawning new runners from existing ones every step, for branching effect. I modified it a bit by having the random movement bias towards the center of map, proportional to distance from center. Near to edges the bias would be strong enough to only allow 180 degree arc towards the center, so the runner would never run out of bounds. This results in roughly circular cave systems.

    The "brush" used was always just 1 tile though, so it could generate pretty patchy-looking caves if the runners crossed a certain area frequently. I added a cleanup script that removed wall tiles with no neighbours at around 90% chance (so a small number would still remain).
     
    Bentley likes this.
  5. Misty

    Misty Member

    Joined:
    Jun 22, 2016
    Posts:
    865
    I don't get it. Where is the terrain I get at the end of this? I just see a picture of black and a white blob.
     
    SnotWaffle Studios likes this.
  6. Simon Gust

    Simon Gust Member

    Joined:
    Nov 15, 2016
    Posts:
    2,967
    I'll add runner properties in part 3. You can do so many things with runners it's absurd.

    come on now, you have give it some thinking too. In my example I showed only a single runner being executed.
    In a real example I would have it set up like this
    Code:
    repeat (100)
    {
        tile_runner(global.tile, random_range(0, 300), random_range(0, 300), random_range(4, 8), random_range(120, 300));
    }
    
     
  7. Misty

    Misty Member

    Joined:
    Jun 22, 2016
    Posts:
    865
    See my latest thread called tired of it.

    If your code does not produce a discernible end result I'm not going to cost my energy to try and comprehend it.

    For example, if a scientist had a page of equations, and I aksed, "What does it do" and he told me "Not sure yet", I would not spend time learning the equations.

    When I see auto-generated terrain, I expect it can generate levels like this for me.
    [​IMG]
    or this
    [​IMG]

    When you can't show me what it can do, its not worth my time.

    All I see is some MS Paint scribbles. I can do that in MS Paint already, I don't need a generator for that.
     
  8. Simon Gust

    Simon Gust Member

    Joined:
    Nov 15, 2016
    Posts:
    2,967
    Carve your learning experience how you want it then. I am not forcing you to participate in my class, and if you don't want to, then please hush.
    The scribles are not an actual representation of how they look like in a game, they show a visual represantation of an array where black is terrain and white is air.

    And also, I don't give happy endings, if you want sh*t done, pay me.
     
  9. Misty

    Misty Member

    Joined:
    Jun 22, 2016
    Posts:
    865
    If you want to get paid, then you need to advertise, what your product can do.
     
  10. Simon Gust

    Simon Gust Member

    Joined:
    Nov 15, 2016
    Posts:
    2,967
    exactly, and here, I am clearly not advertising a product. I am teaching how to do a certain thing.
    You can be grateful that I don't just put a tile runner as a script for a marketplace purchase.
     
  11. GMWolf

    GMWolf aka fel666

    Joined:
    Jun 21, 2016
    Posts:
    3,164
    This is a tutorial...
    Misty, are you ok?
     
  12. Misty

    Misty Member

    Joined:
    Jun 22, 2016
    Posts:
    865
    No. I made a cool thread, and it got closed.

    I don't see how it is terrain generation. It sounds more like cave generation. And it doesn't explain how to tile the actual graphics of the walls.
     
  13. IgniFerroque

    IgniFerroque Member

    Joined:
    Aug 28, 2017
    Posts:
    21
    Here you go.
    https://marketplace.yoyogames.com/assets/5055/grid-auto-tile-47

    Code:
    for (var xx = 0; i < grid_width; xx++)
    {
       for (var yy= 0; j < grid_height; yy++)
       {
        scr_update_tile(ds_grid_for_map,xx,yy, tilemap_id, 1);
        }
    }
    
    EDIT: four things this can be useful for (as far as is see)
    Rivers
    mountain ranges
    biomes
    as a mask for a noise function.
     
    Last edited: Sep 19, 2018
    Simon Gust likes this.
  14. GMWolf

    GMWolf aka fel666

    Joined:
    Jun 21, 2016
    Posts:
    3,164
    Terrain generation is more than just a single algorithm.
    It's a collection of algorithms, each reading into each other to form the final result.
    So having a firm grasp of each technique used is paramount to achieve good results.
     
  15. Misty

    Misty Member

    Joined:
    Jun 22, 2016
    Posts:
    865
    I don't get how that auto-tile thing will be useful for terrain. Also, there are better autotiles in the marketplace, like this or this. But those can't make terrain either.

    Simon's end result looks somewhat similar to rivers, but unlike any rivers I have ever seen. And it contains no depth information to be used for mountain ranges.
     
  16. IgniFerroque

    IgniFerroque Member

    Joined:
    Aug 28, 2017
    Posts:
    21
    Then adapt the alogirthm.
    And as on the usage of the algorithm for mountain ranges
    a) use it as a mask for a noise function
    b) if you want more detailed gradients,even it out with function or change the "brush"
    c) height information is not always needed to make a map
     
  17. Misty

    Misty Member

    Joined:
    Jun 22, 2016
    Posts:
    865
    I thought this was a tutorial.

    As a student, I don't have any idea on how to adapt the algorithm, in order to use it for terrain. Height information is needed to make terrain, that is if this is actually for terrain and not a cave as was implied earlier. If it is a cave then I would politely ask simon to change the topic title to cave tutorial.

    The other thing is, if it is for a cave, even a side view platformer cave, the pixel size is just too blocky, even more blocky than an Atari game.

    I resized it to 800%, even then its still not big enough and there's parts where Mario can't fall through. In order for all areas to be big enough for players it would have to be 2-4x as blocky as this picture:
    [​IMG]

    Now, you could shrink mario, but either way, you get an inevitable blocky, Atari ish result. When I made my lofi thread, I didn't mean all the way back to Atari lofi.
     
    Last edited: Sep 19, 2018
  18. IgniFerroque

    IgniFerroque Member

    Joined:
    Aug 28, 2017
    Posts:
    21
    Procedural terrain generation is one of the most complicated things to do well. As it involves a great number of different usable algorithms to choose from which are put into a great blender and vomitted on one or multiple 2d arrays (or grids) and then interpreted with a "renderer" or "interpreter" to make something to look at.

    If you want to use procedural generation for a jump'n run you should take a look at the spelunky level generator tutorial


    Or if you want to use this tutorial for something like that, you should use a cellular automata on the grid from here
    https://forum.yoyogames.com/index.php?threads/cellular-automata-cave-generation.37895/


    But you wont find ANY procedural terrain generation tutorial which shows how to create "great looking worlds" for any language. The best documented sources are
    https://www.redblobgames.com/
    https://heredragonsabound.blogspot.com/
     
  19. Posh Indie

    Posh Indie Member

    Joined:
    Dec 5, 2016
    Posts:
    166
    @Simon Gust Well written tutorial, and if anyone had any interest in procedural generation they would know how to take this the rest of the way.
     
    Last edited by a moderator: Sep 20, 2018
    chamaeleon, Simon Gust and GMWolf like this.
  20. DarkFireDemon

    DarkFireDemon Member

    Joined:
    Sep 20, 2017
    Posts:
    27
    This a excellent tutorial. I can see this as a going to use in a Terraria style game to generate tunnels.
     
    Simon Gust likes this.
  21. GMWolf

    GMWolf aka fel666

    Joined:
    Jun 21, 2016
    Posts:
    3,164
    I read through the tutorial again, and I did find an optimization to be made if the circular brush is still too slow.
    Rather than using point_distance, you can calculate the distance squared and avoid a square root operation:
    Code:
    if (sqr(i - X) + sqr(j - Y)) < sqr(str)
    
    This should provide a measurable performance increase.
    You can also check if the tile has been already eaten before doing the distance check. (Though, that may depend on if the value is already in cache or not..., More testing required)

    I am also a little confused about the fast brush, I don't quite understand how this will run faster, as it seems to me like the number of distance checks remains the same.
    Perhaps a more detailed explanation would help?



    This tutorial has gotten me quite curious in tile runners, I'll have to see what I can come up with! Also very curious to see where the tutorial takes us (hoping for some cool twisting around on a heightmap according to gradient or something ;) )
     
    Last edited by a moderator: Sep 20, 2018
    Simon Gust likes this.
  22. Simon Gust

    Simon Gust Member

    Joined:
    Nov 15, 2016
    Posts:
    2,967
    This is faster, noticably even. Thank you very much for being interested in my tutorial in a positive way. Really appreciate it :)
    I'll see what I can do to explain it better.
    Basically, the fast brush replaces the need to check the array if the tile isn't already empty. And since reading an array is slower than reading a variable, it should come out faster. Especially, if you choose to have a rectangular brush you don't have to add a second distance check.
    If you tell the runner to ignore tiles that were eaten in the radius of the old runner position, it should be faster than checking every array entry if they're not already eaten.
     
  23. Simon Gust

    Simon Gust Member

    Joined:
    Nov 15, 2016
    Posts:
    2,967
    Terraria uses tile runners. Thats also where I got the idea from, except they do it kinda slow and inefficient.
     
  24. Simon Gust

    Simon Gust Member

    Joined:
    Nov 15, 2016
    Posts:
    2,967
    So I tested again with the squaring of the number but I made a mistake when testing. It seems that point_distance is still faster afterall because internal optimization. Nothing is lost though as if you decide to make your own shape like an elipse, you can still get a lot of use out of the new formular just by altering some numbers.

    I also tested the array check before distance check thesis, and it also is faster, especially if your runners are more dense.
    In addition to that, it also invalidates the speed bonus of the fast brush.

    I'll update all this when I get home. Thanks for contribution.
     
  25. GMWolf

    GMWolf aka fel666

    Joined:
    Jun 21, 2016
    Posts:
    3,164
    Oooh, that's quite interesting!
    GML really is slow! This completely changes my outlook on GML optimization: built in functions before reducing instructions...
     
  26. NightFrost

    NightFrost Member

    Joined:
    Jun 24, 2016
    Posts:
    1,456
    Now that's... interesting. I've been using the distance squared trick in some max distance cutoff checks, thinking it'd be faster because point_distance is going to have to take a slow square root internally, but apparently I've slowed down my code instead.
     
  27. Simon Gust

    Simon Gust Member

    Joined:
    Nov 15, 2016
    Posts:
    2,967
    Part 3 added: Runner properties.
     
  28. Simon Gust

    Simon Gust Member

    Joined:
    Nov 15, 2016
    Posts:
    2,967
    I went ahead and generated a world as fast as possible.
    The world is just a giant spaghetti cave system for now.
    World size: 2000 x 2000 (scaled 4x)
    upload_2018-9-21_14-53-13.png
    Time required: ~420 ms

    I tested this with GMLive in my browser. So it possibly is even faster in GMS itself.
     
  29. Simon Gust

    Simon Gust Member

    Joined:
    Nov 15, 2016
    Posts:
    2,967
    Added new runner type: Selection Runners
     
    GMWolf likes this.
  30. Simon Gust

    Simon Gust Member

    Joined:
    Nov 15, 2016
    Posts:
    2,967
    Added new runner type: Wave Runners
     
    GMWolf likes this.
  31. Simon Gust

    Simon Gust Member

    Joined:
    Nov 15, 2016
    Posts:
    2,967
    Thought I might add this.
    You can get a semi-round brush if you combine the rectangular brush with the diamon brush.
    The code is the same for the diamond brush except the radius to check is greater.
    Code:
    if (abs(i-X) + abs(j-Y) < str * 0.75)
    
    I changed the 0.5 to a 0.75 and your brush should look something like this
    upload_2018-11-9_16-43-14.png
    Technically, it is just a bigger diamond shape, but the edges are cut due to the double for loop range limitation.
    An octagon brush if you will.
     
    GMWolf likes this.

Share This Page

  1. This site uses cookies to help personalise content, tailor your experience and to keep you logged in if you register.
    By continuing to use this site, you are consenting to our use of cookies.
    Dismiss Notice