1" These macros 'solve' any maze produced by the a-maze-ing maze.c program. 2" 3" First, a bit of maze theory. 4" If you were put into a maze, a guaranteed method of finding your way 5" out of the maze is to put your left hand onto a wall and just keep walking, 6" never taking your hand off the wall. This technique is only guaranteed to 7" work if the maze does not have any 'islands', or if the 'exit' is on the 8" same island as your starting point. These conditions hold for the mazes 9" under consideration. 10" 11" Assuming that the maze is made up of horizontal and vertical walls spaced 12" one step apart and that you can move either north, south, east or west, 13" then you can automate this procedure by carrying out the following steps. 14" 15" 1. Put yourself somewhere in the maze near a wall. 16" 2. Check if you have a wall on your left. If so, go to step 4. 17" 3. There is no wall on your left, so turn on the spot to your left and step 18" forward by one step and repeat step 2. 19" 4. Check what is directly in front of you. If it is a wall, turn on the 20" spot to your right by 90 degrees and repeat step 4. 21" 5. There is no wall in front of you, so step forward one step and 22" go to step 2. 23" 24" In this way you will cover all the corridors of the maze (until you get back 25" to where you started from, if you do not stop). 26" 27" By examining a maze produced by the maze.c program you will see that 28" each square of the maze is one character high and two characters wide. 29" To go north or south, you move by a one character step, but to move east or 30" west you move by a two character step. Also note that in any position 31" there are four places where walls could be put - to the north, to the south, 32" to the east and to the west. 33" A wall exists to the north of you if the character to the north of 34" you is a _ (otherwise it is a space). 35" A wall exists to the east of you if the character to the east of you 36" is a | (otherwise it is a .). 37" A wall exists to the west of you if the character to the west of you 38" is a | (otherwise it is a .). 39" A wall exists to the south of you if the character where you are 40" is a _ (otherwise it is a space). 41" 42" Note the difference for direction south, where we must examine the character 43" where the cursor is rather than an adjacent cell. 44" 45" If you were implementing the above procedure is a normal computer language 46" you could use a loop with if statements and continue statements, 47" However, these constructs are not available in vi macros so I have used 48" a state machine with 8 states. Each state signifies the direction you 49" are going in and whether or not you have checked if there is a wall on 50" your left. 51" 52" The transition from state to state and the actions taken on each transition 53" are given in the state table below. 54" The names of the states are N1, N2, S1, S2, E1, E2, W1, W2, where each letter 55" stands for a direction of the compass, the number 1 indicates that the we 56" have not yet checked to see if there is a wall on our left and the number 2 57" indicates that we have checked and there is a wall on our left. 58" 59" For each state we must consider the existence or not of a wall in a 60" particular direction. This direction is given in the following table. 61" 62" NextChar table: 63" state direction vi commands 64" N1 W hF 65" N2 N kF 66" S1 E lF 67" S2 S F 68" E1 N kF 69" E2 E lF 70" W1 S F 71" W2 W hF 72" 73" where F is a macro which yanks the character under the cursor into 74" the NextChar register (n). 75" 76" State table: 77" In the 'vi commands' column is given the actions to carry out when in 78" this state and the NextChar is as given. The commands k, j, ll, hh move 79" the current position north, south, east and west respectively. The 80" command mm is used as a no-op command. 81" In the 'next state' column is given the new state of the machine after 82" the action is carried out. 83" 84" current state NextChar vi commands next state 85" N1 . hh W1 86" N1 | mm N2 87" N2 _ mm E1 88" N2 space k N1 89" S1 . ll E1 90" S1 | mm S2 91" S2 _ mm W1 92" S2 space j S1 93" E1 space k N1 94" E1 _ mm E2 95" E2 | mm S1 96" E2 . ll E1 97" W1 space j S1 98" W1 _ mm W2 99" W2 | mm N1 100" W2 . hh W1 101" 102" 103" Complaint about vi macros: 104" It seems that you cannot have more than one 'undo-able' vi command 105" in the one macro, so you have to make lots of little macros and 106" put them together. 107" 108" I'll explain what I mean by an example. Edit a file and 109" type ':map Q rXY'. This should map the Q key to 'replace the 110" character under the cursor with X and yank the line'. 111" But when I type Q, vi tells me 'Can't yank inside global/macro' and 112" goes into ex mode. However if I type ':map Q rXT' and ':map T Y', 113" everything is OK. I`m doing all this on a Sparcstation. 114" If anyone reading this has an answer to this problem, the author would 115" love to find out. Mail to [email protected]. 116" 117" The macros: 118" The macro to run the maze solver is 'g'. This simply calls two other 119" macros: I, to initialise everything, and L, to loop forever running 120" through the state table. 121" Both of these macros are long sequences of calls to other macros. All 122" of these other macros are quite simple and so to understand how this 123" works, all you need to do is examine macros I and L and learn what they 124" do (a simple sequence of vi actions) and how L loops (by calling U, which 125" simply calls L again). 126" 127" Macro I sets up the state table and NextChar table at the end of the file. 128" Macro L then searches these tables to find out what actions to perform and 129" what state changes to make. 130" 131" The entries in the state table all begin with a key consisting of the 132" letter 's', the current state and the NextChar. After this is the 133" action to take in this state and after this is the next state to change to. 134" 135" The entries in the NextChar table begin with a key consisting of the 136" letter 'n' and the current state. After this is the action to take to 137" obtain NextChar - the character that must be examined to change state. 138" 139" One way to see what each part of the macros is doing is to type in the 140" body of the macros I and L manually (instead of typing 'g') and see 141" what happens at each step. 142" 143" Good luck. 144" 145" Registers used by the macros: 146" s (State) - holds the state the machine is in 147" c (Char) - holds the character under the current position 148" m (Macro) - holds a vi command string to be executed later 149" n (NextChar) - holds the character we must examine to change state 150" r (Second Macro) - holds a second vi command string to be executed later 151" 152set remap 153set nomagic 154set noterse 155set wrapscan 156" 157"================================================================ 158" g - go runs the whole show 159" I - initialise 160" L - then loop forever 161map g IL 162" 163"================================================================ 164" I - initialise everything before running the loop 165" G$?.^M - find the last . in the maze 166" ^ - replace it with an X (the goal) 167" GYKeDP - print the state table and next char table at the end of the file 168" 0S - initialise the state of the machine to E1 169" 2Gl - move to the top left cell of the maze 170map I G$?. 171^GYKeDP0S2Gl 172" 173"================================================================ 174" L - the loop which is executed forever 175" Q - save the current character in the Char register 176" A - replace the current character with an 'O' 177" ma - mark the current position with mark 'a' 178" GNB - on bottom line, create a command to search the NextChar table 179" for the current state 180" 0M0E@m^M - yank the command into the Macro register and execute it 181" wX - we have now found the entry in the table, now yank the 182" following word into the Macro register 183" `a@m - go back to the current position and execute the macro, this will 184" yank the NextChar in register n 185" GT$B$R - on bottom line, create a command to search the state table 186" for the current state and NextChar 187" 0M0E@m^M - yank the command into the Macro register and execute it 188" 2WS - we have now found the entry in the table, now yank the 189" next state into the State macro 190" bX - and yank the action corresponding to this state table entry 191" into the Macro register 192" GVJ - on bottom line, create a command to restore the current character 193" 0H - and save the command into the second Macro register 194" `a@r - go back to the current position and exectute the macro to restore 195" the current character 196" @m - execute the action associated with this state 197" U - and repeat 198map L QAmaGNB0M0E@m 199wX`a@mGT$B$R0M0E@m 2002WSbXGVJ0H`a@r@mU 201" 202"================================================================ 203" U - no tail recursion allowed in vi macros so cheat and set U = L 204map U L 205" 206"================================================================ 207" S - yank the next two characters into the State register 208map S "sy2l 209" 210"================================================================ 211" Q - save the current character in the Char register 212map Q "cyl 213" 214"================================================================ 215" A - replace the current character with an 'O' 216map A rO 217" 218"================================================================ 219" N - replace this line with the string 'n' 220map N C/n 221" 222"================================================================ 223" B - put the current state 224map B "sp 225" 226"================================================================ 227" M - yank this line into the Macro register 228map M "my$ 229" 230"================================================================ 231" E - delete to the end of the line 232map E d$ 233" 234"================================================================ 235" X - yank this word into the Macro register 236map X "myt 237" 238"================================================================ 239" T - replace this line with the string 's' 240map T C/s 241" 242"================================================================ 243" R - put NextChar 244map R "np 245" 246"================================================================ 247" V - add the letter 'r' (the replace vi command) 248map V ar 249" 250"================================================================ 251" J - restore the current character 252map J "cp 253" 254"================================================================ 255" H - yank this line into the second Macro register 256map H "ry$ 257" 258"================================================================ 259" F - yank NextChar (this macro is called from the Macro register) 260map F "nyl 261" 262"================================================================ 263" ^ - replace the current character with an 'X' 264map ^ rX 265" 266"================================================================ 267" YKeDP - create the state table, NextChar table and initial state 268" Note that you have to escape the bar character, since it is special to 269" the map command (it indicates a new line). 270map Y osE1 k N1 sE1_ mm E2 sE2| mm S1 sE2. ll E1 271map K osW1 j S1 sW1_ mm W2 sW2| mm N1 sW2. hh W1 272map e osN1. hh W1 sN1| mm N2 sN2 k N1 sN2_ mm E1 273map D osS1. ll E1 sS1| mm S2 sS2 j S1 sS2_ mm W1 274map P onE1 kF nE2 lF nW1 G$JF nW2 hF nN1 hF nN2 kF nS1 lF nS2 G$JF 275E1 276