Dungeon generation utilities. More...

#include "angband.h"
#include "cave.h"
#include "datafile.h"
#include "math.h"
#include "game-event.h"
#include "generate.h"
#include "init.h"
#include "mon-make.h"
#include "mon-spell.h"
#include "obj-make.h"
#include "obj-pile.h"
#include "obj-tval.h"
#include "obj-util.h"
#include "player-util.h"
#include "trap.h"
#include "z-queue.h"
#include "z-type.h"

Functions
int	grid_to_i (struct loc grid, int w)
	Used to convert grid into an array index (i) in a chunk of width w. More...

void	i_to_grid (int i, int w, struct loc *grid)
	Used to convert an array index (i) into grid in a chunk of width w. More...

void	shuffle (int *arr, int n)
	Shuffle an array using Knuth's shuffle. More...

static bool	cave_find_in_range (struct chunk c, struct loc grid, struct loc top_left, struct loc bottom_right, square_predicate pred)
	Locate a square in a rectangle which satisfies the given predicate. More...

bool	cave_find (struct chunk c, struct loc grid, square_predicate pred)
	Locate a square in the dungeon which satisfies the given predicate. More...

bool	find_empty (struct chunk c, struct loc grid)
	Locate an empty square for 0 <= y < ymax, 0 <= x < xmax. More...

bool	find_empty_range (struct chunk c, struct loc grid, struct loc top_left, struct loc bottom_right)
	Locate an empty square in a given rectangle. More...

bool	find_nearby_grid (struct chunk c, struct loc grid, struct loc centre, int yd, int xd)
	Locate a grid within +/- yd, xd of a centre. More...

void	correct_dir (struct loc *offset, struct loc grid1, struct loc grid2)
	Given two points, pick a valid cardinal direction from one to the other. More...

void	rand_dir (struct loc *offset)
	Pick a random cardinal direction. More...

static bool	find_start (struct chunk c, struct loc grid)
	Determine whether the given coordinate is a valid starting location. More...

void	new_player_spot (struct chunk c, struct player p)
	Place the player at a random starting location. More...

static void	place_rubble (struct chunk *c, struct loc grid)
	Place rubble at a given location. More...

static void	place_stairs (struct chunk *c, struct loc grid, int feat)
	Place stairs (of the requested type 'feat' if allowed) at a given location. More...

void	place_random_stairs (struct chunk *c, struct loc grid)
	Place random stairs at a given location. More...

void	place_object (struct chunk *c, struct loc grid, int level, bool good, bool great, byte origin, int tval)
	Place a random object at a given location. More...

void	place_gold (struct chunk *c, struct loc grid, int level, byte origin)
	Place a random amount of gold at a given location. More...

void	place_secret_door (struct chunk *c, struct loc grid)
	Place a secret door at a given location. More...

void	place_closed_door (struct chunk *c, struct loc grid)
	Place a closed door at a given location. More...

void	place_random_door (struct chunk *c, struct loc grid)
	Place a random door at a given location. More...

void	alloc_stairs (struct chunk *c, int feat, int num)
	Place some staircases near walls. More...

void	alloc_objects (struct chunk *c, int set, int typ, int num, int depth, byte origin)
	Allocates 'num' random entities in the dungeon. More...

bool	alloc_object (struct chunk *c, int set, int typ, int depth, byte origin)
	Allocates a single random object in the dungeon. More...

void	vault_objects (struct chunk *c, struct loc grid, int depth, int num)
	Create up to 'num' objects near the given coordinates in a vault. More...

static void	vault_trap_aux (struct chunk *c, struct loc grid, int yd, int xd)
	Place a trap near (x, y), with a given displacement. More...

void	vault_traps (struct chunk *c, struct loc grid, int yd, int xd, int num)
	Place 'num' traps near a location, with a given displacement. More...

void	vault_monsters (struct chunk *c, struct loc grid, int depth, int num)
	Place 'num' sleeping monsters near the location. More...

Variables
byte	get_angle_to_grid [41][41]
	Accept values for y and x (considered as the endpoints of lines) between 0 and 40, and return an angle in degrees (divided by two). More...

Detailed Description

Dungeon generation utilities.

This work is free software; you can redistribute it and/or modify it under the terms of either:

a) the GNU General Public License as published by the Free Software Foundation, version 2, or

b) the "Angband licence": This software may be copied and distributed for educational, research, and not for profit purposes provided that this copyright and statement are included in all such copies. Other copyrights may also apply.

This file contains various utility functions for dungeon generation - mostly for finding appropriate grids for some purposes, or placing things.

Function Documentation

◆ alloc_object()

bool alloc_object	(	struct chunk *	c,
		int	set,
		int	typ,
		int	depth,
		byte	origin
	)

Allocates a single random object in the dungeon.

Parameters

c	the current chunk
set	where the entity is placed (corridor, room or either)
typ	what is placed (rubble, trap, gold, item)
depth	generation depth
origin	item origin (if appropriate)

'set' controls where the object is placed (corridor, room, either). 'typ' conrols the kind of object (rubble, trap, gold, item).

References find_empty(), place_gold(), place_object(), place_rubble(), place_trap(), SET_CORR, SET_ROOM, square_isroom(), TYP_GOLD, TYP_GOOD, TYP_GREAT, TYP_OBJECT, TYP_RUBBLE, and TYP_TRAP.

Referenced by alloc_objects().

◆ alloc_objects()

void alloc_objects	(	struct chunk *	c,
		int	set,
		int	typ,
		int	num,
		int	depth,
		byte	origin
	)

Allocates 'num' random entities in the dungeon.

Parameters

c	the current chunk
set	where the entity is placed (corridor, room or either)
typ	what is placed (rubble, trap, gold, item)
num	number to place
depth	generation depth
origin	item origin (if appropriate)

See alloc_object() for more information.

References alloc_object(), num, and ok.

Referenced by cavern_gen(), classic_gen(), gauntlet_gen(), hard_centre_gen(), labyrinth_chunk(), labyrinth_gen(), lair_gen(), modified_gen(), and moria_gen().

◆ alloc_stairs()

void alloc_stairs	(	struct chunk *	c,
		int	feat,
		int	num
	)

Place some staircases near walls.

Parameters

c	the current chunk
feat	the stair terrain type
num	number of staircases to place
walls	number of walls to surround the stairs (negotiable)

References cave_find_in_range(), chunk::height, i, loc(), num, place_stairs(), square_isempty(), square_isno_stairs(), square_isvault(), square_num_walls_adjacent(), square_num_walls_diagonal(), square_suits_stairs_ok(), square_suits_stairs_well(), and chunk::width.

Referenced by cavern_gen(), classic_gen(), gauntlet_gen(), hard_centre_gen(), labyrinth_gen(), lair_gen(), modified_gen(), and moria_gen().

◆ cave_find()

bool cave_find	(	struct chunk *	c,
		struct loc *	grid,
		square_predicate	pred
	)

Locate a square in the dungeon which satisfies the given predicate.

Parameters

c	current chunk
grid	found grid
pred	square_predicate specifying what we're looking for

Returns: success

References cave_find_in_range(), chunk::height, loc(), and chunk::width.

Referenced by find_empty(), and labyrinth_gen().

◆ cave_find_in_range()

static bool cave_find_in_range	(	struct chunk *	c,
		struct loc *	grid,
		struct loc	top_left,
		struct loc	bottom_right,
		square_predicate	pred
	)

static

Locate a square in a rectangle which satisfies the given predicate.

Parameters

c	current chunk
grid	found grid
top_left	top left grid of rectangle
bottom_right	bottom right grid of rectangle
pred	square_predicate specifying what we're looking for

Returns: success

References i, loc_diff(), mem_alloc(), mem_free(), randint0, loc::x, and loc::y.

Referenced by alloc_stairs(), cave_find(), find_empty_range(), find_nearby_grid(), and find_start().

◆ correct_dir()

void correct_dir	(	struct loc *	offset,
		struct loc	grid1,
		struct loc	grid2
	)

Given two points, pick a valid cardinal direction from one to the other.

Parameters

offset	found offset direction from grid 1 to grid2
grid1	starting grid
grid2	target grid

References CMP, randint0, loc::x, and loc::y.

Referenced by build_tunnel().

◆ find_empty()

bool find_empty	(	struct chunk *	c,
		struct loc *	grid
	)

Locate an empty square for 0 <= y < ymax, 0 <= x < xmax.

Parameters

c	current chunk
grid	found grid

Returns: success

References cave_find(), and square_isempty().

Referenced by alloc_object(), cave_generate(), and labyrinth_chunk().

◆ find_empty_range()

bool find_empty_range	(	struct chunk *	c,
		struct loc *	grid,
		struct loc	top_left,
		struct loc	bottom_right
	)

Locate an empty square in a given rectangle.

Parameters

c	current chunk
grid	found grid
top_left	top left grid of rectangle
bottom_right	bottom right grid of rectangle

Returns: success

References cave_find_in_range(), and square_isempty().

Referenced by hard_centre_gen(), and town_gen_layout().

◆ find_nearby_grid()

bool find_nearby_grid	(	struct chunk *	c,
		struct loc *	grid,
		struct loc	centre,
		int	yd,
		int	xd
	)

Locate a grid within +/- yd, xd of a centre.

Parameters

c	current chunk
grid	found grid
centre	starting grid
yd	y-range
xd	x-range

Returns: success

References cave_find_in_range(), loc(), square_in_bounds_fully(), loc::x, and loc::y.

Referenced by build_streamer(), vault_objects(), and vault_trap_aux().

◆ find_start()

static bool find_start	(	struct chunk *	c,
		struct loc *	grid
	)

static

Determine whether the given coordinate is a valid starting location.

Parameters

c	current chunk
y	co-ordinates
x	co-ordinates

Returns: success

References cave_find_in_range(), chunk::height, loc(), square_isempty(), square_isno_stairs(), square_isvault(), square_num_walls_adjacent(), square_num_walls_diagonal(), square_suits_stairs_ok(), square_suits_stairs_well(), and chunk::width.

Referenced by new_player_spot().

◆ grid_to_i()

int grid_to_i	(	struct loc	grid,
		int	w
	)

Used to convert grid into an array index (i) in a chunk of width w.

Parameters

grid	location
w	area width

Returns: index

References loc::x, and loc::y.

Referenced by build_color_point(), clear_small_regions(), connect_caverns(), ignore_point(), join_region(), lab_get_adjoin(), labyrinth_chunk(), make_noise(), and mutate_cavern().

◆ i_to_grid()

void i_to_grid	(	int	i,
		int	w,
		struct loc *	grid
	)

Used to convert an array index (i) into grid in a chunk of width w.

Parameters

i	grid index
w	area width
grid	location

References w, loc::x, and loc::y.

Referenced by build_color_point(), join_region(), lab_get_adjoin(), labyrinth_chunk(), and make_noise().

◆ new_player_spot()

void new_player_spot	(	struct chunk *	c,
		struct player *	p
	)

Place the player at a random starting location.

Parameters

c	current chunk
p	the player

References player_upkeep::create_down_stair, player_upkeep::create_up_stair, FEAT_LESS, FEAT_MORE, find_start(), player::grid, OPT, player_place(), quit(), square_in_bounds_fully(), square_isstairs(), square_set_feat(), and player::upkeep.

Referenced by cavern_gen(), classic_gen(), gauntlet_gen(), hard_centre_gen(), labyrinth_gen(), lair_gen(), modified_gen(), and moria_gen().

◆ place_closed_door()

void place_closed_door	(	struct chunk *	c,
		struct loc	grid
	)

Place a closed door at a given location.

Parameters

c	current chunk
grid	location

References FEAT_CLOSED, one_in_, randint1, square_set_door_lock(), and square_set_feat().

Referenced by build_circular(), build_large(), build_room_template(), effect_handler_DETECT_DOORS(), labyrinth_chunk(), place_random_door(), project_feature_handler_KILL_TRAP(), and search().

◆ place_gold()

void place_gold	(	struct chunk *	c,
		struct loc	grid,
		int	level,
		byte	origin
	)

Place a random amount of gold at a given location.

Parameters

c	current chunk
grid	location
level	generation depth
origin	item origin

References floor_carry(), level, list_object(), make_gold(), object_delete(), object::origin, object::origin_depth, square_canputitem(), and square_in_bounds().

Referenced by alloc_object(), blow_knock_back(), build_vault(), do_cmd_tunnel_aux(), project_feature_handler_KILL_WALL(), and vault_objects().

◆ place_object()

void place_object	(	struct chunk *	c,
		struct loc	grid,
		int	level,
		bool	good,
		bool	great,
		byte	origin,
		int	tval
	)

Place a random object at a given location.

Parameters

c	current chunk
grid	location
level	generation depth
good	is it a good object?
great	is it a great object?
origin	item origin
tval	specified tval, if any

References object::artifact, artifact::created, chunk::depth, floor_carry(), chunk::good_item, list_object(), make_object(), chunk::obj_rating, object_delete(), object::origin, object::origin_depth, square_canputitem(), and square_in_bounds().

Referenced by alloc_object(), build_crossed(), build_large(), build_nest(), build_pit(), build_room_template(), build_vault(), do_cmd_tunnel_aux(), project_feature_handler_KILL_WALL(), and vault_objects().

◆ place_random_door()

void place_random_door	(	struct chunk *	c,
		struct loc	grid
	)

Place a random door at a given location.

Parameters

c	current chunk
grid	location

The door generated could be closed, open, broken, or secret.

References FEAT_BROKEN, FEAT_OPEN, place_closed_door(), randint0, and square_set_feat().

Referenced by build_room_of_chambers(), build_tunnel(), and try_door().

◆ place_random_stairs()

void place_random_stairs	(	struct chunk *	c,
		struct loc	grid
	)

Place random stairs at a given location.

Parameters

c	current chunk
grid	location

References FEAT_LESS, FEAT_MORE, place_stairs(), randint0, and square_canputitem().

Referenced by build_large(), and build_room_template().

◆ place_rubble()

static void place_rubble	(	struct chunk *	c,
		struct loc	grid
	)

static

Place rubble at a given location.

Parameters

c	current chunk
grid	location

References FEAT_PASS_RUBBLE, FEAT_RUBBLE, one_in_, and square_set_feat().

Referenced by alloc_object().

◆ place_secret_door()

void place_secret_door	(	struct chunk *	c,
		struct loc	grid
	)

Place a secret door at a given location.

Parameters

c	current chunk
grid	location

References FEAT_SECRET, and square_set_feat().

Referenced by build_large(), build_room_template(), and build_vault().

◆ place_stairs()

static void place_stairs	(	struct chunk *	c,
		struct loc	grid,
		int	feat
	)

static

Place stairs (of the requested type 'feat' if allowed) at a given location.

Parameters

c	current chunk
grid	location
feat	stair terrain type

All stairs from town go down. All stairs on an unfinished quest level go up.

References chunk::depth, FEAT_LESS, FEAT_MORE, is_quest(), angband_constants::max_depth, square_set_feat(), and z_info.

Referenced by alloc_stairs(), and place_random_stairs().

◆ rand_dir()

void rand_dir ( struct loc * offset )

Pick a random cardinal direction.

Parameters

offset direction offset

References ddgrid_ddd, i, and randint0.

Referenced by build_circular(), and build_tunnel().

◆ shuffle()

void shuffle	(	int *	arr,
		int	n
	)

Shuffle an array using Knuth's shuffle.

Parameters

arr	array
n	number of shuffle moves

References i, and randint0.

Referenced by labyrinth_chunk().

◆ vault_monsters()

void vault_monsters	(	struct chunk *	c,
		struct loc	grid,
		int	depth,
		int	num
	)

Place 'num' sleeping monsters near the location.

Parameters

c	the current chunk
grid	location to place the monsters near
depth	generation depth
num	number of monsters to place

References i, num, pick_and_place_monster(), scatter(), square_in_bounds(), and square_isempty().

Referenced by build_circular(), build_crossed(), build_large(), and build_room_template().

◆ vault_objects()

void vault_objects	(	struct chunk *	c,
		struct loc	grid,
		int	depth,
		int	num
	)

Create up to 'num' objects near the given coordinates in a vault.

Parameters

c	the current chunk
grid	location
depth	generation depth
num	number of objects

References find_nearby_grid(), i, num, place_gold(), place_object(), randint0, and square_canputitem().

Referenced by build_circular(), build_large(), and build_room_template().

◆ vault_trap_aux()

static void vault_trap_aux	(	struct chunk *	c,
		struct loc	grid,
		int	yd,
		int	xd
	)

static

Place a trap near (x, y), with a given displacement.

Parameters

c	the current chunk
grid	location to place the trap near
yd	how far afield to look for a place
xd	how far afield to look for a place

References find_nearby_grid(), square_add_trap(), and square_isempty().

Referenced by vault_traps().

◆ vault_traps()

void vault_traps	(	struct chunk *	c,
		struct loc	grid,
		int	yd,
		int	xd,
		int	num
	)

Place 'num' traps near a location, with a given displacement.

Parameters

c	the current chunk
grid	location to place the trap near
yd	how far afield to look for a place
xd	how far afield to look for a place
num	number of traps to place

References i, num, and vault_trap_aux().

Referenced by build_crossed(), and build_large().

Variable Documentation

◆ get_angle_to_grid

byte get_angle_to_grid[41][41]

Accept values for y and x (considered as the endpoints of lines) between 0 and 40, and return an angle in degrees (divided by two).

-LM-

This table's input and output need some processing:

Because this table gives degrees for a whole circle, up to radius 20, its origin is at (x,y) = (20, 20). Therefore, the input code needs to find the origin grid (where the lines being compared come from), and then map it to table grid 20,20. Do not, however, actually try to compare the angle of a line that begins and ends at the origin with any other line - it is impossible mathematically, and the table will return the value "255".

The output of this table also needs to be massaged, in order to avoid the discontinuity at 0/180 degrees. This can be done by: rotate = 90 - first value this rotates the first input to the 90 degree line) tmp = ABS(second value + rotate) % 180 diff = ABS(90 - tmp) = the angular difference (divided by two) between the first and second values.

Note that grids diagonal to the origin have unique angles.

Referenced by generate_starburst_room(), project(), and thrust_away().

Functions

Variables

Detailed Description

Function Documentation

◆ alloc_object()

◆ alloc_objects()

◆ alloc_stairs()

◆ cave_find()

◆ cave_find_in_range()

◆ correct_dir()

◆ find_empty()

◆ find_empty_range()

◆ find_nearby_grid()

◆ find_start()

◆ grid_to_i()

◆ i_to_grid()

◆ new_player_spot()

◆ place_closed_door()

◆ place_gold()

◆ place_object()

◆ place_random_door()

◆ place_random_stairs()

◆ place_rubble()

◆ place_secret_door()

◆ place_stairs()

◆ rand_dir()

◆ shuffle()

◆ vault_monsters()

◆ vault_objects()

◆ vault_trap_aux()

◆ vault_traps()

Variable Documentation

◆ get_angle_to_grid