GM:S 1.4 Maze generator

Discussion in 'Advanced Programming Discussion' started by NicoFIDI, Feb 1, 2018.

  1. NicoFIDI

    NicoFIDI Member

    Joined:
    Apr 7, 2017
    Posts:
    356
    Hello, as a result of try and error I finally made a random maze generator, it's not perfect and the discussion I want to start it's about some other ways to generate a maze.

    The code has 2 parts a base and the polish
    The base it's straight fordward and the easiest one to understand
    Code:
    /// ds_grid_mazeify(grid, wallValue, floorValue, startX, startY, polish)
    var blueprint = argument[0];
    var wallValue = argument[1];
    var floorValue = argument[2];
    var startX = argument[3];
    var startY = argument[4];
    var polish = argument[5];
    
    var maze_width  = ds_grid_width (blueprint);
    var maze_height = ds_grid_height(blueprint);
    
    enum MazePolishOption {
        no_polish,
        walls,
        floors,
        both
    }
    
    ds_grid_clear(blueprint, floorValue);
    for (var xx = 0; xx < maze_width ; xx++) {
    for (var yy = 0; yy < maze_height; yy++) {
        var borderX = xx == 0 || xx == maze_width-1;
        var borderY = yy == 0 || yy == maze_height-1;
        var startPosition = (xx == startX) && (yy == startY);
       
        if ((borderX || borderY)) {
            if (!startPosition)
                blueprint[# xx,yy] = wallValue;
        } else {
            var oddPosition = (xx mod 2 == (startX-1) mod 2) && (yy mod 2 == (startY-1) mod 2)
           
            if (oddPosition) {
                blueprint[# xx,yy] = wallValue;
               
                var wallDirection = irandom(3) * 90;
                blueprint[# xx + dcos(wallDirection),yy + dsin(wallDirection)] = wallValue;
            }
        }
    }
    }
    
    if (polish == MazePolishOption.walls || polish == MazePolishOption.both)
        ds_grid_mazeify_conect_value(blueprint,wallValue);
    if (polish == MazePolishOption.floors || polish == MazePolishOption.both)
        ds_grid_mazeify_conect_value(blueprint,floorValue);
    

    Then to make the maze more maze-like i added the polish witch it's easy to esplain and hard to code:
    The code conects the walls isle that aren't conected with the exteiror walls, with an added wall.
    This it's the code:
    Code:
    /// ds_grid_mazeify_conect_value(grid, value)
    var blueprints = argument[0];
    var content = argument[1];
    
    var maze_width = ds_grid_width(blueprints);
    var maze_height = ds_grid_height(blueprints);
    
    var used = ds_map_create();
    var chain = ds_list_create();
    var chained = ds_grid_create(maze_width, maze_height);
    
    var itsChained = true;
    ds_grid_clear(chained, false);
    for (var xx = 0; xx < maze_width; xx++) {
    for (var yy = 0; yy < maze_height ; yy++) {
        var isContent = blueprints[# xx,yy] == content;
        var itsUsed = ds_map_exists(used, xx*10000+yy);
       
        if (isContent && !itsUsed) {
            var queue = ds_queue_create();
            ds_queue_enqueue(queue,xx,yy);
           
            while(!ds_queue_empty(queue)) {
                var xact = ds_queue_dequeue(queue);
                var yact = ds_queue_dequeue(queue);
                ds_list_add(chain,xact,yact);
                used[? xact*10000+yact] = false;
               
                for (var dir = 0; dir < 360; dir += 90) {
                    var xnew = xact + dcos(dir);
                    var ynew = yact + dsin(dir);
                   
                    var xvalido = between(xnew,0,maze_width-1);
                    var yvalido = between(ynew,0,maze_height-1);
                   
                    if (!itsChained) { itsChained = !(xvalido && yvalido); }
                   
                    var posUsed = ds_map_exists(used, xnew*10000+ynew);
                    used[? xnew*10000+ynew] = false;
                   
                    if (xvalido && yvalido && !posUsed) {
                        if (blueprints[# xnew,ynew] == content) {
                            ds_queue_enqueue(queue, xnew, ynew);
                        }
                    } 
                }
            }
           
            ds_queue_destroy(queue);
           
           
            while (!itsChained) {
                var imax = ds_list_size(chain)/2;
                var i = irandom(imax-1);
               
                var xact = chain[| 2*i+0];
                var yact = chain[| 2*i+1];
               
                var desv = irandom(3) * 90;
               
                for (var dir = 0; dir < 360 && !itsChained; dir += 90) {
                    var deltax = dcos(dir+desv);
                    var deltay = dsin(dir+desv);
                   
                    if (chained[# xact+2*deltax,yact+2*deltay]) {
                        blueprints[# xact+deltax,yact+deltay] = content;
                        ds_list_add(chain,xact+deltax,yact+deltay);
                        itsChained = true;
                    }
                }
            }
           
            for (var i = 0; i < ds_list_size(chain)/2; i++) {
                var xnew = chain[| 2*i+0];
                var ynew = chain[| 2*i+1];
               
                chained[# xnew,ynew] = itsChained;
            }
           
            itsChained = false;
            ds_list_clear(chain);
        }
    }}
    
    ds_map_destroy(used);
    ds_list_destroy(chain);
    ds_grid_destroy(chained);
    

    I wanted to open a discussion about other ways to make random mazes.

    Finally this is how the algorithm works with his polish
    upload_2018-1-31_21-33-46.png
     
  2. sylvain_l

    sylvain_l Member

    Joined:
    Sep 18, 2016
    Posts:
    705
    without more info on the game it's harder to know what's a good maze.

    going to comment on your definition of "more maze-like". Open loop, at least in first person, can be much more maze-hellish as long you don't have a minimap with you or it's small compared to size of the maze. (same can be true for top-down as long as the minimap/dispayed portion is really small compared to the whole maze. And there is no FoW or other element that help know if you already walk through the portion of maze you are in or not.

    in your "polish both" version, the simple trick of put your right hand on the wall on your right and walk on will allow to go through all the maze easly. Which partially kinda kill the concept of maze for me :p (while having some well placed open loop kill the efficiency of that little trick as some portion of the maze will be unreachable that way. of course in game you can also use teleporter to mess with that trick. topologically it's an other way to mess it up)
     
    NicoFIDI likes this.
  3. NicoFIDI

    NicoFIDI Member

    Joined:
    Apr 7, 2017
    Posts:
    356
    Yes, what you say it's true, using the right hand trick you can solve a maze that has all teir walls connected but then again, you can add a simple solution witch is to randomly substract walls that have floors on opositesides or even apply only the floor polish.

    And if you want to spice things, with only a few changes you can make the floor polish to make every unconected floor a secret room, and place keys on the main floor to open the doors.

    What I truly whould like to find out are other completly different ways to make mazes.

    Edit:

    Actually this is absolutelly true, I the game i am triing to make do not benefit from this completly random maze. Yet, I was always facinated about the procedural generated dungeons and structures, so I thought that in the advanced programming forum i whould find some other people with his own randomly generated maze or dungeon.

    What I whould love to see, it's an example of how to make a dungeon "dungeon hack" style, i'm burning my brain to unravel the code behind it.
     
    Last edited: Feb 6, 2018
  4. Wraithious

    Wraithious Member

    Joined:
    Jun 24, 2016
    Posts:
    1,166
    The way I did it was to use ds stacks, using recursion to fill the whole room. I made 2 scripts:
    index, checks if we are within the boundary:
    Code:
    r=argument0;
    s=argument1;
      if (r<0 || s<0 || r>cols-1 || s>rows-1) {
        return -1;
      }
      return r+s*cols;
    nest - does the work:
    Code:
      if (index(i, j-1)!=-1) {
    
        if (visited[i,j-1]==0)
        {
          picker[0]=1;
          checker=1;
        }
      }
      if (index(i+1, j)!=-1) {
        if (visited[i+1,j]==0)
        {
          picker[1]=1;
          checker=1;
        }
      }
      if (index(i, j+1)!=-1) {
        if (visited[i,j+1]==0)
        {
          picker[2]=1;         
          checker=1;
        }
      }
      if (index(i-1, j)!=-1) {
        if (visited[i-1,j]==0)
        {
          picker[3]=1;         
          checker=1;
        }
      }
      if (checker==1) {
        p=round(random(3));
        while (picker[p]!=1) {
          p=round(random(3));
        }
        if (p==0) {
          visited[i,j-1]=1;
          wallPos1[i,j]=0;
          wallPos3[i,j-1]=0;
          current=index(i, j-1);
          useall+=1;
          ds_stack_push(stack,j);
          ds_stack_push(stack,i);
          j=j-1;
        }
        if (p==1) {
          visited[i+1,j]=1;
          wallPos2[i,j]=0;
          wallPos4[i+1,j]=0;
          current=index(i+1, j);
          useall+=1;
          ds_stack_push(stack,j);
          ds_stack_push(stack,i);
          i=i+1;
        }
        if (p==2) {
          visited[i,j+1]=1;
          wallPos3[i,j]=0;
          wallPos1[i,j+1]=0;
          current=index(i, j+1);
          useall+=1;
          ds_stack_push(stack,j);
          ds_stack_push(stack,i);
          j=j+1;
        }
        if (p==3) {     
          visited[i-1,j]=1;
          wallPos4[i,j]=0;
          wallPos2[i-1,j]=0;
          current=index(i-1, j);
          useall+=1;
          ds_stack_push(stack,j);
          ds_stack_push(stack,i);
          i=i-1;
        }
      }
      for (var k=0; k<4; k++) {
        picker[k]=0;
      }
      if (checker==0) {
        if (useall<rows*cols) {
        if !ds_stack_empty(stack) i = ds_stack_pop(stack);
        if !ds_stack_empty(stack) j = ds_stack_pop(stack);   
        }
        if (useall>=rows*cols) {
          m=0;
        }
      }
      checker=0;
    Then in object maze I have
    Code:
    stack = ds_stack_create();
    ds_stack_push(stack,0);
    ds_stack_push(stack,0);
    randomize();
    i=0;
    j=0;
    m = 1;
    p = 0;
    w = 40;
    set=1;
    checker = 0;
    current = 0;
    useall=0;
    timer=5;
    cols = floor(600/w);
    rows = floor(600/w);
    background_color=make_colour_rgb(65, 81, 69);
    vcolor=make_colour_rgb(255, 0, 255);
    ccolor=make_colour_rgb(0, 255, 0);
    xx = 0;
    yy = 0;
      for (var d=0; d<rows+1; d+=1;) {
        for (var e=0; e<cols+1; e+=1;) {
          visited[d,e]=0;
          wallPos1[d,e]=1;
          wallPos2[d,e]=1;
          wallPos3[d,e]=1;
          wallPos4[d,e]=1;
        }
      }
      for (var f=0; f<5; f++) {
         picker[f] = 0;
    }
      visited[0,0]=1;
      nest();
    Code:
          if (timer>0 && m==1 && set==1) {
            timer-=1;
            if (timer<=0) {
              timer=5;
              nest();
            }
          }
    Code:
      for (var r=0; r<rows; r++) {
    
        for (var q=0; q<cols; q++) {
          xx=q*w;
          yy=r*w;
          if (visited[q,r]==1 && current!=index(q, r)) {
            draw_set_color(vcolor);
            draw_rectangle(xx, yy, xx+w, yy+w, 0);
            draw_set_color(c_black);
            draw_text(xx+1, yy+w/2, index(q, r));
          }
          if (current==index(q, r)) {
            draw_set_color(ccolor);
            draw_rectangle(xx, yy, xx+w, yy+w, 0);
            draw_set_color(c_white);
            draw_text(xx+1, yy+w/2, current);
          }
            draw_set_color(c_white);
          if (wallPos1[q,r] !=0) {
            draw_line(xx, yy, xx+w, yy);
          }
          if (wallPos2[q,r] !=0) {
            draw_line(xx+w, yy, xx+w, yy+w);
          }
          if (wallPos3[q,r] !=0) {
            draw_line(xx+w, yy+w, xx, yy+w);
          }
          if (wallPos4[q,r] !=0) {
            draw_line(xx, yy+w, xx, yy);
          }
       }
    }
    And to reset the maze I used the enter pressed event:
    Code:
      for (var d=0; d<rows+1; d+=1;) {
    
        for (var e=0; e<cols+1; e+=1;) {
          visited[d,e]=0;
          wallPos1[d,e]=1;
          wallPos2[d,e]=1;
          wallPos3[d,e]=1;
          wallPos4[d,e]=1;
        }
      }
      for (var f=0; f<5; f++) {
         picker[f] = 0;
    }
      visited[0,0]=1;
      m=1;
      checker=0;
      current = 0;
      useall=0;
      i=0;
      j=0;
      ds_stack_clear(stack);
      ds_stack_push(stack,0);
      ds_stack_push(stack,0);
      nest();
    And last but not least don't forget to free the stack from memory on the game end event:
    Code:
    if ds_exists(stack,ds_type_stack) ds_stack_destroy(stack);
     
    Last edited: Feb 26, 2018
    NicoFIDI likes this.
  5. NicoFIDI

    NicoFIDI Member

    Joined:
    Apr 7, 2017
    Posts:
    356
    I'll try it later ; )
    But why don't you show a capture with the algorithm result?
    That whould allow us to see your work in action without having to code the whole thing XD

    I'll edit this comment when I finally test it :D
     
    Wraithious likes this.
  6. Wraithious

    Wraithious Member

    Joined:
    Jun 24, 2016
    Posts:
    1,166
    Yep, I just uploaded a video of the maze being generated from the android version i made, here it is :)

    As you can see when it gets 'stuck' it backtracks until it finds an available alternate path.
     
    NicoFIDI likes this.
  7. NicoFIDI

    NicoFIDI Member

    Joined:
    Apr 7, 2017
    Posts:
    356
    Well, That's a diferent aproach.
    How does this script works on 2500x2500 grid?
    I guess for the sake of comparation it should be a 1250x1250 grid
    Due the fact that your walls and corridors don't take a space on the final result.
     
    Wraithious likes this.
  8. Wraithious

    Wraithious Member

    Joined:
    Jun 24, 2016
    Posts:
    1,166
    to answer your grid question, in the create event you would set it up there, notice this part of the create event:
    Code:
    w = 40;
    
    cols = floor(600/w);
    rows = floor(600/w);
    you need to make sure the total grid size, in this case 600x600, are both evenly dividable by the width of your grid squares, variable w, (so basically for a 2500x2500 grid change cols and rows numbers to 2500 and w to 25 or 50 or some other evenly dividable number) and that's it :)
    Now as far as the walls go, in my project it just draws them, but if you want to associate them with an object, such as oWall for example, you can just use the wall array variables
    Code:
          wallPos1[d,e]=1;
          wallPos2[d,e]=1;
          wallPos3[d,e]=1;
          wallPos4[d,e]=1;
    to determine weather to put a wall there or not.

    Basically to show how I came to use this method was creating it in processing code engine and then converting it to gamemaker, it was a fun project, I followed this series of videos on the coding train:


    EDIT:
    As a side note, this example is very basic, as you pointed out the walls I use are 1 pixel wide, so to implement this with your setup the way I'd do it would be increase the block size times 3, make the room size some comfortable multiple of that, and then you can just place your wall objects on the left and right (or top and bottom depending on which wall array variable =1) and place your floor tile in the middle. also another option is while the algorithm is running use it to populate your ds_grid_mazeify to store the info so you can refer to it all in code whenever you need it
     
    Last edited: Mar 29, 2018
    Japster 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