💾 Archived View for thrig.me › blog › 2023 › 09 › 08 › rogue-mapgen.gmi captured on 2023-09-08 at 15:57:16. Gemini links have been rewritten to link to archived content
-=-=-=-=-=-=-
The map generation in rogue (1980) is primitive by today's standards, though if you run Moore's Law in reverse for a few decades you may see why. Nor was there much in the way of prior games to borrow from. Even with the simple map generation there are emergent features, notably where passages (represented by the "#" in the screenshots below) cross or loop back on themselves.
------------- --------------
|...........| --------------------- |............|
|...........| |...................+### |............|
|...........| |...................| ##+............|
|...........| |...................| --------+-----
---------+--- --------------------- #
# #
############### ####
--+--------- ------- -----+------------------
|..........| ########+.....| |......................|
|..........+####### |.....| ####+......................|
|..........| |.....+############ |......................|
|...*......| |*....| |......................|
------------ ---+--- --+---------------------
###### #
--+---------- #####
----------------- #+.........*.| ------+---
|...............| #|...........| |........|
|...............| #|...........| |........|
|...............| #|...........| |........|
|..............*+###|...........| |........|
----------------- ------------- ----------
-------------------------
|.....................*.| --------------
|.......................| |............|
|.......................| |.*..........|
----+-------------------- # -------+------
######## # #
---+--- #### #
|.....| # #
|.....| -----------+--- #####
|.....| ##########+.............| -----------+--
|.....| # |.....*.......+######### |............|
|.....+##### |.............| #######+.........*..|
-----+- -----+--------- ----+---------
# # #
# # ##########
##### # --+------------------
# #### |...................|
------+- ---------+------- |...................|
|......+###### |...............| #####+...................|
|......| ############+..........*....+### ---------------------
-------- -----------------
------
---------- |....|
|........| #########+....+###
|........| # |....| #
|...*....+######## ---+-- ###################
---+------ #
# #########
###### #
---------------------+--- ---+------
|.......................| |........|
|.......................+######+........|
|.......................| |........| #
|....................*..| |........| #
------------------------- -----+---- #####
# #
------ #### #
|...*| # #
|....| ------------+----- #
|....+############## |................| ----+--------
------ #######+................| |...........|
|...............*+###########+...........|
------------------ -------------
------------------------
|......................+## --------------
|......................| # |............| -------------------
|.*....................| #########+............| |.................|
---------------------+-- |...*........+###+*................|
# ------------+- -+-----------------
# # #####
# # --+---------------
#################### ## |................|
# # |................|
---+--------------------- # |................|
|.......................| # |................|
|...................*...| # |................|
-------------------+----- # ---+--------------
# # #####
# # -+--
# # |..|
############### # |..|
----+--------------- ########+..|
|..................| # # |.*|
|..................+################## ######### |..|
-------------------- ######## ----
--------- ---------
|.....*.| |.......|
#+.......| |.......|
#####|.......+########################+.......|
--+------ ----+----
# #
# ########
######## ######### ------+--
# # # |.......|
######### ----------+-------- |.......|
## |.................| |.......|
#################+.................| |......*|
# ---------+--------- -------+-
# # #
------+---------- ##### #
|...............| # ##############
|...............| --------------+---------- ------+---
|...............| |.......................| |.......*|
|...............| |....*..................| |........|
|...............| |.......................| |........|
----------------- ------------------------- ----------
There are only at most nine rooms, though some can be skipped. Dead-end passages are possible. Stairs (%), monsters (A-Z), items (various grawlix), and the player (@, of course) are added by other code, often to different curses windows. The minimal room and passages code also puts down the gold (*).
The code is a bit complicated, something that probably makes sense to folks in an EE department in the late 1970s.
void
do_passages(void)
{
struct rdes *r1, *r2 = NULL;
int i, j;
int roomcount;
static struct rdes {
bool conn[MAXROOMS]; /* possible to connect to room i? */
bool isconn[MAXROOMS]; /* connection been made to room i? */
bool ingraph; /* this room in graph already? */
} rdes[MAXROOMS] = {
{{0, 1, 0, 1, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0}, 0},
{{1, 0, 1, 0, 1, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0}, 0},
{{0, 1, 0, 0, 0, 1, 0, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0}, 0},
{{1, 0, 0, 0, 1, 0, 1, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0}, 0},
{{0, 1, 0, 1, 0, 1, 0, 1, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0}, 0},
{{0, 0, 1, 0, 1, 0, 0, 0, 1}, {0, 0, 0, 0, 0, 0, 0, 0, 0}, 0},
{{0, 0, 0, 1, 0, 0, 0, 1, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0}, 0},
{{0, 0, 0, 0, 1, 0, 1, 0, 1}, {0, 0, 0, 0, 0, 0, 0, 0, 0}, 0},
{{0, 0, 0, 0, 0, 1, 0, 1, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0}, 0},
};
...
Another question is whether this an the subsequent code actually produces a fully connected graph. That is, for any seed, is a map generated where the player could be dropped in to room X that is unconnected from the rest of the game, or in other words here the stairs down to the next level.
There are more efficient ways to answer this question, but I went with a simple brute force, which, assuming no bugs on my part, does not find any unconnected levels. Basically you draw the level map for each possible seed (which is not many, given the bad 16-bit random number generator), find a point, flood-fill walkable cells from that point, then look for any point that is walkable but has not been clobbered by the flood-fill. rogue's code is not very modular, so this means pulling together a bunch of object files and globals, and then bootstrapping hopefully enough of the dungeon so that level maps can be drawn.
Given that the audit failed to turn up an unconnected graph, an obvious test is to break the map generation and then see if the audit catches that. One way to do that is to comment out the "do_passages()" call, which does break the map.
------------- --------------
|xxxxxxxxxxx| --------------------- |............|
|xxxxxxxxxxx| |...................| |............|
|xxxxxxxxxxx| |...................| |............|
|xxxxxxxxxxx| |...................| --------------
------------- ---------------------
------------ ------- ------------------------
|..........| |.....| |......................|
|..........| |.....| |......................|
|..........| |.....| |......................|
|...*......| |*....| |......................|
------------ ------- ------------------------
-------------
----------------- |.........*.| ----------
|...............| |...........| |........|
|...............| |...........| |........|
|...............| |...........| |........|
|..............*| |...........| |........|
----------------- ------------- ----------
https://thrig.me/src/rogue36.git
tags #rogue
P.S. knowing what all the maps look like may allow one to guess the seed (possibly as assisted with a scroll of magic mapping) and therefore better predict what the random number generator will do, as complicated by random monster spawns and other bits of code that hit the random number generator.