(42) Maze generator algorithm
06-29-2021, 12:18 AM (This post was last modified: 06-29-2021 12:24 AM by arhtur.)
Post: #1
 arhtur Junior Member Posts: 25 Joined: Jun 2021
(42) Maze generator algorithm
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

Attached File(s)
MZ1.raw.zip (Size: 353 bytes / Downloads: 6)
 « Next Oldest | Next Newest »

User(s) browsing this thread: