/[the-feebs-war]/definitions/mazes.lisp
ViewVC logotype

Contents of /definitions/mazes.lisp

Parent Directory Parent Directory | Revision Log Revision Log


Revision 15 - (show annotations)
Sat Feb 16 20:01:42 2008 UTC (6 years, 2 months ago) by gmilare
File size: 13001 byte(s)
1 ;;; -*- Common Lisp -*-
2
3 #| Copyright (c) 2007,2008 Gustavo Henrique Milar´┐Ż
4
5 This file is part of The Feebs War.
6
7 The Feebs War is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3 of the License, or
10 (at your option) any later version.
11
12 The Feebs War is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with The Feebs War. If not, see <http://www.gnu.org/licenses/>.
19 |#
20
21 ;;; The mazes were
22 ;;; Created by Jim Healy, July 1987.
23 ;;;
24 ;;; **************************************************
25 ;;; Maze guidelines:
26 ;;; X represents a wall.
27 ;;; * represents a mushroom patch.
28 ;;; e is a feeb entry point.
29 ;;;
30 ;;; The maze should be a rectangle bounded by walls
31 ;;; in each side.
32 ;;; These mazes are all 32x32, but you may build
33 ;;; a maze of any size you wish.
34 ;;; **************************************************
35
36 ;;; Maze1 has a good number of dead ends and little nooks.
37
38 (in-package :the-feebs-war)
39
40 (defparameter *maze-1*
41 '("XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX"
42 "XXX *eXXXX *e ** X"
43 "XXX XXXXX XXXX XXXXXXXXXXXX XX X"
44 "XXX XXX XXXXXX X X"
45 "XXXXX XXXXXXX XXXXXXX XXXXXXX XX"
46 "X * XXX XX * XeXX XX"
47 "X XXXXXXX XXX XXXXXXX X XXX XXXX"
48 "X XXXXXX XXX XX X *XX"
49 "X XXXXXXX XXX XXXXXXX XXXXXXXXXX"
50 "X XXXXXXX XXX* e XXXXXX XXX"
51 "X XXXXX XXXXXXXXX * XXX"
52 "X XXXXX XXXXXX XXXXXX XX XX"
53 "X eXXXX XXXXXX XXX XXXXX XX XXX"
54 "X XXXXX* XXXXe XXXX XX XX"
55 "X XXXXX XXXXXX XXXXX XXX XXX XX"
56 "X eXXXX e XXXXXX *XX XX XX"
57 "X XXXXX XXXXXX XXXXXXX X XXeXXX"
58 "X XXX XXXXXXXX XX XX"
59 "X XXXXX XXXXXX XXXXXXXXXX XXXXXX"
60 "X XXXXX * XXXXX XX"
61 "X* XXX XXXXXX XXXXX XXXXXX X XX"
62 "X XXXXX e XXXXX X e X XX"
63 "X XX XX XXXXXX XXXXX X XXXXXX XX"
64 "X *XXX XXXXX * XX"
65 "X XX XX XXXXXX XXXXXXXXXX XXXXXX"
66 "X XXXXX XXXXXX * * XX"
67 "X XXX XXXXXXXXXXXXXXXXXXXXX XX"
68 "X XXXX X X eX X XX"
69 "X XXX XX X XX X XX X XX X XX XX"
70 "X XXXX XX X XX X XX X XX*X XX XX"
71 "X e * XX XX * XX XX XXeXX"
72 "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX"))
73
74 ;;; Maze2 doesn't have any really long corridors.
75
76 (defparameter *maze-2*
77 '("XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX"
78 "X eXXXXX * X XXXXXX X e XXXXX"
79 "X XXXX X X XXXX X X XXXXX"
80 "X XX XXXX XXXX X* X X XXXXX"
81 "XX XX XXX XXXX XX XX X X"
82 "XX e XXX XXXXXXX XX XXXXXXXX*X"
83 "XXXX XXX XXXXX X e XXX XX X"
84 "XXXX XXX XXXXXXXX XXXX X X"
85 "XX * XX XXe XXXXXXXXXX XX XXX"
86 "XX XXXX X XX X XXX XXXXX XXX"
87 "XX XX XXX X XX XXXXX"
88 "XXXXX XXX *XXX X XXXXXXXX"
89 "XX* XXXXXX XXXX XXXX XXXXXXXX"
90 "XXXXX XX XXXX XXXXXXXXX XXXXXXXX"
91 "XXXXX e XXXX *XXXXXX eXXXXX"
92 "XXXXXXXX XXXXXXX XXXXXXXXX XXXXX"
93 "XXXXXX XXXXX eXXXXX XXXXX"
94 "XXXXXX XXX XXXXXXX XXXXX XXXXXXX"
95 "XX XXX X XXX XX X XX"
96 "XX XXX XXXXX XX XX XXX XX XX"
97 "XX XXXXX *X XX X XX XXXXXX*XX"
98 "X XXXXX XXXX X XX XX"
99 "X XX XXXXXXX XXXXX*X X Xe XXXX"
100 "X XXXX e X XXXXX*XX XX XXXX"
101 "X XX XXXXXX XX XXX*XXX XXX"
102 "XXXX eXXX XXXX XX XXXXX X X"
103 "XXXXXX XXXXXXXXX XX XXXX XXX X"
104 "XXX * X X XX XXXX XXX X X"
105 "XX XXXX X XX XXXX XXX X e X"
106 "XX XX * X * X XXXX XX XXX*X"
107 "XX XXX XXX XX eXXX XXX*X"
108 "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX"))
109
110 ;;; Maze3 has the minimum number of mushroom sites, most
111 ;;; of which are between a rock and a hard place. Those
112 ;;; poor feebs!
113
114 (defparameter *maze-3*
115 '("XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX"
116 "X e XXXXXX XXXXXXX*XXXXXXXXX"
117 "X X XXX XXXXX e XXXX XXX e X"
118 "X XXX XXXXXX XX XX XXX XXX X"
119 "XXX XXX XXXXXX XX XX X X e X"
120 "Xe XXX*XXXX* XX XXeX X XXXXX X"
121 "X X XXX XXXXXX XX XX X XXXXX X"
122 "X XXX XXXXXX XX* XXXXXXXXX X"
123 "X XXXXX XX e XX XXXXXXXX XXX X"
124 "X X XXX XXX XXXXX XXXXXX XXX X"
125 "Xe XXX XXXX XXXX X X X"
126 "XXX XXXX XXXXXXXX X XXX XXX"
127 "XXX eXX XXXXXXXXX XXXXX XXXXX"
128 "XXXXX XXXXXXXXXXXX XXXXXX XXX"
129 "XXXXX * XX eXX XXX XX XXX"
130 "XX*XXXX XXXXXX XX XXX XXX XX XXX"
131 "XX X XXXXX X XXX eXX XXX"
132 "X XXXXXXXX XX XXXX XXX XX XXX"
133 "X XXXXeXXXXXX XXXX XXX XX XXX"
134 "X XX*XXXXX XXXXXXXXX XXX"
135 "XXXXXX XXX XXXX XXXXXX XXX"
136 "XXXXXXXXX XXX XXXXXX XXXXXX XXX"
137 "XXX XX e eX XXXX"
138 "XX XXXXX XXXX XXXX XXXX XXXX"
139 "XX XXXXX XX XXXX XXXX XXXX XX"
140 "XX eXXXX XX XXXX XXXX XXXXXX XX"
141 "XXX XX XXX * XXX XX"
142 "XX XX XXXX* XXXX XXXX XXXXXX XX"
143 "XXX X XXXXX XXXX XXXX X XX"
144 "XXXX e XXXX XXXX X XX X X"
145 "XXXXXXXXXXXX *e X e XX"
146 "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX"))
147
148
149 ;;; Maze4 is symmetric about the vertical axis. (Wow...)
150
151 (defparameter *maze-4*
152 '("XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX"
153 "X* eXXXXXXXXXXe *X"
154 "X XXXXXXXX XXXXXXXX X"
155 "X XX XXXXXXX XX XXXXXXX XX X"
156 "X XeXXXXXXX XX XXXXXXXeX X"
157 "XX X XXXXXXX eXXe XXXXXXX X XX"
158 "XX X XXXXXXX XXXXXX XXXXXXX X XX"
159 "XX * XXXXXXX XXXXXX XXXXXXX * XX"
160 "XX X XXXe eXXX X XX"
161 "XX X XXX XXXXXXXXXXXXXX XXX X XX"
162 "XX e XXX XXXXXXXX XXX e XX"
163 "XX X XXXXXX XXXXXXXX XXXXXX X XX"
164 "XX X XXXX XXXXXXXX XXXX X XX"
165 "XX XXXX XXXe eXXXX XXXX XX"
166 "XXX XXXXX XXX XXX XXXX XXXXX XXX"
167 "XXX XXXXX XXX XXX XXXXX XXX"
168 "X* XXXXX XXXX XXXXX *X"
169 "X XXXXX XX XX ** XX XX XXXXX X"
170 "X XXXXX XX XX XXXX XX XX XXXXX X"
171 "X XXX e XX XX XXXX XX XX e XXX X"
172 "X XXXXX XX XXXX XX XXXXX X"
173 "X XXXXX XXXXX XXXX XXXXX XXXXX X"
174 "X X XXXXX XXXX XXXXX X X"
175 "XXXXX * * XXXXX"
176 "XXXXX XXXXXXXX XX XXXXXXXX XXXXX"
177 "XXXXX XXXXXXXX XX XXXXXXXX XXXXX"
178 "XXXXX XXXXX XX XXXXX XXXXX"
179 "XXXX XX XXXXeXXeXXXX XX XXXX"
180 "XXX XXXX XXX XX XXX XXXX XXX"
181 "XXX XXXXXX XXX XX XXX XXXXXX XXX"
182 "XX* e XX e *XX"
183 "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX"))
184
185 ;;; Maze5 has a lot of long corridors good for feeb showdowns.
186 ;;; Furthermore, all the feeb entry-points are in the corridors.
187 ;;; You can run but you can't hide!
188
189 (defparameter *maze-5*
190 '("XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX"
191 "X e e X"
192 "X XXXXXXX*XXXXXXXXXXXX XXXXXXX X"
193 "X e X"
194 "X X XXXXX XXXXXXXXXXXX XXXXX X X"
195 "X * X"
196 "X X XX XX XXXXXXXXXXXX XX XX X X"
197 "X X XX XX XXXXXXXXXXXX XXeXX X X"
198 "X X XX XX * XX XX X X"
199 "XeX XX XX XXXXXXXXXXXX XX XX X X"
200 "X X XX XX XXXXXXXXXXXX XX XX X X"
201 "X X XX XX e XX XXeX X"
202 "X X XXeXX XXXXXXXXXXXX XX XX X X"
203 "X X XX XX XXXXXXXXXXXX XX XX XeX"
204 "X*X XX XX XX XX X X"
205 "X X XX XX XXXXXXXXXXXX XX XX X X"
206 "X XeXX XX XXXXXXXXXXXX*XX XX X X"
207 "X X XX XX * XX XX*X X"
208 "X X XX XX XXXXXXXXXXXX XX XX X X"
209 "X X XX XX XXXXXXXXXXXX XX XX X X"
210 "X X XX XX e XX XX*X X"
211 "X X XX*XX XXXXXXXXXXXX XX XX X X"
212 "X X XX XX XXXXXXXXXXXX XX XX X X"
213 "X X XX XX XX XXeX X"
214 "X X XX XX XXXXXXXXXXXX XX XX X X"
215 "X X XX XX XXXXXXXXXXXX XX XX X X"
216 "X e X"
217 "X*X XXXXX XXXXXXXXXXXX XXXXX X*X"
218 "X e * X"
219 "X XXXXXXX XXXXXXXXXXXX XXXXXXX X"
220 "X e * X"
221 "XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX"))
222
223 ;;; Use this function to create new mazes
224 ;;; of any size.
225
226 (defun make-template (x-size y-size)
227 "Prints map template of the requested size.
228 Use this to create new mazes."
229 (loop repeat y-size collect
230 (make-string x-size :initial-element #\X)))
231
232 (defun density (maze xs ys)
233 (let ((sum 0))
234 (dotimes (x xs)
235 (dotimes (y ys)
236 (if (not (aref maze x y))
237 (incf sum))))
238 (float (/ sum (* xs ys)))))
239
240 (defun horiz-corridor (map y x1 x2)
241 (do ((x x1 (if (< x1 x2) (1+ x) (1- x))))
242 ((= x x2))
243 ;; we need to guarantee that everything in map is
244 ;; corridors, that is, can't have something like
245 ;; XXXXXXXX
246 ;; XXX X
247 ;; X XXX
248 ;; XXXXXXXX
249 ;; that big blank square isn't good due
250 ;; to the limited vision of the feebs
251 (and (not (aref map x (1- y))) ; blank square up
252 (or (and (not (aref map (1+ x) y)) ; blank square to the right
253 (not (aref map (1+ x) (1- y)))) ; blank square up-right
254 (and (not (aref map (1- x) (1- y))) ; blank square up-left
255 (not (aref map (1- x) y)))) ; blank square to the left
256 (return)) ; can't make a blank square here, stop
257 (and (not (aref map x (1+ y))) ; blank square down
258 (or (and (not (aref map (1+ x) y)) ; blank square to the right
259 (not (aref map (1+ x) (1+ y)))) ; blank square down-right
260 (and (not (aref map (1- x) (1+ y))) ; blank square down-left
261 (not (aref map (1- x) y)))) ; blank square to the left
262 (return)) ; can't make a blank square here, stop
263 (setf (aref map x y) nil))
264 map)
265
266 (defun vert-corridor (map x y1 y2)
267 (do ((y y1 (if (< y1 y2) (1+ y) (1- y))))
268 ((= y y2))
269 (and (not (aref map (1- x) y))
270 (or (and (not (aref map x (1+ y)))
271 (not (aref map (1- x) (1+ y))))
272 (and (not (aref map (1- x) (1- y)))
273 (not (aref map x (1- y)))))
274 (return))
275 (and (not (aref map (1+ x) y))
276 (if (or (and (not (aref map x (1+ y)))
277 (not (aref map (1+ x) (1+ y))))
278 (and (not (aref map (1+ x) (1- y)))
279 (not (aref map x (1- y)))))
280 (return)))
281 (setf (aref map x y) nil))
282 map)
283
284 (defun translate (map xs ys)
285 (loop for y from (1- ys) downto 0 collect
286 (let ((str (make-string xs)))
287 (dotimes (x xs str)
288 (setf (aref str x)
289 (if (aref map x y)
290 #\X
291 #\Space))))))
292
293 ;;; This one generates an almost ready-to-use map
294
295 (defun generate-maze (x-size y-size
296 &key (density 0.4)
297 (corridor-x-min 1)
298 (corridor-x-max (- x-size 2))
299 (corridor-x-avg (floor x-size 4))
300 (corridor-y-min 1)
301 (corridor-y-max (- y-size 2))
302 (corridor-y-avg (floor y-size 4)))
303 "Generates a maze of size X-SIZE x Y-SIZE (at least 10x10)
304 with no entry points and no mushroom sites.
305 DENSITY decides aproximatelly the ratio
306 (blank squares) / (total squares)
307 recomended to be between 0.25 and 0.45.
308 The horizontal corridors will be between CORRIDOR-X-MIN
309 and CORRIDOR-X-MAX around CORRIDOR-X-AVG, when
310 possible; similarly for vertical corridors.
311 It returns two values, a layout like *maze-0* and its density."
312 (if (or (< x-size 10) (< y-size 10))
313 (error "Too small - should be at least 10x10."))
314 ;; Certifying the values to be acceptable
315 (ensure-bound corridor-x-avg
316 (ensure-bound corridor-x-min 1 (- x-size 2))
317 (ensure-bound corridor-x-max 3 (- x-size 2)))
318 (ensure-bound corridor-y-avg
319 (ensure-bound corridor-y-min 1 (- y-size 2))
320 (ensure-bound corridor-y-max 3 (- y-size 2)))
321 ;; Beginning with an array of walls
322 (let ((map (make-array (list x-size y-size)
323 :initial-element t
324 :element-type 'boolean)))
325 (do* ((i 1 (1+ i))
326 (y 1 y*) ; position of horizontal corridor
327 (y* (- y-size 2) (1+ (random (- y-size 2))))
328 (x1 (1+ (random (- x-size 2))) ; start position of horiz corridor
329 x1*)
330 (x1* (1+ (random (- x-size 2)))
331 (random-elt
332 (loop for x from 1 to (- x-size 2) ; any blank space
333 if (not (aref map x y)) collect x))) ; in line
334 (x2 (if x1 (bound-random x1 corridor-x-min
335 corridor-x-avg corridor-x-max))
336 (if x1 (bound-random x1 corridor-x-min
337 corridor-x-avg corridor-x-max)))
338 (x 1 x*) ; position of vertical corridor
339 (x* (- x-size 2) (1+ (random (- x-size 2))))
340 (y1 (1+ (random (- y-size 2)))
341 y1*)
342 (y1* (1+ (random (- y-size 2)))
343 (random-elt
344 (loop for y from 1 to (- y-size 2)
345 if (not (aref map x y)) collect y)))
346 (y2 (if y1 (bound-random y1 corridor-y-min
347 corridor-y-avg corridor-y-max))
348 (if y1 (bound-random y1 corridor-y-min
349 corridor-y-avg corridor-y-max)))
350 (real-dens (density map x-size y-size)))
351 ((or (>= real-dens density)
352 (> i (* density x-size y-size))) ; quits after trying TOO MUCH
353 (values (translate map x-size y-size) real-dens))
354 (if x1
355 (setf map (horiz-corridor map y x1
356 (bound x2 1 (- x-size 2)))))
357 (if y1
358 (setf map (vert-corridor map x y1
359 (bound y2 1 (- x-size 2))))))))

Properties

Name Value
svn:executable *

  ViewVC Help
Powered by ViewVC 1.1.5