Contour bombing cave generation algorithm

Intro


To generate procedural caves and caverns, there are not so many algorithms out there that a programmer can use in his wide array of tools. Most developers use a cellular automata to generate complete cavelike levels, which is relatively nice algorithm that outputs decent layouts. The second method is the random walk method, a fairly simple algorithm that is very quick to implement, although the output does not look nearly as good as output from CA. We will touch two different types random walk types here. Let me say few word on both of the algorithms first, before we move onto Contour Bombing Cave Generation Algorithm�specifically developed for Dungeons of Everchange.

Cellular automata

What is Cellular Automata? Simply, cellular automata is mathematical model, where grid is randomly filled with cells, then based on predefined rules, cells fight with each other, dying or mutating to neighbor cells.  A complete separate article could be written about cellular automata, there are much more details at the RogueBasin.
For a visual display of the algorithm itself here is a small presentation:


RANDOM walk algorithm
Second one is random walk algorithm, pretty basic algorithm we can use in lot of scenarios.
The implementation of the random walk algorithm is fair simple. The implementation would look like this:
  • Select the starting position
  • Select a random number between 0 and 3
    • If the number is 0, move the position by one to the left
    • If number is 1, moves the position by one to the right
    • If number is 2 ,moves the position one up
    • If number is 3, moves the position one down
  • At x, y position, mark the cell as a passable.
  • Go to step 2 and repeat this n times

Let us see how this would look in small javascript snippet:

RANDOM WALK ALGORITHM - AGAIN

There is also slightly modified version on random walk. The implementation would look like this:

  • Select the starting position
  • Select a random number between 0 and 3
    • If the number is 0, move the position one by one to the left
    • If number is 1, moves the position by one to the right
    • If number is 2 ,moves the position one up
    • If number is 3, moves the position one down
  • At x, y position, mark the cell as a passable.
  • if we pass n2 iteration, move back to start position.
  • Go to step 2 and repeat this n2 times
Actually we have one simple rule added, that we move our cursor to start position again after several iteration. This will give us level with one big cave in the middle, branching in all directions. 


Problems with existing algorithms


One of the problems of both these algorithms is that they generate complete levels. There are no isolated caves or tunnels. We cannot use it to create level by guiding procedural level layout designer to put those caves at places where we want them to be.  Actually 'cannot use' it was a hard word, we can use and predefine level creation with cellular automata, but is much more complicated. To achieve this, we will setup or cellular automata with slightly different values and slightly increase our iteration number. Let's see what this is all about:

Possible solutions using cellular automata and - blobs

We have following situation: we need to create cavern complex by making one big circular cave system. Caves are connected one onto another following circular path, and in the middle will be our level exit. How can we achieve such layout? One of the possible solution would be to use cellular automata and blobs. We will create a level with a cellular automata, make x iteration, then isolate all the blobs and choose the most suitable blob for our use. That would be our cave. Then we will attach those caves from left to right (or vica versa), following one path and...it sounds complicated. This is not only complicated, but we will facing some other problems as well. For example, while the generation of the level is pretty fast, finding attach points and attaching the blob to our predefined path would be slow. First attachments of blobs will be fast, but as we run out of space we will need to have blobs with specific size for them to be able to fit remaining space. 

In order to get our isolated blob, we have to do the following:
  • Fill the level with random cells
  • Make x iteration on each cell
  • With the flood fill algorithm, check the isolation of the blobs
  • Based on our needs, we will select the most suitable blob, and then attach it, or at least try to attach the blob to our path
  • If we cannot attach the blob, we will generate another level layout and start over again

Initially, before the implementation of Cyclic Dungeon, I used the blob isolation method. Blobs were used in cave generation and water/lava/abyss generations. Water generations were bottleneck, as there were times when program made over 50th iteration of complete generation and isolation to get a blob of the specified size. Plus I needed to run flood fills to ensure that level is passable form beginning to end. And of coursethere were times when the complete method failed, and I was unable to produce and attach the blobs to current level.

This was unacceptable, even if the entire generation of the level was under 3 seconds.

Another solution - bombing the contour


Contour bombing cave generation algorithm
What is all this about? I love to reuse the code. I am not of of those that will reinvent the wheel. If there is a possibility to use part of code, or part of library, I will use it. But sometimes, that is not enough. In this case, if we carefully look at our needs (fast, fail free algorithm), we will see that above methods will not work. We need to create more simpler and more efficient algorithm.

Algorithm Description


The basic idea is to generate the path or the basic shape of the cave with several lines, fill path with cells, and then bombard the cells with the filled circles of a certain size. The newly born cells are pushed to the list of cells that can be bombed again.

This basic premise will generate relatively good caverns, but they lacked distortion and a better edge definition. New rules have been introduced:

  • 1:20 cases, we will use the circle of radius 2, while in other cases we will use the radius 1. This will usually use small circles giving better contour, with giving a chance a bomber to push more cells onto stack.
  • In 1: 3 cases one of the last 15 position will be used as a new bombing position, otherwise we will use bottom half of remaining cells. This will give good distortion of contours, because in 1/3 cases the algorithm will continue on some of the last created cells, and still give chance for oldest cells to be bombed.
  • Last used position is deleted from the list, and during bombarding all newly created cells go onto stack, so they can be reused.

So modified algorithm will actually try to reuse some of the last positions, pushing newly created cells onto stack and forcing algorithm to use last positions as new bombing positions. Let us see this algorithm in action:

Showreel


Here are some examples of the algorithm in action. At the end there is a sourcecode of alghorithm.


  • We make only one thicker line, and bomb it to create cave spreading from left to right.

  •  We can create also one T junction cave.


  • Of course, we can generate a cave with wavy trails. More advanced usage.


  • Or even something much more complex. Possibilities are endless.


Only rule that we must ensure it is met, is that path we create must be connected. If the cells from path are not connected, we are risking to have cave with broken connections. 
function build_cavern( use_borders = true ) {  

  var min_x = 0, min_y = 0, max_x = worldWidth, max_y = worldHeight;
  var candidates = [];

  // create list of tile candidates
  for (var x=0; x < worldWidth; x++)  {
    for (var y=0; y < worldHeight; y++)    {
      if(world[x][y] != 0) {
        candidates.push({x,y});
      }
    }
  }

  // shuffle them all
  for ( var p = 0; p < candidates.length; p++) {
    var off = random_gen_get_i(candidates.length);
    candidates[p] = [candidates[off],candidates[off]=candidates[p]][0];
  }

  var iteration_number = candidates.length * 4.8;

  for (var k = 0; k < iteration_number; k++) {
    var random_offset = 0;
    var tile_variation = 0;

    // 1/3 chance that we will use as a bombing point one of the last 15 positions
    if (random_gen_get_i(3) == 0) {
      random_offset = random_gen_range(candidates.length - 15, candidates.length - 1);
      tile_variation = 1;
    }
    else {
      // otherwise use lower half of remaining tiles
      random_offset = random_gen_get_i(candidates.length/2);
      tile_variation = 2;
    }

    // check boundaries
    if (random_offset >= candidates.length)
     random_offset = candidates.length - 1;
    if (random_offset < 0)
     random_offset = 0;

    var tx = candidates[random_offset].x;
    var ty = candidates[random_offset].y;
    var map_width = worldWidth;
    var map_height = worldHeight;
    var use_borders = true;
   
    // we will use bombs of radius 1 mostly with smaller chance (1/20)
    // that radius will be of size 2
    var bomb_radius = random_gen_get_i(20) != 0 ? 1 : 2;
    
    // bomb    
    for (var x = Math.max(0, tx - bomb_radius - 1); x < Math.max(map_width, tx + bomb_radius); x++) {
      for (var y = Math.max(0, ty - bomb_radius - 1); y < Math.max(map_height, ty + bomb_radius); y++) {

        // check if tile is within the circle
        if ((x - tx)*(x - tx) + (y - ty)*(y - ty) < bomb_radius * bomb_radius +  bomb_radius) {

            if (use_borders) {
              if (x < min_x) continue;
              if (x >= max_x) continue;
              if (y < min_y) continue;
              if (y >= max_y) continue;
            }
            
            // if we have at least one tile bombed on screen
            // push those coordinates to candidate list
            if (world[x][y] != tile_variation)   {
              set_tile(x, y, tile_variation);
              candidates.push({x, y});
            }
         }
      }
    }

    // erase our bombing cell, it is re-added in bombing loop above, if at least one tile is changed.
    candidates.splice(random_offset,1);
  }
 
  return true;
}

Source code (C++)

Download complete source code in C++

bool build_cavern( bool use_borders = true) {

    int min_x = 0, min_y = 0, max_x = MAP_WIDTH, max_y = MAP_HEIGHT;
    // create list of tile candidates
    std::vector> candidates;
    int k = 0;

    for (auto& tile : tile_map ) {
        if (tile ) {
            candidates.emplace_back(std::make_pair(k% MAP_WIDTH, k / MAP_WIDTH ));
        }
        k++;
    }

    // shuffle them all
    for ( unsigned p = 0; p < candidates.size(); p++)
        std::swap(candidates[p], candidates[random_gen_get_i(candidates.size())]);

    unsigned iteration_number = (unsigned)((float)candidates.size() * 4.8f);
    for (unsigned i = 0; i < iteration_number; i++) {

        unsigned random_offset = 0;
        auto tile_variation = 0;
        // 1/3 chance that we will use as a bombing point one of the last 15 positions
        if (random_gen_get_i(3) == 0) {
            random_offset = random_gen_range(candidates.size() - 15, candidates.size() - 1);
            tile_variation = 1;
        }
        else {
            // otherwise use lower half of remaining tiles
            random_offset = random_gen_get_i(candidates.size()/2);
            tile_variation = 2;
        }

        // check boundaries
        if (random_offset >= candidates.size())
            random_offset = candidates.size() - 1;

        int x = candidates[random_offset].first;
        int y = candidates[random_offset].second;
        int map_width = MAP_WIDTH;
        int map_height = MAP_HEIGHT;
        bool use_borders = true;

        // we will use bombs of radius 1 mostly with smaller chance (1 / 20)
        // that radius will be of size 2 
        int bomb_radius = random_gen_get_i(20) != 0 ? 1 : 2;

        // bomb
        for (int i = std::max(0, x - bomb_radius - 1); i < std::max(map_width, x + bomb_radius); i++) {
            for (int j = std::max(0, y - bomb_radius - 1); j < std::max(map_height, y + bomb_radius); j++) {
                if ((i - x)*(i - x) + (j - y)*(j - y) < bomb_radius * bomb_radius + bomb_radius) {
                    int map_offset = i + j * MAP_WIDTH;
                    if (0 <= map_offset && map_offset < (int)tile_map.size())   {
                                            
                        if (use_borders) {
                            if (i < min_x) continue;
                            if (i > max_x) continue;
                            if (j < min_y) continue;
                            if (j > max_y) continue;
                        }
                        
                        auto& data = tile_map[map_offset];
                        // if we have at least one tile bombed on screen
                        // push those coordinates to candidate list
                        if (tile_map[map_offset] != tile_variation)     {
                            set_tile(i, j, tile_variation);
                            candidates.emplace_back(std::make_pair(i, j));
                        }
                    }
                }
            }
        }
        
        // erase our cell, it is re-added in bombing loop above, if at least one tile is changed.
        candidates.erase(candidates.begin() + random_offset);
    }
    candidates.clear();
    return true;
}

Comments (0)