Remarks: Maze Walker

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.

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.

<pre>

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

</pre>

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.