Mazes for the HP-41
Overview
-The program hereunder generates a pseudo-random rectangular maze of
dimensions n x m
-You place a random seed in register R00 , n in register Y and m in
register X and XEQ "MAZE"
-The algorithm uses backtracking ( cf reference [1] ):
Starting at register R01, the HP41 successively finds unvisited
neighbors and deletes the walls between them
When it becomes impossible, it backtracks until it finds
an unvisited cell.
When that also becomes impossible, the HP41 returns to
register R01 and we have our maze.
-Registers R01 , R02 , ............. , Rmm are the 1st raw.
-Rm+1 , Rm+2 , ...................... , R2m are the 2nd raw and
so on...
Program Listing
Data Registers: • R00 = alea ( Register R00 is to be initialized before executing "MAZE" )
R01 to Rmn = the different cells of the maze.
Flags: F01-F02-F03-F04
>>> Set F10 if you want to follow the construction of the maze
Subroutines: /
-Lines 140 & 150 are synthetic three-byte GTO 10
-Register Q is used. It may be replaced by another synthetic register
like register P
| 01 LBL "MAZE"
02 STO M 03 X<>Y 04 STO N 05 * 06 .12 07 LBL 00 08 STO IND Y 09 DSE Y 10 GTO 00 11 SIGN 12 STO O 13 ST+ 01 14 LBL 10 15 FS? 10 16 VIEW O 17 CF 01 18 CF 02 19 CF 03 20 CF 04 21 CLX 22 STO Q 23 RCL N 24 RCL O 25 RCL M 26 ST* Z 27 + |
28 X>Y?
29 GTO 02 30 RCL IND X 31 INT 32 X#0? 33 GTO 02 34 SF 01 35 ISG Q 36 LBL 02 37 RCL O 38 RCL M 39 MOD 40 X=0? 41 GTO 02 42 SIGN 43 RCL O 44 + 45 RCL IND X 46 INT 47 X#0? 48 GTO 02 49 SF 02 50 ISG Q 51 LBL 02 52 RCL O 53 RCL M 54 - |
55 X<=0?
56 GTO 02 57 RCL IND X 58 INT 59 X#0? 60 GTO 02 61 SF 03 62 ISG Q 63 LBL 02 64 CLX 65 SIGN 66 RCL O 67 RCL M 68 MOD 69 X=Y? 70 GTO 02 71 RCL O 72 DSE X 73 INT 74 RCL IND X 75 INT 76 X#0? 77 GTO 02 78 SF 04 79 ISG Q 80 LBL 02 81 X<> Q |
82 X=0?
83 GTO 07 84 RCL 00 85 R-D 86 FRC 87 STO 00 88 * 89 INT 90 SIGN 91 ST+ L 92 FS? 04 93 4 94 FS? 03 95 3 96 FS? 02 97 2 98 FS? 01 99 1 100 LBL 05 101 RDN 102 DSE L 103 GTO 05 104 GTO IND T 105 LBL 01 106 RCL M 107 RCL O 108 ST+ Y |
109 .1
110 GTO 06 111 LBL 02 112 SIGN 113 RCL O 114 ST+ Y 115 .02 116 GTO 06 117 LBL 03 118 RCL O 119 RCL M 120 - 121 STO Y 122 .1 123 GTO 06 124 LBL 04 125 RCL O 126 1 127 - 128 STO Y 129 .02 130 LBL 06 131 ST- IND Y 132 X<> Z 133 X<> O 134 E5 135 / |
136 1
137 + 138 ST+ IND O 139 GTO 10 140 LBL 07 141 RCL IND O 142 E2 143 * 144 FRC 145 E3 146 * 147 STO O 148 X#0? 149 GTO 10 150 RCL M 151 RCL N 152 * 153 E3 154 / 155 ISG X 156 CLA 157 END |
( 261 bytes / SIZE n.m+1 )
| STACK | INPUTS | OUTPUTS |
| Y | n | / |
| X | m | 1.eee |
Where n = number of rows , m = number of columns and 1.eee = cntrol number of the maze with eee = m.n
Example: Let's try with n = 7 and m = 10
-If we choose r = 1 as the random seed: 1 STO 00
7 ENTER^
10 XEQ "MAZE" >>>> 1.070
---Execution time = 5m11s---
-Each register now contains a number of the form a.bcdef
a = 0 for an unvisted cell
a = 1 for a visited cell
So, at the end, all the cells have been visited and a = 1
_3_
-The walls 4 |__| 2 are numbered this way.
The walls n°3 and n°4 are in fact the walls 1 and 2
of other cells, so we only deal with walls 1 & 2
1
bc = 00 if the walls 1 & 2 are both deleted
bc = 10 if the wall 2 only is deleted
bc = 02 if the wall 1 only is deleted
bc = 12 if the walls 1 & 2 are not deleted
-The decimals def indicate the previous visited cell.
-So, we only have to take bc into account to draw the maze ( We assume that the edges of the rectangle are already drawn )
-For R01 bc = 02 , that gives the first cell on the left:
|
-For R02 bc = 10 , ------------- 2nd --- of the 1st raw:
__
... and so on ...
-So, we get a maze that looks ( approximately ) as shown below:
| __ __ __ __ __ __ __ __ __ __
| | __ __ __ __ __ __ | | |__ | __ __ __ | | __| | | | __ __ | __ __ |__ | | | __ | __ | __ __| | | | __ | __ __ __| __ __ | | | | | | __ | | |__ | |__ __ __|__ __ __ |__ | ______| |
-Finally, choose the entry and the exit at random ! though the
HP41 could do that too...
Note:
-If you have an extended functions module or an HP-41CX, adding the
following lines after line 155 may help to visualize the walls more easily:
| 156 ENTER^
157 FIX 0 158 CF 29 159 LBL 08 160 " C" 161 ARCL X 162 "~=" 163 ARCL IND X |
164 FRC
165 10 166 * 167 INT 168 ST- L 169 SF 05 170 X=0? 171 GTO 08 |
172 95
173 XTOA 174 RDN 175 CF 05 176 LBL 08 177 X<> L 178 10 179 * |
180 INT
181 X=0? 182 GTO 08 183 FS?C 05 184 "~ " 185 33 186 XTOA 187 RDN |
188 LBL 08
189 RDN 190 AVIEW 191 ISG X 192 GTO 08 193 X<>Y 194 FIX 4 195 SF 29 |
-Line 162 is "append = "
-Line 184 is "append space"
-Set flag F21 and each AVIEW will stop the HP-41, or replace line 190
by PROMPT.
-Perhaps will you find better characters to display walls n°1 &
n°2 in a cell ?
Reference: