[Maze generation for Rosetta Code. EDSAC program, Initial Orders 2. Cells, horizontal walls, and vertical walls are numbered as shown in this example: +---1---+---2---+---3---+ | | | | 1 1 2 2 3 3 4 N | | | | | +---5---+---6---+---7---+ W---+---E | | | | | 5 5 6 6 7 7 8 S | | | | +---9---+--10---+--11---+ Maze data are held in a single 1-based array of 17-bit values (equivalent to an array of records in a high-level language). In each entry, fields for cells and walls are as shown in "Flags" below.] [Arrange the storage] T51K P56F [G parameter: generator for pseudo-random numbers] T47K P100F [M parameter: main routine + dependent subroutines] T45K P398F [H parameter: storage for maze] [The following once-only code can be overwritten by the maze data.] T46K P398F [N parameter: library subroutine R4 to read data] T50K P420F [X parameter: code executed at start-up only] [=========== Executed at start-up, then overwritten ================] E25K TX GK [Enter with acc = 0] [0] A@ GN [read 35-bit maze width into 0D] AF TM [load and store width, assuming high word = 0] [4] A4@ GN AF T1M [same for height] [Initialize linear congruential generator for pseudo-random numbers] [8] A8@ GN [read seed for LCG into 0D] AD T4D [pass seed to LCG in 4D] [12] A12@ GG [initialize LCG] [Choose a random cell in the maze, for use later.] [Also update storage of width and height.] T4D [clear the whole of 4D, including sandwich bit] AM U4F [load 17-bit width, pass to LCG as 35-bit value] LD A2F TM [width to address field, add 1, store] [20] A20@ G1G [call LCG, 0D := random in 0..(width - 1)] AF T3M [save random to temporary store] T4D A1M U4F [pass height of maze to LCG] LD A2F T1M [height to address field, add 1, store] [30] A30@ G1G [call LCG, 0D := random in 0..(height - 1)] HF VM L64F L32F [acc := random*(width + 1)] A3M LD A2F [add first random, shift to address, add 1] T3M [save random index for use below] HM V1M L64F L32F T2M [store (width+1)*(height+1)] E65M [jump to main routine with acc = 0] [================ Main routine ====================] E25K TM GK [Variables] [0] PF [initially maze width; then (width + 1) in address field] [1] PF [initially maze height; then (height + 1) in address field] [List of up to four E orders to move N, S, W, E.] [The first two are also used as temporary store at program start] [2] PF [3] PF PF PF [6] TF [T order to store E order in list] [Constants] [7] T2@ [initial value of T order] [8] TH [order to store into array{0}] [9] AH [order to load from array{0}] [10] C1H [order to collate with array{1};] [also teleprinter colon in figures mode] [11] MF [add to T order to make A order with same address] [12] LF [add to T order to make C order with same address] [Flags] [13] K4096F [horizontal wall deleted, 10000 hex] [14] IF [vertical wall deleted, 8000 hex] [15] RF [no north neighbour, 4000 hex] [16] WF [no south neighbour, 2000 hex] [17] QF [no west neighbour, 1000 hex] [18] P1024F [no east neighbour, 0800 hex] [19] PD [cell visited, 0001 hex] [20] V2047F [mask to clear visited bit] [21] P1023F [mask to select EDSAC address field, which contains index of previous cell for backtracking (0 if none). [Teleprinter] [22] #F [set figures mode] [23] !F [space] [24] @F [carriage return] [25] &F [line feed] [Subroutine called to set flag "no north neighbour" in cells along north edge, similarly for east, south and west edges (order must be N, E, S, W). Input: 4F = negative count of cells 5F = step in array index 6F = flag to be set] [26] A3F T42@ [plant return link as usual] A36@ G34@ [jump into middle of loop (since A < 0)] [30] T4F [loop: update megative count] A36@ A5F U36@ [34] S11@ T38@ [The following order initially refers to the NW corner cell. First call leaves it referring to NE corner; second call to SE corner, etc. Hence the need for calls to be in the order N, E, S, W.] [36] A1H [planted; loaded as A1H] A6F [38] TF A4F A2F [add 1 to negative count] G30@ [if not yet 0, loop back] [42] ZF [Subroutine to test for unvisited neighbour of current cell in a given direction. Input: 4F = E order to be added to list if unvisited neighbour is found 5F = step in array index to reach neighbour 6F = flag to test for no neighbour in this direction] [43] A3F T64@ [plant return link as usual] S6F H6F CH [if no neighbour then acc = 0, else acc < 0] E64@ [exit if no neighbour] TF A118@ A5F T55@ S19@ H19@ [55] CF E64@ TF A6@ U63@ A2F T6@ A4F [load jump to execute move] [63] TF [store in list of moves] [64] ZF [(planted) jump back to caller] [Jump to here from once-only code, with acc = 0] [Clear maze array] [65] S2@ [66] TF [use 0F as loop counter] [67] TH [planted, loaded as TH] A67@ A2F T67@ AF A2F G66@ [Set flag "no north neighbour" in cells along northern edge] S@ A2F T4F [count = width, pass in 4F] A2F T5F [step in array index = 1, pass in 5F] A15@ T6F [pass flag in 6F] [81] A81@ G26@ [call subroutine to set flag] [Repeat for east, south, west edges (must be in that order)] S1@ A2F T4F A@ T5F A18@ T6F [90] A90@ G26@ S@ A2F T4F S2F T5F A16@ T6F [99] A99@ G26@ S1@ A2F T4F S@ T5F A17@ T6F [108] A108@ G26@ [Start with the random cell chosen at program start (X parameter)] A3@ A8@ [Loop: here acc = T order for current cell] [112] U121@ [plant T order] A12@ T118@ [make and plant C order, same address] [Initialize storing in list of moves] A7@ T6@ H20@ [118] CF A19@ [mark cell as visited] UH [store flags of current cell in array{0} for easy access] [121] TF [and also in the body of the array] [If cell has unvisited North neighbour, add North to list of possible moves] A177@ T4F S@ T5F A15@ T6F [128] A128@ G43@ [Repeat for South, West, East neighbours] A178@ T4F A@ T5F A16@ T6F [136] A136@ G43@ A179@ T4F S2F T5F A17@ T6F [144] A144@ G43@ A180@ T4F A2F T5F A18@ T6F [152] A152@ G43@ [List now has 0..4 possible moves. If more than one, choose randomly.] T4D [clear whole of 4D, including sandwich bit, for randomizer] A6@ S7@ [address field := count of moves] S2F G225@ [jump if none] S2F G169@ [jump if one only] RD A2F T4F [pass count, right-justified, to randomizer] [164] A164@ G1G [0F := random value 0..(count - 1)] AF LD E170@ [169] TF [only one move, must be at list{0}] [170] A7@ A11@ T173@ [173] AF T176@ A121@ [common to all moves] [176] EF [jump to move N,S,E, or W with acc = 0] [177] E181@ [178] E190@ [179] E199@ [180] E208@ [Move North and delete horizontal wall] [181] U186@ A11@ T184@ [184] AF A13@ [186] TF A121@ S@ E216@ [Move South and delete horizontal wall] [190] A@ U196@ A11@ T194@ [194] AF A13@ [196] TF A196@ E216@ [Move West and delete vertical wall] [199] U204@ A11@ T202@ [202] AF A14@ [204] TF A121@ S2F E216@ [Move East and delete vertical wall] [208] A2F U214@ A11@ T212@ [212] AF A14@ [214] TF A214@ [fall through] [Set index of current cell as previous to the new cell. Here with T order for new cell in acc.] [216] U222@ A11@ T221@ A121@ S8@ [221] AF [222] TF A222@ E112@ [No unvisited neighbour, backtrack if possible] [225] TF [clear acc, needed] H21@ CH [get index of previous cell (in address field)] S2F [is it 0?] G233@ [if so, maze is complete, jump to print] A2F [restore] A8@ [make T order] E112@ [Print the maze created above] [233] O22@ [set teleprinter to figures mode] TF [clear acc] S1@ T5F [Outer 'loop and a half' with 5F as negative counter. h + 1 rows for horizontal walls plus h rows for vertical walls] [237] [Print row for horizontal walls] O296@ [print leading + sign] S@ A2F [set inner loop counter in 4F] H13@ [241] T4F [4F := negative count of horizontal walls per row] S13@ [has current horizontal wall been deleted?] [243] C1H [planted; loaded as C1H] G247@ [jump if not] A23@ G249@ [247] T1F [clear acc] [248] A248@ [load hyphen (since A = minus in figures mode)] [249] TF OF OF OF [print 3 spaces or 3 minus] O296@ [print plus sign] A243@ A2F T243@ [inc address in C order] A4F A2F G241@ [Here with acc = 0 after printing one row] A243@ A2F T243@ [skip next element in array] O24@ O25@ [print CR, LF] A5F A2F E295@ T5F [Print row for vertical walls] S@ T4F H14@ [272] S14@ [273] C1H [planted; loaded as C1H] G277@ A23@ G279@ [277] T1F [clear acc] A10@ [colon in figures mode] [279] TF OF [print colon or space] A273@ A2F T273@ [update C order] A4F A2F [inc negative counter for inner loop] E292@ [jump out of loop if counter = 0] T4F [update counter] O23@ O23@ O23@ [print 3 spaces] E272@ [Exit from inner loop for vertical walls] [292] O24@ O25@ [print CR, LF] E237@ [Exit] [295] O22@ [dummy character to flush print buffer] [296] ZF [(1) halt program (2) plus sign in figures mode] [==================== Generator for pseudo-random numbers ===========] [Linear congruential generator, same algorithm as Delphi 7 LCG 38 locations] E25K TG GKG10@G15@T2#ZPFT2ZI514DP257FT4#ZPFT4ZPDPFT6#ZPFT6ZPFRFA6#@S4#@ T6#@E25FE8ZPFT8ZPFPFA3FT14@A4DT8#@ZFA3FT37@H2#@V8#@L512FL512F L1024FA4#@T8#@H6#@C8#@T8#@S4DG32@TDA8#@E35@H4DTDV8#@L1FTDZF [==================== LIBRARY SUBROUTINE ============================] E25K TN [R4 Input of one signed integer. 22 storage locations; working positions 4, 5, and 6.] GKA3FT21@T4DH6@E11@P5DJFT6FVDL4FA4DTDI4FA4FS5@G7@S5@G20@SDTDT6FEF [===================================================================] [The following, without the comments and white space, might have been input from a separate tape.] E25K TX GK EZ [define entry point] PF [acc = 0 on entry] [Integers supplied by user: maze width, maze height, seed for LCG. To be read by library subroutine R4; sign comes after value.] 12+8+987654321+