hp41programs

Mazes

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:

[1]   http://en.wikipedia.org/wiki/Maze_generation_algorithm