2 * @brief ダンジョンの生成 / Dungeon generation
5 * Copyright (c) 1997 Ben Harrison, James E. Wilson, Robert A. Koeneke\n
6 * This software may be copied and distributed for educational, research,\n
7 * and not for profit purposes provided that this copyright and statement\n
8 * are included in all such copies. Other copyrights may also apply.\n
9 * 2014 Deskull rearranged comment for Doxygen. \n
14 #include "dungeon/dungeon-flag-types.h"
15 #include "dungeon/dungeon.h"
16 #include "dungeon/quest.h"
17 #include "floor/cave-generator.h"
18 #include "floor/floor-events.h"
19 #include "floor/floor-generator.h"
20 #include "floor/floor-save.h" // todo precalc_cur_num_of_pet() が依存している、違和感.
21 #include "floor/floor-util.h"
22 #include "floor/wild.h"
23 #include "game-option/birth-options.h"
24 #include "game-option/cheat-types.h"
25 #include "game-option/game-play-options.h"
26 #include "game-option/play-record-options.h"
27 #include "grid/feature.h"
28 #include "grid/grid.h"
29 #include "info-reader/feature-reader.h"
30 #include "info-reader/fixed-map-parser.h"
31 #include "io/write-diary.h"
32 #include "market/arena-info-table.h"
33 #include "monster-floor/monster-generator.h"
34 #include "monster-floor/monster-remover.h"
35 #include "monster-floor/place-monster-types.h"
36 #include "monster-race/monster-race.h"
37 #include "monster/monster-flag-types.h"
38 #include "monster/monster-status-setter.h"
39 #include "monster/monster-status.h"
40 #include "monster/monster-update.h"
41 #include "monster/monster-util.h"
42 #include "system/building-type-definition.h"
43 #include "system/floor-type-definition.h"
44 #include "system/system-variables.h"
45 #include "util/bit-flags-calculator.h"
46 #include "view/display-messages.h"
47 #include "window/main-window-util.h"
48 #include "wizard/wizard-messages.h"
49 #include "world/world.h"
51 //--------------------------------------------------------------------
53 //--------------------------------------------------------------------
62 static Vec vec_with_capacity(const size_t cap)
66 Vec vec = { .len = 0, .cap = cap, .data = NULL };
67 vec.data = malloc(sizeof(int) * cap);
74 // サイズ len で、全要素が init で初期化された Vec を返す。
75 static Vec vec_new(const size_t len, const int init)
79 const size_t cap = 2 * len;
80 Vec vec = vec_with_capacity(cap);
83 for (size_t i = 0; i < len; ++i)
89 static void vec_delete(Vec *const vec)
98 static size_t vec_size(const Vec *const vec) { return vec->len; }
100 static bool vec_is_empty(const Vec *const vec) { return vec_size(vec) == 0; }
102 static void vec_push_back(Vec *const vec, const int e)
105 if (vec->len == vec->cap) {
106 vec->cap = vec->cap > 0 ? 2 * vec->cap : 1;
107 vec->data = realloc(vec->data, sizeof(int) * vec->cap);
112 vec->data[vec->len++] = e;
115 static int vec_pop_back(Vec *const vec)
117 assert(!vec_is_empty(vec));
119 return vec->data[vec->len-- - 1];
122 //--------------------------------------------------------------------
125 * @brief 闘技場用のアリーナ地形を作成する / Builds the on_defeat_arena_monster after it is entered -KMW-
126 * @param player_ptr プレーヤーへの参照ポインタ
129 static void build_arena(player_type *player_ptr, POSITION *start_y, POSITION *start_x)
131 POSITION yval = SCREEN_HGT / 2;
132 POSITION xval = SCREEN_WID / 2;
133 POSITION y_height = yval - 10;
134 POSITION y_depth = yval + 10;
135 POSITION x_left = xval - 32;
136 POSITION x_right = xval + 32;
137 floor_type *floor_ptr = player_ptr->current_floor_ptr;
138 for (POSITION i = y_height; i <= y_height + 5; i++)
139 for (POSITION j = x_left; j <= x_right; j++) {
140 place_bold(player_ptr, i, j, GB_EXTRA_PERM);
141 floor_ptr->grid_array[i][j].info |= (CAVE_GLOW | CAVE_MARK);
144 for (POSITION i = y_depth; i >= y_depth - 5; i--)
145 for (POSITION j = x_left; j <= x_right; j++) {
146 place_bold(player_ptr, i, j, GB_EXTRA_PERM);
147 floor_ptr->grid_array[i][j].info |= (CAVE_GLOW | CAVE_MARK);
150 for (POSITION j = x_left; j <= x_left + 17; j++)
151 for (POSITION i = y_height; i <= y_depth; i++) {
152 place_bold(player_ptr, i, j, GB_EXTRA_PERM);
153 floor_ptr->grid_array[i][j].info |= (CAVE_GLOW | CAVE_MARK);
156 for (POSITION j = x_right; j >= x_right - 17; j--)
157 for (POSITION i = y_height; i <= y_depth; i++) {
158 place_bold(player_ptr, i, j, GB_EXTRA_PERM);
159 floor_ptr->grid_array[i][j].info |= (CAVE_GLOW | CAVE_MARK);
162 place_bold(player_ptr, y_height + 6, x_left + 18, GB_EXTRA_PERM);
163 floor_ptr->grid_array[y_height + 6][x_left + 18].info |= CAVE_GLOW | CAVE_MARK;
164 place_bold(player_ptr, y_depth - 6, x_left + 18, GB_EXTRA_PERM);
165 floor_ptr->grid_array[y_depth - 6][x_left + 18].info |= CAVE_GLOW | CAVE_MARK;
166 place_bold(player_ptr, y_height + 6, x_right - 18, GB_EXTRA_PERM);
167 floor_ptr->grid_array[y_height + 6][x_right - 18].info |= CAVE_GLOW | CAVE_MARK;
168 place_bold(player_ptr, y_depth - 6, x_right - 18, GB_EXTRA_PERM);
169 floor_ptr->grid_array[y_depth - 6][x_right - 18].info |= CAVE_GLOW | CAVE_MARK;
171 *start_y = y_height + 5;
173 floor_ptr->grid_array[*start_y][*start_x].feat = f_tag_to_index("ARENA_GATE");
174 floor_ptr->grid_array[*start_y][*start_x].info |= CAVE_GLOW | CAVE_MARK;
178 * @brief 挑戦時闘技場への入場処理 / Town logic flow for generation of on_defeat_arena_monster -KMW-
181 static void generate_challenge_arena(player_type *challanger_ptr)
185 floor_type *floor_ptr = challanger_ptr->current_floor_ptr;
186 floor_ptr->height = SCREEN_HGT;
187 floor_ptr->width = SCREEN_WID;
190 for (y = 0; y < MAX_HGT; y++)
191 for (x = 0; x < MAX_WID; x++) {
192 place_bold(challanger_ptr, y, x, GB_SOLID_PERM);
193 floor_ptr->grid_array[y][x].info |= (CAVE_GLOW | CAVE_MARK);
196 for (y = qy + 1; y < qy + SCREEN_HGT - 1; y++)
197 for (x = qx + 1; x < qx + SCREEN_WID - 1; x++)
198 floor_ptr->grid_array[y][x].feat = feat_floor;
200 build_arena(challanger_ptr, &y, &x);
201 player_place(challanger_ptr, y, x);
202 if (place_monster_aux(challanger_ptr, 0, challanger_ptr->y + 5, challanger_ptr->x, arena_info[challanger_ptr->arena_number].r_idx, PM_NO_KAGE | PM_NO_PET))
205 challanger_ptr->exit_bldg = TRUE;
206 challanger_ptr->arena_number++;
207 msg_print(_("相手は欠場した。あなたの不戦勝だ。", "The enemy is unable to appear. You won by default."));
211 * @brief モンスター闘技場のフロア生成 / Builds the on_defeat_arena_monster after it is entered -KMW-
212 * @param player_ptr プレーヤーへの参照ポインタ
215 static void build_battle(player_type *player_ptr, POSITION *y, POSITION *x)
217 POSITION yval = SCREEN_HGT / 2;
218 POSITION xval = SCREEN_WID / 2;
219 POSITION y_height = yval - 10;
220 POSITION y_depth = yval + 10;
221 POSITION x_left = xval - 32;
222 POSITION x_right = xval + 32;
224 floor_type *floor_ptr = player_ptr->current_floor_ptr;
225 for (int i = y_height; i <= y_height + 5; i++)
226 for (int j = x_left; j <= x_right; j++) {
227 place_bold(player_ptr, i, j, GB_EXTRA_PERM);
228 floor_ptr->grid_array[i][j].info |= (CAVE_GLOW | CAVE_MARK);
231 for (int i = y_depth; i >= y_depth - 3; i--)
232 for (int j = x_left; j <= x_right; j++) {
233 place_bold(player_ptr, i, j, GB_EXTRA_PERM);
234 floor_ptr->grid_array[i][j].info |= (CAVE_GLOW | CAVE_MARK);
237 for (int j = x_left; j <= x_left + 17; j++)
238 for (int i = y_height; i <= y_depth; i++) {
239 place_bold(player_ptr, i, j, GB_EXTRA_PERM);
240 floor_ptr->grid_array[i][j].info |= (CAVE_GLOW | CAVE_MARK);
243 for (int j = x_right; j >= x_right - 17; j--)
244 for (int i = y_height; i <= y_depth; i++) {
245 place_bold(player_ptr, i, j, GB_EXTRA_PERM);
246 floor_ptr->grid_array[i][j].info |= (CAVE_GLOW | CAVE_MARK);
249 place_bold(player_ptr, y_height + 6, x_left + 18, GB_EXTRA_PERM);
250 floor_ptr->grid_array[y_height + 6][x_left + 18].info |= CAVE_GLOW | CAVE_MARK;
251 place_bold(player_ptr, y_depth - 4, x_left + 18, GB_EXTRA_PERM);
252 floor_ptr->grid_array[y_depth - 4][x_left + 18].info |= CAVE_GLOW | CAVE_MARK;
253 place_bold(player_ptr, y_height + 6, x_right - 18, GB_EXTRA_PERM);
254 floor_ptr->grid_array[y_height + 6][x_right - 18].info |= CAVE_GLOW | CAVE_MARK;
255 place_bold(player_ptr, y_depth - 4, x_right - 18, GB_EXTRA_PERM);
256 floor_ptr->grid_array[y_depth - 4][x_right - 18].info |= CAVE_GLOW | CAVE_MARK;
258 for (int i = y_height + 1; i <= y_height + 5; i++)
259 for (int j = x_left + 20 + 2 * (y_height + 5 - i); j <= x_right - 20 - 2 * (y_height + 5 - i); j++) {
260 floor_ptr->grid_array[i][j].feat = feat_permanent_glass_wall;
263 POSITION last_y = y_height + 1;
264 POSITION last_x = xval;
265 floor_ptr->grid_array[last_y][last_x].feat = f_tag_to_index("BUILDING_3");
266 floor_ptr->grid_array[last_y][last_x].info |= CAVE_GLOW | CAVE_MARK;
272 * @brief モンスター闘技場への導入処理 / Town logic flow for generation of on_defeat_arena_monster -KMW-
275 static void generate_gambling_arena(player_type *creature_ptr)
280 floor_type *floor_ptr = creature_ptr->current_floor_ptr;
281 for (y = 0; y < MAX_HGT; y++)
282 for (x = 0; x < MAX_WID; x++) {
283 place_bold(creature_ptr, y, x, GB_SOLID_PERM);
284 floor_ptr->grid_array[y][x].info |= (CAVE_GLOW | CAVE_MARK);
287 for (y = qy + 1; y < qy + SCREEN_HGT - 1; y++)
288 for (x = qx + 1; x < qx + SCREEN_WID - 1; x++)
289 floor_ptr->grid_array[y][x].feat = feat_floor;
291 build_battle(creature_ptr, &y, &x);
292 player_place(creature_ptr, y, x);
293 for (MONSTER_IDX i = 0; i < 4; i++) {
294 place_monster_aux(creature_ptr, 0, creature_ptr->y + 8 + (i / 2) * 4, creature_ptr->x - 2 + (i % 2) * 4, battle_mon[i], (PM_NO_KAGE | PM_NO_PET));
295 set_friendly(&floor_ptr->m_list[floor_ptr->grid_array[creature_ptr->y + 8 + (i / 2) * 4][creature_ptr->x - 2 + (i % 2) * 4].m_idx]);
298 for (MONSTER_IDX i = 1; i < floor_ptr->m_max; i++) {
299 monster_type *m_ptr = &floor_ptr->m_list[i];
300 if (!monster_is_valid(m_ptr))
303 m_ptr->mflag2 |= MFLAG2_MARK | MFLAG2_SHOW;
304 update_monster(creature_ptr, i, FALSE);
309 * @brief 固定マップクエストのフロア生成 / Generate a quest level
310 * @param player_ptr プレーヤーへの参照ポインタ
313 static void generate_fixed_floor(player_type *player_ptr)
315 floor_type *floor_ptr = player_ptr->current_floor_ptr;
316 for (POSITION y = 0; y < floor_ptr->height; y++)
317 for (POSITION x = 0; x < floor_ptr->width; x++)
318 place_bold(player_ptr, y, x, GB_SOLID_PERM);
320 floor_ptr->base_level = quest[floor_ptr->inside_quest].level;
321 floor_ptr->dun_level = floor_ptr->base_level;
322 floor_ptr->object_level = floor_ptr->base_level;
323 floor_ptr->monster_level = floor_ptr->base_level;
325 exe_write_diary(player_ptr, DIARY_TO_QUEST, floor_ptr->inside_quest, NULL);
327 get_mon_num_prep(player_ptr, get_monster_hook(player_ptr), NULL);
328 init_flags = INIT_CREATE_DUNGEON;
329 parse_fixed_map(player_ptr, "q_info.txt", 0, 0, MAX_HGT, MAX_WID);
333 * @brief ダンジョン時のランダムフロア生成 / Make a real level
334 * @param player_ptr プレーヤーへの参照ポインタ
336 * @return フロアの生成に成功したらTRUE
338 static bool level_gen(player_type *player_ptr, concptr *why)
340 floor_type *floor_ptr = player_ptr->current_floor_ptr;
341 DUNGEON_IDX d_idx = floor_ptr->dungeon_idx;
342 if ((always_small_levels || ironman_small_levels || (one_in_(SMALL_LEVEL) && small_levels) || (d_info[d_idx].flags1 & DF1_BEGINNER)
343 || (d_info[d_idx].flags1 & DF1_SMALLEST))
344 && !(d_info[d_idx].flags1 & DF1_BIG)) {
347 if (d_info[d_idx].flags1 & DF1_SMALLEST) {
350 } else if (d_info[d_idx].flags1 & DF1_BEGINNER) {
354 level_height = randint1(MAX_HGT / SCREEN_HGT);
355 level_width = randint1(MAX_WID / SCREEN_WID);
356 bool is_first_level_area = TRUE;
357 bool is_max_area = (level_height == MAX_HGT / SCREEN_HGT) && (level_width == MAX_WID / SCREEN_WID);
358 while (is_first_level_area || is_max_area) {
359 level_height = randint1(MAX_HGT / SCREEN_HGT);
360 level_width = randint1(MAX_WID / SCREEN_WID);
361 is_first_level_area = FALSE;
362 is_max_area = (level_height == MAX_HGT / SCREEN_HGT) && (level_width == MAX_WID / SCREEN_WID);
366 floor_ptr->height = level_height * SCREEN_HGT;
367 floor_ptr->width = level_width * SCREEN_WID;
368 panel_row_min = floor_ptr->height;
369 panel_col_min = floor_ptr->width;
372 player_ptr, CHEAT_DUNGEON, _("小さなフロア: X:%d, Y:%d", "A 'small' dungeon level: X:%d, Y:%d."), floor_ptr->width, floor_ptr->height);
374 floor_ptr->height = MAX_HGT;
375 floor_ptr->width = MAX_WID;
376 panel_row_min = floor_ptr->height;
377 panel_col_min = floor_ptr->width;
380 return cave_gen(player_ptr, why);
384 * @brief フロアに存在する全マスの記憶状態を初期化する / Wipe all unnecessary flags after grid_array generation
387 void wipe_generate_random_floor_flags(floor_type *floor_ptr)
389 for (POSITION y = 0; y < floor_ptr->height; y++)
390 for (POSITION x = 0; x < floor_ptr->width; x++)
391 floor_ptr->grid_array[y][x].info &= ~(CAVE_MASK);
393 if (floor_ptr->dun_level > 0)
394 for (POSITION y = 1; y < floor_ptr->height - 1; y++)
395 for (POSITION x = 1; x < floor_ptr->width - 1; x++)
396 floor_ptr->grid_array[y][x].info |= CAVE_UNSAFE;
400 * @brief フロアの全情報を初期化する / Clear and empty floor.
401 * @parama player_ptr プレーヤーへの参照ポインタ
404 void clear_cave(player_type *player_ptr)
406 floor_type *floor_ptr = player_ptr->current_floor_ptr;
407 (void)C_WIPE(floor_ptr->o_list, floor_ptr->o_max, object_type);
408 floor_ptr->o_max = 1;
409 floor_ptr->o_cnt = 0;
411 for (int i = 1; i < max_r_idx; i++)
412 r_info[i].cur_num = 0;
414 (void)C_WIPE(floor_ptr->m_list, floor_ptr->m_max, monster_type);
415 floor_ptr->m_max = 1;
416 floor_ptr->m_cnt = 0;
417 for (int i = 0; i < MAX_MTIMED; i++)
418 floor_ptr->mproc_max[i] = 0;
420 precalc_cur_num_of_pet(player_ptr);
421 for (POSITION y = 0; y < MAX_HGT; y++) {
422 for (POSITION x = 0; x < MAX_WID; x++) {
423 grid_type *g_ptr = &floor_ptr->grid_array[y][x];
436 floor_ptr->base_level = floor_ptr->dun_level;
437 floor_ptr->monster_level = floor_ptr->base_level;
438 floor_ptr->object_level = floor_ptr->base_level;
441 typedef bool (*IsWallFunc)(const floor_type *, int, int);
443 // (y,x) がプレイヤーが通れない永久地形かどうかを返す。
444 static bool is_permanent_blocker(const floor_type *const floor_ptr, const int y, const int x)
446 const FEAT_IDX feat = floor_ptr->grid_array[y][x].feat;
447 const BIT_FLAGS *const flags = f_info[feat].flags;
448 return has_flag(flags, FF_PERMANENT) && !has_flag(flags, FF_MOVE);
451 static void floor_is_connected_dfs(
452 const floor_type *const floor_ptr, const IsWallFunc is_wall, const int y_start, const int x_start, Vec *const stk, const Vec *const visited)
455 static const int DY[8] = { -1, -1, -1, 0, 0, 1, 1, 1 };
456 static const int DX[8] = { -1, 0, 1, -1, 1, -1, 0, 1 };
459 const int h = floor_ptr->height;
460 const int w = floor_ptr->width;
461 const int start = w * y_start + x_start;
463 vec_push_back(stk, start);
464 visited->data[start] = 1;
466 while (!vec_is_empty(stk)) {
467 const int cur = vec_pop_back(stk);
468 const int y = cur / w;
469 const int x = cur % w;
471 for (int i = 0; i < 8; ++i) {
472 const int y_nxt = y + DY[i];
473 const int x_nxt = x + DX[i];
474 if (y_nxt < 0 || h <= y_nxt || x_nxt < 0 || w <= x_nxt)
476 const int nxt = w * y_nxt + x_nxt;
477 if (visited->data[nxt])
479 if (is_wall(floor_ptr, y_nxt, x_nxt))
482 vec_push_back(stk, nxt);
483 visited->data[nxt] = 1;
489 // 各セルの8近傍は互いに移動可能とし、is_wall が真を返すセルのみを壁とみなす。
491 // 連結成分数が 0 の場合、偽を返す。
492 static bool floor_is_connected(const floor_type *const floor_ptr, const IsWallFunc is_wall)
494 const int h = floor_ptr->height;
495 const int w = floor_ptr->width;
497 // ヒープ上に確保したスタックを用いてDFSする。
498 // 最大フロアサイズが h=66, w=198 なので、単純に再帰DFSするとスタックオーバーフローが不安。
499 Vec stk = vec_with_capacity(1024);
500 Vec visited = vec_new((size_t)h * (size_t)w, 0);
501 int n_component = 0; // 連結成分数
503 for (int y = 0; y < h; ++y) {
504 for (int x = 0; x < w; ++x) {
505 const int idx = w * y + x;
506 if (visited.data[idx])
508 if (is_wall(floor_ptr, y, x))
511 if (++n_component >= 2)
513 floor_is_connected_dfs(floor_ptr, is_wall, y, x, &stk, &visited);
518 vec_delete(&visited);
521 return n_component == 1;
525 * ダンジョンのランダムフロアを生成する / Generates a random dungeon level -RAK-
526 * @parama player_ptr プレーヤーへの参照ポインタ
528 * @note Hack -- regenerate any "overflow" levels
530 void generate_floor(player_type *player_ptr)
532 floor_type *floor_ptr = player_ptr->current_floor_ptr;
533 floor_ptr->dungeon_idx = player_ptr->dungeon_idx;
534 set_floor_and_wall(floor_ptr->dungeon_idx);
535 for (int num = 0; TRUE; num++) {
538 clear_cave(player_ptr);
539 player_ptr->x = player_ptr->y = 0;
540 if (floor_ptr->inside_arena)
541 generate_challenge_arena(player_ptr);
542 else if (player_ptr->phase_out)
543 generate_gambling_arena(player_ptr);
544 else if (floor_ptr->inside_quest)
545 generate_fixed_floor(player_ptr);
546 else if (!floor_ptr->dun_level)
547 if (player_ptr->wild_mode)
548 wilderness_gen_small(player_ptr);
550 wilderness_gen(player_ptr);
552 okay = level_gen(player_ptr, &why);
554 if (floor_ptr->o_max >= current_world_ptr->max_o_idx) {
555 why = _("アイテムが多すぎる", "too many objects");
557 } else if (floor_ptr->m_max >= current_world_ptr->max_m_idx) {
558 why = _("モンスターが多すぎる", "too many monsters");
562 // ダンジョン内フロアが連結でない(永久壁で区切られた孤立部屋がある)場合、
563 // 狂戦士でのプレイに支障をきたしうるので再生成する。
564 // 地上、荒野マップ、クエストでは連結性判定は行わない。
565 // TODO: 本来はダンジョン生成アルゴリズム自身で連結性を保証するのが理想ではある。
566 const bool check_conn = okay && floor_ptr->dun_level > 0 && floor_ptr->inside_quest == 0;
567 if (check_conn && !floor_is_connected(floor_ptr, is_permanent_blocker)) {
568 // 一定回数試しても連結にならないなら諦める。
570 plog("cannot generate connected floor. giving up...");
572 why = _("フロアが連結でない", "floor is not connected");
581 msg_format(_("生成やり直し(%s)", "Generation restarted (%s)"), why);
583 wipe_o_list(floor_ptr);
584 wipe_monsters_list(player_ptr);
587 glow_deep_lava_and_bldg(player_ptr);
588 player_ptr->enter_dungeon = FALSE;
589 wipe_generate_random_floor_flags(floor_ptr);