Roguelike Building Generator

Question

I decided to make a roguelike for fun. Here's the first part, a building generator (in the link at the bottom of the post, each square represents a building):

var mm=millis()
//var mm2=0
var rooms=[]
var S=63 //What's a better name for S?
S+=S%2 //forces S to be even
for(var i=0;i<S;i++){
 rooms[i]=[]
 for(var j=0;j<S;j++){
 rooms[i][j]=Infinity
 }
}
var pick=function(array){
 var queue=[]
 //var mm3=millis()
 for(var i=1;i<S-1;i++){
 for(var j=1;j<S-1;j++){
 if(rooms[i][j]==Infinity){
 var t = min(min(rooms[i-1][j],rooms[i][j-1]),
 min(rooms[i+1][j],rooms[i][j+1]))
 if(t<Infinity){
 queue.push([i,j,pow(S,2)])
 }
 }
 }
 }
 //mm2+=millis()-mm3
 return queue[~~(Math.random()*queue.length)]
}
var createRoom=function(pos){
 rooms[pos[0]][pos[1]]=pos[2]
}
var drawRooms=function(){
 pushMatrix()
 //scale(4.0)
 colorMode(HSB)
 background(255, 0, 255)
 noStroke()
 for(var i=0;i<S;i++){
 for(var j=0;j<S;j++){
 if(rooms[i][j]!==Infinity){
 fill(rooms[i][j]*10,255,255)
 rect(i*width/S,j*height/S,ceil(width/S),ceil(height/S))
 }
 }
 }
 popMatrix()
}
var redo=function(x,y,t){
 if(rooms[x][y]!==Infinity&&rooms[x][y]>t){
 rooms[x][y]=t
 t++
 redo(x+1,y,t)
 redo(x,y+1,t)
 redo(x-1,y,t)
 redo(x,y-1,t)
 }
}
createRoom([S/2,S/2,1])
for(var i=0;i<pow(S,2)/10;i++){
 createRoom(pick())
}
redo(S/2,S/2,0)
drawRooms()
fill(0)
var benchmark=millis()-mm
text('Took '+benchmark+' milliseconds to run.',10,10)

I would have done it in processing.py, but I had some trouble with matrices. If anyone knows how to use them in vanilla python, feel free to give me an explanation.

Lastly, here's the link I mentioned if you want to have a look at it:

(The "rainbow" part represents the distance from the center "room" (the reddest square) to the colored room.)

https://www.khanacademy.org/computer-programming/roguelike-room-generator/6424540231008256

• Quuxplusone: Could you clarify whether this code even does what you wanted it to do? You talk about "rectangles" and "rooms", but in the linked snippet I don't see any rectangles; it just generates a sort of random-walk-looking blob with rainbow colors. Mini review: use semicolons; min can take 4 arguments as easily as 2; run with warnings enabled and then fix all the warnings. (In this case, Khan Academy's own checker complains about the semicolons and one use of ==.)
• Ben Rivers: Yes, it certainly does what I want it to do. For the part about rectangles, I fixed it so that the boundaries for the rectangles are visible, and so the rectangles are larger and more rectangley. I'm really grateful for the part about min, but personally don't see what's wrong with not using semicolons or using==(I'd be thankful for an explanation on on why these are considered bad practice)
• Joseph: What does this code exactly do (aside from generating rainbow squares)? What is "roguelike"? Never assume everyone knows what you know.
• Ben Rivers: @Joseph, thanks, embedded a link and explained what each square represents.

Answer 1

General disclaimer: I have tried to find as many things in your code that you can fix, but I may not have found everything. Similarly, just because there may be a lot below doesn't mean the code is useless.

Before the review

I will be reviewing the code as posted on KhanAcademy, since I cannot get the code working here. I presume it is run through some kind of compiler. You are currently using an undefined function millis and use min and pow without the Math prefix, which makes those undefined in regular javascript as well.

Use a linter

You have completely disabled the linter in your code. I recommend against this, except for the cases where you have to include a dependency within your own code and cannot spare the time to rewrite it to the same code style you are using.

Linters force you to write consistent code. Their rules have been debated over and over, and their defaults are usually workable. If you do not like a certain rule, you can disable it, or change the rule. If you have a good reason to do something in a specific way and it trips a rule, you can disable that rule for that single line or single block.

KhanAcademy seems to use JSHint. You can find the documentation here. In your case you consistently don't use semicolons. I personally prefer to always use them, because they prevent typos from causing weird bugs, but you can tell JSHint to stop bugging you about it with // jshint asi: true. Most of the weird behaviour will be catched by other rules.

Readability

Naming your variables

The biggest issue with your code is the naming of your variables and functions. Variables and function names are the primary way of understanding what a piece of code does. Comments come second to elaborate on some expectations you have.

• mm is used in the beginning. From the context I understand that this is the start time of your benchmark, so name it something like startTime.
• Single letter variable names are usually a bad idea. S is used to define the dimensions of your grid. Lets just call it that: dimensions.
• In your pick function, you use queue. A queue is a structure where you push things at the end and retrieve things from the beginning. Instead you pick a random element. A better name would be pool or collection or pickableRooms.
• Variables with a number in them usually indicate that you should rename them. dir2 is no exception. Considering that it is in a createPath function, I assume that it is a direction. After reading the context, I think this is actually something like oppositeDirection.
• pos2 is used just below that. Since it is going to point to the position in the direction given, lets call it adjecentPosition.
• t in your redo function puzzles me. I think it is supposed to be the distance from the center, so lets call it distance.
• The function name redo is unclear. You should replace it with what the function actually does, which seems to be to recalculate the distances for created rooms.

Unused variables

You have an unused variable in the argument list of your pick function. I am surprised the linter did not catch that. In any case, if you do not use an argument to a method in the method body, you should not include it in the signature.

If you would have used this argument array, you should have renamed it to what the variable actually contains, not its type. You could have used roomMatrix or distanceMatrix for example.

Odd bitwise NOT

You are using a double bitwise NOT operator in your code. After trying it out, I am guessing that this is some kind of operation to get the integer part of a float.

Since you never pass it negative numbers¹, considering you are calculating an index, just use Math.floor for readability.

Indentation

Somewhere in your code you have the following lines:

var t = min(min(rooms[i-1][j],rooms[i][j-1]),
 min(rooms[i+1][j],rooms[i][j+1]))

I think there are two things wrong with those two lines:

• You are manually aligning the two lines. Don't do this, because when you start using version control it will bite you. Lines that have not been changed should not be changed, because they cause merge conflicts and cause lines to show up in commits that have only whitespace changes.
• If you put an opening brace at a certain indentation, you should put the closing brace at the same indentation. This goes for [, { and (.

The following code is better readable, and highlights that you believe that you can only use two arguments in the Math.min(..) function, which is not the case.

var t = min(
 min(rooms[i-1][j],rooms[i][j-1]),
 min(rooms[i+1][j],rooms[i][j+1])
)

So we can change it to the following code, which makes it clear that you want to actually get the minimum of all adjacent rooms.

var t = min(
 rooms[i-1][j],
 rooms[i][j-1],
 rooms[i+1][j],
 rooms[i][j+1]
)

Code structuring

Functions

You have put part of your code into functions. A notable exception is the initialisation code. Consider moving it to it's own function.

Function syntax

The syntax var a = function (arguments) is a bit odd. It nicely demonstrates that a function is actually a variable that you can call, but it does not seem very useful in this case. Consider just using function a (arguments).

I noticed that KhanAcademy finds this wrong syntax. I am clueless why this is.

Abstract away the underlying data structure

Your functions all interact with the underlying data structure in some way or another. You are currently also not checking for any errors. Once you start doing that, you will probably notice that you are duplicating code.

You probably want to hide the implementation of getting adjacent rooms to separate functions, such as north, and add error handling in there to handle cases where you are trying to get a room outside the boundaries.

Working of the program

Overlapping squares

Because of how you are calculating the width, you are adding up errors on the width of your squares, causing some of them to be off by one pixel.

Off by one

Any easy way of dealing with that is by calculating an effective width and height, and use that everywhere:

var effectiveWidth = floor(width / dimensions)
var effectiveHeight = floor(height / dimensions)

and

for (var i = 0; i < dimensions; i++) {
 for (var j = 0; j < dimensions; j++) {
 if (rooms[i][j] !== Infinity) {
 fill(rooms[i][j] * 255 / dimensions, 255, 255)
 rect(i * effectiveWidth, j * effectiveHeight, effectiveWidth, effectiveHeight)
 }
 }
}

The dimensions constant

You have a constant that defines on what grid we are playing. Except that you 'auto-correct' it. Don't produce erroneous behaviour when wrong input is given, but instead just give an error.

var dimensions = 6
if (dimensions % 2 !== 0) {
 throw new Error('Dimensions must be even')
}

You are off by one... twice

When you set dimensions to 4, you can have a maximum of 2 by 2 rooms. When you set it to 6, you can have a maximum of 4 by 4 rooms. You'll notice that the center is therefore also never in the center.

Off by... two?

What you actually want is to have the dimensions to be odd, so you can actually get the middle. Then you have to loop over all possible rooms. Then you just have to check if you are trying to find the value of a room outside the grid, and return Infinity in that case.

The result

//The "rainbow" part represents the distance from the center "room" (the reddest square) to the colored room.
//jshint asi: true
var startTime = millis()
var rooms = []
var paths = []
var dimensions = 5
var numberOfRooms = Math.floor(pow(dimensions, 2))
var padding = 20
var startX = Math.floor(dimensions / 2)
var startY = Math.floor(dimensions / 2)
var squareWidth = floor((width - padding * 2) / dimensions)
var squareHeight = floor((height - padding * 2) / dimensions)
if (dimensions % 2 !== 1) {
 throw new Error('dimensions should be odd')
}
var initialize = function() {
 for (var i = 0; i < dimensions; i++) {
 rooms[i] = []
 paths[i] = []
 for (var j = 0; j < dimensions; j++) {
 rooms[i][j] = Infinity
 paths[i][j] = [false, false, false, false] // up, right, down, left
 }
 }
}
var north = function(pos) {
 if (pos[1] === 0) {
 return Infinity
 }
 return rooms[pos[0]][pos[1] - 1]
}
var west = function(pos) {
 if (pos[0] === 0) {
 return Infinity
 }
 return rooms[pos[0] - 1][pos[1]]
}
var south = function(pos) {
 if (pos[1] === dimensions - 1) {
 return Infinity
 }
 return rooms[pos[0]][pos[1] + 1]
}
var east = function(pos) {
 if (pos[0] === dimensions - 1) {
 return Infinity
 }
 return rooms[pos[0] + 1][pos[1]]
}
var pickRandomRoom = function() {
 var pool = []
 for (var i = 0; i < dimensions; i++) {
 for (var j = 0; j < dimensions; j++) {
 if (rooms[i][j] === Infinity) {
 var pos = [i, j]
 var t = min(
 north(pos),
 west(pos),
 south(pos),
 east(pos)
 )
 if (t < Infinity) {
 pool.push([i, j, pow(dimensions, 2)])
 }
 }
 }
 }
 return pool[Math.floor(Math.random() * pool.length)]
}
var createRoom = function(pos) {
 rooms[pos[0]][pos[1]] = pos[2]
}
var createPath = function(pos, dir) {
 var oppositeDirection = (dir + 2) % 4
 var adjacentPosition = [pos[0], pos[1]]
 paths[pos[0]][pos[1]][dir] = true
 switch (dir) { //there's gotta be some better way to do this
 case 0:
 adjacentPosition[0]--
 break
 case 1:
 adjacentPosition[1]--
 break
 case 2:
 adjacentPosition[0]++
 break
 case 3:
 adjacentPosition[1]++
 break
 }
 paths[adjacentPosition[0]][adjacentPosition[1]][oppositeDirection] = true
}
var drawRooms = function() {
 pushMatrix()
 //scale(4.0)
 colorMode(HSB)
 background(255, 0, 255)
 //noStroke()
 for (var i = 0; i < dimensions; i++) {
 for (var j = 0; j < dimensions; j++) {
 if (rooms[i][j] !== Infinity) {
 fill(rooms[i][j] * 255 / dimensions, 255, 255)
 rect(
 padding + i * squareWidth,
 padding + j * squareHeight,
 squareWidth,
 squareHeight
 )
 }
 }
 }
 popMatrix()
}
var recalculateDistances = function(x, y, distance) {
 if (
 x >= 0 &&
 x < dimensions &&
 y >= 0 &&
 y < dimensions &&
 rooms[x][y] !== Infinity &&
 rooms[x][y] > distance
 ) {
 rooms[x][y] = distance
 distance += 1
 recalculateDistances(x, y + 1, distance)
 recalculateDistances(x + 1, y, distance)
 recalculateDistances(x, y - 1, distance)
 recalculateDistances(x - 1, y, distance)
 }
}
initialize()
createRoom([startX, startY, 1])
for (var i = 0; i < numberOfRooms - 1; i++) {
 createRoom(pickRandomRoom())
}
recalculateDistances(startX, startY, 0)
drawRooms()
fill(0)
var benchmark = millis() - startTime
text('Took ' + benchmark + ' milliseconds to run.', 10, 10)

Or as working on KhanAcademy

Footnotes

• ¹ Math.floor returns the highest integer smaller than the argument passed to it, so Math.floor(-1.5) === -2. The bitwise not trick returns something different: ~~-1.5 === -1. Add a comment to these kind of tricks so your future self does not have to figure out what such an odd trick does.

• Ben Rivers: Upvote and accept, this is a great answer to an awful question. The reason for function foo(){} being disabled on KA is due to security, and I personally prefer to use it over var foo=function(){} in most cases.
• Ben Rivers: Concerning the footnotes: I've always thought of ~~ as truncation and not rounding.
• Sumurai8: Strictly speaking, the ~~ operation on any variable should return that variable, since flipping all bits twice would return the bits in the normal state. Javascript apparently makes it an int first. If you want the "truncate" behaviour, you could also use parseInt.
• Kruga: @Sumurai8 or just use the built-in Math.trunc()
• Sumurai8: I had no clue that function existed. It appears it is not supported by IE11 though, which is a shame. That would be the obvious choice to well... truncate... a value.

Answer 2

Using objects

Ouch your code is a heading down a road to many problems. You need to organize the code into clear related object.

Rather than a full review this is a suggestion example. See the code sample .

Some info regarding sample.

Code has settings together at too. Uses a canvas directly rather than a library.

displayWidth / roomSize sets what you had as S

There are two object.

Room hold all that is needed for a room. Where it is, if it has been add (open). Rooms that are on the edge (your pick rooms) are call candidates and a room will have a flag to indicate it is a candidate.

Dungeon creates and holds all rooms. It has 3 Arrays, one for all rooms, one for open rooms, and one for candidate rooms.

When a room is added it is moved to he open array. All the rooms next to it that are not open and have not yet been put on the candidate list are flagged as candidates and added to the candidate array.

After a room is added a random room is removed from the candidate array and opened. It is done what no more candidates are avalible or the open room count has been reach.

Then it draws the rooms.

This code is many times faster than using the tedious iteration searches as it does not waste time iterating over unrelated rooms. Also dist calc is done as the rooms are added.

BTW for positive numbers floor them with logical OR zero (see code). ~~ is two operations so half the speed of a single operator.

const displayWidth = 512;
const displayHeight = 512;
const roomSize = 8; // Room size in pixels number of rooms will fit canvae
const distColScale = 20;
const dungeonSize = displayWidth / roomSize | 0;
const roomCount = dungeonSize * dungeonSize | 0;
const maxOpenRooms = roomCount / 3;
const directions = [{x : 0, y : -1}, {x : 1, y : 0}, {x : 0, y : 1}, {x : -1, y : 0}];
const canvas = document.createElement("canvas");
canvas.width = displayWidth;
canvas.height = displayHeight;
document.body.appendChild(canvas);
const ctx = canvas.getContext("2d");
function Room(index, dungeon) {
 this.row = index / dungeon.size | 0;
 this.col = index % dungeon.size;
 this.x = this.col * roomSize;
 this.y = this.row * roomSize;
 this.color = "red";
 this.dist = 0;
 this.open = false; 
 this.candidate = false; 
}
Room.prototype = { // the functions for a room
 draw() { // draws a room
 ctx.fillStyle = "black";
 ctx.fillRect(this.x, this.y, roomSize, roomSize);
 ctx.fillStyle = this.color;
 ctx.fillRect(this.x+1, this.y+1, roomSize-2, roomSize-2);
 },
 distColor(dist) {
 this.color = "hsl(" + ((dist * 255 / distColScale) % 360) + ",100%,50%)";
 this.dist = dist;
 },
}
function Dungeon(size) {
 this.size = size;
 this.rooms = []; // to hold all rooms
 this.open = []; // holds open rooms 
 this.candidates = []; // to hold rooms that can be added
 for (let i = 0; i < roomCount; i++) { this.addRoom(new Room(i, this)) }
 var room = this.roomAt(size / 2 | 0, size / 2 | 0);
 while (room !== undefined && this.open.length < maxOpenRooms) {
 this.openRoom(room);
 room = this.randomCandidate()
 }
 this.drawOpenRooms();
}
Dungeon.prototype = {
 addRoom(room) {this.rooms.push(room) },
 drawOpenRooms() {
 ctx.clearRect(0, 0, displayWidth, displayHeight);
 for (const room of this.open) { room.draw() }
 },
 roomAt(x, y) { // get the room at x,y
 if (x >= 0 && x < this.size && y >= 0 && y < this.size) {
 return this.rooms[x + y * this.size];
 }
 },
 randomCandidate() { // returns a random candidate room
 if (this.candidates.length === 0) { return } // no rooms
 return this.candidates.splice(Math.random() * this.candidates.length | 0, 1)[0];
 },
 openRoom(room) { // open room and add ajoining rooms to candidate array
 room.open = true;
 this.open.push(room);
 const dist = room.dist + 1; //Candidates are 1 more away
 for (const dir of directions) {
 const r = this.roomAt(room.col + dir.x, room.row + dir.y); // r for room
 if (r && !r.open && !r.candidate) {
 r.distColor(dist);
 r.candidate = true;
 this.candidates.push(r); 
 }
 }
 }
}
var testD = new Dungeon(dungeonSize);

Hope this helps, take what you want, it is real quick nut I had to do something as your code looked like it needed a restart.

• Ben Rivers: +1 for good coding practices and using ctx, but the distance detection is off because every initialized tile performs it at the time of their creation.
• Blindman67: @BenRivers The dist calc is correct as your original does not account for the fact that the rooms are connected by doors and the distance is how many doors must be traversed not the line of sight (Manhattan) distance
• Ben Rivers: I don't remember mentioning doors. I had always envisioned each room as being connected to all adjacent rooms.