Procedural Dungeons

[marainein]

Using some GPDL scripting and $SetWall(), it's possible to generate random dungeons, at run time.
There are many methods to do this - I'll start off by describing the "drunkard's walk" method http://www.roguebasin.com/index.php?title=Random_Walk_Cave_Generation, which builds cavern like dungeon maps.
To mark a square as having been dug, I set the background to something non-default.

First, decide how many squares you're going to dig for your cave. Pick a square and dig there.
(1) Take one step in a random direction to a new square
(2) If the square is not already dug, dig it and add 1 to the count of squares dug
(3) If we haven't met the goal for number of squares dug, return to (1)


This gives us rough looking maps, like caves connecting cavern, although the effect is lessened by the relatively small number of squares visible from the first person perspective in this sort of game.

It also guarantees that every part of the dungeon is reachable.

Wall based maps like dungeon craft's need a post-processing step to put walls between the solid rock and the caves.
So loop through every square on the map, and if it's dug, then check each direction to see if the neighboring square is solid rock - if it is, put a wall between the two.

[Milos Gulan]

Wow, Thank You very much. That is very interesting link . I think I will have to check trough that site.

[Dinonykos]

I like this approach. Would you post the GPDL script or is it "top secret"?

[marainein]

Thank you! Actually, I plan to post the script and several others (for generating different styles of dungeons), so anyone who wants can use them, but I'd prefer to wait for the $SetWall() issues to be resolved.

[Milos Gulan]

So cool, this is really something I need to learn

[ProphetSword]

That's pretty impressive.

[manikus]

To echo ProphetSword, that is darn impressive1

I have kicked around ideas for random designs, but not like this. I had been looking at making a number of rooms and hallways that would be randomly connected, the info being stored in quests (so that they would remain the same for the course of the current game, but would change for a new game).

Have you thought of a way to place the starting point randomly? What about transfer module events? I think that this may be the kind of thing that Paul is willing to work with you on.

[marainein]

Thanks guys Although it's really not that hard to write a map generator (I suspect it's much harder to write a good adventure module, although I've never done that) - plus 99% of the work has already been done by the guys who coded DC.

Have you thought of a way to place the starting point randomly? What about transfer module events? I think that this may be the kind of thing that Paul is willing to work with you on.

I haven't thought about the starting point specifically - I was just going to start the player at the middle of the level, and build the map around them.

I've got scripts that randomly 'place' pre-written events on the map - saving an x,y position for each event when the map is generated, then using a script to trigger the event when the party reaches that spot.

Later I'll post a preview thread about the actual game I'm making with this for the one week challenge.

BTW, is there a GPDL function to get the current level's width and height?

[manikus]

This is all very exciting. If you're script can tell which cells have been dug, then you could assign a transfer to a dug cell and then if a dug cell has a Transfer event, give it specific walls.

There are no functions currently which return the length or width of a level.

[Nol Drek]

Can this be used to do the following?

1) Create N rectangular rooms of random sizes. (2x3, 1x2, 4x2, etc)
2) Create hallways which consist of one vertical section and one horizontal section (or vice versa, 50/50 chance) connecting room K to room K+1
3) Place the starting point in room 1.

[marainein]

Can this be used to do the following?

1) Create N rectangular rooms of random sizes. (2x3, 1x2, 4x2, etc)
2) Create hallways which consist of one vertical section and one horizontal section (or vice versa, 50/50 chance) connecting room K to room K+1
3) Place the starting point in room 1.

In a word, yes - I know this because the first script I wrote basically did this - there are a few complications, like making sure the rooms don't overlap, or what to do when a corridor runs into something before its destination - but yeah, it works, and generates nethack style dungeon maps:

[manikus]

After seeing this thread yesterday, I started looking around and thinking on the roomhallway style of procedural dungeon. Then I discovered the large number of web pages devoted to scripts/code to create procedural rogue-like dungeons.

But now, seeing marainein's latest post, I am even more excited, because it looks like those ideas can be implemented in DC.

[marainein]

But now, seeing marainein's latest post, I am even more excited, because it looks like those ideas can be implemented in DC.

Indeed they can. Let's have some cave digging GPDL code.

To use it, create an empty level (10x10 default will be fine) and make sure it doesn't have any backdrop images filling it. Put the script somewhere where it can run - I used an event with a logic block and put the script inside a GPDL function there - and test run the game, and step on the event. The script starts making the dungeon at the center of the level, so it's helpful to put the event there so you end up inside the caves, rather than outside. Also mark the event to only activate once.

Requires at least DC 2.78 (the latest version as of today when I'm writing this) to run properly. If anyone can't get the script to run, post here and I'll try and solve the problem.

Code: [Select]

// Cave Digger

$FUNC GetLevelWidth()
{
  // find the level width by stepping through the cells until we're back where we started
  $VAR level;
  $VAR saved_bg1;
  $VAR saved_bg2;
  $VAR i;

  level = $GET_GAME_CURRLEVEL() +# 1;
  saved_bg1 = $GetBackground(level, 0, 0, 0);
  i = 1;
  $WHILE($GetBackground(level, 0, 0, 0) !=# 1)
  {
    $SetBackground(level, i -# 1, 0, 0, saved_bg2); // restore the background to the previous cell
    saved_bg2 = $GetBackground(level, i, 0, 0); // save the background to the current cell
    $SetBackground(level, i, 0, 0, 1); // set the background to test if we've looped back to our starting point
    i = i +# 1;
  };
  i = i -# 1;
  $SetBackground(level, 0, 0, 0, saved_bg1);
  $RETURN i;
} GetLevelWidth;

$FUNC GetLevelHeight()
{
  // find the level height by stepping through the cells until we're back where we started
  $VAR level;
  $VAR saved_bg1;
  $VAR saved_bg2;
  $VAR i;

  level = $GET_GAME_CURRLEVEL() +# 1;
  saved_bg1 = $GetBackground(level, 0, 0, 0);
  i = 1;
  $WHILE($GetBackground(level, 0, 0, 0) !=# 1)
  {
    $SetBackground(level, 0, i -# 1, 0, saved_bg2); // restore the background to the previous cell
    saved_bg2 = $GetBackground(level, i, 0, 0); // save the background to the current cell
    $SetBackground(level, 0, i, 0, 1); // set the background to test if we've looped back to our starting point
    i = i +# 1;
  };
  i = i -# 1;
  $SetBackground(level, 0, 0, 0, saved_bg1);
  $RETURN i;
} GetLevelHeight;

$FUNC SetCellBackground(x, y, bg)
{
  $VAR level;
  level = $GET_GAME_CURRLEVEL() +# 1;
  $SetBackground(level, x, y, 0, bg);
  $SetBackground(level, x, y, 1, bg);
  $SetBackground(level, x, y, 2, bg);
  $SetBackground(level, x, y, 3, bg);
} SetCellBackground;

$FUNC DigCaves() {
// Dig a dungeon using the drunkard's walk algorithm
// the dungeon generated will resemble a cave system

  $VAR width;
  $VAR height;
  $VAR x;
  $VAR y;
  $VAR dig_count;
  $VAR cavern_size;
  $VAR bg;
  $VAR wall;
  $VAR level;
  $VAR blocked;

  // get basic stats about our level
  width = GetLevelWidth();
  height = GetLevelHeight();
  level = $GET_GAME_CURRLEVEL() +# 1;

  wall = 2; // change this number to the wall slot you want to generate the dungeon with
  bg = 2; // change this number to the background slot you want to generate the dungeon with
  blocked = 2;

  // the location we start digging at. By default, we'll start at the center of the map
  x = width /# 2;
  y = height /# 2;

  // How many squares of cavern you want to dig - obviously it should be less than the total squares on the level
  cavern_size = 50;

  // Dig the first square
  dig_count = 1;
  SetCellBackground(x, y, bg);

  // loop until we've reached our cavern size goal
  $WHILE(dig_count <# cavern_size)
  {
    // Is our current square solid rock? If so, dig it
    $IF($GetBackground(level, x, y, 0) ==# 255)
    {
      dig_count = dig_count +# 1;
      SetCellBackground(x, y, bg);
    };

    // Take a step in a random direction
    $IF($RANDOM(2) ==# 1) {x = x +# $RANDOM(3) -# 1;} // Either East/West
    $ELSE {y = y +# $RANDOM(3) -# 1;}; // Or North/South
  };
  // finished digging the caves

  // Now we need to place walls between the caves we've dug and the remaining solid rock
  // loop through all cells in the level
  x = 0;
  $WHILE(x <# width)
  {
    y = 0;
    $WHILE(y <# height)
    {
      // First test if our current square is part of the caves
      $IF($GetBackground(level, x, y, 0) !=# 255)
      {
        // It is, so check if the square to the north is solid rock
        // and if it is, put a wall on the north side of this square
        // North
        $IF($GetBackground(level, x, y -# 1, 0) ==# 255)
        {
          // Put a wall there
          $SetWall(level, x, y, 0, wall);
          $SetBlockage(level, x, y, 0, blocked);
        };
       
        // East
        $IF($GetBackground(level, x +# 1, y, 0) ==# 255)
        {
          // Put a wall there
          $SetWall(level, x, y, 1, wall);
          $SetBlockage(level, x, y, 1, blocked);
        };
        // South       
        $IF($GetBackground(level, x, y +# 1, 0) ==# 255)
        {
          // Put a wall there
          $SetWall(level, x, y, 2, wall);
          $SetBlockage(level, x, y, 2, blocked);
        };
        // West
        $IF($GetBackground(level, x -# 1, y, 0) ==# 255)
        {
          // Put a wall there
          $SetWall(level, x, y, 3, wall);
          $SetBlockage(level, x, y, 3, blocked);
        };
      };
      y = y +# 1;
    };
    x = x +# 1;
  };
  // finished making the walls

} DigCaves;


DigCaves();


[SilentThief]

Going to test this out later tonight. I like the idea of generating a random dungeon that would not be the same when played again. This could increase reply value, if done right

ST

[manikus]

Woot!!!

Thanks, marainein.