Wiki

List of Tasks

This is a list of tasks in rough order of what I plan to implement. If you want to work on them, please let me (fizzix) know so we don't both work on the same task.

Reasonable stair placement (partially done)
Proper dungeon connection with fill chart (awaiting finalization)
Caverns - make sure they look ok with rooms placed on top!
Angband style special rooms (moat, pit)
Feature placement rules (in data file?)
Doors
Vault placement, construction and vault data loader (can be done before monsters/items are fixed, but I think magnate will get there first)
Pit/nest creation placement
Labyrinth sections

Description for planned dungeon generation. As things get written this will be changed from planned to implemented

Selection of Archetype

When the game generates a new level, the first decision to be made is what type of level to create. In pyrel-angband there will really only be two options for this, town and dungeon. Although this is where you decide whether you have a wildnerness, a mountain, an ocean or whatever other types of maps exist.

What it needs

The only argument that needs to be passed to an archetype is a level value. (or alternatively, level and archetype).

What's in an archetype

The first thing the archetype needs to know is whether the level is permanent. If the level is permanent (e.g. the town) then information needs to be loaded from the appropriate place. The appropriate routines for loading the level are here. (the routines for storing the level should be called on level departure.)

Assuming we're making a new level.

The archetype needs some basic information on how the level is set up. These include what type of tile to fill the new level with. For an angband-style dungeon this is a wall. For the town this is open floor (or null). For an ocean it would be some sort of water tile. The archetype can either be passed, can be randomly generated, or can depend on level.

The archetype also needs to know the maximum level width and height, and needs to create the bounding box for the level. This is not necessary the level boundary. The boundary can be arbitrarily shaped and will be decided later. However, since display windows are almost always rectangular, and the level map will be in a 2 dimensional regular matrix, it makes sense to set a bounding box as a rectangle. The bounding box can depend on the level depth, archetype, and can be affected by random die rolls as well.

It also needs the initial routines for setup. These are the things that exist for all levels of this archetype. E.g permanently light up level.

Archetypes will have other information to help determine the maximum number of rooms and the amount of randomly scattered monsters and items. (alternatively, only the room number needs to be determined here and the monster/item frequencies can be determinable on a feature by feature basis).

Current State: The game has a primitive archetype selection in place. If dlevel 0, then make a town, if not make an Angband level.

Tasks that are still needed Permanent level loading. Allowing for alternate widths and heights. Generalizing to wilderness and other archetypes.

Perimeter

A decision that needs to be made is the type of perimeter. It's not clear to me yet whether this is separate from the feature list or not. The simplest perimeter is a bounding rectangle of permanent walls. However, one can construct perimeters of different shapes including circular, elliptical, one that conforms to the dungeon, or open (leaving the screen loads a new area). The reason this decision needs to be made now, is the generator needs to know whether some areas of the map are off limits for features (i.e. the corners in a circularly bounded level). These can immediately be filled with highest priority permanent walls (or void areas except for the bounding shell I guess). See below for a description on what priority means.

Current state Bounding boxes of permanent walls are set for town and dungeons. Dungeons are mostly wall, town is mostly clear.

Feature Selection Rules

The last piece of information in the archetype is the selection rules for features. These are level dependent probabilities for features occurring and an order in which to attempt them. The first iteration of Angband is only going to have one non-permanent archetype, but it might be a good idea and think ahead to variants that will have several and create a data file, a loader, and a factory for this information.

Current state Not yet implemented. Only feature is a normal room.

Feature selection rules

The feature selection rules indicate what the level looks like. They provide an order of execution to construct the level. Each feature entry has the following information.

Feature type: This is the feature type. Examples are Greater vault, a pit, a moated room, a labyrinth, a cavern, a templated room, a normal room, a corridor, a magma streamer, etc. These are some features already known to angband. But other feature types like magma rivers, forest groves, trading posts would also be supported.

Level dependent probability: This is the chance of one or more of this feature appearing given a level value. The easiest format to create is probably the Oangband method where static values are given per level and a linear interpolation is used for the intermediate points. This is the most flexible way, the only downside is the time spent in creating the tables.

Maximum allowable number of features: If a feature is placed the game rolls to attempt to create another of that feature. This occurs until the maximum number is reached or there is no more room to attempt additional features. The room condition is determined by failing to place the feature some large number of times. This is likely to be level dependent.

Base rating(s): Ratings can determine what messages (feelings) to give a player on entering the level. They can also be used to modify the probabilities of future features occurring. The actual rating should be determined after the feature is placed, since it may depend on information that is unknowable at this stage (e.g. what vault has been selected, what artifacts have been created)

Priority: This is the new piece of information in pyrel, and I don't think it's been used in other variants. Each feature comes with a priority (can be a die roll). The priority indicates whether or not the feature can overwrite an already create feature. This will allow you to place a large cavern on the level (with low priority) and then place a vault on top of it (with high priority). The vault then completely overwrites the section of the cavern that it falls on top of. When placed, priority will be a local property of each tile and may change depending on what's in there. Example: the ant queen makes her home in the cavern giving the squares occupied by her and her escort a high priority while the rest of the cavern has a low priority. Example2: An artifact/unique is created giving the 3x3 block of squares around it a high priority.

Current State Priorities are there along with the "can the room be placed" algorithm for rectangles (only).

Additional rules: Some features may be incompatible with each other, those incompatibilities should be noted here. Some features may increase the chances of other features occurring. This can lead to organically themed levels. Example: the creation of an undead pit leads to an increased chance of creating a crypt. Example 2: A level built on top of a cavern has no need for corridors.

Other additional rules could be whether or not the feature needs to be wholly placed. A vault should probably need to be placed completely. However, it may be ok for a bog-standard room to have it's corner cut out because a vault is already there. This could be a percentage also, so 50% of the time the room needs to be placed in full, and 50% of the time it can be cut off. This would allow low priority features to be placed in part on relatively crowded levels, but also ensures that not every room has some section cut out.

On Feature Failure

A feature may not be placed for two reasons. The first is it fails its probability roll. In this case, the game moves on to the next feature type in the queue. The other failure possibility is due to an inability to place the feature because the dungeon is already full of higher priority squares. In this latter case the feature count is increased by one (as if the feature had been successfully placed) and the next probability roll is attempted.

Feature ordering

The general strategy for features is that larger features should come earlier in the queue than smaller features. Background features that take up or span across the whole level should come first (e.g. a cavern or a magma streamer). Flexible features (ones that can be partially implemented) should come later in the queue. Rarer features should come earlier than more common features. If a feature can't be placed because of lack of room, it should be because more interesting features are taking up the space. In other words, the placement of a normal room should never prevent a greater vault from being placed.

Side-scrolling entrances and exits In specific levels like side-scrolling wilderness, the starting player location is already determined. This place should be marked with a high priority and made into a connection point. Similarly, the exits on the other sides should be determined and marked at this stage.

Placing features

Once a feature passes its probability roll, it needs to be placed. The rules for placement vary from feature to feature but in general the order goes something like this. A feature needs to know its level and its priority and any other special flags (e.g. only undead allowed).

Choose feature sub-type if applicable (e.g. which vault)
Determine size
Pick random (legal) placement for upper left corner (i.e. cannot extend past maximum height/width.)
If feature must be placed in full, check for conflicts with higher priority regions that already exist. (time consuming)
Place feature terrain including rubble if applicable
Mark all feature cells (including wall cells) with the appropriate priority.
Mark boundary cells that can be used for tunnel entrances.
Mark at least one locations internally as entry points for later connectivity test. Place doors at forced entry locations (e.g. entrances to vaults.)
Place traps
Place special monsters/items (e.g. a lair needs its primary denizen) Swap already placed uniques/artifacts from lower priority regions on the level.
Place random monsters/items if applicable
Calculate number of rooms placed, basically a value directly proportional to area.

After feature placement various values need to be updated. The number of rooms placed should be tallied along with the number of items and monsters. These can be used to determine probabilities for monsters and items being placed in future areas.

Features should definitely have a data file, a factory and a loader (Derakon, I'll need your help for this).

Connecting the dungeon

Most archetypes will require connecting tunnels. One of the last features are the tunnels to connect the dungeon. There can be many different tunnel styles, so these should be considered features. The last feature entry should be the standard tunnel with probability of 100%. This tunnel will connect all remaining unconnected points.

Special tunnels should come first (example: double wide tunnels). These should start at a starting location and terminate when they intersect something else including itself. These tunnels are considered decorative and not tasked with actually connecting up the dungeon. But if they manage to do that, all the better. Once these tunnels are created they should be removed from the entry point list.

After the special tunnels have been generated, the connectivity tunnels start. The procedure is as follows

Choose an entry point to start
choose a target point
determine all point simply connected to the starting point.
start a tunnel meandering vaguely in the direction of the end point
while meandering mark all points in the tunnel as connected, and mark the walls as possible entry locations.
if the tunnel intersects something, do one of the following.

if it is a room edge that cannot be entered through, turn and continue (it is important to direct tunnel propagation to the target cell in this case)
if it is an area not contained in the original flow map. Flow out from where the tunnel entered, if the target point is here, choose that as a new starting point and pick a new random target point not in the flow map. Otherwise choose the starting point with the shortest overall distance to the target and start a new tunnel.
if it is an area that is contained in the original flow map (i.e. it intersected itself), choose another starting point in that flow map and continue. If no more starting points exist. Create a new entry location with smallest distance to target and start tunnel from there.
if it is a boundary, backtrack until the last turn and continue. If the last turn was in a room, treat it as if it intersected itself.

Unless I screwed something up (nick?) this should connect all the entry points, and therefore all the stuff that's supposed to be connected.

Current state Dungeon primitively connects.

Player placement

The game selects N random locations in the map and picks randomly from the legal ones (open floor) with the lowest priority. The player is likely to start in a corridor or a normal room.