Copyright 1984 by ABComputing May 15, 1984 ÉÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍ» º Simpmaze Documentation º º º º by º º º º Bill Salkin º ÈÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍÍͼ ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿ ³ Introduction ³ ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ Simpmaze is a maze-generation program created by Dan Rollins. This article presents an overview of the source code. For a full description, see the article "PolyMaze! Solver" in the December 1983 issue of Creative Computing. ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿ ³ Sample Run ³ ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ A sample run of Simpmaze looks like this. ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿ ³ SIMPMAZE ... Generic Maze Generation ³ ³ Public domain program written by Dan Rollins 04/05/83 ³ ³ ³ ³ horizontal size (26 fits on screen)? 4 ³ ³ vertical size (11 fits on screen)? 3 ³ ³ calculating maze... please be patient ³ ³ ³ ³ + +--+--+--+ ³ ³ I I I ³ ³ + +--+--+ + ³ ³ I I I I ³ ³ + + + + + ³ ³ I I I ³ ³ +--+--+--+ + ³ ³ ³ ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿ ³ Coordinate System Used ³ ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ The following coordinate system is used in Simpmaze: X (0,0) .ÄÄÄÄÄÄÄÄÄÄÄ> ³ ³ ³ Y ³ v The origin of the coordinate system is in the upper left-hand corner; X increases as we move eastward, and Y increases as we move southward. ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿ ³ An AMazing Floorplan ³ ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ Think of a maze as a floorplan for a building where each room has precisely two openings (an entrance and an exit). While constructing the maze, though, Simpaze assumes that a room has four doors, and determines which door can act as an exit and which door can act as an entrance. ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿ ³ The Array MZ ³ ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ A convenient method is needed to determine which doors, if any, are open in a room. If the upper left-hand coordinate of the room is (X,Y), then the value of MZ(X,Y) provides this information in a numeric manner that is easy to manipulate. For each room in a maze, an open east door is associated with the number 2; an open west door with 8; an open south door with 4; an open north door with 1. (The value of zero is associated with a closed door.) This is shown below. 1 ÚÄÄÄÄ/ÄÄÄÄ¿ 8 / / 2 MZ(X,Y) = 1 + 2 + 4 + 8 = 15 ÀÄÄÄÄ/ÄÄÄÄÙ 4 Simpmaze initially sets MZ = 0 for each room in the maze, and for any open door adds the corresponding numerical value to the current value of MZ(X,Y). If only the north door of a room is open, then MZ(X,Y) is set equal to 1. If only the east and west doors are open, MZ(X,Y) = 2 + 8 = 10. In the above illustration, all doors are open so MZ(X,Y) is the sum of 1,2,4, and 8 as shown. ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿ ³ The Program Simpmaze ³ ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ The values entered above (in the sample run) for the horizontal and vertical size are called H and V, respectively, in Simpmaze. A random starting point is determined using these values as seeds. Simpmaze closes all doors on all the rooms in the maze with the statement: 1000 FOR J=0 TO H :FOR K=0 TO V :MZ(J,K)=0 :NEXT :NEXT '** "close" all doors The idea behind Simpmaze is: proceed to a room and check if it has any open doors. If an open door is found, do not enter this room. In this manner, we never enter a room that has been previously visited, and when the number of rooms entered equals the total number of rooms, the maze has been solved. (If we are trapped, that is, if all adjacent rooms have been visited, the program scans the maze for an unvisited room, and, if found, we proceed to that room.) Assume that the upper left-hand corner of a room has coordinates (X,Y) and we are positioned near this corner. To test whether the room to the north has a closed door use: 1030 IF Y>0 THEN IF MZ(X,Y-1)=0 THEN Q=Q+1 :T(Q)=0 '** North (Think of the vector from (X,Y) to (X,Y-1) with the tip at the latter point. This vector points to the north as Y decreases in the northward direction.) If the north door is closed, then we can move to the north and this is indicated by setting the value T(1) to 0. Next, the other possible directions of movement are checked: 1040 IF X0 THEN IF MZ(X-1,Y)=0 THEN Q=Q+1 :T(Q)=3 '** West When all possible directions have been tested, a particular direction is selected by: 1100 D=INT(RND*Q)+1 :DIR=T(D) '** choose randomly from list To exit this room in the direction given by DIR, we open the door in the current room using: 1110 MZ(X,Y)=MZ(X,Y) + PWR2(DIR) '** add door in current room Notice from line 1030-1060 that T(Q) if T(Q) = 0, then 2 = 1 = an open north door T(Q) if T(Q) = 1, then 2 = 2 = an open east door T(Q) if T(Q) = 2, then 2 = 4 = an open south door T(Q) if T(Q) = 3, then 2 = 8 = an open west door The association between the values of T, the mysterious PWR2 (power of 2) function, and the potential open doors has been clarified. The values of X and Y are updated to reflect our move to the new room by: 1120 Y=Y+YD(DIR) :X=X+XD(DIR) '** move to new room where XD, YD values are essentially 0, 1, or -1. When we open, say, the north door in the current room for an exit, to complete the passage we must open the south door in the new room as an entrance. To amplify this last statement, notice in the diagram below that exiting the bottom room through the north door requires entering the adjacent room through the south door. ÚÄÄÄÄÄÄÄÄÄ¿ ³ ³ ÀÄÄÄÄ/ÄÄÄÄÙ S ÚÄÄÄÄ/ÄÄÄÄ¿ N ³ ³ ÀÄÄÄÄÄÄÄÄÄÙ This complementary direction is given by the statement: 1130 ND=DIR-2 :IF ND<0 THEN ND=4+ND '** opposite DIR for New Dir The door in the new room is opened by: 1140 MZ(X,Y)=MZ(X,Y) + PWR2(ND) '** add door in new room The room count is updated to reflect that we have entered a new room by: 1150 RC=RC+1 '** update Room Count Finally, when the room count equals the total number of available rooms, the calculations have been completed and the maze is drawn. ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿ ³ Drawing the Maze ³ ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ To draw the maze, we need only draw the north and west doors for, as mentioned above, the south door of one room is essentially the north door of the room beneath it. Two simple facts about MZ are used to draw the maze. 1. If MZ(X,Y) is odd, then the room must have an open north door. (The only way MZ can be odd is if the number 1 has been added to it; that is, a north door was opened.) 2. If MZ(X,Y) > 7 then a west door must be open. For the sum of the values associated with the other three doors is 7 (1 + 2 + 4), and the only way to exceed this value is by having a west door open. The code that draws the maze is: 2010 FOR Y=0 TO V 2020 FOR X=0 TO H 2030 IF INT(MZ(X,Y)/2)=MZ(X,Y)/2 THEN PRINT "+--"; :GOTO 2050 2040 PRINT "+ "; '** must have a North door 2050 NEXT X :PRINT "+" 2060 FOR X=0 TO H 2070 IF MZ(X,Y) > 7 THEN PRINT" "; :GOTO 2090 '** must be a West door 2080 PRINT"I "; 2090 NEXT X :PRINT "I" 2100 NEXT Y To complete the drawing, the door in the southeastern corner of the maze is opened as an exit and the program is complete. ÚÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄ¿ ³ File Name: ÛÛ basic1.txt ÛÛ ³ ÀÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÄÙ