Planned - Randomly Generated Dungeon

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:

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>


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>


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.

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.

The randomly generated dungeons are now in-game!