Mazemaster: Maze Making and Running
Shortly after buying an Atari 800 computer, I bought Basic Computer Games by David H. Ahl (published by Creative Computing Press). After taking care of a few essentials like Life and Hammurabi, I decided to adapt the Amazin' program so that I could use the joysticks to run the maze.
My first study of the program failed to provide any clear idea of the program's logic. The listing lacks even the most rudimentary documentation. Frustrated, I entered the program line for line, changing only the graphics characters. It really did work. Even working, however, the "why" of the program's complicated tree structure and repeated code remained obscure. The project went to the back burner.
Inspiration arrived while I was trying to fall asleep one night. Start with a maze with no paths, all single cells. From the selected starting cell, perform a random walk through the cells, marking each cell you move into and removing the intervening wall. Do not move into a marked cell or off the edge. If you cannot move, select any marked cell and resume the random walk. Continue until all cells are marked. Select any cell as the finish point, and you are done.
As I began laying out my own maze building program, two features of Atari Basic helped the whole routine fall into place. First, Atari Basic arrays have a zero row and a zero column. By adding an extra row and column and setting the elements of all four non-zero, all of the explicit boundary checking disappears, without having to remember any co-ordinate modifiers. Second, Atari Basic allows variable names to be the object of GOSUB statements. The starting line numbers of the move subroutines for all legal moves can be stored in an array. Then, with N a random number, ON N GOSUB JUMP(1),JUMP(2),JUMP(3), makes a classic random walk.
The printing routine works the same as the book version. With the top and left boundaries assumed, it needs information on only two of the four sides: neither, right only, bottom only, or both sides open. These new sides then become the top or left sides of other cells.
The maze running routine used another Atari feature. Neither of the arrays is used to check for legal moves. With the LOCATE statement, the maze displayed on the screen (or, more accurately, the display list of the screen) can be examined directly to detect walls and openings.
Now for the gory details. The main program (lines 1-999) begins with all the things that need to be done only once: DIMensioning arrays, setting the boundaries non-zero, adjusting the margins, setting constants and subroutine names. Three subroutine calls do all the real work. Finally, print the results and repeat on request. Nothing fancy so far.
The MAZEPRINTER routine (lines 1000-1999) uses the SETCOLOR statement to display the maze at the same color and intensity as the background. It is all there, you just cannot see it until the second SETCOLOR statement causes the completed maze to appear suddenly. In earlier versions of this program, you could solve most of the maze before the last line was printed and the timer started. Each cell of the maze is two print positions on a side. The routine prints spaces or graphics characters according to the information stored in array V by the MAZEBUILDER routine. Refer to the program comments for a step-by-step description.
The MAZEBUILDER routine (lines 2000-2999) uses the array W to simulate the cells of the maze. It marks a cell by setting the corresponding element of W non-zero, and removes a wall by changing the corresponding element of array V. After selecting a starting cell in the first row and initializing the cell counter, it checks for a zero neighbor cell in all four directions. For each zero cell found, the appropriate subroutine line number is added to the list kept in the array JUMP. There will be a maximum of three entries; the fourth direction leads to the previous cell. A subroutine is randomly selected from the list if it contains more than one cell. That subroutine is executed to move into the new cell, mark it non-zero, and change V to remove the intervening wall. This continues until no zero neighbors are found.
When the random walk is blocked (no zero neighbors), the routine examines cells at random until a non-zero cell is found and resumes the random walk from this point. This assures us that the new path segment will be connected to the original path. Since the routine will not move into a non-zero cell, each path segment is connected at only one end, and there is exactly one path between any two cells.
The routine halts when 95 percent of the total cells have been added to the path. This leaves some cells unconnected, but saves time by not trying to find those last few cells. The maze exit is a randomly selected non-zero cell in the last row. Actually, any two non-zero cells could be selected as the start and finish.
The MAZERUNNER routine (lines 3000-3999) handles the joystick input, checks for legal moves, displays the trial, and times the run. When decoding the joystick input, I find it easier to work with the complement of the value returned, i.e. "D=15-STICK(0)". The x direction is +1 if GT 7, 0 if D LT 3, otherwise -1. The y direction is +1 if D MOD 2=0, 0 if D MOD 4=0, otherwise -1. The routine uses an inverse video asterisk as a CURSOR with the joystick, and a SPOT, a normal asterisk, is left behind.
If the character, determined by the LOCATE statement, at the new position plus the joystick input, is not a BLANK or a SPOT, the routine ignores the joystick input. You can not move through walls. Otherwise, it plots the CURSOR at the new position and a SPOT at the old position. It continues monitoring the joystick until the CURSOR co-ordinates match the finish conditions. The real-time clock is read immediately before and immediately after running the maze and the total time is computed. The three bytes are read as quickly as possible to minimize the chance of an error caused by one of the bytes rolling over to zero.
The subroutines at lines 4000-4999 do the moving from cell to cell and take out the walls during the random walk. To move right (XPLUS1) or down (YPLUS1), first change V to open the wall, then change the co-ordinates. To move up (YMINUS1) or left (XMINUS1), first change the co-ordinates, then change V.
While this program is an enjoyable game as it is, it is also a starting point for other programs. The random walk technique is easily expandable to three dimensions (or four, if you can name them). A light pen would be ideal for running the maze. The start and finish points can be moved. And a little imagination will turn the cells into rooms in a dungeon or castle.
10 REM MAZE MASTER 15 REM 20 REM FRED BRUMYATE 30 REM HASLETT, MICHIGAN 40 REM 1981 50 REM 100 REM POKE NEW MARGINS, SET SUBROUTINE LOCATIONS, TOTALS, AND CONSTANTS 105 WIDE=17 106 HIGH=10 110 DIM V(WIDE,HIGH),W(WIDE+1,HIGH+1) 120 DIM Y$(1),JUMP(3) 130 POKE 82,1 140 POKE 83,38 150 MAZEPRINTER=1000 160 MAZERUNNER=3000 170 MAZEBUILDER=2000 190 XMINUS1=4200 200 YMINUS1=4300 210 XPLUS1=4400 220 YPLUS1=4500 230 TRIES=0 240 TOTALTIME=0 250 SPOT=ASC("*") 260 CURSOR=ASC("ª"):REM THIS IS INVERSE VIDEO 270 BLANK=ASC(" ") 280 BOTTOM=2*HIGH+1 300 REM SET BOUNDARIES NON-ZERO 310 FOR I=1 TO WIDE 320 W(I,0)=-1:W(I,HIGH+1)=-1 330 NEXT I 340 FOR I=1 TO HIGH 350 W(0,I)=-1:W(WIDE+1,I)=-1 360 NEXT I 490 REM 500 REM CLEAR THE ARRAYS AND SET BOUNDARIES 505 GRAPHICS 0 510 PRINT :PRINT "I'M THINKING UP A GOOD ONE." 515 PRINT :PRINT " DON'T GO AWAY." 520 FOR I=1 TO WIDE 530 FOR J=1 TO HIGH 535 W(I,J)=0:V(I,J)=0 540 NEXT J:NEXT I 590 REM 700 REM 710 GOSUB MAZEBUILDER 720 GOSUB MAZEPRINTER 730 GOSUB MAZERUNNER 740 REM 800 REM DISPLAY RESULTS 810 TRIES=TRIES+1 820 TOTALTIME=TOTALTIME+TIME 830 AVTIME=INT(TOTALTIME/TRIES*100)/100 840 POSITION 1,BOTTOM+1 850 PRINT "TRY #";TRIES;" TIME WAS: ";TIME;" SECONDS." 860 PRINT " AVERAGE TIME: ";AVTIME 870 REM 900 REM ASK USER VITAL QUESTIONS 910 PRINT " REPEAT THIS MAZE (Y OR N)"; 920 INPUT Y$ 930 IF Y$="Y" THEN 720 940 PRINT " ANOTHER MAZE (Y OR N)"; 950 INPUT Y$ 960 IF Y$="Y" THEN GOTO 500 970 END 990 REM 1000 REM MAZEPRINTER 1010 REM 1020 REM VALUES IN 'V' DETERMINE THE 1030 REM RIGHT AND BOTTOM WALLS OF 1040 REM EACH CELL: 1050 REM V(I,J)=0; NO OPENINGS 1051 REM V(I,J)=1; BOTTOM OPEN 1053 REM V(I,J)=2; RIGHT OPEN 1054 REM V(I,J)=3; BOTH OPEN 1055 REM 1060 REM POKE TURNS OFF THE CURSOR 1061 REM SETCOLOR HIDES MAZE UNTIL 1062 REM PRINTING IS DONE. 1080 GRAPHICS 0 1090 POKE 752,1 1091 SETCOLOR 1,9,4 1095 REM PRINT THE TOP LINE 1100 FOR X=1 TO WIDE 1120 PRINT "";:REM CTRL-S,CTRL-R 1150 NEXT X 1160 PRINT "":REM CTRL-S 1165 REM PRINT THE LEFTMOST WALL, THEN 1166 REM A CELL AND WALL OR OPENING. 1170 FOR Y=1 TO HIGH 1180 PRINT "|";:REM SHIFT-= 1190 FOR X=1 TO WIDE 1200 IF V(X,Y)>1 THEN 1230 1210 PRINT " |";:REM SPACE,SHIFT-= 1220 GOTO 1240 1230 PRINT " ";:REM SPACE,SPACE 1240 NEXT X 1250 PRINT 1255 REM PRINT THE LEFTMOST INTERSECTION 1256 REM THEN A WALL OR OPENING AND ANOTHER INTERSECTION. 1257 PRINT "";:REM CTRL-S 1260 FOR X=1 TO WIDE 1270 IF V(X,Y)=0 THEN 1310 1280 IF V(X,Y)=2 THEN 1310 1290 PRINT " ";:REM SPACE, CTRL-S 1300 GOTO 1320 1310 PRINT "";:REM CTRL-R, CTRL-S 1320 NEXT X 1330 PRINT 1340 NEXT Y 1344 REM DISPLAY THE COMPLETED MAZE 1345 SETCOLOR 1,12,10 1350 RETURN 1360 REM 2000 REM SUBRT NAME: MAKEBUILDER 2010 REM 2020 REM PERFORMS A RANDOM WALK THROUGH 2030 REM UNMARKED CELLS, KNOCKING DOWN 2040 REM WALLS AS IT GOES. PRINTING 2050 REM INFORMATION IS STORED FOR LATER, 2060 REM 2070 REM PICK A STARTING POINT 2080 X=INT(RND(0)*WIDE)+1 2090 STARTX=2*X 2100 STARTY=1 2110 C=1 2120 W(X,1)=C 2130 Y=1 2140 REM LIST DIRECTIONS AVAILABLE 2150 J=0 2160 IF W(X-1,Y)<>0 THEN 2190 2170 J=J+1 2180 JUMP(J)=XMINUS1 2190 IF W(X+1,Y)<>0 THEN 2220 2200 J=J+1 2210 JUMP(J)=XPLUS1 2220 IF W(X,Y-1)<>0 THEN 2250 2230 J=J+1 2240 JUMP(J)=YMINUS1 2250 IF W(X,Y+1)<>0 THEN 2280 2260 J=J+1 2270 JUMP(J)=YPLUS1 2280 REM IF BOXED IN 2290 IF J=0 THEN 2420 2300 REM SELECT ONE DIRECTION 2310 IF J=1 THEN GOSUB JUMP(1):GOTO 2350 2330 ON INT(RND(0)*J)+1 GOSUB JUMP(1),JUMP(2),JUMP(3) 2340 REM MARK NEW CELL USED 2350 C=C+1 2360 W(X,Y)=C 2370 GOTO 2150 2380 REM IF BOXED IN, START A NEW PATH 2390 REM FROM ANY EXISTING PATH. STOP 2400 REM IF 95% COMPLETE 2420 IF C>0.95*(HIGH*WIDE+1) THEN 2540 2440 X=INT(RND(0)*WIDE)+1 2450 Y=INT(RND(0)*HIGH)+1 2460 IF W(X,Y)<>0 THEN 2150 2470 GOTO 2440 2500 REM OPEN THE BOTTOM OF A MARKED 2510 REM CELL IN THE LAST ROW. 2540 X=INT(RND(0)*WIDE)+1 2550 IF W(X,HIGH)=0 THEN 2540 2560 V(X,HIGH)=V(X,HIGH)+1 2570 RETURN 3000 REM MAZERUNNER 3005 REM 3010 REM MOVES THE CURSOR ACCORDING 3020 REM TO THE JOYSTICK, CHECKS FOR 3030 REM DONE AND TIMES THE RUN. 3040 REM 3050 REM PUT THE CURSOR AT THE START 3060 X=STARTX:Y=STARTY 3070 COLOR CURSOR:PLOT STARTX,STARTY 3075 REM READ THE CLOCK 3080 A=PEEK(18) 3090 B=PEEK(19) 3100 C=PEEK(20) 3120 FIRSTTIME=(A*256*256+B*256+C)/60 3125 REM READ THE JOYSTICK 3130 D=15-STICK(0) 3140 IF D=0 THEN 3130 3150 X1=-1 3160 IF D<3 THEN X1=0 3170 IF D>7 THEN X1=1 3180 Y1=-1 3190 IF D=INT(D/2)*2 THEN Y1=1 3200 IF D=INT(D/4)*4 THEN Y1=0 3230 REM CHECK FOR WALLS THERE 3240 REM IGNORE JOYSTICK INPUT IF SO 3250 LOCATE X+X1,Y+Y1,CHAR 3260 IF CHAR<>BLANK AND CHAR<>SPOT THEN 3130 3295 REM LEAVE A SPOT, MOVE THE CURSOR 3300 COLOR SPOT:PLOT X,Y 3305 X=X+X1:Y=Y+Y1 3310 COLOR CURSOR:PLOT X,Y 3315 REM REPEAT IF STILL INSIDE 3320 IF Y
Fred Brunyate, 6076 Marsh Rd., Apt. E-2, Haslett, MI 48840.