aboutsummaryrefslogtreecommitdiff
path: root/vendor/github.com/llgcode/ps/samples/maze.ps
blob: c0d7939eed7c45ac6ecc62b034d8995c6da34ab5 (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
272
273
274
275
%!PS
%%Pages: 1
%%EndComments

% Yet Another Maze Maker
% Version 2
% Written by Peter Sorotokin, 1996-1998
% This program is in the public domain.

% Note: do not send this job to the printer until you know
% how to cancel it (it may take a LOT of time on slow printer;
% it takes couple minutes on my LaserJet 4).

%%BeginSetup

% put your sizes here:

/width  25 def
/height 25 def

% seed number here:

0 srand % put your seed number instead of 0 (normally not required)
systemdict /realtime known { realtime srand } if

% initialization

/size  width height mul def
/zone  size array def
/zsize size array def
/vert  width 1 add array def
/hor   height 1 add array def

/w1 width 1 sub def
/h1 height 1 sub def

0 1 size 1 sub { dup zsize exch 1 put zone exch dup put } bind for
0 1 width { vert exch height string 0 1 h1
    { 1 index exch 255 put } for put } bind for
0 1 height { hor exch width string 0 1 w1
    { 1 index exch 255 put } for put } bind for

% define subroutines

/db { dup 20 string cvs = } bind def

/find_set { { zone 1 index get dup 3 1 roll eq {exit} if } loop} bind def

/merge_sets {
  2 copy zsize exch get
  exch zsize exch get 2 copy gt
  3 1 roll add exch
    { zsize 2 index 3 -1 roll put
        zone 3 1 roll put  }
    { zsize 3 index 3 -1 roll put
        zone 3 1 roll exch put  }
  ifelse } bind def

%%EndSetup

%%Page: maze 1

% building

size 1 sub
{
    {
        rand 2 mod 0 eq
        {
            rand height mod
            rand w1 mod 2 copy
            height mul add
            dup height add
            find_set exch find_set
            2 copy eq
            {
                pop pop pop pop
            }
            {
                merge_sets vert exch 1 add get exch 0 put exit
            }
            ifelse
        }
        {
            rand h1 mod
            rand width mod 2 copy
            height mul add
            dup 1 add
            find_set exch find_set
            2 copy eq
            {
                pop pop pop pop
            }
            {
                merge_sets exch hor exch 1 add get exch 0 put exit
            }
            ifelse
        }
        ifelse
    }
    loop
} bind repeat

% make entrance and exit

vert 0     get rand height mod 0 put
vert width get rand height mod 0 put

% setup output

clippath pathbbox
2 index sub exch
3 index sub exch
4 2 roll translate
2 copy height 4 add div exch width 4 add div
2 copy gt {exch} if pop /myscale exch def

myscale height mul sub 2 div exch
myscale width  mul sub 2 div exch
translate

myscale myscale scale
0.05 setlinewidth

newpath

% render the maze

0 1 width { dup 0 moveto vert exch get 0 1 height 1 sub
 { 1 index exch get 0 eq 0 1 3 -1 roll { rmoveto } { rlineto } ifelse }
            for pop } bind for

0 1 height { dup 0 exch moveto hor exch get 0 1 width 1 sub
 { 1 index exch get 0 eq 1 0 3 -1 roll { rmoveto } { rlineto } ifelse }
            for pop } bind for

stroke

stroke

% Quick hack to solve the maze.
% This part written by Christian Lehner.

clear

/NORTH 1 def
/WEST 2 def
/SOUTH 4 def
/EAST 8 def
/CRUMB 16 def

/find_door {% column => index
	dup 0 1 3 -1 roll length 1 sub {
		2 copy get 0 eq {
			exch pop
			exit
		} {
			pop
		} ifelse
	} for
} bind def

/mentrance vert 0 get find_door def
/mexit vert width get find_door def

/maze [height {[width {0} repeat]} repeat] def

/mget {% row col => int
	maze 3 -1 roll get exch get
} bind def

/mset {% row col int => -
	maze 4 -1 roll get 3 -2 roll put
} bind def

/initmaze {
	0 1 height 1 sub {/row exch def
		/mrow maze row get def
		0 1 width 1 sub {/col exch def
			% north
			hor row 1 add get col get 0 eq {
				mrow col 2 copy get //NORTH or put
			} if
			% west
			vert col get row get 0 eq {
				mrow col 2 copy get //WEST or put
			} if
			% south
			hor row get col get 0 eq {
				mrow col 2 copy get //SOUTH or put
			} if
			% east
			vert col 1 add get row get 0 eq {
				mrow col 2 copy get //EAST or put
			} if
		} for
	} for
} bind def

/step {% row col side => row' col'
	/side exch def
	/col exch def
	/row exch def
	side //NORTH eq {
		row 1 add col
	} {
		side //WEST eq {
			row col 1 sub
		} {
			side //SOUTH eq {
				row 1 sub col
			} {
				side //EAST eq {
					row col 1 add
				} {
					(step: bad side ) print side ==
				} ifelse
			} ifelse
		} ifelse
	} ifelse
} bind def

/done false def

/escape {% row col => -
	/col exch def
	/row exch def
	row mexit eq col width 1 sub eq and {
		(done)==
		row col
		/done true store
	} {
		row col 2 copy mget //CRUMB or mset
		row col
		[//NORTH //WEST //SOUTH //EAST] {/side exch def
			done {exit} if
			2 copy mget /val exch def
			val side and 0 ne {
				2 copy side step 2 copy
				mget /val exch def
				val //CRUMB and 0 eq {
					escape
				} {
					pop pop
				} ifelse
			} if
		} forall
		done not {
			pop pop
		} if
	} ifelse
} bind def

/solve {
	% close the entrance
	vert 0 get mentrance 1 put
	initmaze
	% start the escape
	/path [mentrance -1 mentrance 0 escape 2 copy 1 add] def
	% draw the path
	.5 setgray
	.5 .5 translate
	path 1 get path 0 get moveto
	2 2 path length 1 sub {/i exch def
		path i 1 add get path i get lineto
	} for
	stroke
	showpage
} bind def

% eject the page

copypage solve

%%EOF