ZX Review #11-12 26 ноября 1997

professional approach - Algorithms for the construction and transmission of labyrinths.

   PROFESSIONAL APPROACH



Music by ZET

(C) Lykhin D., Kemerovo


           Labyrinths


   "Labyrinths - architectural
structures with complex passages, which were constructed in 
order to lead in awe the uninitiated ... "


                 Martin Gardner.


   The word "labyrinth" of Greek
origin, and translates as
underground tunnels or underground. In
nature, there are many underground caves with lots of turns, 
intersections, and puffins. There are examples and other 
natural labyrinths, here say, Skerries - many small islands 
that make up a single group. In the archipelago tens of 
fairways, straits, bays, coves, in

which is easy to get lost.

   But there are mazes and artificial, man-made voluntarily or 
involuntarily. An example of unwitting creation of labyrinths 
are the different mines, quarries, called the common word 
"Catacombs." Most often, the word "Labyrinth", we mean 
artificial, specially designed, highly complex structures. The 
origin of such "Labyrinths" is pretty old.

For example, Herodotus describes the Egyptian Labyrinth, which 
had 5,000 rooms. First, Labyrinths were a religious-mystical 
character, but in more recent times have been the subject 
entertainment by going to the gardens and parks as a hedge

complex configuration. In our
time, according to Martin
Gardner, "there are two areas of science, in which interest
Maze remains consistently
High: psychology and design of computers. "

   However, there is one
area of ​​human activity in which the maze is a necessary 
attribute - it is computer games. Indeed, almost all game 
genres, Adventure, Arcade and Arcade / Adventure Labyrinths are 
used. They occur in other genres: Puzzle, Action, occasionally 
in Simulations. In this connection, a computer user there are 
two problem: the passage of labyrinths

game programs and the creation of
Labyrinths for "their" programs.

   Problem for the passage of the Labyrinth "splits for a 
couple of others: the technical and logical. The technical part 
is to cope with the management of his "puppets" to avoid

collisions with byaka-sprites "
and do not fall into the trap. The logical part - finding the 
right path. 

   As soon as a logical problem,
then obviously there must be an algorithm for solving it. C
mathematical point of view, the path from
entrance to the target is a topological invariant. Simply put, 
it means: a plan of the Labyrinth, drawn on a piece of rubber 
can be stretched so that entrance and joined by one goal

direct corridor.

   Having a straight line along this corridor, we find the 
shortest path to goal. Almost However, if we have a plan of the 
Labyrinth, it should hatch (fill up) all the puffins. The 
remaining part - the way (or multiple paths) to the target. In 
some games You can see the entire maze as a whole (sometimes 
his plan). But usually in these games aim games are not passage 
of the Labyrinth, a collection of objects (Miss Pocman, Fast 
Food, CHUCKE, etc.). Or maze is equipped with "switches" in the 
form of close-opening doors, falling lattices drawbridges, 
etc., that can change the configuration of the Labyrinth. The 
task - to choose time to pass, when

"Switches" in the right position (or toggle them myself)
to achieve the goal.

   So, if the screen the entire maze, then finding the right 
way is not difficult. Another thing, if the maze is divided 
into many screens. Then, to find a way

path will have to make a plan
Maze. But without a plan?

   Here we come to
on configurations and types
Labyrinths. First of all, note that there are two mazes
types: two-or three-dimensional,
ie single or multi-storey. When
This two-dimensional game graphics are not
necessarily mean the two-dimensional maze, and, conversely, 
often three-dimensional graphics combined with

two-dimensional maze. When two-dimensional graphics image of 
the Labyrinth can be horizontal (Look above) or vertical 
(looking from the side). With three-dimensional graphics, too, 
there two methods of image (usually

only part of the labyrinth): isometry and front projection.

   Now the configuration of the Labyrinth. Specialists are three
configuration: simply connected mazes, labyrinths multiply
without the "loop" around the target and Mazes multiply with a 
closed "Noose" around the goal. Simply-called Labyrinth, not

containing closed routes and
no free-standing walls. Mazes with free-standing walls and a 
closed- routes are said to multiply. In this case, if the closed

route does not pass around the target
Labyrinth is the second configuration;
if the goal can be circumvented by
closed route, then Maze third configuration.

   In the labyrinths of the first and second
configuration is always possible to achieve the goal, if we 
move all while touching the hand of the wall.

However, this path will not be the shortest. In Tangle third 
configuration in such a way never reach the goal. You

simply bypass it by the largest closed route. Often we
do not know, with a labyrinth
what configuration are dealing with.
Is there a universal algorithm for passage of any maze?

   Exists.


   Algorithm Luc-three:

1. At the exit of the tunnel to perekres
   weaving at the entrance to the intersection

   the tunnel always do from
   label with the same hand
   Ny (eg right) during

   movement.
2. From the first intersection go

   on any desired path, while

   will not achieve or a new ne
   rekrestka, or do not let us enter the

   deadlock. Then:
3. If we are at an impasse, then

   should go back and

   distance traveled dropped

   (Paragraph 1), noting its twice continuously
   dy (input-output). From perekres
   tis to go in another direction
   Research Institute.
4. If we arrive at a new

   intersection, then move in

   any direction, noting

   the way in which they came, and

   the way in which we depart.
5. If we come to know
   Therefore, we are not crossing those ny
   those who left, it is not
   slowly turning back

   (Not forgetting to point 1).
6. Never walk on the path

   marked twice.
7. If there are no paths from without
   Tag, you must choose a path

   marked by a label.


   I think that this algorithm
will help you in passing Labyrinths, although "put" tag on
screen is very problematic.


   We now turn to the question of
creation of labyrinths. Will not
address problems associated with
Hand development and storage
Labyrinths in the computer memory.
This is a very time-consuming work. You can see this on the 
example program "MUTANT" from the book INFORKOMa "Games in 
BASIC with their own hands." Eight simple Labyrinths are 
written in a "very plump" lines 2000 ... 2700. To recruit them 
rather "a chore" even if you use ready-made

Thongs and their sections. Much better to have the procedure
creating mazes in the course of the program as they need. This 
idea is not new. Such a program can be found, For example, in 
"Interactive Graphics". The program was not written for 
"SPECTRUM", but it is easy adapted.


   Let's try to simulate the process of the Labyrinth.
Where does the Maze in the wild? Under the influence
water, wind, temperature conditions, soil erosion, collapses
in the weakest places, forming passages, dead ends, corners. C
Geographically, the direction of tunnels created by accident. 
Denote the direction of "the erosion of soil" numbers 1-4 and 
take his chance, using the RND. 


            LISTING 1 REM

10 BORDER 0: PAPER 0: INK 7: CLS "Source Ground"
20 LET Y = INT (RND * 22): Coordinates "sample

                                         source "

   LET X = INT (RND * 32)
30 FOR N = 0 TO 350 Processing Time

                                        "Blurring"
40 LET B = INT (RND * 4) + 1 Direction "blur"
50 IF B = 1 AND Y <> 0 THEN

   LET Y = Y - 1: GO TO 100 Calculation of coordinates

                                       "New Tunnel"
60 IF B = 2 AND X <> 31 THEN

   LET X = X + 1: GO TO 100
70 IF B = 3 AND X <> 21 THEN

   LET Y = Y + 1: GO TO 100
80 IF B = 4 AND X <> 0 THEN

   LET X = X - 1: GO TO 100
90 GO TO 40
100 PRINT AT Y, X; CHR $ 143 "smears"
110 NEXT N


   What happened on the screen,
little like a maze. As
says: "The process did not go."

   "Primer" was sufficiently
'Uniform', and tunnels have arisen. Violate the "uniformity
soil, replacing the program
Line 50 ... 80, 100 for the following:

50 IF B = 1 AND Y> 1 THEN LET Y1 = Y - 1: LET Y = Y - 2:

   LET X1 = X: GO TO 100
60 IF B = 2 AND X <30 THEN LET X1 = X + 1: LET X = X + 2:

   LET Y1 = Y: GO TO 100
70 IF B = 3 AND Y <20 THEN LET Y1 = Y + 1: LET Y = Y + 2:

   LET X1 = X: GO TO 100
80 IF B = 4 AND X> 1 THEN LET X1 = X - 1: LET X = X - 2:

   LET Y1 = Y: GO TO 100
90 .......
100 PRINT AT Y1, X1; CHR $ 143; AT Y, X; CHR $ 143


   Now the result is satisfactory. If
You satisfied with the speed of the procedure, you can use
her say, in the same program
"MUTANT". The complexity of the Labyrinth
can be changed by changing the loop variable "N" and the length 
traveled by the "drift" in one step. The resulting algorithm I 
call the "algorithm of penetration," which he really looks 
like. Overlooking the Labyrinth - multiply. Can I use this 
algorithm to obtain a simply-connected? Obviously, yes. Should 
impose restrictions (for example, by function ATTR), in which 
connection is impossible "drifts" between them. But this may be 
the case "converging spiral (Fig. 1),




   Fig. 1

which further "sinking"
impossible. Then we must go back to the moment
when will it happen though
least in one direction. Therefore,
have to memorize the coordinates
previous positions of the press. If
want, then do it themselves, and we consider another algorithm 
for generating mazes. This algorithm is used in

program from the already mentioned book "Interactive Graphics". 
Let's call it algorithm "removal partitions. "How it works

clear from the title. First "build" a number of isolated from 
each other "rooms" and then remove the partition between them 
in an arbitrary manner, but adhering to certain restrictions. 
(See Listing 2). 


             Code Listing 2 REM


  5 BORDER 0: PAPER 0: CLS
 10 FOR N = 1 TO 29 STEP 2 "Building a House"
 20 FOR M = 1 TO 19 STEP 2
 30 PRINT PAPER 7: AT M, N; ""
 40 NEXT M: NEXT N

                                    Index the vertical and
 50 DIM A (10,14): DIM B (9,15) horizontal "partitioning"
 60 FOR N = 1 TO 105 Number of "deleted" vertices
                                    tical "partitions"
 70 LET I = INT (RND * 10) + 1 define the index is removed
                                    emoy "partitioning
 80 LET J = INT (RND * 14) + 1

                                    We check not to delete
 90 IF A (I, J) = 1 THEN GO TO 70 "wall" before, and if

                                    "Delete", then assign

                                    other indexes.
100 LET A (I, J) = a mark on the removal of "transition
                                    towns "
110 PRINT PAPER 7; AT I * 2 - 1, "Removal of partition"

    J * 2;
120 NEXT N Go to the next "re
                                    town "
130 FOR N = 1 TO 100 Similarly, it deletes the negotiations
                                    Rodkey, facing horizontal
                                    but
140 LET I = INT (RND * 9) + 1 define the index is removed
                                    emoy "partitioning
150 LET J = INT (RND * 15) + 1
160 IF B (I, J) = 1 THEN GO TO 140
170 LET B (I, J) = 1
180 PRINT PAPER 7; AT I * 2,

    J * 2 - 1; "
110 NEXT N


   Restrictions that we imposed in this program, it
number of remote vertical and horizontal "partition". At the 
same time we also watched that no "wall" is not

removed more than once.
Can impose other restrictions. For example, restrict the number 
of inputs / outputs in each room. 


             Listing 3 REM

 10 BORDER 7: PAPER 7: INK 0: CLS
 20 FOR N = 0 TO 30 "Building a House"
 30 FOR M = 0 TO 20 STEP 2
 40 PRINT AT M, N; CHR $ 143
 50 NEXT M: NEXT N
 60 FOR N = 0 TO 30 STEP 2
 70 FOR M = 0 TO 20
 80 PRINT AT M, N; CHR $ 143
 90 NEXT M: NEXT N

                                    Indexing "partitions"
100 DIM A (10,15): DIM G (10,14): and "rooms"

     DIM V (9,15)
110 FOR N = 1 TO 205 Number of "deleted"

                                              "Partitions"
120 LET B = INT (RND * 2) What is the "partition" to remove,

                                    vertical or gorizon130 GO 
TO 205 * (B = 1) + 140 * tal 

    (B = 0)
140 LET I = INT (RND * 10) + 1 Determine the partition for

                                    removal.
150 LET J = INT (RND * 14) + 1

                                    If it was deleted, it will
160 IF G (I, J) = 1 THEN GO TO 120 look for another.

170 IF A (I, J)> = 3 OR A (I, J +1)> = 3 If the mating room

    THEN GO TO 120 each have three inputs, we seek

                                    another partition.
180 PRINT AT I * 2 - 1, J * 2; "deleted partition"

    ""
190 LET G (I, J) = 1: LET A (I, J) = Note the remote "bargaining
    A (I, J) + 1: LET A (I, (J +1)) = Rodkey and connected "Room
    A (I, (J +1)) you "
200 GO TO 260 Go to the next succeeded
                                    leniyu.
205 LET I = INT (RND * 9) + 1 a similar act in the

                                    removing horizontal "pe210 
LET J = INT (RND * 15) + 1 regorodok" 

                                    If it was deleted, it will
220 IF V (I, J) = 1 THEN GO TO 120 look for another.
230 IF A (I, J)> = 3 OR A (I +1, J)> = 3 If the mating room

    THEN GO TO 120 each have three inputs, we seek

                                    another partition.
240 PRINT AT I * 2, J * 2 - 1; "deleted partition"

    ""

250 LET V (I, J) = 1: LET A (I, J) =

    A (I, J) + 1: LET A (I +1, J) =

    A (I + 1, J) + 1
260 NEXT N


   Labyrinth received this
program, the more "elegant" than
in the previous case, but the program works a little slower. 
And generally, the more restrictions imposed, the slower the 
program. The resulting algorithm - multiply, but the author of 
"Interactive Graphics" builds with this algorithm is simply 
connected maze. May try to repeat his experience. To me 
According to the construction of simply connected Labyrinths 
more suitable algorithm partitions mounted. " It is much easier

and most importantly, much faster. The essence of the algorithm 
is as follows: first "build" a few isolated from each other 
"corridors", and then put them in the septum, while connecting 
corridors between themselves (Listing 4).



             Listing 4 REM

 10 BORDER 7: PAPER 7: INK 1: CLS
 20 FOR N = 1 TO 21 STEP 2 "Building corridors"
 30 FOR M = 1 TO 30
 40 PRINT AT N, M; CHR $ 143
 50 NEXT M: NEXT N
 60 FOR N = 1 TO 21
 70 PRINT AT N, 0; CHR $ 143;

           AT N, 31; CHR 143
 80 NEXT N
 90 FOR N = 1 TO 9 Number of "partitions"

                                     between the "corridors"
100 LET K = INT (RND * 4) + 1, define the number of mouths
                                     establishes "partition" in
                                     A "corridor"
110 LET L = INT ((30 - K) / K) The length of the interval 
between these 

                                     "Partitions".
120 FOR M = 1 TO K Install "partition" and

                                     connection "corridors"
130 LET B = (L + 1) * (M - 1) + INT (RND among themselves.

        * (L - 3)) + 1
140 IF B> 28 THEN GO TO 130
150 PRINT AT N * 2 + 1, B; (2 spaces)

    ""
160 PRINT AT N + 2, B + 2; CHR $

    143; AT N * 2 - 1, B +2; CHR 143
170 IF M = K THEN PRINT AT N * 2 +

    1, B + 3 "(2 spaces)
180 NEXT M: NEXT N
190 LET Y = INT (RND * 10) + 1
200 PRINT AT Y * 2, 0, "", makes entry
210 LET Y = INT (RND * 10) + 1
220 PRINT AT Y * 2, 31 Making out


   Program (Listing 4) may
be used in games
BASIC type "Racing through the labyrinth." Can I use the 
algorithm "imposed barriers to" get multiply "Labyrinth"? 

   It is easy to see that if
slightly increase the number of installed barriers and make
a few "extra" connections
between the corridors, we get
the desired result. Leave it
You.

   But instead offers a program with the same algorithm for
Maze of the multiply, but for vector graphics
(Listing 5).


          Listing 5

 10 BORDER 7: PAPER 7: INK 2: CLS
 20 LET M = 1
 30 FOR R = 16 TO 80 STEP 16
 40 FOR N = 0 TO 19
 50 LET B = INT (RND * 4)
 60 LET X1 = R * COS (PI/10 * N): LET Y1 = R * SIN (PI/10 * N)
 70 IF B = 0 AND M = 0 THEN GO TO 90
 80 IF B = 0 THEN GO TO 120
 82 IF B = 1 AND (M = 1 OR M = 0) THEN GO TO 90
 85 IF B = 1 AND R <> 16 AND R <> 80 THEN GO TO 150
 90 LET X2 = R * COS (PI/10 * (N + 1)): LET Y2 = R * SIN (PI/10 
* 

    (N +1))
100 PLOT 128 + X1, 88 + Y1: DRAW X2 - X1, Y2 - Y1, PI/10
110 GO TO 150
120 LET X3 = (R +16) * COS (PI/10 * N): LET Y3 = (R +16) * SIN 
(PI/10 * 

    N)
130 IF R = 80 THEN GO TO 150
140 PLOT 128 + X1, 88 + Y1: DRAW X3 - X1, Y3 - Y1
150 LET M = B
160 NEXT N: NEXT R


   I cite this listing without
comments. It should, perhaps,
just to clarify that the variable
"M" was introduced for remembering previous result variable
on "B", to avoid posing the two partitions in a row and
double connection "corridors"
without partitioning. The purpose of the Labyrinth - its 
center. Labyrinth multiply, can get a second or third 
configuration. Unfortunately, the trigonometric functions and 
operators for creating arcs - DRAW - very slow

program. To speed up the advice to write it in BETA BASIC,
function using fast and COSE
SINE. And if you do not do not want to
away from the "SPECTRUM BASIC", then
can replace the listing on the
following (Listing 6). In principle, it generates the same type 
maze, replacing the circle by rectangles. Despite its

length, it works with the same
rate as shown in Listing 4.


          Listing 6


  5 BORDER 0: PAPER 0: INK 6: CLS
 10 FOR N = 1 TO 6
 20 LET X = 112 - 16 * N: LET Y = 78 + 16 * N
 30 LET A = 63 + 32 * (N - 1): LET B = 14 + 32 * (N - 1)
 40 PLOT X, Y: DRAW A, 0: DRAW 0,-B: DRAW-A, 0: DRAW 0, B
 50 IF N = G THEN GO TO 200
 60 LET C = INT (RND * 5)
 70 GO TO 200 - 20 * C
120 LET D = INT (RND * (A - 10))
130 PLOT X + D, Y: DRAW 0,15: PLOT X + D, Y: DRAW OVER 1; 10.0
140 LET D = INT (RND * (A - 10))
150 PLOT X + D, Y: DRAW 0,15: PLOT X + D, Y: DRAW OVER 1; 10.0
160 LET D = INT (RND * (A - 10))
170 PLOT X + D, Y: DRAW 0,15: PLOT X + D, Y: DRAW OVER 1; 10.0
180 LET D = INT (RND * (A - 10))
190 PLOT X + D, Y: DRAW 0,15: PLOT X + D, Y: DRAW OVER 1; 10.0
200 PLOT X + INT (RND * (A - 10)), Y: DRAW OVER 1; 10.0
205 IF N = G THEN GO TO 400
210 LET C = INT (RND * 5)
220 GO TO 400 - 20 * C
320 LET D = INT (RND * (A - 10))
330 PLOT X + D, YB: DRAW 0, -15: PLOT X + D, Y - B: DRAW OVER 1;

    10,0
340 LET D = INT (RND * (A - 10))
350 PLOT X + D, YB: DRAW 0, -15: PLOT X + D, Y - B: DRAW OVER 1;

    10,0
360 LET D = INT (RND * (A - 10))
370 PLOT X + D, YB: DRAW 0, -15: PLOT X + D, Y - B: DRAW OVER 1;

    10,0
380 LET D = INT (RND * (A - 10))
390 PLOT X + D, YB: DRAW 0, -15: PLOT X + D, Y - B: DRAW OVER 1;

    10,0
400 IF N = 6 OR N = 1 THEN GO TO 500
410 LET C = INT (RND * 4)
420 GO TO 500 - 20 * C
440 LET D = INT (RND * (B - 10))
450 PLOT X, YD: DRAW -15,0: PLOT X, Y - D: DRAW OVER 1, 0, -10
460 LET D = INT (RND * (B - 10))
470 PLOT X, YD: DRAW -15,0: PLOT X, Y - D: DRAW OVER 1, 0, -10
480 LET D = INT (RND * (B - 10))
490 PLOT X, YD: DRAW -15,0: PLOT X, Y - D: DRAW OVER 1, 0, -10
500 PLOT X, Y - INT (RND * (B - 10)): DRAW OVER 1, 0, -10
505 IF N = 6 OR N = 1 THEN GO TO 600
510 LET C = INT (RND * 4)
520 GO TO 600 - 20 * C
540 LET D = INT (RND * (B - 10))
550 PLOT X + A, YD: DRAW 15,0: PLOT X + A, Y - D: DRAW OVER 1, 
0, 

    -10
560 LET D = INT (RND * (B - 10))
570 PLOT X + A, YD: DRAW 15,0: PLOT X + A, Y - D: DRAW OVER 1, 
0, 

    -10
580 LET D = INT (RND * (B - 10))
590 PLOT X + A, YD: DRAW 15,0: PLOT X + A, Y - D: DRAW OVER 1, 
0, 

    -10
600 NEXT N


   Of course, the length of the listing can be somewhat reduced 
by applying the inner loop, but I wanted to demonstrate the 
method of "stepwise transition. In addition, cycles slow down 
the program. As in the previous maze, the goal - the center, 
built Labyrinth of the second or third configuration. But the 
consequences of applying the operator OVER 1 is the possibility 
of such a case, when the target is cut off.


   Now you know the basic algorithms for generating mazes and, 
of course, understood that Here the main problem - the speed of 
the programs. Exiting of the traditional - the use of machine 
code. To cite an example of a program generator Labyrinths of 
the first configuration, made on the basis of Beysikprogrammy 
Listing 4. Program relotsiruema not due to use of routines 
(though All sub relotsiruemy)

its total length - 412 bytes, address
Start 50210. In its composition
it contains four routines, and combines "core"
block.

   Sub-print the original screen (Listing 7) "RES", address 
start with the beginning of the procedure - 5000, length 99 
bytes. 

   Subprogramme "RND" (listing
8) serves to obtain a battery of random numbers. Written with 
the address 5100, length 12 bytes.


   Sub-program "PRINT" (Listing 9) print "Partition" and
connects the "corridors". Start address 50175, the length of
62 bytes.

   Procedures provided "ERASE" (listing 10)
makes the missing link
"Corridors". Start address 50175,
length 35 bytes.

   Unit, combining procedures
"PROG" (listing 11), written with
Address 50210, 202 bytes in length.

   Comments do not cite, they
is in Listing 4.


     Listing 7 RES


                      10 ORG (50,000) C350
C350 3E07 1920 LD A, 07
C352 CD9722 1930 CALL 2297
C355 FD02 40 LD (IY +83), 39
C359 3E02 1950 LD A, 02
C35B CD0116 1960 CALL 1601
C35E CD6B0D 70 CALL 0D68
C361 0E14 1980 LD C, 14
C363 0619 1990 NEXT 2 LD B, 19
C365 C5 100 1 NEXT PUSH B, C
C366 3E02 110 LD A, 02
C368 CD0116 CALL 120 1601
C36B 3E16 130 LD A, 16
C36D D7 RST 140 1910
C36E C1 150 POP BC
C36F 79160 LD A, C
C370 D7 RST 170 1910
C371 78180 LD A, B
C372 D7 RST 190 1910
C373 3E8F 200 LD A, 8F
C375 D7 RST 210 1910
C376 10ED 220 DJNZ NEXT 1
C378 0D DEC C 230
C379 0D DEC C 240
C37A 20E7 250 JR NZ, NEXT 2
C37C 061A 260 LD B, 1A
C37E C5 270 NEXT 3 PUSH BC
C37F 3E02 280 LD A, 02
C381 CD0116 CALL 290 1601
C384 3E16 300 LD A, 16
C386 D7 RST 310 1910
C387 3E00 320 LD A, 0
C389 D7 RST 330 1910
C38A C1 340 POP BC
C38B 78350 LD B, A
C38C D7 RST 360 1910
C38D 3E8F 370 LD A, 8F
C38F D7 RST 380 1910
C390 10EC 390 DJNZ NEXT 3
C392 0614 400 LD B, 14
C394 C5 410 4 NEXT PUSH BC
C395 3E02 420 LD A, 02
C397 CD0116 CALL 430 1601
C39A 3E16 440 LD A, 16
C39C D7 RST 450 1910
C39D C1 460 POP BC
C39E 78470 LD A, B
C39F D7 RST 480 1910
C3A0 3E01 490 LD A, 01
C3A2 D7 RST 500 1910
C3A3 3E8F 510 LD A, 8F
C3A5 D7 RST 520 1910
C3A6 3E16 530 LD A, 16
C3A8 D7 RST 540 1910
C3A9 78550 LD A, AB
C3AA D7 RST 560 1910
C3AB 3E1A 570 LD A, 1A
C3AD D7 RST 580 1910
C3AE 3EF8 590 LD A, 8F
C3B0 D7 RST 600 1910
C3B1 10E1 610 DJNZ NEXT 4
C3B3 C9 620 RET

                      630 END



     Listing 8 RND



                      10 ORG C3B4
C3B4 2A765C 20 LD HL, (5C76)
C3B7 ED5B785C 30 LD DE, (5C78)
C3BB 19 40 ADD HL, DE), 39
C3BC 22765C 50 LD (5C76), HL
C3BF 7D 60 LD FL
C3C0 C9 1970 RET

                      80 END



     Listing 9 PRINT



                      10 ORG C3C1
C3C1 3E02 1920 LD A, 02
C3C3 CD0116 1930 CALL 1601
C3C3 3E16 1940 LD A, 16
C3C8 D7 50 RST 1910
C3C9 E1 1960 POP HL
C3CA D1 1970 POP DE
C3CB C1 1980 POP BC
C3CC F1 1990 POP AF
C3CD F5 PUSH AF 100
110 C3CE C5 PUSH BC
120 C3CF D5 PUSH DE
C3D0 E5 PUSH HL 130
C3D1 87 140 ADD A, A
150 C3D2 F5 PUSH AF
C3D3 3C 160 INC A
C3D4 47 170 LD B, A
C3D5 D7 RST 180 1910
C3D6 7A 190 LD D, A
C3D7 D7 RST 200 1910
C3D8 3E8F 210 LD A, 8F
C3DA D7 RST 220 1910
C3DB 3E16 230 LD A, 16
C3DD D7 RST 240 1910
C3DE 78250 LD A, B
C3DF 3C 260 INC A
C3E0 D7 RST 270 1910
280 C3E1 7A LD A, D
C3E2 D7 RST 290 1910
C3E3 3E8F 300 LD A, 8F
C3E5 D7 RST 310 1910
C3E6 3E16 320 LD A, 16
C3E8 D7 RST 330 1910
C3E9 F1 POP AF 340
C3EA 47350 LD B, A
C3EB D7 RST 360 1910
C3EC 7A 370 LD A, D
C3ED 3C 380 INC A
C3EE 57390 LD D, A
C3EF D7 RST 400 1910
C3F0 3E20 410 LD A, 20
C3F2 D7 RST 420 1910
C3F3 3E16 430 LD A, 16
C3F5 D7 RST 440 1910
C3F6 78450 LD A, B
C3F7 D7 RST 460 1910
C3F8 7A 470 LD A, D
C3FA D7 RST 490 1910
C3FB 3E20 500 LD A, 20
C3FD D7 RST 510 1910
C3FE C9 520 RET

                      530 END



     Listing 10 ERASE



                      10 ORG C3FF
C3FF 3E02 1920 LD A, 02
C401 CD0116 1930 CALL 1601
C404 3E16 1940 LD A, 16
C406 D7 50 RST 1910
C407 E1 1960 POP HL
C408 D1 1970 POP DE
C409 F1 1980 POP AF
C40A F5 1990 PUSH AF
C40B E5 PUSH HL 100
C40C 87 110 ADD A, A
C40D F5 PUSH AF 120
C40E D7 RST 130 1910
C40F 7A 140 LD A, D
C410 3D 150 DEC A
C411 57160 LD D, A
C412 D7 RST 170 1910
C413 3E20 180 LD A, 20
C415 D7 RST 190 1910
C416 3E16 200 LD A, 16
C418 D7 RST 210 1910
C419 F1 POP AF 220
C41A D7 RST 230 1910
C41B 7A 240 LD A, D
C41C 3D 250 DEC A
C41D D7 RST 260 1910
C41E 3E20 270 LD A, 20
C420 D7 RST 280 1910
C421 C9 290 RET

                      300 END



     Listing 11 PROG



                      10 ORG C422
C422 CD50C3 20 CALL C350 (RES)
C425 0609 1930 LD B, 09
C427 C5 40 NEXT PUSH BC
C428 CDB4C3 50 CALL C3B4 (RND)
C42B E603 1960 AND 2003
C42D FE03 1970 CP 03
C42F 301C 1980 JR NC, FOUR
C431 FE02 1990 CP 02
C433 3035 100 JR NC, THREE
C435 FE01 2001 CP 110
C437 304E 120 JR NC, TWO
C428 CDB4C3 130 CALL C3B4 (RND)
C43C E60F 140 AND 0F
C43E C606 150 ADD A, 06
160 C440 C5 PUSH BC
C441 F5 PUSH AF 170
C442 CDC1C3 180 CALL C3C1 (PRINT)
C445 F1 POP AF 190
C446 C1 200 POP BC
C447 F5 PUSH AF 210
C448 CDFFC3 220 CALL C3FF (ERASE)
C44B 1855 230 JR FIN
C44D 0E1C 240 FOUR LD C, 1C
C44F 0604 250 LD B, 04
C451 79 260 ST 4 LD A, C
C452 D606 270 SUB 06
C454 4F 280 LD C, A
C455 CDB4C3 290 CALL C3B4 (RND)
C458 E601 300 AND 01
C45A 81 310 ADD A, C
320 C45B C5 PUSH BC
C45C F5 PUSH AF 330
C45D CDC1C3 340 CALL C3C1 (PRINT)
C460 F1 POP AF 350
C461 C1 360 POP BC
C462 10ED 370 DJNZ ST4
C464 F5 PUSH AF 380
C465 CDFFC3 390 CALL C3FF (ERASE)
C468 1838 400 JR FIN
C46A 0E1C 410 THREE LD C, 1C
C46C 0603 420 LD B, 03
C46E 79430 ST 3 LD A, C
C46F D608 440 SUB 08
C471 4F 450 LD C, A
C472 CDB4C3 460 CALL C3B4 (RND)
C475 E603 470 AND 03
C477 81 480 ADD A, C
490 C478 C5 PUSH BC
C479 F5 PUSH AF 500
C47A CDC1C3 510 CALL C3C1 (PRINT)
C47D F1 POP AF 520
C47E C1 530 POP BC
C47F 10ED 540 DJNZ ST3
C481 F5 PUSH AF 550
C482 CDFFC3 560 CALL C3FF (ERASE)
C485 181B 570 JR FIN
C487 0E1C 580 TWO LD C, 1C
C489 0602 590 LD B, 02
C48B 79 600 ST 2 LD A, C
C48C D60C 610 SUB 0C
620 C48E 4F LD C, A
C48F CDB4C3 630 CALL C3B4 (RND)
C492 E607 640 AND 07
C494 81 650 ADD A, C

660 C495 C5 PUSH BC
C496 F5 PUSH AF 670
C497 CDC1C3 680 CALL C3C1 (PRINT)
C49A F1 POP AF 690
C49B C1 700 POP BC
C49C 10ED 710 DJNZ ST2
C49E F5 PUSH AF 720
C49F CDFFC3 730 CALL C3FF (ERASE)
C4A2 C1 740 FIN POP BC
C4A3 1082 750 DJNZ NEXT
C4A5 CDB4C3 760 REP1 CALL C3B4 (RND)
C4A8 E607 770 AND 07
C4AA 47780 LD B, A
C4AB CDB4C3 790 CALL C3B4 (RND)
C4AE E603 800 AND 03
C4B0 80 810 ADD A, B
C4B1 FE01 820 CP 01
C4B3 38F0 830 JR C, REP1
C4B5 F5 PUSH AF 840
C4B6 3E02 850 LD A, 02
C4B8 CD0116 CALL 860 1601
C4BB 3E16 870 LD A, 16
C4BD D7 RST 880 1910
C4BE F1 POP AF 890
C4BF 87 900 ADD A, A
C4C0 3D 910 DEC A
C4C1 D7 RST 920 1910
C4C2 3E01 930 LD A, 01
C4C4 D7 RST 940 1910
C4C5 3E20 950 LD A, 20
C4C7 D7 RST 960 1910
C4C8 CDB4C3 970 REP2 CALL C3B4 (RND)
C4CB E607 980 AND 07
C4CD 47990 LD B, A
C4CE CDB4C3 1000 CALL C3B4 (RND)
C4D1 E603 1010 AND 2003
C4D3 1980 1020 ADD A, B
C4D4 FE01 1030 CP 01
C4D6 38F0 1040 JR C, REP2
C4D8 F5 1050 PUSH AF
C4D9 3E02 1060 LD A, 02
C4DB CD0116 1070 CALL 1601
C4DE 3E16 1080 LD A, 16
C4E0 D7 1090 RST 1910
C4E1 F1 1100 POP AF
C4E2 87 1110 ADD A, A
C4E3 3D 1120 DEC A
C4E4 D7 1130 RST 1910
C4E5 3E1A 1140 LD A, 1A
C4E7 D7 1150 RST 1910
C4E8 3E20 1160 LD A, 20
C4EA D7 1170 RST 1910
C4EB C9 1180 RET

                      1190 END


   And now once again turn to
INFORKOMA book "The Games in BASIC with their own hands." Open
Page 55. Here is
description and a program of classical computer game "SNAKMAN".
I must say that for the last 6
years, she met me three times in different ways. Two of
They were called "PITON", and one -
"KOBRA". "SNAKMAN" also uses the Labyrinth, though one that
unimportant (they can be
how much you like). So, Mazes for "SNAKMAN" and not suitable
any, and only possess the necessary properties: they are either
do not have to be blind alleys,
or dead ends should be wide enough to maneuver. Otherwise, you
never collect all the "fruit"
(Frogs, mice, etc.). As for the "wide" dead ends, such a maze 
to build a fairly easily, making all the corridors and

Rooms double or triple the width. And build a maze without any 
dead ends? I am sure that now you started to think,

what system of restrictions should be imposed on the algorithm 
and the algorithm is more appropriate. Go tell - the way "bad 
job". None of the above algorithms are not suitable due to the 
complexity imposed restrictions.


   Need a new algorithm.

   As soon as deadlocks should not
be at all, let us build
a maze of closed corridors
where there are no dead ends (they are electrically connected). 
Then in the Labyrinth can not appear deadlocks. 


  So, "An algorithm for the closed corridors: Listing 12.


          Listing 12

10 BORDER 0: PAPER 0: CLS
15 FOR M = 1 TO 30
20 LET A = INT (RND * 8) + 3
30 LET X = INT (RND * (32 - A))
40 LET Y = INT (RND * (22 - A))
50 FOR N = 0 TO A
60 PRINT PAPER 5; AT Y + N, X; ""; AT Y + N, X + A; "";

   AT Y + A, X + N; ""; AT Y, X + N; ""
70 NEXT N: NEXT M


   We used as
the original shape of a closed corridor square, choosing its 
size and location coordinates to plane in an arbitrary manner.

Labyrinth has a free "oral" and some passages of increased 
width. This gives the possibility of free maneuver. The 
likelihood that any square will be "cut off"

depends on the loop variable "M".
For a sufficiently large value of its "cut" squares are not
be. Of course, the original figure for the corridors may not be
only the square. Fit any
closed figure: a rectangle,
triangle, any polygon, circle, etc. Perhaps
that in their program you use more than one closed figure, and 
a combination thereof. 

   And now, it is impossible
around the question of "degree of freedom" Labyrinth. Until 
now, we generated a maze with four degrees of freedom, ie the 
possibility of motion in four areas (excluding Listing

5, as for the curved shapes of degrees of freedom is not 
defined (= infinity)). If the latter algorithm, the original 
figure of the corridor is a triangle, then the degrees

Freedom is not 4, and 6 (see
Fig. 2)

                           <



         > <>
<>

             Fig. 2

For the hexagon they too will be 6. Increasing the degree of 
freedom inevitably leads to the Maze complicate the control 
system "Puppet" and therefore unlikely

advisable to have them anymore
than 8. The question of the degree of freedom
Maze directly related to the task "of parquet", that is, 
filling the plane (for us the screen) polygonal plates. 

   If all the tiles from the same
regular polygons, then
perhaps all three options
"Parquet": triangles, squares, rectangles. Deforming them, you 
can get a few different form, such as rectangles (Fig. 3). If as

original image



            Fig. 3

take a "parquet" is not of the quadrangles, then using the 
algorithm "Remove partition" obtain a maze with six (6)

degrees of freedom. All this applies to two-dimensional 
Labyrinth. It is clear that in three-dimensional maze of 
freedom will always be on 2 more (up-down). 

   I quote "program from" filling the screen plane hexagons 
(Listing 13) 


          Listing 13

10 FOR N = 65368 TO 65399
20 READ A: POKE N, A
30 NEXT N
1940 DATA 1,2,4,8,16,32,64,128,

           255,0,0,0,0,0,0,0,

           128,64,32,16,8,4,2,1,

           0,0,0,0,0,0,0,255
50 FOR N = 0 TO 31 STEP 4
60 FOR M = 0 TO 21 STEP 2
70 PRINT AT M, N; "ABCD"; AT M + 1, N; "CA"; REM (dec. G)
80 NEXT M: NEXT N


   Never mind that the hexagons
slightly deformed. On the other hand, each partition is on a 
separate familiarity and can be removed without damage to 
others. 

  Besides the three listed homogeneous "parquet" there is
11 homogeneous, combining different shapes. Perhaps they, too,
suitable for our purposes. Those
who are interested in this matter, I refer to the book by 
Steinhaus, "Mathematical Kaleidoscope (Library "Kvant", 1981)


   Perhaps this is complete. I think you understand - Labyrinth 
"this thing", which opens a vast field of activity for computer 
users of all skill levels, and for research and for 
programming. There still remains a lot of unaffected subjects 
(eg, the use of ROM as a table of random numbers, combined 
scrolling and the generation of the Maze, the generation of 
three-dimensional mazes and so on) 

   The "dessert" will bring another
algorithm for generating mazes, striking in its simplicity
and the complexity of the output of the multiply, with the 
degree of freedom 8, Maze. In the environment, "Sinklermanov, 
it is known as a strange called "Fodder" (Listing

14).


           Listing 14

 10 FOR N = 65368 TO 65423
 20 READ A: POKE N, A
 30 NEXT N
 1940 DATA 128,128,128,128,128,128,128,128,

            255, 0, 0, 0, 0, 0, 0, 0,

             1, 1, 1, 1, 1, 1, 1, 1,

             0, 0, 0, 0, 0, 0, 0, 255,

            128, 64, 32, 16, 8, 4, 2, 1,

             1, 2, 4, 8, 16, 32, 64, 128,

             0, 0, 0, 0, 0, 0, 0, 0
 50 FOR N = 1 TO 32
 60 LET B = INT (RND * 7) + 144
 70 PRINT CHR $ B; "";: REM (;)!
 80 NEXT N
 90 FOR N = 1 TO 512
100 LET B = INT (RND * 7) + 144
110 PRINT CHR $ B;: REM (;)!
120 NEXT N
130 FOR N = 1 TO 32
140 LET B = INT (RND * 7) + 144
150 PRINT CHR $ B; "";: REM (;)!
160 NEXT N
170 PLOT 8,175: DRAW 247,0: PLOT 255,167: DRAW 0, -152:

    DRAW -247,0: PLOT 0,15: DRAW 0,160


   Of course, in practice the scale
Image too small, but typing
pair stringovyh arrays dimension (7,2), you can easily imitate 
print a double-width and height. And a native generally can 
print characters of any size (see the book Inforkoma Applied 
Graphics). 


     EVERYTHING. I wish you success.