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