# GM:S 1.4 Randomly generated terrain using tile runners

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

Tags:
1. ### Simon GustMember

Joined:
Nov 15, 2016
Posts:
3,086
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.

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.

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:

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.

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

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
Binsk, immortalx, ROK and 8 others like this.
2. ### BentleyMember

Joined:
Jun 18, 2017
Posts:
721
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 GustMember

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

4. ### NightFrostMember

Joined:
Jun 24, 2016
Posts:
1,757
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. ### MistyMember

Joined:
Jun 22, 2016
Posts:
1,005
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 GustMember

Joined:
Nov 15, 2016
Posts:
3,086
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. ### MistyMember

Joined:
Jun 22, 2016
Posts:
1,005
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.

or this

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 GustMember

Joined:
Nov 15, 2016
Posts:
3,086
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. ### MistyMember

Joined:
Jun 22, 2016
Posts:
1,005
If you want to get paid, then you need to advertise, what your product can do.

10. ### Simon GustMember

Joined:
Nov 15, 2016
Posts:
3,086
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. ### GMWolfaka fel666

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

12. ### MistyMember

Joined:
Jun 22, 2016
Posts:
1,005
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. ### IgniFerroqueMember

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. ### GMWolfaka fel666

Joined:
Jun 21, 2016
Posts:
3,241
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. ### MistyMember

Joined:
Jun 22, 2016
Posts:
1,005
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. ### IgniFerroqueMember

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. ### MistyMember

Joined:
Jun 22, 2016
Posts:
1,005
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:

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. ### IgniFerroqueMember

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 IndieMember

Joined:
Dec 5, 2016
Posts:
182
@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
20. ### DarkFireDemonMember

Joined:
Sep 20, 2017
Posts:
30
This a excellent tutorial. I can see this as a going to use in a Terraria style game to generate tunnels.

Binsk and Simon Gust like this.
21. ### GMWolfaka fel666

Joined:
Jun 21, 2016
Posts:
3,241
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 GustMember

Joined:
Nov 15, 2016
Posts:
3,086
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 GustMember

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

24. ### Simon GustMember

Joined:
Nov 15, 2016
Posts:
3,086
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. ### GMWolfaka fel666

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

26. ### NightFrostMember

Joined:
Jun 24, 2016
Posts:
1,757
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 GustMember

Joined:
Nov 15, 2016
Posts:
3,086
Part 3 added: Runner properties.

28. ### Simon GustMember

Joined:
Nov 15, 2016
Posts:
3,086
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)

Time required: ~420 ms

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

29. ### Simon GustMember

Joined:
Nov 15, 2016
Posts:
3,086
Added new runner type: Selection Runners

GMWolf likes this.
30. ### Simon GustMember

Joined:
Nov 15, 2016
Posts:
3,086
Added new runner type: Wave Runners

GMWolf likes this.
31. ### Simon GustMember

Joined:
Nov 15, 2016
Posts:
3,086
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

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.
32. ### steveyg90Member

Joined:
Feb 27, 2017
Posts:
124
Kudos for this. I often use cellular automata for cave generation (I've got a thread in the design forum on this) but this seems very effective. Would be nice to get temperatures in here also to generate the likes
of biomes ;-)

33. ### LoadingDevelopmentMember

Joined:
Sep 10, 2017
Posts:
313
This tutorial is exactly what I expected from you @Simon Gust. Top notch.
Do you mind if I use it later, if I ever finish my first game, probably on a second commercial game?

34. ### Simon GustMember

Joined:
Nov 15, 2016
Posts:
3,086
Thank you, I don't mind. I can't legally stop you from stealing technology that I have already stolen.

LoadingDevelopment and immortalx like this.