GMLscripts.com

Discuss and collaborate on GML scripts
Invert

You are not logged in.

#1 2018-07-05 04:33:39

lostdarkwolf
Member
Registered: 2015-11-19
Posts: 31

generate a random data-based maze for a ds_grid

This has MANY uses. Enjoy! There is five required scripts below.

Expand/// generate_maze(ds_grid, x_start*, y_start*)
// 
// Turns a ds_grid into a data-based maze. (See data values below.)
// Each cell only contains information about which neighbors the specified cell links foreward to.
// 
// ds_grid   The ds_grid to turn into a data-based maze. real
// x_start   The starting x coordinate for maze generation. real
// y_start   The starting y coordinate for maze generation. real
// 
// A dead end links to nothing, so it has its own maze value.
// Because of the way the maze is built, every point within the maze is accessible.
//
/// GMLscripts.com/license

/***************************\
|  DS_GRID MAZE VALUES:     |
|-1  = dead end             |
| 0  = full solid cell      |
| 1  = open right           |
| 2  = open up              |
| 3  = open left            |
| 4  = open down            |
| 5  = open up & down       |
| 6  = open left & right    |
| 7  = open right & up      |
| 8  = open right & down    |
| 9  = open left & down     |
| 10 = open left & up       |
| 11 = closed right         | 
| 12 = closed up            |
| 13 = closed left          |
| 14 = closed down          |
| 15 = full open            |
\***************************/

MAV_grid=argument[0];
MAV_x=0;
if argument_count>1 MAV_x=argument[1];
MAV_y=0;
if argument_count>2 MAV_y=argument[2];

var var_width; var_width=ds_grid_width(MAV_grid)-1;
var var_height; var_height=ds_grid_height(MAV_grid)-1;


ds_grid_set_region(MAV_grid,0,0,var_width,var_height,0); // maze values
var var_history_stack_x; var_history_stack_x=ds_stack_create(); // history
var var_history_stack_y; var_history_stack_y=ds_stack_create(); // history


var var_east_check, var_north_check, var_west_check, var_south_check, var_done, var_cell_value, var_found_cell;

var_cell_value=ds_grid_get(MAV_grid,MAV_x,MAV_y);

repeat ((var_width+1)*(var_height+1)) {
 var_found_cell=0;
 
 // check if the current cell can link to each neighboring cell
 if MAV_x<var_width var_east_check=ds_grid_get(MAV_grid,MAV_x+1,MAV_y)=0;
 else var_east_check=0;
 if MAV_y>0 var_north_check=ds_grid_get(MAV_grid,MAV_x,MAV_y-1)=0; 
 else var_north_check=0;
 if MAV_x>0 var_west_check=ds_grid_get(MAV_grid,MAV_x-1,MAV_y)=0;
 else var_west_check=0;
 if MAV_y<var_height var_south_check=ds_grid_get(MAV_grid,MAV_x,MAV_y+1)=0;
 else var_south_check=0;
 
 while var_found_cell=0 { // do not stop looping until a new cell is found
  var_cell_value=ds_grid_get(MAV_grid,MAV_x,MAV_y);
  
  if var_east_check+var_north_check+var_west_check+var_south_check>0 { // if ANY direction is availible
   chosen_dir=irandom(3); // make the direction choice random
   repeat 4 { // choose a direction that works
    var_done=0;
    if chosen_dir=0 and not var_east_check and not var_done {
     chosen_dir+=1;
     var_done=1;
    }
    if chosen_dir=1 and not var_north_check and not var_done {
     chosen_dir+=1;
     var_done=1;
    }
    if chosen_dir=2 and not var_west_check and not var_done {
     chosen_dir+=1;
     var_done=1;
    }
    if chosen_dir=3 and not var_south_check and not var_done {
     chosen_dir-=3;
     var_done=1;
    }
   }
 
   if chosen_dir=0 { // move current cell and write link choice to the maze grid and to the history stack.
    var_cell_value=maze_cell_generate(1,maze_cell_link_n(var_cell_value),maze_cell_link_w(var_cell_value),maze_cell_link_s(var_cell_value));
    ds_grid_set(MAV_grid,MAV_x,MAV_y,var_cell_value);
    ds_stack_push(var_history_stack_x,MAV_x);
    ds_stack_push(var_history_stack_y,MAV_y);
    MAV_x+=1;
    var_found_cell=1;
   }
   if chosen_dir=1 {
    var_cell_value=maze_cell_generate(maze_cell_link_e(var_cell_value),1,maze_cell_link_w(var_cell_value),maze_cell_link_s(var_cell_value));
    ds_grid_set(MAV_grid,MAV_x,MAV_y,var_cell_value);
    ds_stack_push(var_history_stack_x,MAV_x);
    ds_stack_push(var_history_stack_y,MAV_y);
    MAV_y-=1;
    var_found_cell=1;
   }
   if chosen_dir=2 {
    var_cell_value=maze_cell_generate(maze_cell_link_e(var_cell_value),maze_cell_link_n(var_cell_value),1,maze_cell_link_s(var_cell_value));
    ds_grid_set(MAV_grid,MAV_x,MAV_y,var_cell_value);
    ds_stack_push(var_history_stack_x,MAV_x);
    ds_stack_push(var_history_stack_y,MAV_y);
    MAV_x-=1;
    var_found_cell=1;
   }
   if chosen_dir=3 {
    var_cell_value=maze_cell_generate(maze_cell_link_e(var_cell_value),maze_cell_link_n(var_cell_value),maze_cell_link_w(var_cell_value),1);
    ds_grid_set(MAV_grid,MAV_x,MAV_y,var_cell_value);
    ds_stack_push(var_history_stack_x,MAV_x);
    ds_stack_push(var_history_stack_y,MAV_y);
    MAV_y+=1;
    var_found_cell=1;
   }
  }
  else { // back tracking
   ds_grid_set(MAV_grid,MAV_x,MAV_y,-1); // set dead end (or else an infinite loop will occor)
   while var_east_check+var_north_check+var_west_check+var_south_check=0 and ds_stack_size(var_history_stack_x)>0 {
    MAV_x=ds_stack_pop(var_history_stack_x);
    MAV_y=ds_stack_pop(var_history_stack_y);
    
    if MAV_x<var_width var_east_check=ds_grid_get(MAV_grid,MAV_x+1,MAV_y)=0;
    else var_east_check=0;
    if MAV_y>0 var_north_check=ds_grid_get(MAV_grid,MAV_x,MAV_y-1)=0; 
    else var_north_check=0;
    if MAV_x>0 var_west_check=ds_grid_get(MAV_grid,MAV_x-1,MAV_y)=0;
    else var_west_check=0;
    if MAV_y<var_height var_south_check=ds_grid_get(MAV_grid,MAV_x,MAV_y+1)=0;
    else var_south_check=0;
   }
  }
  if ds_stack_size(var_history_stack_x)=0 var_found_cell=1;
 }
}
ds_stack_destroy(var_history_stack_x);
ds_stack_destroy(var_history_stack_y);

This script might also help, but it is not required. This script also requires the five scripts below.

Expand///maze_dual_link(ds_grid)
// 
// Dual links maze tiles on a ds grid so they will link forward and backward.
//
// ds_grid   The maze or ds grid to dual link.
//
/// GMLscripts.com/license

/***************************\
|  DS_GRID MAZE VALUES:     |
|-1  = dead end             |
| 0  = full solid cell      |
| 1  = open right           |
| 2  = open up              |
| 3  = open left            |
| 4  = open down            |
| 5  = open up & down       |
| 6  = open left & right    |
| 7  = open right & up      |
| 8  = open right & down    |
| 9  = open left & down     |
| 10 = open left & up       |
| 11 = closed right         | 
| 12 = closed up            |
| 13 = closed left          |
| 14 = closed down          |
| 15 = full open            |
\***************************/

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 iix, iiy, var_current_value;
for (iix=var_width; iix>=0; iix-=1;) {
 for (iiy=var_width; iiy>=0; iiy-=1;) {
  var_current_value=ds_grid_get(MAV_grid,iix,iiy)
  if var_current_value=median(var_current_value,-1,15) {
   ds_grid_set(MAV_grid,iix,iiy,maze_cell_generate(maze_cell_link_e(var_current_value) or maze_cell_link_w(ds_grid_get(MAV_grid,iix+1,iiy)),
                                                   maze_cell_link_n(var_current_value) or maze_cell_link_s(ds_grid_get(MAV_grid,iix,iiy-1)),
                                                   maze_cell_link_w(var_current_value) or maze_cell_link_e(ds_grid_get(MAV_grid,iix-1,iiy)),
                                                   maze_cell_link_s(var_current_value) or maze_cell_link_n(ds_grid_get(MAV_grid,iix,iiy+1))));
  }
 }
}

REQUIRED SCRIPTS:  (five total)

Expand///maze_cell_generate(right,up,left,down)
// 
// returns a maze cell value given its accessible directions.
//
// right   true if the right cell can be accessed
// up      true if the upper cell can be accessed
// left    true if the left cell can be accessed
// down    true if the lower cell can be accessed
//
/// GMLscripts.com/license

/***************************\
|  DS_GRID MAZE VALUES:     |
| 0  = full solid cell      |
| 1  = open right           |
| 2  = open up              |
| 3  = open left            |
| 4  = open down            |
| 5  = open up & down       |
| 6  = open left & right    |
| 7  = open right & up      |
| 8  = open right & down    |
| 9  = open left & down     |
| 10 = open left & up       |
| 11 = closed right         | 
| 12 = closed up            |
| 13 = closed left          |
| 14 = closed down          |
| 15 = full open            |
\***************************/

//         right                up              left              down
if argument[0]=0 and argument[1]=0 and argument[2]=0 and argument[3]=0 return 0;
if argument[0]=1 and argument[1]=0 and argument[2]=0 and argument[3]=0 return 1;
if argument[0]=0 and argument[1]=1 and argument[2]=0 and argument[3]=0 return 2;
if argument[0]=0 and argument[1]=0 and argument[2]=1 and argument[3]=0 return 3;
if argument[0]=0 and argument[1]=0 and argument[2]=0 and argument[3]=1 return 4;
if argument[0]=0 and argument[1]=1 and argument[2]=0 and argument[3]=1 return 5;
if argument[0]=1 and argument[1]=0 and argument[2]=1 and argument[3]=0 return 6;
if argument[0]=1 and argument[1]=1 and argument[2]=0 and argument[3]=0 return 7;
if argument[0]=1 and argument[1]=0 and argument[2]=0 and argument[3]=1 return 8;
if argument[0]=0 and argument[1]=0 and argument[2]=1 and argument[3]=1 return 9;
if argument[0]=0 and argument[1]=1 and argument[2]=1 and argument[3]=0 return 10;
if argument[0]=0 and argument[1]=1 and argument[2]=1 and argument[3]=1 return 11;
if argument[0]=1 and argument[1]=0 and argument[2]=1 and argument[3]=1 return 12;
if argument[0]=1 and argument[1]=1 and argument[2]=0 and argument[3]=1 return 13;
if argument[0]=1 and argument[1]=1 and argument[2]=1 and argument[3]=0 return 14;
if argument[0]=1 and argument[1]=1 and argument[2]=1 and argument[3]=1 return 15;
Expand///maze_cell_link_e(maze_value)
// 
// returns true if the defined maze value is linked to the eastern neighbor cell.
// 
// maze_value   value contained in any one maze cell. real
// 
/// GMLscripts.com/license

/***************************\
|  DS_GRID MAZE VALUES:     |
| 0  = full solid cell      |
| 1  = open right           |
| 2  = open up              |
| 3  = open left            |
| 4  = open down            |
| 5  = open up & down       |
| 6  = open left & right    |
| 7  = open right & up      |
| 8  = open right & down    |
| 9  = open left & down     |
| 10 = open left & up       |
| 11 = closed right         | 
| 12 = closed up            |
| 13 = closed left          |
| 14 = closed down          |
| 15 = full open            |
\***************************/

if argument[0]=0 return 0;
if argument[0]=1 return 1;
if argument[0]=2 return 0;
if argument[0]=3 return 0;
if argument[0]=4 return 0;
if argument[0]=5 return 0;
if argument[0]=6 return 1;
if argument[0]=7 return 1;
if argument[0]=8 return 1;
if argument[0]=9 return 0;
if argument[0]=10 return 0;
if argument[0]=11 return 0;
if argument[0]=12 return 1;
if argument[0]=13 return 1;
if argument[0]=14 return 1;
if argument[0]=15 return 1;
Expand///maze_cell_link_n(maze_value)
// 
// returns true if the defined maze value is linked to the northern neighbor cell.
// 
// maze_value   value contained in any one maze cell. real
// 
/// GMLscripts.com/license

/***************************\
|  DS_GRID MAZE VALUES:     |
| 0  = full solid cell      |
| 1  = open right           |
| 2  = open up              |
| 3  = open left            |
| 4  = open down            |
| 5  = open up & down       |
| 6  = open left & right    |
| 7  = open right & up      |
| 8  = open right & down    |
| 9  = open left & down     |
| 10 = open left & up       |
| 11 = closed right         | 
| 12 = closed up            |
| 13 = closed left          |
| 14 = closed down          |
| 15 = full open            |
\***************************/

if argument[0]=0 return 0;
if argument[0]=1 return 0;
if argument[0]=2 return 1;
if argument[0]=3 return 0;
if argument[0]=4 return 0;
if argument[0]=5 return 1;
if argument[0]=6 return 0;
if argument[0]=7 return 1;
if argument[0]=8 return 0;
if argument[0]=9 return 0;
if argument[0]=10 return 1;
if argument[0]=11 return 1;
if argument[0]=12 return 0;
if argument[0]=13 return 1;
if argument[0]=14 return 1;
if argument[0]=15 return 1;
Expand///maze_cell_link_w(maze_value)
// 
// returns true if the defined maze value is linked to the western neighbor cell.
// 
// maze_value   value contained in any one maze cell. real
// 
/// GMLscripts.com/license

/***************************\
|  DS_GRID MAZE VALUES:     |
| 0  = full solid cell      |
| 1  = open right           |
| 2  = open up              |
| 3  = open left            |
| 4  = open down            |
| 5  = open up & down       |
| 6  = open left & right    |
| 7  = open right & up      |
| 8  = open right & down    |
| 9  = open left & down     |
| 10 = open left & up       |
| 11 = closed right         | 
| 12 = closed up            |
| 13 = closed left          |
| 14 = closed down          |
| 15 = full open            |
\***************************/

if argument[0]=0 return 0;
if argument[0]=1 return 0;
if argument[0]=2 return 0;
if argument[0]=3 return 1;
if argument[0]=4 return 0;
if argument[0]=5 return 0;
if argument[0]=6 return 1;
if argument[0]=7 return 0;
if argument[0]=8 return 0;
if argument[0]=9 return 1;
if argument[0]=10 return 1;
if argument[0]=11 return 1;
if argument[0]=12 return 1;
if argument[0]=13 return 0;
if argument[0]=14 return 1;
if argument[0]=15 return 1;
Expand///maze_cell_link_s(maze_value)
// 
// returns true if the defined maze value is linked to the southern neighbor cell.
// 
// maze_value   value contained in any one maze cell. real
// 
/// GMLscripts.com/license

/***************************\
|  DS_GRID MAZE VALUES:     |
| 0  = full solid cell      |
| 1  = open right           |
| 2  = open up              |
| 3  = open left            |
| 4  = open down            |
| 5  = open up & down       |
| 6  = open left & right    |
| 7  = open right & up      |
| 8  = open right & down    |
| 9  = open left & down     |
| 10 = open left & up       |
| 11 = closed right         | 
| 12 = closed up            |
| 13 = closed left          |
| 14 = closed down          |
| 15 = full open            |
\***************************/

if argument[0]=0 return 0;
if argument[0]=1 return 0;
if argument[0]=2 return 0;
if argument[0]=3 return 0;
if argument[0]=4 return 1;
if argument[0]=5 return 1;
if argument[0]=6 return 0;
if argument[0]=7 return 0;
if argument[0]=8 return 1;
if argument[0]=9 return 1;
if argument[0]=10 return 0;
if argument[0]=11 return 1;
if argument[0]=12 return 1;
if argument[0]=13 return 1;
if argument[0]=14 return 0;
if argument[0]=15 return 1;

Last edited by lostdarkwolf (2018-07-14 14:02:16)

Offline

Board footer

Powered by FluxBB