ROT.Map.Rogue

[blinkdog]

Opening a new issue for ROT.Map.Rogue per @ondras in #61.

--- Want to back this issue? **[Post a bounty on it!](https://www.bountysource.com/issues/14802760-rot-map-rogue?utm_campaign=plugin&utm_content=tracker%2F297828&utm_medium=issues&utm_source=github)** We accept bounties via [Bountysource](https://www.bountysource.com/?utm_campaign=plugin&utm_content=tracker%2F297828&utm_medium=issues&utm_source=github).

[blinkdog]

ROT.Map.Rogue extends ROT.Map and not ROT.Map.Dungeon:

    ROT.Map.Rogue.extend(ROT.Map); 

In a way, it makes sense. My first quick glance over the code, it doesn't seem to populate this._rooms or this._corridors, so it doesn't really meet the contract of Dungeon.

However, the Interactive Manual documents the Rogue algorithm in the Map creation / Dungeon section, so it might be a little confusing if someone expects a Dungeon and they don't actually get one.

[blinkdog]

The Interactive Manual doesn't document the options for the Rogue generator.

[blinkdog]

I think there is a bug in the options processing in the Rogue constructor:

    if (!this._options.hasOwnProperty("roomWidth")) {
        this._options["roomWidth"] = this._calculateRoomSize(this._width, this._options["cellWidth"]);
    }

    if (!this._options.hasOwnProperty["roomHeight"]) {
        this._options["roomHeight"] = this._calculateRoomSize(this._height, this._options["cellHeight"]);
    }

Look very carefully:

    hasOwnProperty("roomWidth")

vs.

    hasOwnProperty["roomHeight"]

The brackets [ ] instead of the parens ( ) cause the if-statement to always be true in the roomHeight case.

[blinkdog]

Rogue has it's own random number generator function

ROT.Map.Rogue.prototype._getRandomInt = function(min, max) {
    return Math.floor(ROT.RNG.getUniform() * (max - min + 1)) + min;
}

that can probably be replaced by calls to ROT.RNG.getUniformInt instead :

    getUniformInt: function(lowerBound, upperBound) {
        var max = Math.max(lowerBound, upperBound);
        var min = Math.min(lowerBound, upperBound);
        return Math.floor(this.getUniform() * (max - min + 1)) + min;
    },

[CelticMinstrel]

Not sure if I should make a new issue for this, but... I'd like to see room and corridor information added to the Rogue generator.

[ondras]

@CelticMinstrel that is a reasonable request. I have, however, zero knowledge with respect to ROT.Map.Rogue (it is a contributed code), so it might take a while.

[hyakugei]

@CelticMinstrel What kind of info are you looking for? Specifically?

[CelticMinstrel]

Something similar to what the other dungeon map generators in ROT already supply, and preferably compatible with them so that I can choose a generator at runtime and then access room information without needing to remember what kind of generator it was.

[MattMcFarland]

@hyakugei first thanks a bunch for making this contribution 👍 👍 👍 👍

I'm currently dissecting the code for Rogue and have a number of questions about these "cells"

1. Why use cellWidth and cellHeight to compute the number of rooms, and also compute room sizes? If you have too many rooms, room width and heights fall into negative numbers, causing an error.

2. Why are cellWidth and cellHeight a configurable thing? What are the use cases for this?

3. What if we removed them and used the maps dimensions and room size to figure out how many cells we need? What would be the trade offs?

Thanks again for the awesome work, the rogue maps look really cool 👍

[CelticMinstrel]

Just for the record, I'm currently using the cellWidth and cellHeight parameters, so if they're removed I'd want to know how to get the exact same result with the new parameters.

My impression was that the Rogue algorithm divides the map into equal-sized cells, places a room in each cell (randomly sized to fit into the cell), and then randomly connects adjacent cells until all rooms are connected. I'm not sure how you could get the same effect by specifying room size instead of the size of the grid, without making the configuration rather more complicated.

[MattMcFarland]

Thanks for sharing CelticMinstrel, you are showing the good use case for cellWidth and cellHeight for the purpose of finding out the dimensions of the cells that rooms may fit into - what I'm wondering though, is can we make this not a configurable thing?

I'm currently writing my own interpretation of this algorithm, and instead I'm using a function to get the capacity of the grid itself, so you can get the max number of rooms that will fit in a given 2 dimensional grid providing you supply it with arguments describing the grid dimensions and maxRoom dimensions

For example:

const getMapCapacity = (mapWidth, mapHeight, maxRoomWidth, maxRoomHeight) =>
  (Math.floor(mapWidth / maxRoomWidth) * Math.floor(mapHeight / maxRoomHeight))
// returns the amount of rooms that will fit in the map

That way I can figure out how many rooms will fit in my map, and from there I should have my constraints, my cellWidth and cellHeight can be the maxRoomHeight and maxRoomWidth, so I figure I dont need those explicitly. The entire game-map is just divided up but the "cells" are just the right size (maybe maxRoom + 1) and the rooms are created, then connected, as you said.

Am I missing something?

[CelticMinstrel]

Well, I guess your formula isn't quite right since you've left no room for corridors... I'd think you need at least... say, five tiles between rooms in order to fit in a corridor? I mean you could do it with less, but accounting for the fact that most corridors have two bends, five tiles is probably a good minimum.

... what the heck is =>? Lambda or something?

Anyway, I guess you'd want to look at how the max room size is currently calculated from cell width/height and reverse the formula... but note that just because you can, doesn't mean you should. Is it more useful to specify the max room size, or is it more useful to specify the size of the grid in which the rooms sit? The answer is certainly not obvious - both ways make sense in certain situations.

[MattMcFarland]

It really makes sense to me to specify max room size, but I'm just not sure about letting users specify cell size from the start. Unless there is a valid use case? I think the largest a cell should be is the maximum size a room could be. This generator actually lets you specify the cell size AND room size, then creates the amount of rooms that fit for cell sizing, but then starts conflicting with the room size which can cause an exception to be thrown.

That being said, if someone finds they need to use cellWidth and cellHeight when they create a new Rogue() instance, it might be worth trying setting the roomSize, because the cells can be configured to fit the rooms (the calc I shared) - which also leaves plenty of room for corridors, and reduces the amount of code because you're not having to modify room sizing in a forloop because cell size is conflicting.

I will share my POC when I'm done.. and yes thats a lambda 👍

[MattMcFarland]

So I finally finished my POC! This only uses maxRoomWidth, maxRoomHeight, mapWidth, mapHeight, to internally figure out the cell sizes.

It follows the same algorithm, but its not using ROT.js - and its just a POC so it probably (most likely) has bugs D:

You can check it out here: https://github.com/MattMcFarland/learn-to-rogue (its got some ugly code, I just hacked it together over the past 4-5 hours xD) I still have a lot to learn, these algorithms are very fascinating to me.

[CelticMinstrel]

That... somehow doesn't really look like the same algorithm to me. The rooms are bumpy and the corridors are weird.

[hyakugei]

Just as a FYI, the ROGUE map code i wrote tries to follow the original ROGUE's room generation - a 3 x 3 "grid" , where each grid cell could have a room, or not. That is all that this map generator was built to do - follow the original ROGUEs style of map making. This is the article the code tries to follow:

http://web.archive.org/web/20080612035939/http://kuoi.com/~kamikaze/GameDesign/art07_rogue_dungeon.php

[MattMcFarland]

Thanks for the replies guys, Can we remove the cell width / height from configuration? Please outline for me what the use case is for it. The author has stated it is to be 3x3, and I dont think anyone is disagreeing that maxroom width and maxroom height are kindof the same thing, but less buggy.

Thanks, I love this project, and I hope I'm not offending anoyne, it kinda seems like I am and it's been totally unintentional.

also, yeah I purposely made the rooms bumpy, and corridors are using a random line variation, I can smooth that out, but it is more or less the same algorithm but with less operations. The visual is different because I thought it looked better, but I can take them out and will do later.

[CelticMinstrel]

I don't think I ever suggested that it's less buggy to use max room size instead of cell size. Whichever you use, the other can be trivially calculated from it and the overall map size. Both choices have their advantages. Since ROT is already using cell size, though, I don't see why you'd change it.

Regarding the corridors, they should favour fewer bends rather than more bends. I was apparently wrong about the current algorithm using no more than two bends, but it also doesn't generally produce "fat" corridors that look like a bad diagonal line, as your example shows.

I think making rooms irregular should be an option independent of the map generation algorithm. Exactly how to do that though, I'm not sure. In any case, rectangular rooms should be the default, not irregular rooms. It generates a dungeon, not a cave system, after all (there are better generators you can use if you want a cave system).

[MattMcFarland]

Thanks! Awesome advice, I am going to try again but this time implementing the algorithm according to the post that @hyakugei has shared.

Since ROT already uses cell sizing and room sizing, then yes I agree that really makes sense to keep it. Its just a minor caveat after-all, not too much a big of a deal. For some reason I thought it was a special case for just the rogue one.. 🐙

Big thanks on the web archive algo, I'm going to try that!

[CelticMinstrel]

Looking at the page @hyakugei linked, I can see an additional potential configurable parameter - how many extra connections to make. That would be nice to see too.

Also, it looks like the space between grid cells should be one tile. So, for example, with the default 3x3 cell grid and a 64x64 map, the maximum room size would be 20.

(As for what that page calls "gone rooms", that seems like it'd be relatively easy if you simply allow 1x1 rooms... though it's silly to call that a room, and I wouldn't want to see it have doors or show up in the list of rooms...)

[MattMcFarland]

I think I may have figured it out!!

[CelticMinstrel]

Well, that's definitely a good start but uhh... there still seem to be a few problems.

1. Your cellWidth / cellHeight seem to have a different meaning than the one accepted by the existing generator. The existing generator allows you to specify the number of cells, not their size (the 3 in your example). I'll call this gridWidth / gridHeight for the rest of this post. (This isn't exactly a problem per se, so much as something you should be aware of.)
2. Your cellWidth and cellHeight appear to be incorrect, going solely by the description of the algorithm - if I understand correctly, this could give you two rooms that are joined together (though presumably you've corrected for that later). It should be more like cellWidth = (mapWidth / gridWidth) - gridWidth - 1, where in your example gridWidth = 3; likewise for cellHeight. Of course you then need to account for the tile between cells in the rest of your code. (That's not to say that your method can't work too, but I'd think it's a little easier to reserve the space between cells.)
3. Maybe it's just because these are such tiny examples, but your corridors are all completely straight lines, with no bends in them.

[MattMcFarland]

@CelticMinstrel This latest rendition has been trying to faithfully follow the algorithm that was shared here: http://web.archive.org/web/20080612035939/http://kuoi.com/~kamikaze/GameDesign/art07_rogue_dungeon.php

So in there, I'm not seeing anything about combining rooms together as one room (as you're talking about in point 2??) - I'm also not seeing anything about diagonal rooms, instead the algorithm says to go from the center of one room to another. But I suppose you could go diagonal to a room that is diagonally placed (I didn't think about that until typing this)

Though the only mentioning of corridors turning is at the end where the person describing the algorithm says there were sometimes "L" shaped rooms. The person writing about the algorithm also suggests that you could have more than 9 rooms because the algorithm is fast. But I think the original algorithm was strictly for 3x3. That being said, changing the cell sizes should be pretty easy to do.

If the original algorithm is strictly 3x3, and corridors were not diagonal, then I might have something more accurate than what is in ROT (not necessarily better though!) Not sure really!

[CelticMinstrel]

@MattMcFarland wrote:

So in there, I'm not seeing anything about combining rooms together as one room (as you're talking about in point 2??)

You misunderstood what I was saying, so let me try again...

I was referring to this point in the linked article:

Mark Damon Hughes wrote:

If your rooms fill most or all of the space of the grid, your corridors will very short - just holes in the wall.

From that, I inferred that even if all of your rooms fill all of the space of the grid, there will still be walls between them. Thus, the total map size in the 3x3 version of the algorithm is equal to cellSize * 3 + 4 - three cells, plus walls between them and outer walls. More generally, this would be (cellSize + 1) * gridSize + 1.

That was my interpretation of the article, and it seems you interpreted differently... I don't think I can actually claim that your interpretation is wrong, though, as long as your algorithm does not create the possibility of two rooms being joined together without a corridor in between.

@MattMcFarland wrote:

I'm also not seeing anything about diagonal rooms, instead the algorithm says to go from the center of one room to another. But I suppose you could go diagonal to a room that is diagonally placed (I didn't think about that until typing this)

I assume you meant diagonal corridors. The article linked doesn't actually say anything about how rooms are connected, so I suppose it's understandable that you'd simply assume connecting the centers (though that's a very simplistic choice - it might be more interesting if corridors could exit from closer to the corners of a room, for example).

When I brought up diagonal corridors, I was using ROT's Rogue implementation as a reference, which can be experimented with at the bottom of this page. As you can see, the corridors typically have two or four bends in them. That doesn't make them diagonal corridors, but it does make them non-straight.

@MattMcFarland wrote:

The person writing about the algorithm also suggests that you could have more than 9 rooms because the algorithm is fast. But I think the original algorithm was strictly for 3x3. That being said, changing the cell sizes should be pretty easy to do.

The original Rogue algorithm was 3x3 according to the article, yes, but the person writing the article noted that this parameter is easily configurable, so you might as well allow it. More options are better in this case, I think.

@MattMcFarland wrote:

Though the only mentioning of corridors turning is at the end where the person describing the algorithm says there were sometimes "L" shaped rooms.

Yeah, that was interesting. As far as I can tell, ROT's Rogue algorithm doesn't allow this (unless it's incredibly rare). It might be interesting to change that.

@MattMcFarland wrote:

If the original algorithm is strictly 3x3, and corridors were not diagonal, then I might have something more accurate than what is in ROT (not necessarily better though!)

The original algorithm did have non-straight corridors. I just launched up rogue itself to check. I died pretty quickly, but every corridor I saw had exactly two bends. I didn't see any with four as in ROT's algorithm, nor any that were completely straight.

I also found some dead-end corridors, which I'm guessing is related to what the article called "gone rooms". If you're not distinguishing rooms from corridors, I think allowing these might be as simple as rarely letting the rooms be 1x1. Even if you are distinguishing rooms from corridors, you can just do that and then replace any 1x1 rooms with a corridor.

[MattMcFarland]

@CelticMinstrel Thanks again for your feedback.

I have reworked the algorithm, and while its still not perfect because the corridor construction is a little messy, it is a lot more flexible because it allows you to configure how many cells you want, and map dimensions. The rooms are also no longer centered in their cells, and the hall ways make twists and turns.

Source code: https://github.com/MattMcFarland/rogue-classic-map/blob/master/lib/index.js

[R-Gerard]

Not sure if I should make a new issue for this, but... I'd like to see room and corridor information added to the Rogue generator.

+1 for this. Extending Dungeon instead of Map would be very helpful.