generate a random cave for a ds_grid (Update 9/2/20)

lostdarkwolf · 2018-07-09 05:35:22

See the updated script in the post below this one.
- - -
No required scripts. Enjoy!
EDIT: The last script worked okay, but it took me a while to realize that the generation didn't exactly do what I wanted it to do. This script has been corrected in that regard, and is more flexible.

Expand/// generate_cave(ds_grid, path_repetitions*, expansion_repetitions*, smooth_repetitions*, safe_smoothing*, expansion_size_limit*, tries*, boundary_wall_width*)
// * argument not required
// 
// Turns a ds_grid into a simple boolean cave.
// The bigger the ds_grid is, the better the cave will look.
// 
// ds_grid                 The ds_grid to turn into a data-based cave. real
// path_repetitions        Approximate length of the initial cave path. real
// expansion_repetitions   How many times to randomly expand the cave. real
// smooth_repetitions      How many times to smooth the cave. If this value is -1, the script will then smooth until smoothing becomes redundant. real
// safe_smoothing          If true, smoothing will not create solids, just remove them. real
// expansion_size_limit    upper limit for the expansion radius, the lower limit is 1. real
// tries                   amount of tries for expansion. real
// boundry_wall_width      width of the solid edge around the ds_grid. Use zero for none. real
// 
// Generation avoids using noise.
// If safe_smoothing is on, every open point within the cave should be accessible.
// Expansion does not respect the ds_grid boundaries. Use it respectfully.
// Cell values are either one for solid, or zero for open.
//
/// GMLscripts.com/license

MAV_grid=argument[0];
var var_width; var_width=ds_grid_width(MAV_grid)-1;
var var_height; var_height=ds_grid_height(MAV_grid)-1;

var MAV_repetitions1; MAV_repetitions1=sqr(mean(var_width,var_height));
if argument_count>1 MAV_repetitions1=argument[1];
var MAV_repetitions2; MAV_repetitions2=mean(var_width,var_height);
if argument_count>2 MAV_repetitions2=argument[2];
var MAV_repetitions3; MAV_repetitions3=-1;
if argument_count>3 MAV_repetitions3=argument[3];
var var_safe_smoothing; var_safe_smoothing=1;
if argument_count>4 var_safe_smoothing=argument[4];
var MAV_expansion_size; MAV_expansion_size=floor(mean(var_width,var_height)/50);
if argument_count>5 MAV_expansion_size=argument[5];
var MAV_tries; MAV_tries=max(mean(var_width,var_height),100);
if argument_count>6 MAV_tries=argument[6];
var MAV_renew_boundary_wall_width; MAV_renew_boundary_wall_width=1;
if argument_count>7 MAV_renew_boundary_wall_width=argument[7];

//make the initial cave path
ds_grid_set_region(MAV_grid,0,0,var_width,var_height,1)
var iix, iiy, var_dir;
iix=floor(var_width/2);
iiy=floor(var_height/2);
repeat MAV_repetitions1 {
 ds_grid_set(MAV_grid,iix,iiy,0)
 var_dir=irandom(4);
 switch var_dir {
  case 0:
   iix+=1;
  break;
  case 1:
   iiy-=1;
  break;
  case 2:
   iix-=1;
  break;
  case 3:
   iiy+=1;
  break;
 }
 if iix<var_width*0.1 and irandom(var_width*0.1)=0 iix+=1;
 if iix>var_width*0.9 and irandom(var_width*0.1)=0 iix-=1;
 if iiy<var_height*0.1 and irandom(var_width*0.1)=0 iiy+=1;
 if iiy>var_height*0.9 and irandom(var_width*0.1)=0 iiy-=1;
 iix=median(round(iix),1,var_width-1);
 iiy=median(round(iiy),1,var_height-1);
}

// randomly expand the cave path
var iix, iiy, var_buddy_count;
if MAV_repetitions2>0 {
 var var_source_value, var_expand_way;
 var var_tries; var_tries=0;
 var var_runs_done; var_runs_done=0;
 var var_done; var_done=0;
 while var_done=0 {
  iix=median(2,irandom(var_width),var_width-2);
  iiy=median(2,irandom(var_height),var_width-2);
  var_source_value=ds_grid_get(MAV_grid,iix,iiy)
  if iix=2 or iix=var_width-2 var_source_value=1
  if iiy=2 or iiy=var_height-2 var_source_value=1
  var_buddy_count=ds_grid_get(MAV_grid,iix+1,iiy)+ds_grid_get(MAV_grid,iix,iiy-1)+ds_grid_get(MAV_grid,iix-1,iiy)+ds_grid_get(MAV_grid,iix,iiy+1)
  if not (var_source_value=1 and var_buddy_count=4 or var_source_value=0 and var_buddy_count=0) and var_source_value=0 {
   var_runs_done+=1;
   repeat irandom(2) {
    var_expand_way=irandom(3);
    var_expansion_size=1+random(MAV_expansion_size-1);
    if var_expand_way=0 ds_grid_set_disk(MAV_grid,iix+(var_expansion_size*0.75),iiy,var_expansion_size,var_source_value);
    if var_expand_way=1 ds_grid_set_disk(MAV_grid,iix,iiy-(var_expansion_size*0.75),var_expansion_size,var_source_value);
    if var_expand_way=2 ds_grid_set_disk(MAV_grid,iix-(var_expansion_size*0.75),iiy,var_expansion_size,var_source_value);
    if var_expand_way=3 ds_grid_set_disk(MAV_grid,iix,iiy+(var_expansion_size*0.75),var_expansion_size,var_source_value);
   }
  }
  else {
   var_tries+=1;
  }
  if var_tries>=MAV_tries var_done=1;
  if var_runs_done>=MAV_repetitions2 var_done=1;
 }
}

//smooth the cave
repeat max(MAV_repetitions3,0) {
 for (iix=var_width-1; iix>=1; iix-=1;) {
  for (iiy=var_height-1; iiy>=1; iiy-=1;) {
   var_buddy_count = ds_grid_get(MAV_grid,iix+1,iiy)+
                     ds_grid_get(MAV_grid,iix,iiy-1)+
                     ds_grid_get(MAV_grid,iix-1,iiy)+
                     ds_grid_get(MAV_grid,iix,iiy+1)+
                     ds_grid_get(MAV_grid,iix+1,iiy-1)+
                     ds_grid_get(MAV_grid,iix-1,iiy-1)+
                     ds_grid_get(MAV_grid,iix-1,iiy+1)+
                     ds_grid_get(MAV_grid,iix+1,iiy+1);
   if var_buddy_count<4 ds_grid_set(MAV_grid,iix,iiy,0)
   if var_buddy_count>5 and var_safe_smoothing=false ds_grid_set(MAV_grid,iix,iiy,1)
  }
 }
}
if MAV_repetitions3=-1 {
 var var_orig_val;
 var var_changes;
 var_changes=1;
 while var_changes>0 {
  var_changes=0;
  for (iix=var_width-1; iix>=1; iix-=1;) {
   for (iiy=var_height-1; iiy>=1; iiy-=1;) {
    var_buddy_count = ds_grid_get(MAV_grid,iix+1,iiy)+
                      ds_grid_get(MAV_grid,iix,iiy-1)+
                      ds_grid_get(MAV_grid,iix-1,iiy)+
                      ds_grid_get(MAV_grid,iix,iiy+1)+
                      ds_grid_get(MAV_grid,iix+1,iiy-1)+
                      ds_grid_get(MAV_grid,iix-1,iiy-1)+
                      ds_grid_get(MAV_grid,iix-1,iiy+1)+
                      ds_grid_get(MAV_grid,iix+1,iiy+1);
    if var_buddy_count<4 {
     var_orig_val=ds_grid_get(MAV_grid,iix,iiy);
     if var_orig_val!=0 {
      ds_grid_set(MAV_grid,iix,iiy,0)
      var_changes+=1;
     }
    }
    if var_buddy_count>5 and var_safe_smoothing=false {
     var_orig_val=ds_grid_get(MAV_grid,iix,iiy);
     if var_orig_val!=1 {
      ds_grid_set(MAV_grid,iix,iiy,1)
      var_changes+=1;
     }
    }
   }
  }
 }
}

// renew boundary wall
if MAV_renew_boundary_wall_width>0 {
 var var_line_number; var_line_number=0;
 repeat MAV_renew_boundary_wall_width {
  for (iix=var_width-1-var_line_number; iix>=1+var_line_number; iix-=1;) {
   ds_grid_set(MAV_grid,iix,var_line_number,1)
   ds_grid_set(MAV_grid,iix,var_height-1-var_line_number,1)
  }
  for (iiy=var_height-1-var_line_number; iiy>=1+var_line_number; iiy-=1;) {
   ds_grid_set(MAV_grid,var_line_number,iiy,1)
   ds_grid_set(MAV_grid,var_width-1-var_line_number,iiy,1)
  }
  var_line_number+=1;
 }
 for (iix=var_width-1-var_line_number; iix>=1+var_line_number; iix-=1;) {
  if irandom(1) ds_grid_set(MAV_grid,iix,var_line_number,1)
  if irandom(1) ds_grid_set(MAV_grid,iix,var_height-1-var_line_number,1)
 }
 for (iiy=var_height-1-var_line_number; iiy>=1+var_line_number; iiy-=1;) {
  if irandom(1) ds_grid_set(MAV_grid,var_line_number,iiy,1)
  if irandom(1) ds_grid_set(MAV_grid,var_width-1-var_line_number,iiy,1)
 }
}

Last edited by lostdarkwolf (2020-09-02 21:25:54)

lostdarkwolf · 2020-02-28 12:49:36

Update! This new script is more efficient and has zoning capabilities. If you aim to replace the old script, know that returned values do work differently. Zero is always solid, and three is the first zone value. Every number beyond 3 is for more zones. With zones, you can generate a biome-filled overworld map.

EDIT 9/2/20: There is now an example showcasing this collection of generation scripts, and more. Maze, Dungeon, Cave, and Overworld Example GMZ. Hosted at Host-a.net.
There has been a recent bugfix in the example. (Dungeon door refresh bug.)
EDIT 9/4/20: simple bugfix for proper room refreshing when pressing F5 in game presentation.

My device isnt that great, but this should give you an idea of how long this script can take.
with full smoothing
500 x 500 = 17.83 seconds
400 x 400 = 12.22 seconds
300 X 300 = 7.53 seconds
200 X 200 = 3.73 seconds
100 X 100 = 1.01 seconds
without smoothing
500 X 500 = 3.03 seconds
100 X 100 = 0.93 seconds

Expand///generate_cave(ds_grid, free_cells*, edge_limit*, smooth_power*, smooth_block*, zones*, xn_start*, yn_start*, convex_smooth_scope*, concave_smooth_scope*)
// * arguments are optional
// 
// Generates a cave-like splotch.
// See value key for ds_grid below.
// 
// ds_grid                ds_grid to splotch, or undefined  a new grid, real (ds_grid)
// free_cells             the number of free cells within the unsmoothed cave splotch, real (integer)
// edge_limit             size of the boundry that suppresses cave generation, real (integer)
// smooth_power           power of smoothing for the cave splotch, real (bool)
// smooth_block           blocks concave smoothing at 1, and convex smoothing at 2, real (integer)
// zones                  number of zones to generate within the splotch, real (integer)
// xn_start               starting x position of splotch generation, real (normal)
// yn_start               starting y position of splotch generation, real (normal)
// convex_smooth_scope    scope size for convex smoothing, ranges from 0 to 7, real (integer)
// concave_smooth_scope   scope size for concave smoothing, ranges from 1 to 8, real (integer)
// 
// The first zone (last generated) occors at 3. Other zones occor subsequently.
// Set argument smooth_power to -1 to smooth until smoothing becomes ineffective.
// - This causes significant slowdown with large ds_grids.
// If argument concave_smooth_scope is 6 or more, passages won't be blocked.
// Zones may not be fully connected.
//
/// GMLscripts.com/license

// value key for ds_grid:
// NOTE: Values 1 and 2 should never be seen.
// 0 = solid cell
// 1 = blocked generation cell (solid) (removed during generation cleanup)
// 2 = zoneless cell (free) (presence implies unsuccessful zone eyedrop during smoothing)
// 3 and up = zones (free)

var var_xsn, var_ysn, var_buddy_count, var_dsg, var_reps, var_chance_edge_limit, 
var_smooth_power, var_smoothing_block, var_dsg_width, var_dsg_height, 
var_potential_list_x, var_potential_list_y, var_iix, var_iiy, var_buddy_count, 
var_differ_check, var_concave_smooth_scope, var_convex_smooth_scope, var_zones, 
var_zone_wrap, var_eyedrop, var_grid_get;

var_dsg=argument[0];

var_reps=500;
if argument_count>1 var_reps=argument[1];

var_chance_edge_limit=12;
if argument_count>2 var_chance_edge_limit=argument[2];

var_smooth_power=1
if argument_count>3 var_smooth_power=argument[3];

var_smoothing_block=0
if argument_count>4 var_smoothing_block=argument[4];

var_zones=1
if argument_count>5 var_zones=argument[5]

var_xsn=0.5
if argument_count>6 var_xsn=argument[6]

var_ysn=0.5
if argument_count>7 var_ysn=argument[7]

var_convex_smooth_scope=3
if argument_count>8 var_convex_smooth_scope=median(0,7,argument[8])

var_concave_smooth_scope=6
if argument_count>9 var_concave_smooth_scope=median(1,8,argument[9])


var_dsg_width=ds_grid_width(var_dsg)
var_dsg_height=ds_grid_height(var_dsg)
var_potential_list_x=ds_list_create();
var_potential_list_y=ds_list_create();
var_iix=median(1,var_dsg_width-2,floor(var_dsg_width*var_xsn))
var_iiy=median(1,var_dsg_height-2,floor(var_dsg_height*var_ysn))

ds_grid_clear(var_dsg,0);
ds_grid_add(var_dsg,var_iix,var_iiy,3);

ds_list_add(var_potential_list_x,var_iix-1)
ds_list_add(var_potential_list_y,var_iiy)

ds_list_add(var_potential_list_x,var_iix)
ds_list_add(var_potential_list_y,var_iiy-1)

ds_list_add(var_potential_list_x,var_iix+1)
ds_list_add(var_potential_list_y,var_iiy)

ds_list_add(var_potential_list_x,var_iix)
ds_list_add(var_potential_list_y,var_iiy+1)

var_initial_limit=min(irandom_range(100, 1000),var_reps*0.2)
var_zone_wrap=ceil(var_reps/var_zones);
while var_reps>0 {
 // choose cell to free
 var_potential_list_size=ds_list_size(var_potential_list_x)
 if var_potential_list_size>var_initial_limit var_list_value=(var_potential_list_size-1)-irandom(  max(floor((var_potential_list_size*0.005)),3)  )
 else var_list_value=(var_potential_list_size-1)-irandom(  max(floor((var_potential_list_size*0.1)),3)  )
 
 var_iix=ds_list_find_value(var_potential_list_x,var_list_value)
 var_iiy=ds_list_find_value(var_potential_list_y,var_list_value)
 
 if ds_grid_get(var_dsg,var_iix,var_iiy)=0 {
  ds_list_delete(var_potential_list_x,var_list_value);
  ds_list_delete(var_potential_list_y,var_list_value);
  ds_grid_set(var_dsg,var_iix,var_iiy,3+floor(var_reps/var_zone_wrap));
  var_reps-=1;
 }
 else {
  ds_list_delete(var_potential_list_x,var_list_value);
  ds_list_delete(var_potential_list_y,var_list_value);
 }
 
 // potentialize neighbor cells
 if var_iix>1 { // west cell
  if ds_grid_get(var_dsg, var_iix-1, var_iiy)=0 {
   if var_iix>irandom(var_chance_edge_limit) {
    ds_list_add(var_potential_list_x,var_iix-1)
    ds_list_add(var_potential_list_y,var_iiy)
   }
   else {
    ds_grid_set(var_dsg, var_iix-1, var_iiy, 1)
   }
  }
 }

 if var_iiy>1 { // north cell
  if ds_grid_get(var_dsg, var_iix, var_iiy-1)=0 {
   if var_iiy>irandom(var_chance_edge_limit) {
    ds_list_add(var_potential_list_x,var_iix)
    ds_list_add(var_potential_list_y,var_iiy-1)
   }
   else {
    ds_grid_set(var_dsg, var_iix, var_iiy-1, 1)
   }
  }
 }

 if var_iix<var_dsg_width-2 { // south cell
  if ds_grid_get(var_dsg, var_iix+1, var_iiy)=0 {
   if var_iix<(var_dsg_width-1)-irandom(var_chance_edge_limit) {
    ds_list_add(var_potential_list_x,var_iix+1)
    ds_list_add(var_potential_list_y,var_iiy)
   }
   else {
    ds_grid_set(var_dsg, var_iix+1, var_iiy, 1)
   }
  }
 }

 if var_iiy<var_dsg_height-2 { // east cell
  if ds_grid_get(var_dsg, var_iix, var_iiy+1)=0 {
   if var_iiy<(var_dsg_height-1)-irandom(var_chance_edge_limit) {
    ds_list_add(var_potential_list_x,var_iix)
    ds_list_add(var_potential_list_y,var_iiy+1)
   }
   else {
    ds_grid_set(var_dsg, var_iix, var_iiy+1, 1)
   }
  }
 }
}

// generation cleanup
ds_list_destroy(var_potential_list_x);
ds_list_destroy(var_potential_list_y);
var_iix=1;
while var_iix<var_dsg_width-1 {
 var_iiy=1;
 while var_iiy<var_dsg_height-1 {
  if ds_grid_get(var_dsg, var_iix, var_iiy)=1 ds_grid_set(var_dsg, var_iix, var_iiy, 0)
  
  var_iiy+=1;
 }
 var_iix+=1;
}

// smoothing
if var_smooth_power=-1 var_smooth_power=9007199254740991;
while var_smooth_power>0 {
 var_smooth_count=0;
 var_iix=1;
 while var_iix<var_dsg_width-1 {
  var_iiy=1;
  while var_iiy<var_dsg_height-1 {
   var_buddy_count=0;
   var_eyedrop=2;
   var_grid_get=ds_grid_get(var_dsg, var_iix-1, var_iiy-1)
   if var_grid_get<=1 {
    var_buddy_count+=1
   }
   else var_eyedrop=var_grid_get
   var_grid_get=ds_grid_get(var_dsg, var_iix, var_iiy-1)
   if var_grid_get<=1 {
    var_buddy_count+=1
   }
   else var_eyedrop=var_grid_get
   var_grid_get=ds_grid_get(var_dsg, var_iix+1, var_iiy-1)
   if var_grid_get<=1 {
    var_buddy_count+=1
   }
   else var_eyedrop=var_grid_get
   var_grid_get=ds_grid_get(var_dsg, var_iix-1, var_iiy)
   if var_grid_get<=1 {
    var_buddy_count+=1
   }
   else var_eyedrop=var_grid_get
   var_grid_get=ds_grid_get(var_dsg, var_iix+1, var_iiy)
   if var_grid_get<=1 {
    var_buddy_count+=1
   }
   else var_eyedrop=var_grid_get
   var_grid_get=ds_grid_get(var_dsg, var_iix-1, var_iiy+1)
   if var_grid_get<=1 {
    var_buddy_count+=1
   }
   else var_eyedrop=var_grid_get
   var_grid_get=ds_grid_get(var_dsg, var_iix, var_iiy+1)
   if var_grid_get<=1 {
    var_buddy_count+=1
   }
   else var_eyedrop=var_grid_get
   var_grid_get=ds_grid_get(var_dsg, var_iix+1, var_iiy+1)
   if var_grid_get<=1 {
    var_buddy_count+=1
   }
   else var_eyedrop=var_grid_get
   
   if var_buddy_count<var_convex_smooth_scope and var_smoothing_block!=2 {
    var_differ_check=ds_grid_get(var_dsg, var_iix, var_iiy)
    if (var_differ_check<=1) != (var_eyedrop<=1) {
     ds_grid_set(var_dsg, var_iix, var_iiy, var_eyedrop)
     var_smooth_count+=1;
    }
   }
   if var_buddy_count>var_concave_smooth_scope and var_smoothing_block!=1 {
    var_differ_check=ds_grid_get(var_dsg, var_iix, var_iiy)
    if var_differ_check!=0 {
     ds_grid_set(var_dsg, var_iix, var_iiy, 0)
     var_smooth_count+=1;
    }
   }
   
   var_iiy+=1;
  }
  var_iix+=1;
 }
 if var_smooth_power>0 {
  if var_smooth_power=9007199254740991 {
   if var_smooth_count=0 var_smooth_power=0;
  }
  else {
   if var_smooth_count=0 var_smooth_power=0;
   else var_smooth_power-=1;
  }
 }
}

return var_dsg;

Last edited by lostdarkwolf (2020-09-04 13:34:14)

redeyesmaster · 2020-08-16 07:07:45

I would love to see an example of the code to use this script and a visual representation would be great as well. But from what I can tell this is quite impressive.

xot · 2020-08-17 16:07:36

Yeah, this is such a complex script, a demonstration would be very helpful.

I'm not yet sure what to do with submissions like this. It stretches my definition of "general purpose" but it seems very useful. There are a number of more complex examples that get sent as well. They are deserving of a better way of presenting them.

redeyesmaster · 2020-08-18 01:56:29

Ideally the genoration/perlin and physic's scripts should have a place of their own in the sripts page. Since they dont follow any of the other categories that well, and are frequently used. Similarly to chuck handling codes, and unique camera, and deactivate/activate codes.

I'll probably make something with this script if lostdarkwolf isnt on in a while. I would post it here if I do.

lostdarkwolf · 2020-09-02 03:16:08

Feel free to post and/or edit whatever, if you want. I don't mind. I will work on an example, but it wont be ready for about 12 to 48 hours (if nothing unexpected happens with my day plans).

redeyesmaster · 2020-09-04 23:00:26

Awesome looking forward to it. The other generation codes would be great to see too.

GMLscripts.com

#1 2018-07-09 05:35:22

generate a random cave for a ds_grid (Update 9/2/20)

#2 2020-02-28 12:49:36

Re: generate a random cave for a ds_grid (Update 9/2/20)

#3 2020-08-16 07:07:45

Re: generate a random cave for a ds_grid (Update 9/2/20)

#4 2020-08-17 16:07:36

Re: generate a random cave for a ds_grid (Update 9/2/20)

#5 2020-08-18 01:56:29

Re: generate a random cave for a ds_grid (Update 9/2/20)

#6 2020-09-02 03:16:08

Re: generate a random cave for a ds_grid (Update 9/2/20)

#7 2020-09-04 23:00:26

Re: generate a random cave for a ds_grid (Update 9/2/20)

Board footer