Part V
User Programs
Mazemaster: Maze Making and Running
Fred Brunyate
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.
Table of Contents
Previous Section: Using Disks With Atari Basic
Next Section: Monster Combat
