GameMaker Removing small chunks

[Thijmen Langendam]

Heyo, so i recently started on random world generation, and this is a small piece of the result so far:

I was wondering if there was an easy way to remove the ponds that are smaller than a certain size. For example, at the top you see a pond of size 3, below that (shaped like a sideways F) that pond is size 6. Is there an easy and non-intensive way of removing all ponds that have less than 10 blocks of water?

Kind regards.

 

[Strawbry_jam]

Hard to say without any code. Any solution will be dependent on how you implemented it.

 

[Alex_Beach]

Yeah, we need to see some code. You could set a minimum area so that smaller chunks would either have to fit the minimum, or wouldn't exist

 

[FrostyCat]

The most basic solution is to implement a flood-fill script (recommended pseudocode here), derive a similar script for determining if the fill area is smaller than a given size, then use them both in a simple loop:

• For xx from 0 to width-1:
  • For yy from 0 to height-1:
    • If (xx, yy) is water and the flood fill area from (xx, yy) is less than the given size:
      • Flood fill at (xx, yy) with land

 

[Thijmen Langendam]

Hard to say without any code. Any solution will be dependent on how you implemented it.

Yeah, we need to see some code. You could set a minimum area so that smaller chunks would either have to fit the minimum, or wouldn't exist

Basically i just create a world full of water, then start at the center, make it grass, go randomly to either the north, south, east or west, then make that tile grass and repeat the process.

After this is done i have a function that checks if a certain piece of grass is a beach or not, and turn it into sand if it is.

 

[Thijmen Langendam]

The most basic solution is to implement a flood-fill script (recommended pseudocode here), derive a similar script for determining if the fill area is smaller than a given size, then use them both in a simple loop:

• For xx from 0 to width-1:
  • For yy from 0 to height-1:
    • If (xx, yy) is water and the flood fill area from (xx, yy) is less than the given size:
      • Flood fill at (xx, yy) with land

I tried this, but the only way i knew how to create that function was:
- Create an array with the size of the world that would be there to check if it had checked a certain tile yet.
- Then if the tile has not been checked yet, add 1 to the total and recursively call the function on all 4 neighbouring tiles.
(however initializing an array of size 10k+ in both the x and y dimensions is quite intensive and probably not optimal in any way).

 

[drowned]

After this is done i have a function that checks if a certain piece of grass is a beach or not, and turn it into sand if it is.

so have this function (or another one) also check to see if a certain adjacent body of water contains ten or more pixels of water and change them to grass if not, rather than to beach

 

[Thijmen Langendam]

so have this function (or another one) also check to see if a certain adjacent body of water contains ten or more pixels of water and change them to grass if not, rather than to beach

Yeah i understand this, but how would i approach the problem of calculating the "pond size" without creating data-structures that take insanely long to initialize and iterate through?
Because i assume i need a function to check the beach size that uses some sort of "matrix" like data-structure that saves if a certain tile has already been added to the pond size or not to prevent infinite loops.

 

[drowned]

...how did you approach the problem of calculating whether a certain piece of grass is beach or not?

 

[Thijmen Langendam]

...how did you approach the problem of calculating whether a certain piece of grass is beach or not?

Simple function that checks if the to be checked piece is land, and if it has at least 1 water tile directly touching it.

 

[drowned]

So why can't you do the same thing for water? Simple function that checks if the tile to be checked is water and recursively checks adjacent tiles to add up the total area of water?

 

[Thijmen Langendam]

So why can't you do the same thing for water? Simple function that checks if the tile to be checked is water and recursively checks adjacent tiles to add up the total area of water?

I want to do this, this was my initial idea, but how do i save if a certain tile of water has already recursively been checked without using data-structures that are intensive to initialize/use when having gigantic game levels.

 

[drowned]

How about by coordinates

 

[Thijmen Langendam]

How about by coordinates

But then i'd still need some sort of data-structure that keeps track if certain coordinates have been checked already or not.

 

[drowned]

So what? The ponds are self-contained. Once your recursive algorithm finishes you can wipe out the data structure until you hit the next pond.

Edit: That would only account for ponds which are small and get filled in. If you don't want it to spend time checking large ponds over and over, and you also don't want to store the data in memory, what if you have two sets of water tiles... one for the temporary "pre-checked" state and one for post-checked which would be applied to ponds of the appropriate size.

 

[Thijmen Langendam]

So what? The ponds are self-contained. Once your recursive algorithm finishes you can wipe out the data structure until you hit the next pond.

That's not the point, my worlds go up to 10k by 10k tiles, if we use a simple 2D array to save this it takes a tremendous amount of time.
Unless there are other ways of saving this data next to 2D array's (matrices).

 

[drowned]

I follow, but here's what I'm imagining. You are iterating over the map to check each tile for water right? You hit water and run the recursive function to calculate the size of the lake. If it's too small, you fill it with land. If it's large enough, you replace the temporary water tiles with permanent water tiles. When you're checking the map, you skip permanent water and grass. You only need to store coordinates of temporary water tiles during the area-calc function. As soon as you fill in or convert to permanent water, you wipe the structure. No need to store a 10k x 10k matrix.

 

[Thijmen Langendam]

I follow, but here's what I'm imagining. You are iterating over the map to check each tile for water right? You hit water and run the recursive function to calculate the size of the lake. If it's too small, you fill it with land. If it's large enough, you replace the temporary water tiles with permanent water tiles. When you're checking the map, you skip permanent water and grass. You only need to store coordinates of temporary water tiles during the area-calc function. As soon as you fill in or convert to permanent water, you wipe the structure. No need to store a 10k x 10k matrix.

Good point, i'll try this

 

[Thijmen Langendam]

I follow, but here's what I'm imagining. You are iterating over the map to check each tile for water right? You hit water and run the recursive function to calculate the size of the lake. If it's too small, you fill it with land. If it's large enough, you replace the temporary water tiles with permanent water tiles. When you're checking the map, you skip permanent water and grass. You only need to store coordinates of temporary water tiles during the area-calc function. As soon as you fill in or convert to permanent water, you wipe the structure. No need to store a 10k x 10k matrix.

Allright it works now, but it's very slow and if i press R (reloading the room) it crashes, if not, it'll crash the second time i reload the room or it'll generate an empty room, odd..

 

[drowned]

The very slow might be a symptom of the design or the implementation, or both. The crashing is likely a mistake you made, right?. If it crashes on the second reload, maybe you have a memory leak?

 

[Thijmen Langendam]

The very slow might be a symptom of the design or the implementation, or both. The crashing is likely a mistake you made, right?. If it crashes on the second reload, maybe you have a memory leak?

For some reason the crashing when re-running was temporary, when i use the following code to remove small "ponds" it completely crashes.

Code snippet that (should) remove(s) ponds:

var pond_check_grid = ds_grid_create(grid_width, grid_height);

for (var xcoord = 1; xcoord < grid_width-1; xcoord++) {
    for (var ycoord = 1; ycoord < grid_height-1; ycoord++) {
        if (ds_grid_get(level_grid, xcoord, ycoord) == temp_water_id) {
            ds_grid_set_region(pond_check_grid, 0, 0, grid_width-1, grid_height-1, false);
            var pondsize = pond_check(pond_check_grid, xcoord, ycoord);
            if (pondsize < 10) {
                ds_grid_set(level_grid, xcoord, ycoord, grass_id);
            }
        }
    }
}

pond_check(in_grid, xcheck, ycheck) below:

var in_grid = argument0;
var xcheck = argument1;
var ycheck = argument2;

if (xcheck < 1 || ycheck < 1 || xcheck >= grid_width || ycheck >= grid_height) {
    return 0;
}

if (ds_grid_get(level_grid, xcheck, ycheck) != temp_water_id) {
    return 0;
}

if (ds_grid_get(in_grid, xcheck, ycheck) == false) {
    ds_grid_set(in_grid, xcheck, ycheck, true);
    return (1 + pond_check(in_grid, xcheck+1, ycheck)
                        + pond_check(in_grid, xcheck, ycheck+1)
                        + pond_check(in_grid, xcheck-1, ycheck)
                        + pond_check(in_grid, xcheck, ycheck-1));
}

 

[Simon Gust]

Must be a recursive crash.
Thread on the issue
https://forum.yoyogames.com/index.php?threads/recursion.16562/