Remarks: Maze Walker
From Maze
The abstract visual pattern produced by 10 PRINT can be appreciated purely for its formal, compositional qualities, like an abstract painting or a fabric pattern. [reference other sections of the book that discuss 10 PRINT as a formal pattern]. However, as has been discussed in [reference to section/chapter on cultural history of mazes and 10 PRINT's location and context within this history], the 10 PRINT pattern can also be interpreted as a maze. In this chapter, we investigate how it is that 10 PRINT, as an abstract machine, succeeds in representing a maze or labyrinth. More specifically, we employ our software studies methodology of writing programs to interpret programs, writing a series of hermeneutic probes in Commodore BASIC that employ representational machinery of increasing complexity to ever more elaborately cash out the interpretation of the 10 PRINT pattern as a maze.
Stabilizing the Maze
The first step in this process is to stabilize the pattern so that it can be contemplated as a fixed maze. Throughout this book we have shown figures of static rectangular patterns produced by 10 PRINT [reference to a figure depicting such a pattern]. But this is not what someone running 10 PRINT on a Commodore 64 experiences; rather than a fixed maze, 10 PRINT produces an endlessly scrolling sequence of symbols. Figure [fig] shows a sequence of screen shots as 10 PRINT executes. As the program starts executing, a growing line of symbols starts printing out below the typed command RUN 10, continuing in the first column of the next line as each line becomes full. When the line at the bottom of the screen fills with symbols, the screen begins scrolling, moving all lines up by one on the screen, pushing the line at the top off the screen. The bottom line of the screen is blank after this scroll operation, and the bottom line again refills with symbols. Eventually, any text that was on the screen above the RUN 10 command has been pushed off the screen. At this point, when the bottom line fills with symbols, the screen scrolls upwards by two lines instead of one, pushing the top two lines of the pattern off the top of the screen, and creating two blank lines at the bottom of the screen (this apparently anomalous scrolling behavior is explained below). From this point on, the two blank lines are continuously filled with randomly selected symbols, scrolling by two when the bottom line fills. Only for the fraction of a second when a line has filled, and before the first symbol of the next line is drawn, is there ever a rectangular maze pattern present on the screen. And not even for that fraction of second is there ever a maze pattern filling the whole screen, as the pattern immediately scrolls up by two lines when the symbol in the last row and column is drawn.
To draw a fixed rectangular maze pattern, 10 PRINT must be modified to draw a finite number of symbols, rather than an infinite sequence. Instead of repeating the PRINT statement forever (which the GOTO statement does), we should repeat the PRINT statement a fixed number of times. How many symbols should be drawn? To avoid the extra complexity of having to format maze rows that are narrower than the width of the screen (by either centering the maze pattern by padding each line with blank spaces on each side of the maze pattern, or by having to explicitly terminate each maze line if not centering), consider only rectangular mazes that are as wide as the entire screen. Forty text symbols (characters or graphic symbols) can fit on one line of the C64 screen. Therefore, any rectangular pattern will consist of a multiple of 40 symbols. To make this concrete, consider a modified version of 10 PRINT that will create a rectangular pattern 10 lines high; it will consist of 10 x 40 = 400 maze symbols.
Now 10 PRINT must be modified to execute the PRINT statement 400 times. One way would be to write the following 400 line program:
1 PRINT CHR$(205.5 + RND(1)); 2 PRINT CHR$(205.5 + RND(1)); … 400 PRINT CHR$(205.5 + RND(1));
There are, however, significant problems with writing the program this way. For one thing, the program is long; the programmer must engage in the repetitive task of writing the same line over and over again (changing the line numbers). Computers are good at repetition; whenever a program involves tedious and repetitive steps, programmers look for ways to make the computer do the repetitive work. More significantly, this version of the program is very hard to change. To create a longer sequence of 600 symbols, 200 more lines must be added to the program. To create a shorter sequence of 100 symbols, 300 lines must be deleted from the program. To create a pattern of two different symbols, or to change the relative frequency with which the two symbols appear, the number 205.5 must be changed in every line. Clearly the best way to write this program is to write the PRINT line once and have the computer execute the line 400 times. The program must somehow count to 400, so that it can keep track of how many times it has executed the PRINT line and stop after 400 times. The following program does this, introducing the FOR NEXT construct in BASIC.
5 FOR X = 1 to 400 10 PRINT CHR$(205.5 + RND(1)); 15 NEXT X
The purpose of the FOR NEXT construct is to repeatedly execute lines (to loop over them) a fixed number of times. The lines to loop over are placed between the line with the FOR statement and the line with NEXT statement. In this case there is only one line between FOR and NEXT - the PRINT line that randomly prints one of two symbols to the screen. The FOR statement specifies a starting and ending number to count between, as well as a variable to hold the count. In this case, the count starts at 1 and ends at 400 (thus looping 400 times), and specifies a variable named X to store the count. [Not sure if we'll need to go into the concept of a variable in more detail - hopefully the concept of a variable has been introduced elsewhere]. The NEXT statement increments the counting variable, in this case, X. If the value of the count variable (X) is less than or equal to the maximum count specified in the FOR statement, control returns to the line after the FOR (in this case line 10 with the PRINT statement) and execution continues, looping one more time over the lines between FOR and NEXT. Otherwise, if the value of the count variable (X) is greater than the maximum count, execution continues on the line after the NEXT statement - the loop is done. In this case, since there is no program line after the NEXT statement, the program terminates. By utilizing the FOR NEXT looping construct, this very short program produces the desired rectangular pattern of 400 symbols, producing the first screen pattern that can be stably contemplated as a maze. [Reference screen image showing 10 line maze pattern followed by READY. and blinking cursor.]
It is interesting to note that in this program no use is made in the PRINT statement of the counting variable X. This counting variable is employed only by the FOR and NEXT statements to keep track of how many iterations have occurred. This involves repeatedly testing the current value of X against the maximum value to decide whether to increment the count and loop one more time or to leave the loop. This increment and test logic is performed by the BASIC interpreter, in its implementation of the semantics of FOR and NEXT. A BASIC program can also reference the count value in the lines appearing between the FOR and NEXT statements, though the maze program does not do this.
The increment and test logic, which is implemented within the interpreter, can also be implemented directly in BASIC. This makes fully explicit the work that the counting variable X is performing in our program.
This program loops from 1 to 10, doing nothing but maintaining the count through each iteration:
10 FOR X = 1 TO 10 20 NEXT X
This is the equivalent BASIC program where the initialization, incrementing and testing of the count variable is made explicit, without using the FOR and NEXT statements:
10 LET X = 1 20 IF X > 10 THEN GOTO 50 30 LET X = X + 1 40 GOTO 20 50 END
The rectangular maze, though now a stabilized pattern, still does not appear on the screen by itself. The space above the maze contains whatever characters were already on the screen above the prompt where the RUN command was typed, while the space below the maze contains the READY prompt [reference figure above showing the 10 line rectangular maze]. Clearing the screen and moving the active print location to the top of the screen before printing the maze would eliminate stray characters appearing above the maze. The C64 keyboard has a special key, named CLR, which clears the screen. By printing this special CLR character within our program, we can clear the screen before printing the maze characters. [If the chapter on the C64 and BASIC don't talk about control characters, say more about control characters here]. There are two ways to refer to any keyboard character within a program: either by pushing the appropriate keyboard key within quotes, or using the character code with the CHR$ function. The control characters all have a visual counterpart for use within quoted strings. The CLR key can thus be referred to within a program by either "[CLR symbol]" or by CHR$(147). Printing this character clears the screen.
The program:
1 PRINT CHR$(147); 5 FOR X = 1 TO 400 10 PRINT CHR$(205.5 + RND(1)); 15 NEXT X
now generates a rectangular maze, 10 lines high, with the READY prompt appearing below the maze. The semicolon on the first line tells the PRINT statement not to start a new line after printing the CLR character. Without the semicolon, there would be one blank line above the maze, resulting from the PRINT on line 1 starting a new line. The READY prompt is generated by BASIC when a program terminates. In our case, after the FOR and NEXT statements increment X to 401, program execution continues past line 15, terminating the program and returning control of the C64 to the BASIC operating environment. In order to prevent the READY prompt from being printed, control must not return to BASIC; the maze program must execute forever. The original 10 PRINT program already demonstrated how to use a GOTO statement to make a program loop forever. Now, however, we don't want the maze program to keep on printing forever, but rather to do nothing forever, so as not to return control to the BASIC operating environment and the resulting printing of the READY prompt. This is accomplished by including a line at the end of the program with a GOTO statement that loops to itself.
1 PRINT CHR$(147); 5 FOR X = 1 TO 400 10 PRINT CHR$(205.5 + RND(1)); 15 NEXT X 20 GOTO 20
This finally results in the generation of a pristine rectangular maze sitting on a screen by itself [reference figure depicting clean maze]. The next step is to fill the entire screen with a stabilized maze pattern.
Before moving onto this step, however, let us reflect on the additional complexity that has been introduced in our efforts to stabilize the maze. Our original one line program has grown to five lines, though the original kernel of the program, which randomly prints a forward or backward slanting character, still appears on line 10. The additional complexity comes from the need to produce a finite number of forward and back slashes, and from the formatting requirements of placing the maze on a blank screen. To produce a finite number of symbols, the FOR and NEXT statements, with their corresponding count variable X, are introduced. To place the maze on a clear screen, the CLR control character is printed and an infinite loop that prevents the return to the BASIC prompt is introduced. This is a common experience in programming, that the input and output behavior of the program, the formatting and interface, the "surface" of the program, requires more programming complexity than the simulation or calculation that defines the kernel or "depth" of the program.
To fill the whole screen with a stable maze, the program should loop for 1000 characters instead of 400. However, instead of filling the whole screen, the screen scrolls up by two lines when the last character is printed. This is verified by printing 999 characters, which almost perfectly fills the screen, leaving one blank space in the lower right-hand corner [image?]. This is the same ragged scrolling behavior observed at the bottom of the screen in the original, infinitely scrolling version of 10 PRINT. The seemingly innocent PRINT command, which promises to simply place text on the screen, is doing something more. As discussed in [C64 chapter], PRINT is actually enforcing the concept of 80 character logical lines, on top of the C64's 40 character wide screen. So, starting with a blank screen, when the 1000th character is printed, this happens to be the 80th character of the last logical line on the display, causing the screen to scroll by two physical (40 character) lines to make room for the next 80 character logical line. Two layers of code underwrite the operation of PRINTing to the screen: code in the BASIC interpreter, which handles the various language-specific features associated with PRINT, such as formatting operations like the semi-colon, and code specific to the C64 hardware platform, invoked by the BASIC interpreter, providing facilities such as the ability to output a character to the screen. So to generate our screen full of stable maze, a mechanism other than the virtual teletype enforced by PRINT and its two layers of language platform and hardware platform code, must be used.
Fortunately, BASIC provides the commands POKE and PEEK to directly write and read physical memory addresses. These commands provide a mechanism for subverting the language abstractions of BASIC, giving the BASIC programmer access to the arbitrary memory manipulation available via assembly language opcodes. If computer memory truly consisted only of data and code, as described by the von Neumann architecture, then POKE and PEEK would have limited utility to the BASIC programmer, merely providing a less convenient mechanism than variables for storing data, as well as the somewhat esoteric ability for a program to modify its own code during execution. But the C64 employs a common computer architecture approach of memory-mapped hardware registers. With memory mapping, in addition to the standard memory space that stores code and data, there are memory addresses for hardware registers that directly control the execution of the machine. These special memory addresses include control for input and output devices, such as screens, keyboards, and printers. On the C64, the BASIC interpreter and operating system code that create abstractions such as PRINT's virtual teletype, perform their lowest level operations by writing and reading these special memory addresses. By providing POKE and PEEK, which were not available in the original Dartmouth BASIC [I don't think memory-mapping was common in 1964, so POKE and PEEK would have had limited utility - further BASIC was operating in a time-sharing environment, so you wouldn't have wanted to provide individual programs access to hardware registers anyway - if we want to go into this, it would be wherever we want to introduce POKE and PEEK], Commodore BASIC provides a backdoor by which BASIC programmers can directly manipulate hardware registers that would typically only be accessible to assembly language programmers.
The characters displayed on the C64 screen are stored in one of these special regions of memory, called video memory. Display hardware continuously scans video memory, reading character codes, looking up the bitmap describing each character, and drawing each character pixel-by-pixel onto the screen. Thus, even when no user code is executing, and the C64 is just sitting with text visible on the screen, the illusion of stable text is underwritten by frenetic activity, as character codes are accessed, bitmaps looked up, and characters painstakingly drawn, pixel by pixel, over and over again. So even in a one-line program like 10 PRINT, layers of process complexity underwrite the abstractions which provide the visual experience of an endlessly scrolling maze-like pattern.
To create a stable screen-sized maze, we will use POKE to bypass PRINT's virtual teletype and directly place PETSCII codes in video memory. Rather than iterating from 1 to 1000, the FOR loop must iterate over the 1000 character locations in video memory, which begins at memory location 1024.
1 PRINT CHR$(147) 10 FOR X = 1024 TO 2023 20 POKE X,205.5+RND(1) 30 NEXT X 40 GOTO 40
Here we meet our last surprise in stabilizing the maze. This program does finally produce a stable screen-full of maze, but the foreground and background color is inverted [figure]. Replacing the PETSCII code 205 with 109 (employed in one of the variations of 10 PRINT) produces something even further from the maze, two different graphic characters entirely. It turns out there are two different layers of character encodings used in the C64, the PETSCII codes, and screen codes. As discussed in [chapter], PETSCII codes extend ASCII to include C64 specific graphics characters. Screen codes, on the other hand, are used to directly index character memory to look up the 8 by 8 grid pixel pattern for an individual character. That is screen code 0 refers to the first 8 by 8 character in character memory, screen code 1 to the next character in character memory and so forth. Since PETSCII, like ASCII, includes codes for non-printing control characters (characters with no visual representation), it would be more awkward to use the PETSCII codes as character memory indices, since the first visible character appears at PETSCII 32. By PRINTing PETSCII 109 and using PEEK to look in video memory, one finds that the resulting screen code is 77; this makes sense, as 109 - 32 (subtracting the first 32 non-printing PETSCII characters) is 77. The PETSCII code 205 also works to produce the forward and backward slanting maze characters because the PETSCII characters in the range 192 to 223 mirror the characters in the range 96 to 127; so PETSCII codes 205 and 206 represent the same characters as 109 and 110. But this means that PRINT, and the kernal routine called by PRINT, have to perform a somewhat complex mapping between PETSCII and the screen codes employed by the display system. In bypassing PRINT by POKEing directly to video memory, awareness of the double layer of character encodings was forced upon us. Somewhat amusingly, the use of the BASIC command POKE is forcing closer attention to C64 hardware concerns than lower level assembly language program described in Remark: Thread. This is because thread makes use of a kernal character output routine, which is performing the PETSCII to screen code mapping, while POKE bypasses the kernal; the assembly language equivalent would be to use the sta opcode to directly store a screen code in video memory.
The following BASIC program finally produces a stable screen full of maze pattern.
1 PRINT CHR$(147) 10 FOR X = 1024 TO 2023 20 POKE X,77.5+RND(1) 30 NEXT X 40 GOTO 40
Walking the Maze
Given a screen full of maze pattern, it is time to finally cash out the interpretation of the pattern as a maze by writing a program that can walk it. The first step is to interpret a location within the maze. As viewers, we can interpret the light slanting characters as thin walls and the dark blue background as floor, or the light blue characters as a thin corridor or tunnel and the dark blue background as thick walls or material being burrowed through. The former interpretation (dark blue as floor) is probably dominant with most viewers, so the maze walker discussed here will use that interpretation.
The first step in operationalizing this interpretation (that is, in creating a computational system that behaves in a way consistent with this interpretation) is defining what it means to occupy a location within the maze. The challenge is that the visual distinction between walls and floor is not represented in the program. [Figure] shows a closeup of the maze pattern, uses black squares to distinguish individual characters. The dark blue is the background of characters, but positions within the dark blue "corridor" are not themselves identified by unique character locations. Dark blue and light blue areas of the screen are distinguished at the level of individual pixels, but in the graphics mode that our BASIC program is drawing in, we can only access character-level blocks (8 by 8 pixel blocks) in video memory.
MazeCharacterLocations.gif
610 × 376 pixels
Thus, a particular screen location (such as the yellow highlighted location in [figure]), identifies one of the slanting characters (a wall segment), but does not identify which side of the wall (corridor segment) is currently occupied.
The esoteric programming language Path, which uses forward and backslashes as reflectors to control the 2D program counter, provides a set of movement rules that can be used to disambiguate maze location. Given a character location (identified wall segment), we can imagine someone approaching the wall from above, below, left and right. The walker ricochets off the wall in the directions indicated in [figure]. Approaching a forward slashing character from above or from the left implicitly indicates that the walker is in the corridor segment above the wall, while approaching from below or from the right indicates the walker is in the corridor segment below the wall. These relationships are reversed for the backward slashing characters. Therefore, in addition to an x,y location, a third piece of information, movement direction, is required to uniquely identify a maze location as well as where the walker will go next.
Given an initial location and direction, the walker moves through the maze in a drunken walk, bouncing off walls in the manner depicted in [figure].
The BASIC code for the maze walker appears below.
1 REM MAKE MAZE 5 PRINT CHR$(147) 10 FOR X = 1024 TO 2023 20 POKE X,77.5+RND(1) 30 NEXT X 100 REM SET INITIAL X AND Y WALKER LOCATION AND DIRECTION 110 REM DIRECTIONS (DR): 0 LEFT, 1 RIGHT, 2 UP, 3 DOWN 120 X = INT(RND(1) * 39) : X1 = -1 130 Y = INT(RND(1) * 24) : Y1 = -1 140 DR = INT(RND(1) * 3) 150 W1 = -1 160 GOSUB 500 200 REM START WALKING MAZE USING PATH RULES FOR BOUNCING OFF WALLS 210 REM COMPUTE NEW LOCATION BASED ON INITIAL DIRECTION 220 IF DR = 0 THEN X = X - 1 : GOTO 270 230 IF DR = 1 THEN X = X + 1 : GOTO 270 240 IF DR = 2 THEN Y = Y - 1 : GOTO 270 250 IF DR = 3 THEN Y = Y + 1 260 REM DETERMINE IF WE'RE OFF THE SCREEN 270 IF X >= 0 AND X <= 39 AND Y >= 0 AND Y <= 24 THEN GOTO 300 280 GOSUB 600 : GOSUB 650 290 GOTO 5 300 REM BOUNCE OFF WALL AS FUNCTION OF DIRECTION 310 REM 77=\, 78=/ 320 W = PEEK(1024 + X + (Y * 40)) 330 IF W = 78 THEN GOTO 380 340 IF DR = 0 THEN DR = 2 : GOTO 420 350 IF DR = 1 THEN DR = 3 : GOTO 420 360 IF DR = 2 THEN DR = 0 : GOTO 420 370 IF DR = 3 THEN DR = 1 : GOTO 420 380 IF DR = 0 THEN DR = 3 : GOTO 420 390 IF DR = 1 THEN DR = 2 : GOTO 420 400 IF DR = 2 THEN DR = 1 : GOTO 420 410 IF DR = 3 THEN DR = 0 420 GOTO 160 499 REM DRAW WALKER, RESTORING PREVIOUS WALL CHARACTER 500 GOSUB 600 510 X1 = X : Y1 = Y 520 M = 1024 + X + (Y * 40) 530 W1 = PEEK(M) 535 C = 55296 + X + (Y * 40) 540 POKE C, 1 : POKE M, 87 550 GOSUB 650 560 RETURN 599 REM RESTORE WALL AT PREVIOUS WALKER LOCATION 600 IF X1 = -1 THEN GOTO 620 610 POKE 1024 + X1 + (Y1 * 40), W1 620 RETURN 649 REM BUSY WAIT 650 FOR C = 1 TO 500 : NEXT C 660 RETURN
Lines 5 through 30 draw a screen of random maze.
Line 120 initializes a random x location between 0 and 39 (each line on the screen is 40 characters wide). We count x locations from 0 to 39 instead of 1 to 40 because this x value will be used to index a location in video memory, and counting from 0 more directly corresponds to memory locations. This will be described in a bit more detail below. The variable X1 holds the previous x location of the walker. Since a new x location has just been initialized, there is no old x location, so the x location is set to a value that is not a legal x value, in this case, -1. This is a common pattern used when dealing with a variable that can take a range of values. If the variable does not have a value yet, it is assigned a value outside of the expected range, so that it can easily be tested to determine if it has a valid value yet. Line 130 initializes a random y location between 0 and 24 (there are 25 lines on the screen), and initializes the old y location, which has no legal value yet, to -1. Line 140 sets the initial direction to a number between 0 and 3; the program will interpret 0 as left, 1 as right, 2 as up and 3 as down. W1, initialized in line 150, will be used to store the value of the screen code at the given location. This will be used to redraw the wall after the walker has passed, and is described in more detail below.
Line 160 makes use of the GOSUB statement to jump to line 500. GOSUB, short for GO SUBroutine, is the statement that supports functional abstraction in BASIC. Functional abstraction is a powerful idea in computing in which a block of code can be written once and reused in multiple places. In BASIC, a line number is used to indicate the start of a reusable block of code. The end of the block is marked with a RETURN statement, which causes execution to return to the line after the most recently executed GOSUB. Subroutines are allowed to jump to other subroutines, as BASIC stores the return locations for each active GOSUB so that it can return correctly from nested GOSUBs. (If GOSUBs are nested too deeply, BASIC will report an error when it runs out of memory to store RETURN locations).
The maze walker uses three subroutines: one to draw the current location of the walker, and to change the color of walls that have been bumped into, one to redraw the wall after the walker has passed, and one to add a wait to slow down how fast the walker moves. The GOSUB at line 160 is jumping to the subroutine to draw the walker, so that it can be drawn at its initial location.
Lines 220 through 250 determine the next x, y location of the walker, based on what direction the walker is moving. Leftward movements decrease the x value, rightward movements increase it, upward movements decrease the Y value, and downward movements increase it. For the y values, this is the opposite of the standard Cartesian grid, in which the origin in the lower left-hand corner means that upward movement increases Y. However, screen coordinates commonly use an origin in the upper left-hand corner, as this allows a coordinates to be easily converted into memory locations in video memory. As discussed earlier, on the C64 (and on most contemporaneous or modern computer platforms) the screen is memory mapped, so that all drawing operations correspond to manipulating video memory.
Lines 270 through 290 describe what to do if the walker runs off the edge of the screen. Line 270 uses an IF THEN statement to test whether the walker still has a legal position on the screen; if it does, execution jumps to line 300, where a new direction for the walker is determined. An IF THEN statement consists of two parts, a test, which immediately follows the IF, and statement(s) to execute if the test is true, which follows the THEN. The combination of an IF THEN with GOTO is an extremely common pattern in BASIC. In fact, the original Dartmouth BASIC only allowed line numbers to follow the THEN (an implicit GOTO statement), while C64 BASIC supports an alternate IF GOTO statement to save memory and typing for the THEN in this common case. Unlike structured programing languages such as C or Java, there are no facilities in BASIC to hierarchically structure code into blocks, requiring frequent use of the GOTO statement, particularly in combination with IF. This leads to the "spaghetti code" complaint frequently lodged against BASIC and other languages that make heavy use of GOTO, most famously articulated in Edsger Dijkstra's article Go To Statement Considered Harmful.
