Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I am trying to convert this dungeon algorithm from java into javascript, however, my script works 70% of the time. When it works, the rooms are missing a wall on one side, and when it does not work, it is stuck in an infinite loop.

room is missing a side

room is missing a side

room is missing a side

(Sorry the images are small, getting the pixels to scale is another problem :P)

I am guessing the makeRoom() is the problem, and if not, its definitly createDungeon(). So when the algorithm works, after the first makeRoom() call, I get some 1 and 2, in my dungeon_map array, where 1 is the brown wall, and 2 is the yellow floor. When the algorithm does not work, there arent any 1 or 2 in the dungeon_map array, leading to an infinite loop.

I am pretty sure the java code works, because here is one with the output online. And here is the original.

The only thing that differs between my code and the others is the getRand() method, which I am pretty sure, just returns a number between the min and max that is passed in.

My entire code:

//size of the map
var xsize = 0;
var ysize = 0;

var tileSize = 100;
var objects = 0;

//define the %chance to generate either a room or a corridor on the map
//BTW, rooms are 1st priority so actually it's enough to just define the chance
//of generating a room
var chanceRoom = 75;
var chanceCorridor = 25;

//map
var dungeon_map = [];

//a list over tile types we're using
var tileUnused = 0;
var tileDirtWall = 1;
var tileDirtFloor = 2;
var tileStoneWall = 3;
var tileCorridor = 4;
var tileDoor = 5;
var tileUpStairs = 6;
var tileDownStairs = 7;

//setting a tile's type
function setCell(x, y, celltype)
{
   dungeon_map[x + xsize * y] = celltype;
}

//returns the type of a tile
function getCell(x, y)
{
   return dungeon_map[x + xsize * y];
}

function getRand(min, max)
{
   return Math.floor(Math.random() * (max - min + 1) + min);
}

function makeCorridor(x, y, length, direction)
{
   var len = getRand(2, length);
   var floor = tileCorridor;
   var dir = 0;

   if (direction > 0 && direction < 4)
      dir = direction;

   var xtemp = 0;
   var ytemp = 0;

   if (x < 0 || x > xsize)
         return false;
   if (y < 0 || y > ysize)
         return false;

   if (dir == 0)
   {
      // north
      xtemp = x;

      //make sure its not out of bounds
      for (ytemp = y; ytemp > (y - len); ytemp--)
      {
         if (ytemp < 0 || ytemp > ysize)
            return false;
         if (getCell(xtemp, ytemp) != tileUnused)
            return false;
      }

      //start building
      for (ytemp = y; ytemp > (y - len); ytemp--)
      {
         setCell(xtemp, ytemp, floor);
      }
   }
   else if (dir == 1)
   {
      // east
      ytemp = y;

      for (xtemp = x; xtemp < (x + len); xtemp++)
      {
         if (xtemp < 0 || xtemp > xsize)
            return false;
         if (getCell(xtemp, ytemp) != tileUnused)
            return false;
      }

      for (xtemp = x; xtemp < (x + len); xtemp++)
      {
         setCell(xtemp, ytemp, floor);
      }
   }
   else if (dir == 2)
   {
      // south
      xtemp = x;

      //make sure its not out of bounds
      for (ytemp = y; ytemp < (y + len); ytemp++)
      {
         if (ytemp < 0 || ytemp > ysize)
            return false;
         if (getCell(xtemp, ytemp) != tileUnused)
            return false;
      }

      //start building
      for (ytemp = y; ytemp < (y + len); ytemp++)
      {
         setCell(xtemp, ytemp, floor);
      }
   }
   else if(dir == 3)
   {
      // west
      ytemp = y;

      for (xtemp = x; xtemp > (x - len); xtemp--)
      {
         if (xtemp < 0 || xtemp > xsize)
            return false;
         if (getCell(xtemp, ytemp) != tileUnused)
            return false;
      }

      for (xtemp = x; xtemp > (x - len); xtemp--)
      {
         setCell(xtemp, ytemp, floor);
      }
   }

   return true;
}

function makeRoom(x, y, xlength, ylength, direction)
{
   console.log("DIRECTION: " + direction);
   //define the dimensions of the room, it should be at least 4x4 tiles 
   //(2x2 for walking on, the rest is walls)
   var xlen = getRand(4, xlength);
   var ylen = getRand(4, ylength);

   //tile type its going to be filled with
   var floor = tileDirtFloor;
   var wall = tileDirtWall;

   var dir = 0;
   if (direction > 0 && direction < 4)
      dir = direction;

   if (dir == 0)
   {
      //north
      //check if there is enough space left for a room
      for (var ytemp = y; ytemp > (y - ylen); ytemp--)
      {
         if (ytemp < 0 || ytemp > ysize) 
            return false;

         for (var xtemp = (x - xlen / 2); xtemp < (x + (xlen + 1) / 2); xtemp++)
         {
            if (xtemp < 0 || xtemp > xsize) 
               return false;
            if (getCell(xtemp, ytemp) != tileUnused) 
               return false;
         }
      }

      //we're still here, build
      for (var ytemp = y; ytemp > (y - ylen); ytemp--)
      {
         for (var xtemp = (x - xlen / 2); xtemp < (x + (xlen + 1) / 2); xtemp++)
         {
            //start with the walls
            if (xtemp == (x - xlen / 2)) 
               setCell(xtemp, ytemp, wall);
            else if (xtemp == (x + (xlen - 1) / 2)) 
               setCell(xtemp, ytemp, wall);
            else if (ytemp == y) 
               setCell(xtemp, ytemp, wall);
            else if (ytemp == (y - ylen + 1)) 
               setCell(xtemp, ytemp, wall);
            else 
               setCell(xtemp, ytemp, floor); //and then fill with the floor
         }
      }
   }
   else if (dir == 1)
   {
      //east
      for (var ytemp = (y - ylen / 2); ytemp < (y + (ylen + 1) / 2); ytemp++)
      {
         if (ytemp < 0 || ytemp > ysize) 
            return false;

         for (var xtemp = x; xtemp < (x + xlen); xtemp++)
         {
            if (xtemp < 0 || xtemp > xsize) 
               return false;
            if (getCell(xtemp, ytemp) != tileUnused) 
               return false;
         }
      }

      for (var ytemp = (y - ylen / 2); ytemp < (y + (ylen + 1) / 2); ytemp++)
      {
         for (var xtemp = x; xtemp < (x + xlen); xtemp++)
         {
            if (xtemp == x) 
               setCell(xtemp, ytemp, wall);
            else if (xtemp == (x + xlen - 1)) 
               setCell(xtemp, ytemp, wall);
            else if (ytemp == (y - ylen / 2)) 
               setCell(xtemp, ytemp, wall);
            else if (ytemp == (y + (ylen - 1) / 2)) 
               setCell(xtemp, ytemp, wall);
            else 
               setCell(xtemp, ytemp, floor);
         }
      }
   }
   else if (dir == 2)
   {
      //south
      for (var ytemp = y; ytemp < (y + ylen); ytemp++)
      {
         if (ytemp < 0 || ytemp > ysize) 
            return false;

         for (var xtemp = (x - xlen / 2); xtemp < (x + (xlen + 1) / 2); xtemp++)
         {
            if (xtemp < 0 || xtemp > xsize) 
               return false;
            if (getCell(xtemp, ytemp) != tileUnused) 
               return false;
         }
      }

      for (var ytemp = y; ytemp < (y + ylen); ytemp++)
      {
         for (var xtemp = (x - xlen / 2); xtemp < (x + (xlen + 1) / 2); xtemp++)
         {
            if (xtemp == (x - xlen / 2)) 
               setCell(xtemp, ytemp, wall);
            else if (xtemp == (x + (xlen - 1) / 2)) 
               setCell(xtemp, ytemp, wall);
            else if (ytemp == y) 
               setCell(xtemp, ytemp, wall);
            else if (ytemp == (y + ylen - 1)) 
               setCell(xtemp, ytemp, wall);
            else setCell(xtemp, ytemp, floor);
         }
      }
   }
   else if (dir == 3)
   {
      //west
      for (var ytemp = (y - ylen / 2); ytemp < (y + (ylen + 1) / 2); ytemp++)
      {
         if (ytemp < 0 || ytemp > ysize) 
            return false;

         for (var xtemp = x; xtemp > (x - xlen); xtemp--)
         {
            if (xtemp < 0 || xtemp > xsize) 
               return false;
            if (getCell(xtemp, ytemp) != tileUnused) 
               return false; 
         }
      }

      for (var ytemp = (y - ylen / 2); ytemp < (y + (ylen + 1) / 2); ytemp++)
      {
         for (var xtemp = x; xtemp > (x - xlen); xtemp--)
         {
            if (xtemp == x) 
               setCell(xtemp, ytemp, wall);
            else if (xtemp == (x - xlen + 1)) 
               setCell(xtemp, ytemp, wall);
            else if (ytemp == (y - ylen / 2)) 
               setCell(xtemp, ytemp, wall);
            else if (ytemp == (y + (ylen - 1) / 2)) 
               setCell(xtemp, ytemp, wall);
            else setCell(xtemp, ytemp, floor);
         }
      }
   }

   return true;
}

//print map to screen
function showDungeon()
{
   for (var y = 0; y < ysize; y++)
   {
      for (var x = 0; x < xsize; x++)
      {
         var cell = getCell(x, y);

         if (cell == tileUnused)
         {
            ctx.fillStyle = "#fff"; //white
         }
         else if (cell == tileDirtWall)
         {
            ctx.fillStyle = "#663300"; //brown
         }
         else if (cell == tileDirtFloor)
         {
            ctx.fillStyle = "#FFFFCC"; //yellow
         }
         else if (cell == tileStoneWall)
         {
            ctx.fillStyle = "#000"; //black
         }
         else if (cell == tileCorridor)
         {
            ctx.fillStyle = "#0033FF"; //dark blue
         }
         else if (cell == tileDoor)
         {
            ctx.fillStyle = "#00CCFF"; //lightblue
         }
         else if (cell == tileUpStairs)
         {
            ctx.fillStyle = "#00FF33"; //green
         }
         else if (cell == tileDownStairs)
         {
            ctx.fillStyle = "#FF0000"; //red
         }

         ctx.fillRect(x, y, tileSize, tileSize);
      }
   }
}

function createDungeon(inx, iny, inobj)
{
   if (inobj < 1) 
      objects = 10;
   else 
      objects = inobj;

   //adjust the size of the map, if it's smaller or bigger than the limits
   if (inx < 3) 
      xsize = 3;
   else 
      xsize = inx;

   if (iny < 3) 
      ysize = 3;
   else 
      ysize = iny;

   console.log("X size of dungeon: \t" + xsize);
   console.log("Y size of dungeon: \t" + ysize);
   console.log("max # of objects: \t" + objects);

   //redefine the map var, so it's adjusted to our new map size
   dungeon_map = new Array(xsize * ysize);

   //start with making the "standard stuff" on the map
   for (var y = 0; y < ysize; y++)
   {
      for (var x = 0; x < xsize; x++)
      {
         //ie, making the borders of unwalkable walls
         if (y == 0) 
            setCell(x, y, tileStoneWall);
         else if (y == ysize - 1) 
            setCell(x, y, tileStoneWall);
         else if (x == 0) 
            setCell(x, y, tileStoneWall);
         else if (x == xsize - 1) 
            setCell(x, y, tileStoneWall);
         else 
            setCell(x, y, tileUnused);
      }
   }

   /*******************************************************************************
   And now the code of the random-map-generation-algorithm begins!
   *******************************************************************************/

   //start with making a room in the middle, which we can start building upon
   makeRoom(xsize / 2, ysize / 2, 8, 6, getRand(0,3));
   console.log("make room\n" + dungeon_map);
   //keep count of the number of "objects" we've made
   var currentFeatures = 1; //+1 for the first room we just made

   for (var countingTries = 0; countingTries < 1000; countingTries++)
   {
      //check if we've reached our quota
      if (currentFeatures == objects){
         break;
      }

      //start with a random wall
      var newx = 0;
      var xmod = 0;
      var newy = 0;
      var ymod = 0;
      var validTile = -1;

      //1000 chances to find a suitable object (room or corridor)..
      for (var testing = 0; testing < 1000; testing++)
      {
         newx = getRand(1, xsize - 1);
         newy = getRand(1, ysize - 1);
         validTile = -1;

         if (getCell(newx, newy) == tileDirtWall || getCell(newx, newy) == tileCorridor)
         {
            //check if we can reach the place
            if (getCell(newx, newy + 1) == tileDirtFloor || getCell(newx, newy + 1) == tileCorridor)
            {
               validTile = 0;
               xmod = 0;
               ymod = -1;
            }
            else if (getCell(newx - 1, newy) == tileDirtFloor || getCell(newx - 1, newy) == tileCorridor)
            {
               validTile = 1;
               xmod = +1;
               ymod = 0;
            }
            else if (getCell(newx, newy - 1) == tileDirtFloor || getCell(newx, newy - 1) == tileCorridor)
            {
               validTile = 2;
               xmod = 0;
               ymod = +1;
            }
            else if (getCell(newx + 1, newy) == tileDirtFloor || getCell(newx + 1, newy) == tileCorridor)
            {
               validTile = 3;
               xmod = -1;
               ymod = 0;
            }

            //check that we haven't got another door nearby, so we won't get alot of openings besides
            //each other
            if (validTile > -1)
            {
               if (getCell(newx, newy + 1) == tileDoor) //north
                  validTile = -1;
               else if (getCell(newx - 1, newy) == tileDoor)//east
                  validTile = -1;
               else if (getCell(newx, newy - 1) == tileDoor)//south
                  validTile = -1;
               else if (getCell(newx + 1, newy) == tileDoor)//west
                  validTile = -1;
            }

            //if we can, jump out of the loop and continue with the rest
            if (validTile > -1) 
               break;
         }
      }

      if (validTile > -1)
      {
         //choose what to build now at our newly found place, and at what direction
         var feature = getRand(0, 100);
         if (feature <= chanceRoom)
         { 
            if (makeRoom((newx + xmod), (newy + ymod), 8, 6, validTile))
            {
               //a new room
               currentFeatures++; //add to our quota
               //then we mark the wall opening with a door
               setCell(newx, newy, tileDoor);
               //clean up infront of the door so we can reach it
               setCell((newx + xmod), (newy + ymod), tileDirtFloor);
            }
         }
         else if (feature >= chanceRoom)
         { //new corridor
            if (makeCorridor((newx + xmod), (newy + ymod), 6, validTile))
            {
               //same thing here, add to the quota and a door
               currentFeatures++;
               setCell(newx, newy, tileDoor);
            }
         }
      }
   }

   console.log("\ndone making room\n" + dungeon_map);
   /*******************************************************************************
   All done with the building, let's finish this one off
   *******************************************************************************/

   //sprinkle out the bonusstuff (stairs, chests etc.) over the map
   var newx = 0;
   var newy = 0;
   var ways = 0; //from how many directions we can reach the random spot from
   var state = 0; //the state the loop is in, start with the stairs

   while (state != 10)
   {
      for (var testing = 0; testing < 1000; testing++)
      {
         newx = getRand(1, xsize - 1);
         newy = getRand(1, ysize - 2); //cheap bugfix, pulls down newy to 0<y<24, from 0<y<25

         ways = 4; //the lower the better

         //check if we can reach the spot
         if (getCell(newx, newy + 1) == tileDirtFloor || getCell(newx, newy + 1) == tileCorridor)
         {
            //north
            if (getCell(newx, newy + 1) != tileDoor)
               ways--;
         }
         if (getCell(newx - 1, newy) == tileDirtFloor || getCell(newx - 1, newy) == tileCorridor)
         {
            //east
            if (getCell(newx - 1, newy) != tileDoor)
               ways--;
         }
         if (getCell(newx, newy - 1) == tileDirtFloor || getCell(newx, newy - 1) == tileCorridor)
         {
            //south
            if (getCell(newx, newy - 1) != tileDoor)
               ways--;
         }
         if (getCell(newx + 1, newy) == tileDirtFloor || getCell(newx + 1, newy) == tileCorridor)
         {
            //west
            if (getCell(newx + 1, newy) != tileDoor)
               ways--;
         }

         //console.log("ways: " + ways);

         if (state == 0)
         {
            if (ways == 0)
            {
               console.log("upstairs");
               //we're in state 0, let's place a "upstairs" thing
               setCell(newx, newy, tileUpStairs);
               state = 1;
               break;
            }
         }
         else if (state == 1)
         {
            if (ways == 0)
            {
               console.log("downstairs");
               //state 1, place a "downstairs"
               setCell(newx, newy, tileDownStairs);
               state = 10;
               break;
            }
         }
      }
   }

   //all done with the map generation, tell the user about it and finish
   console.log("# of objects made: \t" + currentFeatures);

   return true;
}


///////////////////////////////////////////////////////////////////////////////////////////////////
// Create the canvas
var canvas = document.createElement("canvas");
var ctx = canvas.getContext("2d");
canvas.width = 70;
canvas.height = 70;
document.body.appendChild(canvas);

//test
var x = 70;
var y = 70;
var dungeon_objects = 40;

//then we create a new dungeon map
if (createDungeon(x, y, dungeon_objects))
{
   //always good to be able to see the results..
   showDungeon();
}

and jfiddle.

share|improve this question
5  
"My entire code" is never a good start. –  Lohoris Sep 1 '11 at 10:03

1 Answer 1

You have a full algorithmic description there.

It seems to me this is a simple matter of intercepting your code flow after each step that the author describes, looking at the inputs and outputs by generating a log of sorts, and then just see where things go wrong, no?

I mean, unless you are a really sharp with Java and JavaScript both (i.e. you know like the back of your hand the difference in how the collections work, how null-values are handled, how the math functions differ etc.), then you are going to likely need to understand the algorithm to some degree, in order to know where it's going wrong, and thus in order to port it successfully. This has been my experience in porting game algorithms. Some of them were really tough, but only once I understood each step, could I know if things were going wrong in that step.

Learn to use a step-through debugger like FireBug. Learn to watch values as they change. Either log values for perusal after runtime, or in realtime code, keep readouts on your screen that are constantly updating, Matrix-style.

As Lo'oris said, few people will want to trawl through your broken code to help you... we'd rather give you the tools to learn how to do this not only this time around, but in the future too.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.