Can the Wumpus Program be Simplified?
Sunday, 13th October 2019
Hunt the Wumpus was the first example program I developed for Tiny BASIC, and is still probably the most entertaining of all the samples. It suits the language very well, and is a great example of how the computed GOTO or GOSUB can make up for a lack of array functionality. But the computed GOTO in Wumpus is the very thing I've been thinking can be replaced with something more elegant.
The caves in Wumpus are laid out in the same way as the points on a dodecahedron, the paths between them being the edges of that dodecahedron. Trying to map that 3D geometric arrangement by a set algorithm to a 1-dimensional list of caves and connections seems pretty difficult, which is why most people just number those caves arbitrarily and then construct the lists of paths by hand.
Squashing the shape flat as in the illustration reveals a pattern, and that pattern might give a clue as to how the paths can be calculated rather than worked out by hand. The outer pentagon has an obvious algorithm that determines the path around it:
Each cave p is connected to caves p-1 and p+1, substituting 5 for 0 and 1 for 6.
The inner connections from here are slightly more complicated in the image provided. If the numbers 6-15 were shifted clockwise so that 6 connects to 1, then the connections from the edge nodes to the middle could be calculated as:
Each cave p is also connected to cave 4+2p.
These algorithms would be expressed in Tiny BASIC something like:
LET E=P-1 IF E=0 THEN LET E=5 LET F=P+1 IF F=6 THEN LET F=1 LET G=4+2*P RETURN
These six lines would replace the twenty lines of code in the current Hunt the Wumpus game that deal with the five outer caves. The inner five caves would have an algorithm of equal complexity; I'd write it as:
LET E=P-1 IF E=15 THEN LET E=20 LET F=P+1 IF F=21 THEN LET F=16 LET G=2*P-25 RETURN
The middle ring of ten caves is somewhat different. Travel around the ring is still simple, but half of the caves link to an inner cave, while half of them link to an outer cave. So the algorithm would be something like:
Each cave p is connected to caves p-1 and p+1, substituting 15 for 5 and 6 for 16.
Each odd cave p is also connected to cave 13+p/2.
Each even cave p is also connected to cave p/2-2.
Note that the p/2 will be rounded down for the odd-numbered caves. In BASIC, this algorithm becomes:
LET E=P-1 IF E=5 THEN LET E=15 LET F=P+1 IF F=16 THEN LET F=6 IF P/2*2<>P THEN LET G=13+P/2 IF P/2*2=P THEN LET G=P/2-2 RETURN
These seven lines replace the forty in the current Hunt the Wumpus code that cover the same ten locations. The computed GOTO, that chooses which of the twenty routines to call, could be replaced by a slightly more complicated GOTO that reduces those twenty cave numbers to 1 for outer caves, 2 for the middle, or 3 for the outer ones, with a formula like (14+p)/10. Or if more readability is required, 3 IF/GOTO combinations would do the trick.
Using this algorithm would have a couple of advantages. First, the program would be smaller and slightly more elegant. Secondly, it would be easier to mentally picture the location of a cave from its number, since the series of numbers is less arbitrary.
The disadvantage is that it would leave the sample program collection without an illustration of the power of the computed GOTO. If I decide not to modify the Wumpus game before I release the project, then this will probably be the reason.