Planned - Randomly Generated Dungeon

View previous topic View next topic Go down

Planned - Randomly Generated Dungeon

Post by rc on Sun Jul 17, 2016 7:25 pm

The player selects the size and the difficulty of the dungeon. The dungeon is randomly generated.
The player starts at one map and must find his way to the dungeon boss. Killing it unlocks the exit. Leaving the dungeon gives rewards based on difficulty, dungeon size, # rooms explored, # monster killed, # deaths, party size.

A dungeon is a bunch of premade maps connected by map transitions.

This new feature requires an algorithm that randomly generate a dungeon.

Here's the general schema:

Schema:

Code:
DungeonGenerator
 Dungeon generate(duration:number,difficulty:number)
 
Dungeon
 rooms:Room[]

Room
 monsters:Monster[]
 teleporters:Teleporter[]
 keys:Key[]
 id:number
 type:RoomType
 x:number
 y:number
 size:Size = Size._1x1
 

Monster
 actorModel:ActorModel = getRandomActorModel()
 dmg = 1
 def = 1
 size = 1

Key
 mustKillAllToPickup:boolean

Here's the code that contains the class and enum declarations and a simple dungeon example.
It also draws the dungeon on a canvas.
The global variable `dungeon` holds the dungeon created. Can be used for JSON.stringify(dungeon).

Code:

<canvas id="canvas"></canvas>


<script>
var DRAW_ROOM_ID = true;
var DUNGEON_DURATION = 10;
var DUNGEON_DIFFICULTY = 1;

function DungeonGenerator() {}
DungeonGenerator.prototype.generate = function (duration,difficulty) {
 //#####################################
 //edit this part
 
 var d = new Dungeon();
 
 //##################
 //room1
 var room1 = new Room();
 room1.id = 1;
 room1.type = RoomType.entrance;
 room1.x = 0;
 room1.y = 0;
 var teleport1 = new Teleporter();
 teleport1.position = Position.south;
 teleport1.destination = { roomId: 2, position: Position.north };
 teleport1.mustKillAllToUse = true;
 var teleport12 = new Teleporter();
 teleport12.position = Position.east;
 teleport12.destination = { roomId: 3, position: Position.west };
 room1.teleporters = [
 teleport1,teleport12,
 ];
 var key = new Key();
 key.mustKillAllToPickup = true;
 room1.keys = [
 key
 ];
 var monster1 = new Monster();
 monster1.dmg = 2;
 monster1.def = 2;
 monster1.size = 2;
 room1.monsters = [
 new Monster(),
 new Monster(),
 new Monster(),
 monster1
 ];
 
 //###################
 //room2
 var room2 = new Room();
 room2.id = 2;
 room2.type = RoomType.exit;
 room2.x = 0;
 room2.y = 1;
 var teleport2 = new Teleporter();
 teleport2.position = Position.north;
 teleport2.destination = { roomId: 1, position: Position.south };
 room2.teleporters = [
 teleport2,
 ];
 room2.monsters = [
 new Monster(),
 ];
 
 
 //###################
 //room3
 var room3 = new Room();
 room3.id = 3;
 room3.type = RoomType.exit;
 room3.x = 1;
 room3.y = 0;
 var teleport3 = new Teleporter();
 teleport3.position = Position.west;
 teleport3.destination = { roomId: 1, position: Position.east };
 room3.teleporters = [
 teleport3,
 ];
 
 d.rooms = [room1, room2,room3];
 return d;
};

//DONT TOUCH BELOW

setTimeout(function(){
 var now = Date.now();
 var d = (new DungeonGenerator()).generate(DUNGEON_DURATION,DUNGEON_DIFFICULTY);
 console.log("Generation time for %d rooms: %d ms",d.rooms.length, Date.now() - now);
 console.log(d);
 d.draw(canvas);
 window.dungeon = d;
},10);

var Position = {
 north:0,
 south:1,
 west:2,
 east:3,
}

var Size = {
 _1x1:0
}

var RoomType = {
 normal:0,
 entrance:1,
 exit:2,
}

var getRandomActorModel = function () {
    return 'bat';
}

var Monster = function(){
 this.actorModel = getRandomActorModel();
 this.dmg = 1;
 this.def = 1;
 this.size = 1;
}

var Key = function() {
   this.mustKillAllToPickup = false;
}
var Teleporter = function () {
 this.position = null;
 this.destination = null;
 this.mustKillAllToUse = false;
 this.keysRequiredToUse = 0;
}

var Dungeon = function(){
 this.rooms = [];
}
Dungeon.prototype.draw = function(canvas){
 canvas.width = 1000;
 canvas.height = 1000;
 canvas.style.width = '1000px';
 canvas.style.height = '1000px';
 
 var sx = 500;
 var sy = 500;
 var ROOM_SIZE = 32;
 var TILE_SIZE = 40;
 var margin = (TILE_SIZE - ROOM_SIZE) / 2;
 var TELE_SIZE = 4;
 
 var ctx = canvas.getContext('2d');
 ctx.fillStyle = 'black';
 for(var i = 0 ; i < this.rooms.length; i++){
 var room = this.rooms[i];
 ctx.fillRect(sx + room.x * TILE_SIZE + margin,
 sy + room.y * TILE_SIZE + margin,ROOM_SIZE,ROOM_SIZE);
 if(DRAW_ROOM_ID){
 ctx.fillStyle = 'yellow';
 ctx.fillText('' + room.id,
 sx + room.x * TILE_SIZE + margin,
 sy + room.y * TILE_SIZE + margin + 10)
 ctx.fillStyle = 'black';
 }
 for(var j = 0; j < room.teleporters.length; j++){
 if(room.teleporters[j].position === Position.north)
 ctx.fillRect(sx + (room.x + 0.5) * TILE_SIZE - TELE_SIZE / 2,
 sy + room.y * TILE_SIZE,
 TELE_SIZE,
 margin);
 else if(room.teleporters[j].position === Position.south)
 ctx.fillRect(sx + (room.x + 0.5) * TILE_SIZE - TELE_SIZE / 2,
 sy + (room.y + 1) * TILE_SIZE - margin,
 TELE_SIZE,
 margin);
 else if(room.teleporters[j].position === Position.west)
 ctx.fillRect(sx + room.x * TILE_SIZE,
 sy + (room.y + 0.5) * TILE_SIZE - TELE_SIZE / 2,
 margin,
 TELE_SIZE);
 else if(room.teleporters[j].position === Position.east)
 ctx.fillRect(sx + (room.x + 1) * TILE_SIZE - margin,
 sy + (room.y + 0.5) * TILE_SIZE - TELE_SIZE / 2,
 margin * 2,
 TELE_SIZE);
 }
 }
}

var Room = function Room() {
 this.id = Math.random();
 this.type = RoomType.normal;
 this.x = 0;
 this.y = 0;
 this.size = Size._1x1;
 this.teleporters = [];
 this.monsters = [];
 this.keys = [];
};
</script>

rc
Admin

Posts : 164
Reputation : 9
Join date : 2016-04-04
Age : 22
Location : Montreal

View user profile http://rainingchain.com

Back to top Go down

Re: Planned - Randomly Generated Dungeon

Post by rc on Tue Jul 19, 2016 8:33 pm

Here's the algo submitted by siiz

Code:

<meta charset="utf-8">
<canvas id="canvas"></canvas>

<script>
var DRAW_ROOM_ID = true;
var DUNGEON_DURATION = 90;
var DUNGEON_DIFFICULTY = 3;

function oppositePosition( pos )
{
  if( pos == Position.north ) return Position.south;
  if( pos == Position.south ) return Position.north;
  if( pos == Position.west ) return Position.east;
  if( pos == Position.east ) return Position.west;
// LOG ERROR HERE
  console.log( "oppositePosition()" );
  return Position.north;
}

function generateRooms( d, prevRoom, prevRoomDir, x, y )
{
  if( d.maxRooms <= 0 ) { return; }

  var chance = 0.7;
  // dont try to make tele/room where we just were! make sure it doesnt overlap.
  var teleSouth = prevRoomDir !== Position.south && !d.roomExists( x, y + 1 ) && Math.random() < chance;
  var teleNorth = prevRoomDir !== Position.north && !d.roomExists( x, y - 1 ) && Math.random() < chance;
  var teleWest  = prevRoomDir !== Position.west  && !d.roomExists( x - 1, y ) && Math.random() < chance;
  var teleEast  = prevRoomDir !== Position.east  && !d.roomExists( x + 1, y ) && Math.random() < chance;

  // basic info
  this.id = d.maxRooms;
  this.keys = [];
  this.x = x;
  this.y = y;
  this.teleporters = [];

  this.size = Size._1x1;
// EXAMPLE:
// if teleNorth && teleSouth && !teleWest && !teleEast
//  this.size = Size._2x1;


  if( x == 0 && y == 0 ) { // bossroom at center (first room)
    teleSouth = false;
    teleNorth = true;
    teleWest = false;
    teleEast = false;

    this.type = RoomType.exit;
    var boss = new Monster();
    boss.dmg = 1 + Math.random() * d.difficulty;
    boss.def = 2.5 * d.difficulty;
    boss.size = 1 + 2 * d.difficulty;
    boss.actorModel = getRandomBossActorModel();
    this.monsters = [boss, new Monster(), new Monster()]; // boss + 2 weak minions

  } else if( d.maxRooms == 1 ) { // last room generated, make it entrance

    this.type = RoomType.entrance;
    this.monsters = [];  // guide npc or something to entrance?

  } else {
   if( prevRoom.type === RoomType.exit ) // the room before bossroom
   {
      if( d.keys < d.maxKeys )
      {
         d.keys++;
         this.keys = [{mustKillAllToPickup:false}];
      }
   }
   else if( d.keys < d.maxKeys && Math.random() < 0.2 )
   {
      d.keys++;
      this.keys = [{mustKillAllToPickup:false}];
   }

    this.type = RoomType.normal;
    d.accommodate( this );
  }

  // teleport to previous room (starting from bossroom to entrance)
  if( typeof prevRoom !== "undefined" )
  {
    var prevTele = new Teleporter();
    prevTele.position = oppositePosition(prevRoomDir);
    prevTele.destination = { roomId:prevRoom.id, position:prevRoomDir };
    prevTele.mustKillAllToUse = true;

    if( prevRoom.type === RoomType.exit ) { d.bossTeleport = prevTele; }
    this.teleporters.push( prevTele );
  }

  d.length++;
  d.setRoom( x, y, this );
  d.maxRooms--;

  var roomTemporary;
  if( teleSouth && d.maxRooms > 0 ) {
    roomTemporary = new generateRooms( d, this, Position.south, x, y + 1 );
    this.teleporters.push( {position:Position.south, destination:{roomId:roomTemporary.id, position:Position.north}, mustKillAllToUse:true} );
  }

  if( teleNorth && d.maxRooms > 0 ) {
    roomTemporary = new generateRooms( d, this, Position.north, x, y - 1 );
    this.teleporters.push( {position:Position.north, destination:{roomId:roomTemporary.id, position:Position.south}, mustKillAllToUse:true} );
  }

  if( teleWest && d.maxRooms > 0 ) {
    roomTemporary = new generateRooms( d, this, Position.west, x - 1, y );
    this.teleporters.push( {position:Position.west, destination:{roomId:roomTemporary.id, position:Position.east}, mustKillAllToUse:true} );
  }

  if( teleEast && d.maxRooms > 0 ) {
    roomTemporary = new generateRooms( d, this, Position.east, x + 1, y );
    this.teleporters.push( {position:Position.east, destination:{roomId:roomTemporary.id, position:Position.west}, mustKillAllToUse:true} );
  }

  return this;
}

function DungeonGenerator() {
}

DungeonGenerator.prototype.generate = function ( duration, difficulty ) {
   var d = new Dungeon();
   d.difficulty = difficulty;
   d.duration = duration;
   d.setRoom = function( x, y, room ) {
      this.roomsHash[x + "," + y] = room;
   };
   d.getRoom = function( x, y ) {
      return this.roomsHash[x + "," + y];
   };
    d.roomExists = function( x, y ) {
      return typeof this.roomsHash[x + "," + y] !== "undefined";
   };
   d.accommodate = function( room ) {
      if( Math.random() > 0.75 ) {
         // a big one with a few small
         var bigMonster = new Monster();
         bigMonster.size = 1.5 + 0.3 * d.difficulty;
         bigMonster.def = 1 + 0.4 * d.difficulty;
         bigMonster.dmg = 1 + 0.4 * d.difficulty;
         room.monsters = [ new Monster(), new Monster(), bigMonster ];
      } else {
         // many small enemies
         room.monsters = [  // generic monsters here
                      new Monster(), new Monster(),
                      new Monster(), new Monster(),
                      new Monster(), new Monster()  ];

         for( var i = 0; i < d.difficulty; i++ )
            room.monsters.push( new Monster() );
      }

   };

   d.rooms = [];
   d.length = 0;
   while( d.length < 5 || d.maxRooms > 0 ) // in case of bad seed we regenerate
   {
           d.length = 0;
           d.roomsHash = {};
           d.maxRooms = 1 + Math.floor( (Math.random()+0.5) * difficulty * difficulty * duration / 5 );
      d.keys = 0;
      d.maxKeys = 1 + Math.round( duration / 10 );
      d.bossTeleport = {};
           // 0,0 coordinates generate bossroom
           var bossRoom = new generateRooms( d, undefined, null, 0, 0 );
      d.bossTeleport.keysRequiredToUse = Math.round(d.keys / 2);
   }
   for( var i in d.roomsHash ) { d.rooms.push( d.roomsHash[i] ); }
   return d;
};

///////////////////////////////////////////////

setTimeout(function(){
   var now = Date.now();
   var d = (new DungeonGenerator()).generate( DUNGEON_DURATION, DUNGEON_DIFFICULTY );
   console.log("Generation time for %d rooms, %d keys: %d ms",d.rooms.length, d.keys, Date.now() - now);
   console.log(d);   
   d.draw(document.getElementById("canvas"));
   window.dungeon = d;
},10);

var Position = {
   north:0,
   south:1,
   west:2,
   east:3,
}

var Size = {
   _1x1:0
}

var RoomType = {
   normal:0,
   entrance:1,
   exit:2,
}

var getRandomActorModel = function () {
    return 'bat';
}

var getRandomBossActorModel = function () {
    return 'bat';
}

var Monster = function(){
   this.actorModel = getRandomActorModel();
   this.dmg = 1;
   this.def = 1;
   this.size = 1;
}

var Key = function() {
  this.mustKillAllToPickup = false;
}

var Teleporter = function () {
   this.position = null;
   this.destination = null;
   this.mustKillAllToUse = false;
   this.keysRequiredToUse = 0;
}

var Dungeon = function(){
   this.rooms = [];
}

Dungeon.prototype.draw = function(canvas){
   canvas.width = 1000;
   canvas.height = 1000;
   canvas.style.width = '1000px';
   canvas.style.height = '1000px';
   
   var sx = 500;
   var sy = 500;
   var ROOM_SIZE = 32;
   var TILE_SIZE = 40;
   var margin = (TILE_SIZE - ROOM_SIZE) / 2;
   var TELE_SIZE = 4;
   
   var ctx = canvas.getContext('2d');
   ctx.fillStyle = 'black';
   for(var i = 0 ; i < this.rooms.length; i++){   
      var room = this.rooms[i];
      if( room.type === RoomType.normal ) ctx.fillStyle="#000000";
      else if( room.type === RoomType.entrance ) ctx.fillStyle="#00FF00";
      else if( room.type === RoomType.exit ) ctx.fillStyle="#FF0000";
      else ctx.fillStyle="#0000FF";

      ctx.fillRect(sx + room.x * TILE_SIZE + margin,
         sy + room.y * TILE_SIZE + margin,ROOM_SIZE,ROOM_SIZE);
      if(DRAW_ROOM_ID){
         ctx.fillStyle = 'yellow';
         ctx.fillText('' + room.id + ((room.keys.length > 0) ? " key" : ""),
            sx + room.x * TILE_SIZE + margin,
            sy + room.y * TILE_SIZE + margin + 10)
         ctx.fillStyle = 'black';      
      }
      for(var j = 0; j < room.teleporters.length; j++){
         if(room.teleporters[j].position === Position.north)
            ctx.fillRect(sx + (room.x + 0.5) * TILE_SIZE - TELE_SIZE / 2,
               sy + room.y * TILE_SIZE,
               TELE_SIZE,
               margin);
         else if(room.teleporters[j].position === Position.south)
            ctx.fillRect(sx + (room.x + 0.5) * TILE_SIZE - TELE_SIZE / 2,
               sy + (room.y + 1) * TILE_SIZE - margin,
               TELE_SIZE,
               margin);
         else if(room.teleporters[j].position === Position.west)
            ctx.fillRect(sx + room.x * TILE_SIZE,
               sy + (room.y + 0.5) * TILE_SIZE - TELE_SIZE / 2,
               margin,
               TELE_SIZE);
         else if(room.teleporters[j].position === Position.east)
            ctx.fillRect(sx + (room.x + 1) * TILE_SIZE - margin,
               sy + (room.y + 0.5) * TILE_SIZE - TELE_SIZE / 2,
               margin * 2,
               TELE_SIZE);
      }   
   }   
}

var Room = function Room() {
   this.id = Math.random();
   this.type = RoomType.normal;
   this.x = 0;
   this.y = 0;
   this.size = Size._1x1;
   this.teleporters = [];
   this.monsters = [];
   this.keys = [];
};
</script>

rc
Admin

Posts : 164
Reputation : 9
Join date : 2016-04-04
Age : 22
Location : Montreal

View user profile http://rainingchain.com

Back to top Go down

Re: Planned - Randomly Generated Dungeon

Post by Ark on Thu Jul 21, 2016 3:22 pm

I already suggested a random walk algorithm and even wrote one ( https://htmlpreview.github.io/?https://github.com/ArkNameThatIsNotTaken/Random-Walk-Dungeon-Generator/blob/master/RandomWalkDungeonCreator.html ), but siiz' algorithm has the advantage of stopping at already generated rooms preventing inefficient walking through them like random walk does.
My suggestion is to improve siiz' algorithm so that once it tries to walk into an already generated room, a teleport to that room is created before aborting the walk. This allows for shortcuts and circles, thus requiring and rewarding greater navigation skills.
I also believe that readability and maintenance can be significantly improved by using prototypes. Refer to my algorithm for inspiration.

Thank you for the contribution, siiz. It is impressive work for a beginner.

Ark

Posts : 59
Reputation : 3
Join date : 2016-04-10

View user profile

Back to top Go down

Re: Planned - Randomly Generated Dungeon

Post by rc on Thu Jul 21, 2016 10:58 pm

His script will actually be re-written in Typescript using classes and optimized a bit.
Like you said, I will modify it so it can create cycles.
I will also make it so keys appear in dead-ends and I will add a bias to encourage more compact layout.

Overall, his algo is really good. Very Happy

rc
Admin

Posts : 164
Reputation : 9
Join date : 2016-04-04
Age : 22
Location : Montreal

View user profile http://rainingchain.com

Back to top Go down

Re: Planned - Randomly Generated Dungeon

Post by rc on Wed Oct 26, 2016 11:33 pm

The randomly generated dungeons are now in-game!


rc
Admin

Posts : 164
Reputation : 9
Join date : 2016-04-04
Age : 22
Location : Montreal

View user profile http://rainingchain.com

Back to top Go down

Re: Planned - Randomly Generated Dungeon

Post by Sponsored content Today at 9:28 am


Sponsored content


Back to top Go down

View previous topic View next topic Back to top

- Similar topics

 
Permissions in this forum:
You cannot reply to topics in this forum