(42) Maze generator algorithm

[arhtur]

I'm not sure if this is a previously implemented algorithm. I have found that a maze can be generated if an array of pillars are drawn, and a wall is drawn as follows:

From top border: draw a wall from a pillar either above or to the right.
From right border: draw a wall from a pillar either to the right or below.
From the bottom border: draw a wall from a pillar either below or to the left.
From the left border: draw a wall from a pillar either to the left or above.

A pattern has to be followed, where these walls are drawn first from the outer part of the maze to the inner.

A random number Z is either 0 or 1.

Then, from the top border, the X and Y coordinate of the wall to draw are determined from the following 2 equations, where px and py are the coordinates of the pillar.

X=Z+px
Y=Z-1+py

If Z is 0, then X=px and Y=py-1 (draw a wall above the pillar)
If Z is 1, then X=px+1 and Y=py (draw a wall to the right of the pillar)

This same approach is used to draw walls from pillars from the other 3 borders.

When the algorithm reaches the middle of the screen, there is a small row remaining, so one of 3 directions to draw a wall is picked (4 directions cannot be used, because overlap of walls is possible).

When run on a 42s, it is easier to see the algorithm work to generate the maze. On Free42 and the DM42 it runs much faster and almost instantly, you see the maze.

This can run on the HP 42s, Free42 and the DM42.

Code:


00 { 437-Byte Prgm }
01▸LBL "MZ"
02 CF 34
03 SF 35
04 3
05 STO "I"
06 CLLCD
07 CLA
08 21
09 XTOA
10 0
11 XTOA
12▸LBL "MZ4"
13 3
14 RCL "I"
15 AGRAPH
16 9
17 RCL "I"
18 AGRAPH
19 2
20 STO+ "I"
21 RCL "I"
22 131
23 X>Y?
24 GTO "MZ4"
25 -1
26 ENTER
27 PIXEL
28 -15
29 -131
30 PIXEL
31 CLA
32 253
33 XTOA
34 1
35 ENTER
36 AGRAPH
37 CLA
38 191
39 XTOA
40 8
41 131
42 AGRAPH
43 0
44 STO "J"
45▸LBL "MZ1"
46 0
47 STO "I"
48▸LBL "MZ2"
49 RAN
50 0.5
51 +
52 IP
53 STO "Z"
54 XEQ "MZ5"
55 3
56 RCL "J"
57 2
58 ×
59 +
60 RCL "Z"
61 -
62 RCL "I"
63 2
64 ×
65 4
66 +
67 RCL "J"
68 2
69 ×
70 +
71 RCL "Z"
72 ABS
73 -
74 PIXEL
75 RAN
76 0.5
77 +
78 IP
79 STO "Z"
80 13
81 RCL "Z"
82 +
83 RCL "J"
84 2
85 ×
86 -
87 RCL "I"
88 2
89 ×
90 4
91 +
92 RCL "J"
93 2
94 ×
95 +
96 RCL "Z"
97 +
98 PIXEL
99 1
100 STO+ "I"
101 RCL "I"
102 62
103 RCL "J"
104 2
105 ×
106 -
107 X≥Y?
108 GTO "MZ2"
109▸LBL "ML"
110 0
111 STO "I"
112▸LBL "MZ3"
113 RAN
114 0.5
115 +
116 IP
117 STO "Z"
118 RCL "I"
119 2
120 ×
121 4
122 +
123 RCL "Z"
124 +
125 RCL "J"
126 2
127 ×
128 +
129 3
130 RCL "Z"
131 -
132 RCL "J"
133 2
134 ×
135 +
136 PIXEL
137 RCL "I"
138 2
139 ×
140 4
141 +
142 RCL "Z"
143 -
144 RCL "J"
145 2
146 ×
147 +
148 129
149 RCL "Z"
150 +
151 RCL "J"
152 2
153 ×
154 -
155 PIXEL
156 1
157 STO+ "I"
158 RCL "I"
159 5
160 RCL "J"
161 2
162 ×
163 -
164 X>Y?
165 GTO "MZ3"
166 1
167 STO+ "J"
168 RCL "J"
169 3
170 X>Y?
171 GTO "MZ1"
172 RTN
173▸LBL "MZ5"
174 RAN
175 0.5
176 +
177 IP
178 STO "Z"
179 RCL "J"
180 2
181 X>Y?
182 RTN
183 3
184 RAN
185 ×
186 IP
187 1
188 -
189 STO "Z"
190 RTN
191 END