1 /**
2 * \file gen-util.c
3 * \brief Dungeon generation utilities
4 *
5 * Copyright (c) 1997 Ben Harrison, James E. Wilson, Robert A. Koeneke
6 * Copyright (c) 2013 Erik Osheim, Nick McConnell
7 *
8 * This work is free software; you can redistribute it and/or modify it
9 * under the terms of either:
10 *
11 * a) the GNU General Public License as published by the Free Software
12 * Foundation, version 2, or
13 *
14 * b) the "Angband licence":
15 * This software may be copied and distributed for educational, research,
16 * and not for profit purposes provided that this copyright and statement
17 * are included in all such copies. Other copyrights may also apply.
18 *
19 * This file contains various utility functions for dungeon generation - mostly
20 * for finding appropriate grids for some purposes, or placing things.
21 */
22
23 #include "angband.h"
24 #include "cave.h"
25 #include "datafile.h"
26 #include "math.h"
27 #include "game-event.h"
28 #include "generate.h"
29 #include "init.h"
30 #include "mon-make.h"
31 #include "mon-spell.h"
32 #include "obj-make.h"
33 #include "obj-pile.h"
34 #include "obj-tval.h"
35 #include "obj-util.h"
36 #include "player-util.h"
37 #include "trap.h"
38 #include "z-queue.h"
39 #include "z-type.h"
40
41 /**
42 * Accept values for y and x (considered as the endpoints of lines) between
43 * 0 and 40, and return an angle in degrees (divided by two). -LM-
44 *
45 * This table's input and output need some processing:
46 *
47 * Because this table gives degrees for a whole circle, up to radius 20, its
48 * origin is at (x,y) = (20, 20). Therefore, the input code needs to find
49 * the origin grid (where the lines being compared come from), and then map
50 * it to table grid 20,20. Do not, however, actually try to compare the
51 * angle of a line that begins and ends at the origin with any other line -
52 * it is impossible mathematically, and the table will return the value "255".
53 *
54 * The output of this table also needs to be massaged, in order to avoid the
55 * discontinuity at 0/180 degrees. This can be done by:
56 * rotate = 90 - first value
57 * this rotates the first input to the 90 degree line)
58 * tmp = ABS(second value + rotate) % 180
59 * diff = ABS(90 - tmp) = the angular difference (divided by two) between
60 * the first and second values.
61 *
62 * Note that grids diagonal to the origin have unique angles.
63 */
64 byte get_angle_to_grid[41][41] =
65 {
66 { 68, 67, 66, 65, 64, 63, 62, 62, 60, 59, 58, 57, 56, 55, 53, 52, 51, 49, 48, 46, 45, 44, 42, 41, 39, 38, 37, 35, 34, 33, 32, 31, 30, 28, 28, 27, 26, 25, 24, 24, 23 },
67 { 69, 68, 67, 66, 65, 64, 63, 62, 61, 60, 59, 58, 56, 55, 54, 52, 51, 49, 48, 47, 45, 43, 42, 41, 39, 38, 36, 35, 34, 32, 31, 30, 29, 28, 27, 26, 25, 24, 24, 23, 22 },
68 { 69, 69, 68, 67, 66, 65, 64, 63, 62, 61, 60, 58, 57, 56, 54, 53, 51, 50, 48, 47, 45, 43, 42, 40, 39, 37, 36, 34, 33, 32, 30, 29, 28, 27, 26, 25, 24, 24, 23, 22, 21 },
69 { 70, 69, 69, 68, 67, 66, 65, 64, 63, 61, 60, 59, 58, 56, 55, 53, 52, 50, 48, 47, 45, 43, 42, 40, 38, 37, 35, 34, 32, 31, 30, 29, 27, 26, 25, 24, 24, 23, 22, 21, 20 },
70 { 71, 70, 69, 69, 68, 67, 66, 65, 63, 62, 61, 60, 58, 57, 55, 54, 52, 50, 49, 47, 45, 43, 41, 40, 38, 36, 35, 33, 32, 30, 29, 28, 27, 25, 24, 24, 23, 22, 21, 20, 19 },
71 { 72, 71, 70, 69, 69, 68, 67, 65, 64, 63, 62, 60, 59, 58, 56, 54, 52, 51, 49, 47, 45, 43, 41, 39, 38, 36, 34, 32, 31, 30, 28, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18 },
72 { 73, 72, 71, 70, 69, 69, 68, 66, 65, 64, 63, 61, 60, 58, 57, 55, 53, 51, 49, 47, 45, 43, 41, 39, 37, 35, 33, 32, 30, 29, 27, 26, 25, 24, 23, 22, 21, 20, 19, 18, 17 },
73 { 73, 73, 72, 71, 70, 70, 69, 68, 66, 65, 64, 62, 61, 59, 57, 56, 54, 51, 49, 47, 45, 43, 41, 39, 36, 34, 33, 31, 29, 28, 26, 25, 24, 23, 21, 20, 20, 19, 18, 17, 17 },
74 { 75, 74, 73, 72, 72, 71, 70, 69, 68, 66, 65, 63, 62, 60, 58, 56, 54, 52, 50, 47, 45, 43, 40, 38, 36, 34, 32, 30, 28, 27, 25, 24, 23, 21, 20, 19, 18, 18, 17, 16, 15 },
75 { 76, 75, 74, 74, 73, 72, 71, 70, 69, 68, 66, 65, 63, 61, 59, 57, 55, 53, 50, 48, 45, 42, 40, 37, 35, 33, 31, 29, 27, 25, 24, 23, 21, 20, 19, 18, 17, 16, 16, 15, 14 },
76 { 77, 76, 75, 75, 74, 73, 72, 71, 70, 69, 68, 66, 64, 62, 60, 58, 56, 53, 51, 48, 45, 42, 39, 37, 34, 32, 30, 28, 26, 24, 23, 21, 20, 19, 18, 17, 16, 15, 15, 14, 13 },
77 { 78, 77, 77, 76, 75, 75, 74, 73, 72, 70, 69, 68, 66, 64, 62, 60, 57, 54, 51, 48, 45, 42, 39, 36, 33, 30, 28, 26, 24, 23, 21, 20, 18, 17, 16, 15, 15, 14, 13, 13, 12 },
78 { 79, 79, 78, 77, 77, 76, 75, 74, 73, 72, 71, 69, 68, 66, 63, 61, 58, 55, 52, 49, 45, 41, 38, 35, 32, 29, 27, 24, 23, 21, 19, 18, 17, 16, 15, 14, 13, 13, 12, 11, 11 },
79 { 80, 80, 79, 79, 78, 77, 77, 76, 75, 74, 73, 71, 69, 68, 65, 63, 60, 57, 53, 49, 45, 41, 37, 33, 30, 27, 25, 23, 21, 19, 17, 16, 15, 14, 13, 13, 12, 11, 11, 10, 10 },
80 { 82, 81, 81, 80, 80, 79, 78, 78, 77, 76, 75, 73, 72, 70, 68, 65, 62, 58, 54, 50, 45, 40, 36, 32, 28, 25, 23, 20, 18, 17, 15, 14, 13, 12, 12, 11, 10, 10, 9, 9, 8 },
81 { 83, 83, 82, 82, 81, 81, 80, 79, 79, 78, 77, 75, 74, 72, 70, 68, 64, 60, 56, 51, 45, 39, 34, 30, 26, 23, 20, 18, 16, 15, 13, 12, 11, 11, 10, 9, 9, 8, 8, 7, 7 },
82 { 84, 84, 84, 83, 83, 83, 82, 81, 81, 80, 79, 78, 77, 75, 73, 71, 68, 63, 58, 52, 45, 38, 32, 27, 23, 19, 17, 15, 13, 12, 11, 10, 9, 9, 8, 7, 7, 7, 6, 6, 6 },
83 { 86, 86, 85, 85, 85, 84, 84, 84, 83, 82, 82, 81, 80, 78, 77, 75, 72, 68, 62, 54, 45, 36, 28, 23, 18, 15, 13, 12, 10, 9, 8, 8, 7, 6, 6, 6, 5, 5, 5, 4, 4 },
84 { 87, 87, 87, 87, 86, 86, 86, 86, 85, 85, 84, 84, 83, 82, 81, 79, 77, 73, 68, 58, 45, 32, 23, 17, 13, 11, 9, 8, 7, 6, 6, 5, 5, 4, 4, 4, 4, 3, 3, 3, 3 },
85 { 89, 88, 88, 88, 88, 88, 88, 88, 88, 87, 87, 87, 86, 86, 85, 84, 83, 81, 77, 68, 45, 23, 13, 9, 7, 6, 5, 4, 4, 3, 3, 3, 2, 2, 2, 2, 2, 2, 2, 2, 1 },
86 { 90, 90, 90, 90, 90, 90, 90, 90, 90, 90, 90, 90, 90, 90, 90, 90, 90, 90, 90, 90, 255, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
87 { 91, 92, 92, 92, 92, 92, 92, 92, 92, 93, 93, 93, 94, 94, 95, 96, 97, 99, 103, 113, 135, 158, 167, 171, 173, 174, 175, 176, 176, 177, 177, 177, 178, 178, 178, 178, 178, 178, 178, 178, 179 },
88 { 93, 93, 93, 93, 94, 94, 94, 94, 95, 95, 96, 96, 97, 98, 99, 101, 103, 107, 113, 122, 135, 148, 158, 163, 167, 169, 171, 172, 173, 174, 174, 175, 175, 176, 176, 176, 176, 177, 177, 177, 177 },
89 { 94, 94, 95, 95, 95, 96, 96, 96, 97, 98, 98, 99, 100, 102, 103, 105, 108, 113, 118, 126, 135, 144, 152, 158, 162, 165, 167, 168, 170, 171, 172, 172, 173, 174, 174, 174, 175, 175, 175, 176, 176 },
90 { 96, 96, 96, 97, 97, 97, 98, 99, 99, 100, 101, 102, 103, 105, 107, 109, 113, 117, 122, 128, 135, 142, 148, 153, 158, 161, 163, 165, 167, 168, 169, 170, 171, 171, 172, 173, 173, 173, 174, 174, 174 },
91 { 97, 97, 98, 98, 99, 99, 100, 101, 101, 102, 103, 105, 106, 108, 110, 113, 116, 120, 124, 129, 135, 141, 146, 150, 154, 158, 160, 162, 164, 165, 167, 168, 169, 169, 170, 171, 171, 172, 172, 173, 173 },
92 { 98, 99, 99, 100, 100, 101, 102, 102, 103, 104, 105, 107, 108, 110, 113, 115, 118, 122, 126, 130, 135, 140, 144, 148, 152, 155, 158, 160, 162, 163, 165, 166, 167, 168, 168, 169, 170, 170, 171, 171, 172 },
93 { 100, 100, 101, 101, 102, 103, 103, 104, 105, 106, 107, 109, 111, 113, 115, 117, 120, 123, 127, 131, 135, 139, 143, 147, 150, 153, 155, 158, 159, 161, 163, 164, 165, 166, 167, 167, 168, 169, 169, 170, 170 },
94 { 101, 101, 102, 103, 103, 104, 105, 106, 107, 108, 109, 111, 113, 114, 117, 119, 122, 125, 128, 131, 135, 139, 142, 145, 148, 151, 153, 156, 158, 159, 161, 162, 163, 164, 165, 166, 167, 167, 168, 169, 169 },
95 { 102, 103, 103, 104, 105, 105, 106, 107, 108, 110, 111, 113, 114, 116, 118, 120, 123, 126, 129, 132, 135, 138, 141, 144, 147, 150, 152, 154, 156, 158, 159, 160, 162, 163, 164, 165, 165, 166, 167, 167, 168 },
96 { 103, 104, 105, 105, 106, 107, 108, 109, 110, 111, 113, 114, 116, 118, 120, 122, 124, 127, 129, 132, 135, 138, 141, 143, 146, 148, 150, 152, 154, 156, 158, 159, 160, 161, 162, 163, 164, 165, 165, 166, 167 },
97 { 104, 105, 106, 106, 107, 108, 109, 110, 111, 113, 114, 115, 117, 119, 121, 123, 125, 127, 130, 132, 135, 138, 140, 143, 145, 147, 149, 151, 153, 155, 156, 158, 159, 160, 161, 162, 163, 164, 164, 165, 166 },
98 { 105, 106, 107, 108, 108, 109, 110, 111, 113, 114, 115, 117, 118, 120, 122, 124, 126, 128, 130, 133, 135, 137, 140, 142, 144, 146, 148, 150, 152, 153, 155, 156, 158, 159, 160, 161, 162, 162, 163, 164, 165 },
99 { 107, 107, 108, 109, 110, 110, 111, 113, 114, 115, 116, 118, 119, 121, 123, 124, 126, 129, 131, 133, 135, 137, 139, 141, 144, 146, 147, 149, 151, 152, 154, 155, 156, 158, 159, 160, 160, 161, 162, 163, 163 },
100 { 107, 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 119, 120, 122, 123, 125, 127, 129, 131, 133, 135, 137, 139, 141, 143, 145, 147, 148, 150, 151, 153, 154, 155, 156, 158, 159, 159, 160, 161, 162, 163 },
101 { 108, 109, 110, 111, 112, 113, 114, 115, 116, 117, 118, 120, 121, 122, 124, 126, 128, 129, 131, 133, 135, 137, 139, 141, 142, 144, 146, 148, 149, 150, 152, 153, 154, 155, 157, 158, 159, 159, 160, 161, 162 },
102 { 109, 110, 111, 112, 113, 114, 114, 115, 117, 118, 119, 120, 122, 123, 125, 126, 128, 130, 131, 133, 135, 137, 139, 140, 142, 144, 145, 147, 148, 150, 151, 152, 153, 155, 156, 157, 158, 159, 159, 160, 161 },
103 { 110, 111, 112, 113, 114, 114, 115, 116, 117, 119, 120, 121, 122, 124, 125, 127, 128, 130, 132, 133, 135, 137, 138, 140, 142, 143, 145, 146, 148, 149, 150, 151, 153, 154, 155, 156, 157, 158, 159, 159, 160 },
104 { 111, 112, 113, 114, 114, 115, 116, 117, 118, 119, 120, 122, 123, 124, 126, 127, 129, 130, 132, 133, 135, 137, 138, 140, 141, 143, 144, 146, 147, 148, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159, 159 },
105 { 112, 113, 114, 114, 115, 116, 117, 118, 119, 120, 121, 122, 124, 125, 126, 128, 129, 131, 132, 133, 135, 137, 138, 139, 141, 142, 144, 145, 146, 148, 149, 150, 151, 152, 153, 154, 155, 156, 157, 158, 159 },
106 { 113, 114, 114, 115, 116, 117, 118, 118, 120, 121, 122, 123, 124, 125, 127, 128, 129, 131, 132, 134, 135, 136, 138, 139, 141, 142, 143, 145, 146, 147, 148, 149, 150, 152, 152, 153, 154, 155, 156, 157, 158 }
107 };
108
109
110 /**
111 * Used to convert grid into an array index (i) in a chunk of width w.
112 * \param grid location
113 * \param w area width
114 * \return index
115 */
grid_to_i(struct loc grid,int w)116 int grid_to_i(struct loc grid, int w)
117 {
118 return grid.y * w + grid.x;
119 }
120
121 /**
122 * Used to convert an array index (i) into grid in a chunk of width w.
123 * \param i grid index
124 * \param w area width
125 * \param grid location
126 */
i_to_grid(int i,int w,struct loc * grid)127 void i_to_grid(int i, int w, struct loc *grid)
128 {
129 grid->y = i / w;
130 grid->x = i % w;
131 }
132
133 /**
134 * Shuffle an array using Knuth's shuffle.
135 * \param arr array
136 * \param n number of shuffle moves
137 */
shuffle(int * arr,int n)138 void shuffle(int *arr, int n)
139 {
140 int i, j, k;
141 for (i = 0; i < n; i++) {
142 j = randint0(n - i) + i;
143 k = arr[j];
144 arr[j] = arr[i];
145 arr[i] = k;
146 }
147 }
148
149
150 /**
151 * Locate a square in a rectangle which satisfies the given predicate.
152 *
153 * \param c current chunk
154 * \param grid found grid
155 * \param top_left top left grid of rectangle
156 * \param bottom_right bottom right grid of rectangle
157 * \param pred square_predicate specifying what we're looking for
158 * \return success
159 */
cave_find_in_range(struct chunk * c,struct loc * grid,struct loc top_left,struct loc bottom_right,square_predicate pred)160 static bool cave_find_in_range(struct chunk *c, struct loc *grid,
161 struct loc top_left, struct loc bottom_right,
162 square_predicate pred)
163 {
164 struct loc diff = loc_diff(bottom_right, top_left);
165 int i, n = diff.y * diff.x;
166 bool found = false;
167
168 /* Allocate the squares, and randomize their order */
169 int *squares = mem_alloc(n * sizeof(int));
170 for (i = 0; i < n; i++) squares[i] = i;
171
172 /* Test each square in (random) order for openness */
173 for (i = 0; i < n && !found; i++) {
174 int j = randint0(n - i) + i;
175 int k = squares[j];
176 squares[j] = squares[i];
177 squares[i] = k;
178
179 grid->y = (k / diff.x) + top_left.y;
180 grid->x = (k % diff.x) + top_left.x;
181 if (pred(c, *grid)) found = true;
182 }
183
184 mem_free(squares);
185
186 /* Return whether we found an empty square or not. */
187 return found;
188 }
189
190
191 /**
192 * Locate a square in the dungeon which satisfies the given predicate.
193 * \param c current chunk
194 * \param grid found grid
195 * \param pred square_predicate specifying what we're looking for
196 * \return success
197 */
cave_find(struct chunk * c,struct loc * grid,square_predicate pred)198 bool cave_find(struct chunk *c, struct loc *grid, square_predicate pred)
199 {
200 struct loc top_left = loc(0, 0);
201 struct loc bottom_right = loc(c->width - 1, c->height - 1);
202 return cave_find_in_range(c, grid, top_left, bottom_right, pred);
203 }
204
205
206 /**
207 * Locate an empty square for 0 <= y < ymax, 0 <= x < xmax.
208 * \param c current chunk
209 * \param grid found grid
210 * \return success
211 */
find_empty(struct chunk * c,struct loc * grid)212 bool find_empty(struct chunk *c, struct loc *grid)
213 {
214 return cave_find(c, grid, square_isempty);
215 }
216
217
218 /**
219 * Locate an empty square in a given rectangle.
220 * \param c current chunk
221 * \param grid found grid
222 * \param top_left top left grid of rectangle
223 * \param bottom_right bottom right grid of rectangle
224 * \return success
225 */
find_empty_range(struct chunk * c,struct loc * grid,struct loc top_left,struct loc bottom_right)226 bool find_empty_range(struct chunk *c, struct loc *grid, struct loc top_left,
227 struct loc bottom_right)
228 {
229 return cave_find_in_range(c, grid, top_left, bottom_right, square_isempty);
230 }
231
232
233 /**
234 * Locate a grid within +/- yd, xd of a centre.
235 * \param c current chunk
236 * \param grid found grid
237 * \param centre starting grid
238 * \param yd y-range
239 * \param xd x-range
240 * \return success
241 */
find_nearby_grid(struct chunk * c,struct loc * grid,struct loc centre,int yd,int xd)242 bool find_nearby_grid(struct chunk *c, struct loc *grid, struct loc centre,
243 int yd, int xd)
244 {
245 struct loc top_left = loc(centre.x - xd, centre.y - yd);
246 struct loc bottom_right = loc(centre.x + xd + 1, centre.y + yd + 1);
247 return cave_find_in_range(c, grid, top_left, bottom_right,
248 square_in_bounds_fully);
249 }
250
251
252 /**
253 * Given two points, pick a valid cardinal direction from one to the other.
254 * \param offset found offset direction from grid 1 to grid2
255 * \param grid1 starting grid
256 * \param grid2 target grid
257 */
correct_dir(struct loc * offset,struct loc grid1,struct loc grid2)258 void correct_dir(struct loc *offset, struct loc grid1, struct loc grid2)
259 {
260 /* Extract horizontal and vertical directions */
261 offset->x = CMP(grid2.x, grid1.x);
262 offset->y = CMP(grid2.y, grid1.y);
263
264 /* If we only have one direction to go, then we're done */
265 if (!offset->x || !offset->y) return;
266
267 /* If we need to go diagonally, then choose a random direction */
268 if (randint0(100) < 50)
269 offset->y = 0;
270 else
271 offset->x = 0;
272 }
273
274
275 /**
276 * Pick a random cardinal direction.
277 * \param offset direction offset
278 */
rand_dir(struct loc * offset)279 void rand_dir(struct loc *offset)
280 {
281 /* Pick a random direction and extract the dy/dx components */
282 int i = randint0(4);
283 *offset = ddgrid_ddd[i];
284 }
285
286
287 /**
288 * Determine whether the given coordinate is a valid starting location.
289 * \param c current chunk
290 * \param y co-ordinates
291 * \param x co-ordinates
292 * \return success
293 */
find_start(struct chunk * c,struct loc * grid)294 static bool find_start(struct chunk *c, struct loc *grid)
295 {
296 /* Find the best possible place */
297 if (cave_find_in_range(c, grid, loc(1, 1), loc(c->width - 2, c->height - 2),
298 square_suits_stairs_well)) {
299 return true;
300 } else if (cave_find_in_range(c, grid, loc(1, 1),
301 loc(c->width - 2, c->height - 2),
302 square_suits_stairs_ok)) {
303 return true;
304 } else {
305 int walls = 6;
306
307 /* Gradually reduce number of walls if having trouble */
308 while (walls >= 0) {
309 int j;
310
311 /* Try hard to find a square with the given number of walls */
312 for (j = 0; j < 10000; j++) {
313 int total_walls = 0;
314
315 if (!cave_find_in_range(c, grid, loc(1, 1),
316 loc(c->width - 2, c->height - 2),
317 square_isempty)) continue;
318 if (square_isvault(c, *grid) || square_isno_stairs(c, *grid)) {
319 continue;
320 }
321 total_walls = square_num_walls_adjacent(c, *grid) +
322 square_num_walls_diagonal(c, *grid);
323
324 if (total_walls == walls) {
325 return true;
326 }
327 }
328
329 walls--;
330 }
331 }
332 return false;
333 }
334
335
336 /**
337 * Place the player at a random starting location.
338 * \param c current chunk
339 * \param p the player
340 */
new_player_spot(struct chunk * c,struct player * p)341 void new_player_spot(struct chunk *c, struct player *p)
342 {
343 struct loc grid;
344
345 /* Try to find a good place to put the player */
346 if (OPT(p, birth_levels_persist) &&
347 square_in_bounds_fully(c, p->grid) &&
348 square_isstairs(c, p->grid)) {
349 grid = p->grid;
350 } else if (!find_start(c, &grid)) {
351 dump_level_simple(NULL, "Player Placement Failure", c);
352 quit("Failed to place player!");
353 }
354
355 /* Create stairs the player came down if allowed and necessary */
356 if (!OPT(p, birth_connect_stairs))
357 ;
358 else if (p->upkeep->create_down_stair)
359 square_set_feat(c, grid, FEAT_MORE);
360 else if (p->upkeep->create_up_stair)
361 square_set_feat(c, grid, FEAT_LESS);
362
363 player_place(c, p, grid);
364 }
365
366
367 /**
368 * Place rubble at a given location.
369 * \param c current chunk
370 * \param grid location
371 */
place_rubble(struct chunk * c,struct loc grid)372 static void place_rubble(struct chunk *c, struct loc grid)
373 {
374 square_set_feat(c, grid, one_in_(2) ? FEAT_RUBBLE : FEAT_PASS_RUBBLE);
375 }
376
377
378 /**
379 * Place stairs (of the requested type 'feat' if allowed) at a given location.
380 * \param c current chunk
381 * \param grid location
382 * \param feat stair terrain type
383 *
384 * All stairs from town go down. All stairs on an unfinished quest level go up.
385 */
place_stairs(struct chunk * c,struct loc grid,int feat)386 static void place_stairs(struct chunk *c, struct loc grid, int feat)
387 {
388 if (!c->depth)
389 square_set_feat(c, grid, FEAT_MORE);
390 else if (is_quest(c->depth) || c->depth >= z_info->max_depth - 1)
391 square_set_feat(c, grid, FEAT_LESS);
392 else
393 square_set_feat(c, grid, feat);
394 }
395
396
397 /**
398 * Place random stairs at a given location.
399 * \param c current chunk
400 * \param grid location
401 */
place_random_stairs(struct chunk * c,struct loc grid)402 void place_random_stairs(struct chunk *c, struct loc grid)
403 {
404 int feat = randint0(100) < 50 ? FEAT_LESS : FEAT_MORE;
405 if (square_canputitem(c, grid))
406 place_stairs(c, grid, feat);
407 }
408
409
410 /**
411 * Place a random object at a given location.
412 * \param c current chunk
413 * \param grid location
414 * \param level generation depth
415 * \param good is it a good object?
416 * \param great is it a great object?
417 * \param origin item origin
418 * \param tval specified tval, if any
419 */
place_object(struct chunk * c,struct loc grid,int level,bool good,bool great,byte origin,int tval)420 void place_object(struct chunk *c, struct loc grid, int level, bool good,
421 bool great, byte origin, int tval)
422 {
423 s32b rating = 0;
424 struct object *new_obj;
425 bool dummy = true;
426
427 if (!square_in_bounds(c, grid)) return;
428 if (!square_canputitem(c, grid)) return;
429
430 /* Make an appropriate object */
431 new_obj = make_object(c, level, good, great, false, &rating, tval);
432 if (!new_obj) return;
433 new_obj->origin = origin;
434 new_obj->origin_depth = c->depth;
435
436 /* Give it to the floor */
437 if (!floor_carry(c, grid, new_obj, &dummy)) {
438 if (new_obj->artifact) {
439 new_obj->artifact->created = false;
440 }
441 object_delete(&new_obj);
442 return;
443 } else {
444 list_object(c, new_obj);
445 if (new_obj->artifact) {
446 c->good_item = true;
447 }
448 /* Avoid overflows */
449 if (rating > 2500000) {
450 rating = 2500000;
451 }
452 c->obj_rating += (rating / 100) * (rating / 100);
453 }
454 }
455
456
457 /**
458 * Place a random amount of gold at a given location.
459 * \param c current chunk
460 * \param grid location
461 * \param level generation depth
462 * \param origin item origin
463 */
place_gold(struct chunk * c,struct loc grid,int level,byte origin)464 void place_gold(struct chunk *c, struct loc grid, int level, byte origin)
465 {
466 struct object *money = NULL;
467 bool dummy = true;
468
469 if (!square_in_bounds(c, grid)) return;
470 if (!square_canputitem(c, grid)) return;
471
472 money = make_gold(level, "any");
473 money->origin = origin;
474 money->origin_depth = level;
475
476 if (!floor_carry(c, grid, money, &dummy)) {
477 object_delete(&money);
478 } else {
479 list_object(c, money);
480 }
481 }
482
483
484 /**
485 * Place a secret door at a given location.
486 * \param c current chunk
487 * \param grid location
488 */
place_secret_door(struct chunk * c,struct loc grid)489 void place_secret_door(struct chunk *c, struct loc grid)
490 {
491 square_set_feat(c, grid, FEAT_SECRET);
492 }
493
494
495 /**
496 * Place a closed door at a given location.
497 * \param c current chunk
498 * \param grid location
499 */
place_closed_door(struct chunk * c,struct loc grid)500 void place_closed_door(struct chunk *c, struct loc grid)
501 {
502 square_set_feat(c, grid, FEAT_CLOSED);
503 if (one_in_(4))
504 square_set_door_lock(c, grid, randint1(7));
505 }
506
507
508 /**
509 * Place a random door at a given location.
510 * \param c current chunk
511 * \param grid location
512 *
513 * The door generated could be closed, open, broken, or secret.
514 */
place_random_door(struct chunk * c,struct loc grid)515 void place_random_door(struct chunk *c, struct loc grid)
516 {
517 int tmp = randint0(100);
518
519 if (tmp < 30)
520 square_set_feat(c, grid, FEAT_OPEN);
521 else if (tmp < 40)
522 square_set_feat(c, grid, FEAT_BROKEN);
523 else
524 place_closed_door(c, grid);
525 }
526
527 /**
528 * Place some staircases near walls.
529 * \param c the current chunk
530 * \param feat the stair terrain type
531 * \param num number of staircases to place
532 * \param walls number of walls to surround the stairs (negotiable)
533 */
alloc_stairs(struct chunk * c,int feat,int num)534 void alloc_stairs(struct chunk *c, int feat, int num)
535 {
536 int i;
537
538 /* Place "num" stairs */
539 for (i = 0; i < num; i++) {
540 struct loc grid;
541 bool done = false;
542 int walls = 3;
543
544 /* Place some stairs */
545 for (done = false; !done; ) {
546 int j;
547
548 /* Try several times, then decrease "walls" */
549 for (j = 0; !done && j <= 100; j++) {
550 if (!find_empty(c, &grid)) continue;
551
552 if (square_num_walls_adjacent(c, grid) < walls) continue;
553
554 place_stairs(c, grid, feat);
555 assert(square_isstairs(c, grid));
556 done = true;
557 }
558
559 /* Require fewer walls */
560 if (walls) walls--;
561 }
562 }
563 }
564
565
566 /**
567 * Allocates 'num' random entities in the dungeon.
568 * \param c the current chunk
569 * \param set where the entity is placed (corridor, room or either)
570 * \param typ what is placed (rubble, trap, gold, item)
571 * \param num number to place
572 * \param depth generation depth
573 * \param origin item origin (if appropriate)
574 *
575 * See alloc_object() for more information.
576 */
alloc_objects(struct chunk * c,int set,int typ,int num,int depth,byte origin)577 void alloc_objects(struct chunk *c, int set, int typ, int num, int depth,
578 byte origin)
579 {
580 int k, l = 0;
581 for (k = 0; k < num; k++) {
582 bool ok = alloc_object(c, set, typ, depth, origin);
583 if (!ok) l++;
584 }
585 }
586
587
588 /**
589 * Allocates a single random object in the dungeon.
590 * \param c the current chunk
591 * \param set where the entity is placed (corridor, room or either)
592 * \param typ what is placed (rubble, trap, gold, item)
593 * \param depth generation depth
594 * \param origin item origin (if appropriate)
595 *
596 * 'set' controls where the object is placed (corridor, room, either).
597 * 'typ' conrols the kind of object (rubble, trap, gold, item).
598 */
alloc_object(struct chunk * c,int set,int typ,int depth,byte origin)599 bool alloc_object(struct chunk *c, int set, int typ, int depth, byte origin)
600 {
601 int tries = 0;
602 struct loc grid;
603
604 /* Pick a "legal" spot */
605 while (tries < 2000) {
606 tries++;
607
608 if (!find_empty(c, &grid)) continue;
609
610 /* If we are ok with a corridor and we're in one, we're done */
611 if (set & SET_CORR && !square_isroom(c, grid)) break;
612
613 /* If we are ok with a room and we're in one, we're done */
614 if (set & SET_ROOM && square_isroom(c, grid)) break;
615 }
616
617 if (tries == 2000) return false;
618
619 /* Place something */
620 switch (typ) {
621 case TYP_RUBBLE: place_rubble(c, grid); break;
622 case TYP_TRAP: place_trap(c, grid, -1, depth); break;
623 case TYP_GOLD: place_gold(c, grid, depth, origin); break;
624 case TYP_OBJECT: place_object(c, grid, depth, false, false, origin, 0);
625 break;
626 case TYP_GOOD: place_object(c, grid, depth, true, false, origin, 0); break;
627 case TYP_GREAT: place_object(c, grid, depth, true, true, origin, 0); break;
628 }
629 return true;
630 }
631
632 /**
633 * Create up to 'num' objects near the given coordinates in a vault.
634 * \param c the current chunk
635 * \param grid location
636 * \param depth generation depth
637 * \param num number of objects
638 */
vault_objects(struct chunk * c,struct loc grid,int depth,int num)639 void vault_objects(struct chunk *c, struct loc grid, int depth, int num)
640 {
641 int i;
642
643 /* Attempt to place 'num' objects */
644 for (; num > 0; --num) {
645 /* Try up to 11 spots looking for empty space */
646 for (i = 0; i < 11; ++i) {
647 struct loc near;
648
649 /* Pick a random location */
650 if (!find_nearby_grid(c, &near, grid, 2, 3)) assert(0);
651
652 /* Require "clean" floor space */
653 if (!square_canputitem(c, near)) continue;
654
655 /* Place an item or gold */
656 if (randint0(100) < 75)
657 place_object(c, near, depth, false, false, ORIGIN_SPECIAL, 0);
658 else
659 place_gold(c, near, depth, ORIGIN_VAULT);
660
661 /* Placement accomplished */
662 break;
663 }
664 }
665 }
666
667 /**
668 * Place a trap near (x, y), with a given displacement.
669 * \param c the current chunk
670 * \param grid location to place the trap near
671 * \param yd how far afield to look for a place
672 * \param xd how far afield to look for a place
673 */
vault_trap_aux(struct chunk * c,struct loc grid,int yd,int xd)674 static void vault_trap_aux(struct chunk *c, struct loc grid, int yd, int xd)
675 {
676 int tries;
677
678 /* Find a nearby empty grid and place a trap */
679 for (tries = 0; tries <= 5; tries++) {
680 struct loc near;
681 if (!find_nearby_grid(c, &near, grid, yd, xd)) assert(0);
682 if (!square_isempty(c, near)) continue;
683
684 square_add_trap(c, near);
685 break;
686 }
687 }
688
689
690 /**
691 * Place 'num' traps near a location, with a given displacement.
692 * \param c the current chunk
693 * \param grid location to place the trap near
694 * \param yd how far afield to look for a place
695 * \param xd how far afield to look for a place
696 * \param num number of traps to place
697 */
vault_traps(struct chunk * c,struct loc grid,int yd,int xd,int num)698 void vault_traps(struct chunk *c, struct loc grid, int yd, int xd, int num)
699 {
700 int i;
701 for (i = 0; i < num; i++)
702 vault_trap_aux(c, grid, yd, xd);
703 }
704
705
706 /**
707 * Place 'num' sleeping monsters near the location.
708 * \param c the current chunk
709 * \param grid location to place the monsters near
710 * \param depth generation depth
711 * \param num number of monsters to place
712 */
vault_monsters(struct chunk * c,struct loc grid,int depth,int num)713 void vault_monsters(struct chunk *c, struct loc grid, int depth, int num)
714 {
715 int k, i;
716
717 /* If the starting location is illegal, don't even start */
718 if (!square_in_bounds(c, grid)) return;
719
720 /* Try to summon "num" monsters "near" the given location */
721 for (k = 0; k < num; k++) {
722 /* Try nine locations */
723 for (i = 0; i < 9; i++) {
724 struct loc near;
725
726 /* Pick a nearby location */
727 scatter(c, &near, grid, 1, true);
728
729 /* Require "empty" floor grids */
730 if (!square_isempty(c, near)) continue;
731
732 /* Place the monster (allow groups) */
733 pick_and_place_monster(c, near, depth, true, true,
734 ORIGIN_DROP_SPECIAL);
735
736 break;
737 }
738 }
739 }
740
741
742 /**
743 * Dump the given level for post-mortem analysis; handle all I/O.
744 * \param basefilename Is the base name (no directory or extension) for the
745 * file to use. If NULL, "dumpedlevel" will be used.
746 * \param title Is the label to use within the file. If NULL, "Dumped Level"
747 * will be used.
748 * \param c Is the chunk to dump.
749 */
dump_level_simple(const char * basefilename,const char * title,struct chunk * c)750 void dump_level_simple(const char *basefilename, const char *title,
751 struct chunk *c)
752 {
753 char path[1024];
754 ang_file *fo;
755
756 path_build(path, sizeof(path), ANGBAND_DIR_USER, (basefilename) ?
757 format("%s.html", basefilename) : "dumpedlevel.html");
758 fo = file_open(path, MODE_WRITE, FTYPE_TEXT);
759 if (fo) {
760 dump_level(fo, (title) ? title : "Dumped Level", c, NULL);
761 if (file_close(fo)) {
762 msg(format("Level dumped to %s.html",
763 (basefilename) ? basefilename : "dumpedlevel"));
764 }
765 }
766 }
767
768
769 /**
770 * Dump the given level to a file for post-mortem analysis.
771 * \param fo Is the file handle to use. Must be capable of sequential writes
772 * in text format. The level is dumped starting at the current offset in the
773 * file.
774 * \param title Is the title to use for the contents.
775 * \param c Is the chunk to dump.
776 * \param dist If not NULL, must act like a two dimensional C array with the
777 * first dimension being at least c->height elements and the second being at
778 * least c->width elements. For a location (x,y) in the level, if dist[y][x]
779 * is negative, the contents will be rendered differently.
780 *
781 * The current output format is HTML since a typical browser will happily
782 * display the content in a scrollable area without wrapping lines. This
783 * function is a convenience to replace a set of calls to dump_level_header(),
784 * dump_level_body(), and dump_level_footer().
785 */
dump_level(ang_file * fo,const char * title,struct chunk * c,int ** dist)786 void dump_level(ang_file *fo, const char *title, struct chunk *c, int **dist)
787 {
788 dump_level_header(fo, title);
789 dump_level_body(fo, title, c, dist);
790 dump_level_footer(fo);
791 }
792
793
794 /**
795 * Helper function to write a string while escaping any special characters.
796 * \param fo Is the file handle to use.
797 * \param s Is the string to write.
798 */
dump_level_escaped_string(ang_file * fo,const char * s)799 static void dump_level_escaped_string(ang_file *fo, const char *s)
800 {
801 while (*s) {
802 switch (*s) {
803 case '&':
804 file_put(fo, "&");
805 break;
806
807 case '<':
808 file_put(fo, "<");
809 break;
810
811 case '>':
812 file_put(fo, ">");
813 break;
814
815 case '\"':
816 file_put(fo, """);
817 break;
818
819 default:
820 file_putf(fo, "%c", *s);
821 break;
822 }
823 ++s;
824 }
825 }
826
827
828 /**
829 * Write the introductory material for the dump of one or move levels.
830 * \param fo Is the file handle to use. Must be capable of sequential writes
831 * in text format. Writes start at the current offset in the file.
832 * \param title Is the title to use for the contents of the file.
833 *
834 * The current format uses HTML. This should be called once per dump (or
835 * take other measures to overwrite a previous call).
836 */
dump_level_header(ang_file * fo,const char * title)837 void dump_level_header(ang_file *fo, const char *title)
838 {
839 file_put(fo,
840 "<!DOCTYPE html>\n"
841 "<html lang=\"en\" xml:lang=\"en\" xmlns=\"http://www.w3.org/1999/xhtml\">\n"
842 " <head>\n"
843 " <meta http-equiv=\"Content-Type\" content=\"text/html; charset=UTF-8\">\n"
844 " <title>");
845 dump_level_escaped_string(fo, title);
846 file_put(fo, "</title>\n </head>\n <body>\n");
847 }
848
849
850 /**
851 * Dump the given level to a file.
852 * \param fo Is the file handle to use. Must be capable of sequential writes
853 * in text format. The level is dumped starting at the current offset in the
854 * file.
855 * \param title Is the title to use for the level.
856 * \param c Is the chunk to dump.
857 * \param dist If not NULL, must act like a two dimensional C array with the
858 * first dimension being at least c->height elements and the second being at
859 * least c->width elements. For a location (x,y) in the level, if dist[y][x]
860 * is negative, the contents will be rendered differently.
861 *
862 * The current output format is HTML. You can dump more than one level to
863 * the same file by calling dump_level_header() once for the file, followed
864 * by calling dump_level_body() for each level of interest, then calling
865 * dump_level_footer() once to finish things off before you close the file
866 * with file_close().
867 */
dump_level_body(ang_file * fo,const char * title,struct chunk * c,int ** dist)868 void dump_level_body(ang_file *fo, const char *title, struct chunk *c,
869 int **dist)
870 {
871 int y;
872
873 file_put(fo, " <p>");
874 dump_level_escaped_string(fo, title);
875 if (dist != NULL) {
876 file_put(fo, "\n <p>A location where the distance array was negative is marked with *.");
877 }
878 file_put(fo, "\n <pre>\n");
879 for (y = 0; y < c->height; ++y) {
880 int x;
881
882 for (x = 0; x < c->width; ++x) {
883 struct loc grid = loc(x, y);
884 const char *s = "#";
885
886 if (square_in_bounds_fully(c, grid)) {
887 if (square_isplayer(c, grid)) {
888 s = "@";
889 } else if (square_isoccupied(c, grid)) {
890 s = (dist == NULL || dist[y][x] >= 0) ?
891 "M" : "*";
892 } else if (square_isdoor(c, grid)) {
893 s = (dist == NULL || dist[y][x] >= 0) ?
894 "+" : "*";
895 } else if (square_isrubble(c, grid)) {
896 s = (dist == NULL || dist[y][x] >= 0) ?
897 ":" : "*";
898 } else if (square_isdownstairs(c, grid)) {
899 s = (dist == NULL || dist[y][x] >= 0) ?
900 ">" : "*";
901 } else if (square_isupstairs(c, grid)) {
902 s = (dist == NULL || dist[y][x] >= 0) ?
903 "<" : "*";
904 } else if (square_istrap(c, grid) ||
905 square_isplayertrap(c, grid)) {
906 s = (dist == NULL || dist[y][x] >= 0) ?
907 "^" : "*";
908 } else if (square_iswebbed(c, grid)) {
909 s = (dist == NULL || dist[y][x] >= 0) ?
910 "w" : "*";
911 } else if (square_object(c, grid)) {
912 s = (dist == NULL || dist[y][x] >= 0) ?
913 "$" : "*";
914 } else if (square_isempty(c, grid) &&
915 (square_isvault(c, grid) ||
916 square_isno_stairs(c, grid))) {
917 s = (dist == NULL || dist[y][x] >= 0) ?
918 " " : "*";
919 } else if (square_ispassable(c, grid)) {
920 s = (dist == NULL || dist[y][x] >= 0) ?
921 "." : "*";
922 }
923 }
924 file_put(fo, s);
925 }
926 file_put(fo, "\n");
927 }
928 file_put(fo, " </pre>\n");
929 }
930
931
932 /**
933 * Write the concluding material for the dump of one or more levels.
934 * \param fo Is the file handle to use. Must be capable of sequential writes
935 * in text format. Writes start at the current offset in the file.
936 */
dump_level_footer(ang_file * fo)937 void dump_level_footer(ang_file *fo)
938 {
939 file_put(fo, " </body>\n</html>\n");
940 }
941