🅲:o2:🅳🅴🆁’🆂・🅲🆄:parking:
🆁🅳 
For those who like to sit down and chat with their computers, let’s crack open the Cupboard and peek inside and see how both the original Wumpus and the bsdgames version articulate their cave layouts in their code. That way you can go and make your own maze game! Or all sorts of other things, honestly.
The Original: Hardcoded
We can do the original Wumpus first because it’s simpler—as aforementioned the cave layout is hardcoded there. Here it is, in HP BASIC:
0068 REM- SET UP CAVE (DODECAHEDRAL NODE LIST)
0070 DIM S(20,3)
0080 FOR J=1 TO 20
0090 FOR K=1 TO 3
0100 READ S(J,K)
0110 NEXT K
0120 NEXT J
0130 DATA 2,5,8,1,3,10,2,4,12,3,5,14,1,4,6
0140 DATA 5,7,15,6,8,17,1,7,9,8,10,18,2,9,11
0150 DATA 10,12,19,3,11,13,12,14,20,4,13,15,6,14,16
0160 DATA 15,17,20,7,16,18,9,17,19,11,18,20,13,16,19
I used this book to make sense of this, since naturally I don’t know HP BASIC offhand, it not being 1973. 
REM is for comments (unsurprisingly). Apparently it stands for “REMark.” Everything after the REM is ignored.
DIM creates a multidimensional array. In this case, we have essentially a 20-element list-of-lists with each sublist having 3 elements, named S. You can also think of this as a 20x3 matrix. Access is 1-indexed, as you can see. The FOR/NEXT statements are probably self-explanatory, but the READ/DATA parts are a little more subtle for a modern reader.
Basically (ha ha), any DATA statements in the program are all read and concatenated together into a single “stream” in the order they occur by the implementation before the program runs. Then during execution, every time a READ statement runs, the implementation retrieves one or more items from the “data stream” and advances an internal offset into the “stream” accordingly. So, even though the DATA statements here come after the READ, their effect—which is to put a long stream of numbers into the program’s data—is actually applied beforehand. 
_ These are the first READ and DATA statements the program contains, so the ultimate effect is that the program sets up a multidimensional array of integers like so, expressed in a more modern kind of array syntax:
S = [
[ 2, 5, 8],
[ 1, 3, 10],
[ 2, 4, 12],
[ 3, 5, 14],
[ 1, 4, 6],
[ 5, 7, 15],
[ 6, 8, 17],
[ 1, 7, 9],
[ 8, 10, 18],
[ 2, 9, 11],
[10, 12, 19],
[ 3, 11, 13],
[12, 14, 20],
[ 4, 13, 15],
[ 6, 14, 16],
[15, 17, 20],
[ 7, 16, 18],
[ 9, 17, 19],
[11, 18, 20],
[13, 16, 19],
]
You can use this diagram to help make sense of this data structure. Basically, S[1] would yield [2,5,8], meaning that room 1 has connections to rooms 2, 5, and 8. So, the index of the subarray in S is used to represent the number of the room that the subarray itself stores the connections of.
This is an adjacency list representation of an undirected graph, so named because the inner lists describe which vertices a given vertex is adjacent to. It’s a convenient and compact way to represent a graph. (You can also represent a graph as an adjacency matrix, where the node indices number both the rows and columns, and the cells of the matrix are 1-bit flags indicating whether the row vertex has an edge with the column vertex or vice-versa. This is rather space-inefficient unless the number of edges is close to the square of the number of vertices, so the adjacency list representation is more common, but the adjacency matrix can come in handy when there are tons of edges or when the performance of a given algorithm is dominated by how fast you can check if one vertex is adjacent to another.)
The advantage of just hardcoding the cave layout like this is that it can be any shape you please, without you having to go to the trouble to design an algorithm that can generate it. The coding is as easy as can be, since you’re just describing structured data. On the other hand, though, you have to figure out how to number the vertices and record all their connections yourself. This isn’t necessarily very hard—like, if you want to base your graph on a polygon, you can just look at a model of one, assign numbers to each of its corners, and figure out the connections from there—but recording all the data could be rather tedious, especially if you want a large or complex graph. If you like the by-hand approach but you’re getting sick of typing in numbers, you might consider creating some sort of level editor, or repurposing an existing program as a level editor.
bsdgames: procedural generation
The bsdgames implementation gives the player a set of parameters to describe the cave they want and then generates the cave accordingly at the outset of play. Here’s the function that generates the cave, which is written in ANSI C:
static void
cave_init(void)
{
int i, j, k, lnk;
int delta;
/*
* This does most of the interesting work in this program actually!
* In this routine we'll initialize the Wumpus cave to have all rooms
* linking to all others by stepping through our data structure once,
* recording all forward links and backwards links too. The parallel
* "linkcount" data structure ensures that no room ends up with more
* than three links, regardless of the quality of the random number
* generator that we're using.
*/
srandom((int)time((time_t *)0));
/* initialize the cave first off. */
for (i = 1; i <= room_num; ++i)
for (j = 0; j < link_num ; ++j)
cave[i].tunnel[j] = -1;
/*
* Choose a random 'hop' delta for our guaranteed link.
* To keep the cave connected, we need the greatest common divisor
* of (delta + 1) and room_num to be 1.
*/
do {
delta = (random() % (room_num - 1)) + 1;
} while (gcd(room_num, delta + 1) != 1);
for (i = 1; i <= room_num; ++i) {
lnk = ((i + delta) % room_num) + 1; /* connection */
cave[i].tunnel[0] = lnk; /* forw link */
cave[lnk].tunnel[1] = i; /* back link */
}
/* now fill in the rest of the cave with random connections */
for (i = 1; i <= room_num; i++)
for (j = 2; j < link_num ; j++) {
if (cave[i].tunnel[j] != -1)
continue;
try_again: lnk = (random() % room_num) + 1;
/* skip duplicates */
for (k = 0; k < j; k++)
if (cave[i].tunnel[k] == lnk)
goto try_again;
cave[i].tunnel[j] = lnk;
if (random() % 2 == 1)
continue;
for (k = 0; k < link_num; ++k) {
/* if duplicate, skip it */
if (cave[lnk].tunnel[k] == i)
k = link_num;
/* if open link, use it, force exit */
if (cave[lnk].tunnel[k] == -1) {
cave[lnk].tunnel[k] = i;
k = link_num;
}
}
}
/*
* now that we're done, sort the tunnels in each of the rooms to
* make it easier on the intrepid adventurer.
*/
for (i = 1; i <= room_num; ++i)
qsort(cave[i].tunnel, link_num,
sizeof(cave[i].tunnel[0]), int_compare);
#ifdef DEBUG
if (debug)
for (i = 1; i <= room_num; ++i) {
(void)printf("<room %d has tunnels to ", i);
for (j = 0; j < link_num; ++j)
(void)printf("%d ", cave[i].tunnel[j]);
(void)printf(">\n");
}
#endif
}
We can take it step-by-step. First we declare our variables at the top of the function, since this is old-school C:
int i, j, k, lnk;
int delta;
Then we seed the random number generator with the current number of seconds since the Epoch:
srandom((int)time((time_t *)0));
Then we initialize a data structure called cave. This is defined and declared globally near the top of the program:
/* simple cave data structure; +1 so we can index from '1' not '0' */
static struct room_record {
int tunnel[MAX_LINKS_IN_ROOM];
int has_a_pit, has_a_bat;
} cave[MAX_ROOMS_IN_CAVE+1];
You may note that cave is basically an adjacency-list representation of a graph like S in the original Wumpus, although it also carries some flags with each vertex indicating whether it has a pit or bat. cave[1] returns the information for room 1, and cave[1].tunnel gives room 1’s adjacency list. cave[1].tunnel[0] would be the index of the first room in room 1’s adjacency list. (They leave cave[0] empty so the rooms can be 1-indexed; I would probably take care of that using an access function so as not to waste space, but you can do what you like since the wasted space is of essentially no consequence here anyway. In a language where you can redefine the array-subscripting operator for a type, like C++ or Ruby, you can base the subscripting on 1 without the user of the type needing to employ any unusual syntax).
Anyway, here’s the initialization of cave, to return to cave_init():
/* initialize the cave first off. */
for (i = 1; i <= room_num; ++i)
for (j = 0; j < link_num ; ++j)
cave[i].tunnel[j] = -1;
This puts -1 for every entry in every room’s adjacency list. -1 is used here to represent “no connection.” (You might consider assigning a value like this -1 to a named constant like no_cnctn or something instead of just writing -1 in a place like this, both for the sake of semantic clarity and in case you later decide you want to have -1 in an adjacency list mean something else).
At this point, the cave layout looks like this:
1: -1, -1, -1
2: -1, -1, -1
3: -1, -1, -1
4: -1, -1, -1
5: -1, -1, -1
6: -1, -1, -1
7: -1, -1, -1
8: -1, -1, -1
9: -1, -1, -1
10: -1, -1, -1
11: -1, -1, -1
12: -1, -1, -1
13: -1, -1, -1
14: -1, -1, -1
15: -1, -1, -1
16: -1, -1, -1
17: -1, -1, -1
18: -1, -1, -1
19: -1, -1, -1
20: -1, -1, -1
Next we ensure that every room can be reached from every other room—this is where the big loop, i.e. the Hamiltonian cycle, comes from.
/*
* Choose a random 'hop' delta for our guaranteed link.
* To keep the cave connected, we need the greatest common divisor
* of (delta + 1) and room_num to be 1.
*/
do {
delta = (random() % (room_num - 1)) + 1;
} while (gcd(room_num, delta + 1) != 1);
for (i = 1; i <= room_num; ++i) {
lnk = ((i + delta) % room_num) + 1; /* connection */
cave[i].tunnel[0] = lnk; /* forw link */
cave[lnk].tunnel[1] = i; /* back link */
}
The way this works conceptually is that you pick a distance between vertices—what they call delta here—and then step through the vertices with two indices, one starting at 1 and one starting at 1 + (delta + 1), then move to 2 and 2 + (delta + 1), etc., looping an index back around to 1 whenever it goes past the index of the last vertex, and making connections going both ways between each pair of vertices referenced this way. As they note in the comments, (delta + 1) and room_num (the highest room number, 20 by default) must be coprime, or some of the index pairs will lead to redundant or self-referencing connections and you won’t end up with a Hamiltonian cycle. (To gain some intuition about why this is, I recommend thinking about polyrhythms, and which combinations of meters layered polyrhythmically produce overlapping beats vs. not; it’s the same principle from a different angle.)
The cave layout at this point will vary depending on the delta; here’s what it would look like with a delta of 2:
1: 4, 18, -1
2: 5, 19, -1
3: 6, 20, -1
4: 7, 1, -1
5: 8, 2, -1
6: 9, 3, -1
7: 10, 4, -1
8: 11, 5, -1
9: 12, 6, -1
10: 13, 7, -1
11: 14, 8, -1
12: 15, 9, -1
13: 16, 10, -1
14: 17, 11, -1
15: 18, 12, -1
16: 19, 13, -1
17: 20, 14, -1
18: 1, 15, -1
19: 2, 16, -1
20: 3, 17, -1
You can see for example that 1 connects to 4 (i.e. 1 + (2 + 1)) and vice-versa.
This takes care of the first two entries in every room’s adjacency list. For the third entries, or the rest of the entries if the player has set an alternate link_num value in the options, the program connects rooms at random, more or less:
/* now fill in the rest of the cave with random connections */
for (i = 1; i <= room_num; i++)
for (j = 2; j < link_num ; j++) {
if (cave[i].tunnel[j] != -1)
continue;
try_again: lnk = (random() % room_num) + 1;
/* skip duplicates */
for (k = 0; k < j; k++)
if (cave[i].tunnel[k] == lnk)
goto try_again;
cave[i].tunnel[j] = lnk;
if (random() % 2 == 1)
continue;
for (k = 0; k < link_num; ++k) {
/* if duplicate, skip it */
if (cave[lnk].tunnel[k] == i)
k = link_num;
/* if open link, use it, force exit */
if (cave[lnk].tunnel[k] == -1) {
cave[lnk].tunnel[k] = i;
k = link_num;
}
}
}
For each room, we iterate through its adjacency list from the third entry on. If the current entry is not -1, we skip to the next entry and don’t do anything, because that means it’s already a legit connection (hopefully ). Then we pick a random room. We iterate through the adjacency list entries before the current one and see if that room is already listed. If not, we add it to the adjacency list at the current location; if so, we pick another random room and try again until it works. Then we flip a coin. If heads, we go to the next adjacency list entry and repeat. Otherwise, we iterate through all the entries in the adjacency list of the destination room. If we find the number of the current source room there, we immediately stop, go to the next adjacency list entry, and start the whole loop again. Otherwise, if we find a -1 entry in the adjacency list of the destination room, we set it to the current room number, and then also go back to the top of the loop and start again.
That’s all a bit of a mouthful 
so just to summarize, the basic effect for a default cave with 3 connections-per-room is:
- For a given room, if it doesn’t already have a third connection, make the third connection to a room that the given room isn’t already connected to.
- Flip a coin. If heads, go to step 4.
- If the destination room doesn’t already have a third connection, make it link back to the given room.
- Pick a new given room and repeat, until every room has 3 unique connections.
You can see how this would tend to produce more one-way connections than two-way, because there’s always a 50% chance to force a one-way connection, but then on top of that, sometimes the destination room already has a third connection to somewhere else even if the coin flip doesn’t force a one-way path. In practice, I’ve tested and you often end up with around 75–100% one-way connections for the random ones using this algorithm with the default cave settings.
Here’s what the cave might look like at this point:
1: 4, 18, 3
2: 5, 19, 14
3: 6, 20, 1
4: 7, 1, 17
5: 8, 2, 11
6: 9, 3, 16
7: 10, 4, 3
8: 11, 5, 8
9: 12, 6, 2
10: 13, 7, 10
11: 14, 8, 2
12: 15, 9, 17
13: 16, 10, 6
14: 17, 11, 2
15: 18, 12, 9
16: 19, 13, 6
17: 20, 14, 4
18: 1, 15, 2
19: 2, 16, 13
20: 3, 17, 12
After all that complexity, the finale is simple:
/*
* now that we're done, sort the tunnels in each of the rooms to
* make it easier on the intrepid adventurer.
*/
for (i = 1; i <= room_num; ++i)
qsort(cave[i].tunnel, link_num,
sizeof(cave[i].tunnel[0]), int_compare);
This just sorts the adjacency lists in ascending order—disguising the varying origins of the connections. That’s how the game displays them to the player.
I think I can kind of guess at the thought process that led to this algorithm. If you look at this diagram of a Hamiltonian cycle through a regular dodecahedron from Wikimedia Commons…
…you can see how it’s hard to approach the non-Hamiltonian-cycle edges (the dotted-line edges here) in a systematic way algorithmically. There are other Hamiltonian cycles you can find in a dodecahedron, but you always end up with this kind of sundry collection of other edges to complete the dodecahedron with afterwards. If you want to have other numbers of vertices, which imply other shapes, you can still find ways to complete a Hamiltonian cycle with them, but you’re still left with a sundry collection of edges that doesn’t necessarily even follow whatever patterns you might have been able to find in the dodecahedron’s sundry edges. I can only imagine that the programmers threw up their hands at this and said “Who cares if it generates a regular polyhedron or not, that’s kind of boring anyway!” and decided to just pick the sundry edges at random, seeing as how they already feel sort of random. As I discussed above, I feel like that ended up producing an excellent game design, but I can imagine that the programmers weren’t necessarily seeing it from that angle—they may have just wanted to add some customization options as a way to add features onto the original Wumpus, and just did this pragmatically as a relatively easy way to support those options.
Anyway, I think this is a pretty cool algorithm! It can generate a wide variety of cave layouts, it makes for fascinating gameplay, and it’s not even very complicated as these things go. It might have looked kind of thorny depending on your level of comfort with C, but in a more expressive language it wouldn’t take much code at all to implement—and you’ve already got, like, half of a game going at the point that you have an algorithm like this. What’s more, if you want to generate a map or some other kind of graph structure for your game, you might be able to find ways to tweak or extend this algorithm and get yet new cool graphs that aren’t even possible within this version of Wumpus. One of the fun things about procedural generation, I feel like, is that once you have a small piece of code that gives varied results, another small piece of code added on can give exponentially more varied results.
Since it’s in several sections, I guess what I’ll do is make each section its own post. Hopefully that’s the right thing to do.
𝓓𝓮𝓼𝓲𝓰𝓷𝓮𝓻’𝓼 𝓓𝓲𝓽𝓬𝓱 
Isn’t it amazing that a little computer game from the early '70s—augmented a bit in the early '90s in my case—could lead to so much? I really think it’s incredible. What a game. What a Wumpus.
) Wumpus mod as a child. I feel like I read someone in a '70s computer magazine or something also making reference to not liking the “hunting” theme of the game on the same account (if I can find it I’ll share it in this thread). I felt a bit sad about it myself when I started playing—it seemed rather cruel to me to just storm into the cave and start attacking the Wumpus who was just there minding their own business and not necessarily eating anyone. It’s kind of interesting to me how much that sentiment seems to turn up among Wumpus players, considering that so many computer games are focused entirely on attacking random creatures in the game environment without prompting much hesitation from the players—although, I suppose it is commonly the conceit that you are attacked first. In Wizardry terms, it might be considered “Evil” to attack the Wumpus. 
I wouldn’t knock yourself at all for doing a straight port in that context—it’s not exactly a trivial undertaking, and I’m sure the Channel F community would have appreciated it even in the late '70s!
I’m really curious to know what other people speculate about or whatnot when they think about this game.
Those are pretty strong counter-motives.
What was your print routine like? Can I ask? 
Especially since there’s so few pixels.
