Bomberman Style Level Generator using a Dungeon Generation Technique

GM Version: GMS2
Target Platform: HTML5
Download: https://ladyluck.itch.io/hybrid-bomberman-level-generator-for-game-maker-studio-2
Video:





Summary:
I just recently discovered how to use diffusion limited aggregation to create random maps and I wanted to apply it to a bomberman style level generation. I'll give you a rough description of how my code works, but in the download you have access to the full project, as well as a running sample in HTML5 I hosted on itch.io

Tutorial:

[ HOW I WENT ABOUT DOING IT ]

  • Define a cell size (in this case I used 15)
  • Make a grid with any size (I conviniently used 64x46, because when I multiply both by the cell size I get 960x540, the screen size).
  • Define 2 flags for spaces where the player can walk and spaces that it can't. (I literally just used strings: "UNPASSABLE"/"PASSABLE").
  • Hard code the center of the grid in such way that: the center cell is passable and all surrounding cells (including diagonals) are unpassable.
GML:
cell_size = 15; // conviniently divides both room width and height
grid_W = room_width/cell_size; // grid width
grid_H = room_height/cell_size; // grid height
grid = ds_grid_create(grid_W,grid_H); // general grid for placing the cells

//Get the center X and center Y of the grid
center_X = floor(grid_W/2)-1;
center_Y = floor(grid_H/2)-1;

// This snippet defines the center of the grid in the following manner:
// P P P
// P U P
// P P P
for(var _row = center_Y-1; _row <= center_Y+1; _row++){
    for(var _col = center_X-1; _col <= center_X+1; _col++){
        grid[# _col,_row] = "PASSABLE";
    }
}

grid[# center_X,center_Y] = "UNPASSABLE";
  • Build a function that does the following:
  1. Select a random cell in the grid, define it as a anchor point for reference.
  2. Check to see if any of the surrounding cells (including diagonals) is flagged as "UNPASSABLE".
  3. If true: go back to step 1 of this function.
  4. If false: Check to see if at least one of the surrounding cells will overlap a "PASSABLE" cell in the grid and certify that the anchor point align either vertically or horizontally with any anchor point placed previously. (Checking alignment is very easy. In this case, I don't even check this at all. All I do is make sure that the random points selected in the beginning of this function are odd numbers. Since the center of grid is an pair of odd numbers, every other odd pair aligns, so they're good to go).
  5. If true: define all surrounding cells to the anchor point as "PASSABLE" in the grid and make the anchor point itself "UNPASSABLE".
  6. If false: go back to step 1.
GML:
function place_smallSet(center_X,center_Y){
    can_place = false;
   
    if(center_X mod 2 == 0){
        center_X = center_X + choose(1,-1);
        // forces center X to become an odd number, so it aligns properly
        // with the rest of the grid
    }
   
    if(center_Y mod 2 == 0){
        center_Y = center_Y + choose(1,-1);
        // forces center Y to become an odd number, so it aligns properly
        // with the rest of the grid
    }
   
    if(center_X < 2 or center_X > grid_W-2){
        exit; // boots out of this function if the point selected goes out of bounds horizontally
    }
   
    if(center_Y < 2 or center_Y > grid_H-2){
        exit; // boots out of this function if the point selected goes out of bounds vertically
    }
   
    // checks to see if any surrounding cells to center_X, center_Y is unpassable
    for(var _row = center_Y-1; _row <= center_Y+1; _row++){
        for(var _col = center_X-1; _col <= center_X+1; _col++){
            if(grid[# _col,_row] == "UNPASSABLE"){
                exit; // boots out if true
            }
        }
    }
   
    // checks to see if any surrounding cells to center_X, center_Y is passable
    for(var _row = center_Y-1; _row <= center_Y+1; _row++){
        for(var _col = center_X-1; _col <= center_X+1; _col++){
            if(grid[# _col,_row] == "PASSABLE"){
                can_place = true; // certify this as good spot for placing a room
            }
        }
    }
   
    //If everything checked correctly, flag the surrounding cells as passable and center cell as unpassable
    if(can_place){
        for(var _row = center_Y-1; _row <= center_Y+1; _row++){
            for(var _col = center_X-1; _col <= center_X+1; _col++){
                grid[# _col,_row] = "PASSABLE";
            }
        }
        grid[# center_X,center_Y] = "UNPASSABLE";
    }
}
  • Make the program use the function above a set number of times (this is trial and error, you'll eventually get to a number that creates maps roughly the size you need. Make it repeat too much and the grid will be so full you might as well not even use a generator).
  • Make a nested loop that checks all cells flagged as "PASSABLE" and make them flag all surrounding cells (including diagonal) as "UNPASSABLE", if they're otherwise not flagged as anything else.
  • Use sprites to draw the cells on the screen so you can have an idea of the result.

The actual result should be something similar to a Bomberman style level, dotted around with walls that align in sort of a grid shape, completely random and with some branching spaces and pockets separated by walls. This implementation is an adaptation of the concept of Diffusion Limited Aggregation, a technique that can be used generate random dungeons. A cool thing about this code is that it's quite simple. Even though it may sound complicated, you have to realise that all I used here was a single ds_grid and all my tests are done using tried and true nested loops. I should add that even though the code seems to run slowly, it really doesn't. The reason why it slowly animates in the video is because the animation occurs even when the code fails to place a set of cells. By commenting out the step event in the project and bringing the code to the create event of the object that runs this generation, the full map generates on the first frame.

As you can see, I also went a step further and populated the level with walls that would be destroyable (in the case of Bomberman, with bombs). This is just for visual interest, in an actual game I imagine you'd have to make previous test to define preset powerups, enemy distribution, etc. There are countless other techniques that you could use to turn this into a full game or prototype.

(LAST WORDS: As you may imagine, the function we created is trying to see if it can connect another structure, similar to the one we hard codded in the beginning, by selecting a random point in the grid and doing the proper checks. Doing this randomly gives the map a dungeonlike feel. You could try to make the program check different combinations of cells BUT MAKE SURE PASSABLE WAYS CONNECT, otherwise the code might create closed off pockets of space making certain areas unreachable - unless you want that).
 

Attachments

Last edited:
Top