< rld> <@respect_the_pouch> Does anyone know of any writeups about
Rogue's level generation?
< thrig> not much to say, it put down up to 9 rooms then wires them
up with corridors; corridors may sometimes dead end or
emergently cross one another. secret doors, items,
monsters, etcIn more detail there's a "new_level" function call that is run on level change. rogue, at least as of version 3.6.3 from 1981, does not have stairs, but rather has optional and non-optional level change teleporters, where the optional one is used with the ">" key and puts you somewhere on a new random level one level down, or you can also go up on the "stair", when you have the amulet, for a random level one level up. The non-optional level teleporter is a pit trap that drops you down a level, though you could optionally jump into one of those to escape a monster. new_level is called at random points during a game, and only then is the new level generated. This is in contrast to roguelikes that generate the entire dungeon in advance, or use a distinct random number generator for level generation such that different players playing the same random seed see the same dungeon, regardless of how or when they reach particular levels. In rogue, the level generation for a particular level depends on the RNG state at the time new_level is entered. Ancient systems lacked the memory to build the entire dungeon in advance, and competitive play where players all play the same seed and therefore may expect to see the same dungeon had not yet been invented?
The RNG used a (I'm pretty sure) 16-bit seed, so not that many unique levels can be generated compared to modern systems using larger seeds. A player with a level catalog and knowledge of the code may be able to determine the RNG state at the time new_level is called, and therefore from that know where and what things are on the level. This could be a problem in competitive play, and is why some modern roguelikes use much larger seed values or distinct RNG streams for level generation to make this sort of attack more difficult. NetHack suffered from a RNG prediction attack, so this is not a theoretical concern.
=> all the rogue levels in my version of rogue
The "new_level" function steps through the following:
And that's it! Control returns to the "get a key from the player" command loop after some checks whether the player has won and maybe to print a message describing the level change. Some more detail on particular steps above follows.
The "do_rooms" call draws up to nine rooms, placed randomly within a grid. An array of structs holds various details.
typedef struct {
int x;
int y;
} coord;
struct room {
coord r_pos; /* Upper left corner */
coord r_max; /* Size of room */
coord r_gold; /* Where the gold is */
unsigned int r_goldval; /* How much the gold is worth */
int r_flags; /* Info about the room */
int r_nexits; /* Number of exits */
coord r_exit[4]; /* Where the exits are */
};Zero to three rooms inclusive may be left out; this has some complications for passage drawing which traverses through the grid space a room would occupy. Besides whether a room is gone, the only other r_flags is whether a room is dark, or not. Rooms get darker more often deeper. If dark, the "passage" field of view is used, which only allows adjacent cells to be seen. Otherwise, the whole room is lit up and visible.
Some random numbers are rolled to vary the room size and placement of each not-missing room within the grid where that room can appear.
Gold is maybe allocated to r_gold for each room, but only on levels deeper than the player has already been, and not if the player has the amulet.
Each room is drawn; this is mostly curses addch(3) calls, and also to mvaddch(3) the gold if there is any.
A single monster is maybe placed into each room, with higher odds of creation (80% versus 25%) if the room has gold. As mentioned above, gold is only placed when the player is reaching a new, deeper level, and not when they have the amulet.
Monsters are defined with a "thing" struct held in a linked list, in addition to where the monster's ASCII character (A..Z) is in a curses window. This allows telepathy to show where the monsters are by temporarily drawing that curses window, and the linked list can be walked through to find monsters. There usually are not very many monsters; memory was very limited back then, and rogue was a pretty heavy process for the time.
WINDOW *cw; /* Window that the player sees */
WINDOW *hw; /* Used for the help command */
WINDOW *mw; /* Used to store mosnters */rogue also uses the curses stdscr window; that holds the level map, gold, items or objects, the "stairways", traps, doors, but not the player nor any monsters.
Certain monsters may carry item; that code is run here.
"do_passages" uses some pretty complicated logic to wire up a graph of passages between the rooms. This is run multiple times "so that there isn't just one unique passage through it". That is, the graph will tend to have some number of cycles in it, but may not have any cycles.
There's some debugging code that indicates the graph may not always have been wired up aright.
A fairly complicated "conn" function is called to "addch(PASSAGE)" characters for the corridors. These are "#" as opposed to the "." used for room floors; the different floor characters are used to determine things that differ depending on whether the tile being interacted with is a room floor, passage floor, door, or trap. As mentioned elsewhere the "field of view" can differ if one is on a room versus a passage tile.
"conn" creates "dog leg" turns (90 degree bends), and there sometimes can be emergent design where two different passages cross one another (or maybe the same passage crosses itself?). A picture, or something like that, is worth a thousand words here? This level has almost all the notable features: a dead-end corridor, a missing room or three, but not an emergent passage crossing.
-----------
|.........|
----- ----------- |.........|
|...+############+.........| #############+.......*.|
|.*.| |.........+####### --+--------
----- -----+----- #
# ###
# ---------------+----
########## |..................|
################# |..................|
# # # |...*..............|
# # # |..................|
################# # ####################+..................|
# ---+----------------
### #
# #
----------- # #
|.........| # #
|.........| --+-------------- ##################
|.........+###### |...............| ##########################
|.........| ##########+.....*.........+##
----------- -----------------Secret doors are drawn in with the wall characters "|" or "-" so that the player cannot see them without searching or other means; there are more secret doors deeper.
Here's a map with all nine rooms and no loops; the rooms more typically have multiple connections to one another, though a more detailed analysis could be done for how cyclical rogue levels are.
------------- --------------
|...........| --------------------- |............|
|...........| |...................+### |............|
|...........| |...................| ##+............|
|...........| |...................| --------+-----
---------+--- --------------------- #
# #
############### ####
--+--------- ------- -----+------------------
|..........| ########+.....| |......................|
|..........+####### |.....| ####+......................|
|..........| |.....+############ |......................|
|...*......| |*....| |......................|
------------ ---+--- --+---------------------
###### #
--+---------- #####
----------------- #+.........*.| ------+---
|...............| #|...........| |........|
|...............| #|...........| |........|
|...............| #|...........| |........|
|..............*+###|...........| |........|
----------------- ------------- ----------And one with a passage crossing that creates a passage that loops. These are uncommon? There are at least two ways such crossings could be created, either by one passage going up and then left to a fixed point, and the other going left and then up to the same fixed point. Or, a passage could change direction now and then, like the passage over in the upper right has done, and sometimes cross itself.
############### ---------
# # |.......+#######
#################################+.......| #
# |.......| #
# |.......| #
# ----+---- #####################
# # ######
# ## ---------+---
------+----- --+-- |...........|
|..........| |...| |...........|
|..........| |...| |...........|
|..........| |...| |...........|
|..........| |...| |...........|
---------+-- --+-- ---+---------
####### ###### ####
-----------+---- -----------------+------ --+-------
|..............| |......................| |........|
|..............| |.....................*+###### |........|
|.........*....| #+......................| ###+........|
|..............| #|......................| |........|
|..............+##########|......................| |.....*..|
---------------- ------------------------ ----------There is always enough space between the rooms to fit a passage in.
There are also limitations on where diagonal moves are allowed. In particular, if the player is standing on a door "+" they cannot move diagonally onto a "." floor or possibly "#" passage tile. Only h j k l motions are allowed. Elsewhere, the full range of motion h j k l y u b n is allowed. Keypad? What's a keypad. I use the rogue keys.
y k u
\ | /
h - @ - l
/ | \
b j n"put_things" clears the linked list of level objects. Items are not placed if you have the amulet, unless you go deeper than you've gone before. The dungeon in theory goes on down forever; what happens when "level" overflows is left as an exercise to the reader. Human players may lack the patience to overflow a 32-bit integer.
My version of rogue has fiddled around with item generation; in the original code for 3.6.3 there is "rnd(100) < 35" percent odds of putting up to nine objects or items. Items are placed randomly on some free tile within some room (never in passages, nor on doors). The amulet is only placed when the level is below 25 and they do not have the amulet.
"new_thing" has some special code to place a food ration if one hasn't been generated in some number of levels, probably to help avoid the RNG going on a bad streak and causing a death due to lack of food (or a softlock in the rare case of the player being stuck in a passage between two floating eyes). This is an early instance of something like the "rubber band" odds that can be found in some roguelikes and various other games. Otherwise, the "pick_one" call figures out what the item type is by weighted odds (potions and scrolls being more common than rings or "sticks" (wand versus staff is just flavor text), then another weighted odds check is done for the type of potion or whatever, and then there's some code for each item that sets any necessary attributes on the item in question: whether the item is cursed, plus or minus value of rings, etc.
struct magic_item things[NUMTHINGS] = {
{ "", 27 }, /* potion */
{ "", 27 }, /* scroll */
{ "", 18 }, /* food */
{ "", 9 }, /* weapon */
{ "", 9 }, /* armor */
{ "", 5 }, /* ring */
{ "", 5 }, /* stick */
};Items are also "mvaddch" drawn into a curses window, in addition to living in the linked list of items.
Items do not stack on the floor, and only may be placed on a "." room tile or "#" passage tile. The monster (or player) structure has a "char t_oldch" field so that after moving the char that was before moving under the entity can be redrawn. Basically the monster "picks up" the tile they move to, then puts it back down when they move elsewhere. With this trick, mosnters can walk over items or whatever without destroying them.
ch = (char) mvwinch(stdscr, hero.y, hero.x);
if (ch != FLOOR && ch != PASSAGE) {
msg("There is something there already");
return;
}Note that the "put_things" function places "struct object" items, not monsters, but that monsters use a "struct thing" that is unrelated to objects. Ideally there would not be a naming confusion between items and monsters.
There are more of these deeper; an unoccupied point is found in a room (that is, only on "." floor tiles) and a trap is placed into a curses window with "addch(TRAP)". There's a fixed array of traps that details the type of trap and any flags (notably whether the trap has been found), and of course it's important that the map (used by the game) has the trap while the map (seen by the player) does not reveal unknown traps. Traps only affect the player, which is either unfair, or maybe they didn't have the tuits to code up trap and monster interactions.
And that's hopefully enough of a writeup for you to get the gist; for more detail see the code itself. There is not too much of it.
Welcome to the dungeon. Lit room, so the field of view is that room.
Welcome to dungeon 17979, Wizard.
-----------------------
+.....................|
|.....................+
|...............@.....|
----------+------------
Level: 1 Gold: 0 Hp: 12(12) Str: 12 Ac: 8 Exp: 1/0The "level map" at the same time as the prior picture, this is held in the curses stdscr window. Note how the "@" (the player) is not drawn; monsters cheat and home in on the player.t_pos coordinate instead of "looking" around like the player has to do. The "%" is the stairway, or as discussed above the optional level teleporter. Subsequent roguelikes would instead use "<" and ">" for stairs, and some would even dabble with persistent levels.
--More (level map)--
-------------- ------------------------
|............| #######+......................|
######+............| # |..............%.......|
# |.......*....+## |.............?........|
# -------------- |........!......:.....*|
######## ------------------------
#
# -----------------------
########################+.....................| ###
# # |.....................+###########
################ |.....................|
# ----------+------------
# #
# #
# #####
#################### ----+--------
# |...........| --------------------
# |...:..!....+## |...........?......|
---------------+- ##+...........| # |..................|
|....)..........+############ ------------- # |.........!........|
|/*.............| ###+...........*......|
----------------- --------------------And the monsters are off on their own window.
--More (monsters)--
S
J
K
KTwo kobolds, a jackal, and a snake. Why did it have to be snakes?
=> https://thrig.me/src/rogue36.git This content has been proxied by September (ba2dc).Proxy Information
text/gemini