This document describes how PWMAngband actually works at a high level.
As you probably know if you’re reading this, PWMAngband is a roguelike game set in a high-fantasy universe. The game world is made up of levels, numbered from zero (“the town”) to some maximum depth. Levels are increasingly dangerous the deeper they are into the dungeon. Levels are filled with monsters, traps, and objects. Monsters move and act on their own, traps react to creatures entering their square, and objects are inert unless used by a creature. The objective of the game is to find Morgoth at depth 100 and kill him.
There are three important top-level data structures in PWMAngband: the ‘chunk’, the player, and the static data tables.
A chunk represents an area of dungeon, and contains everything inside it; this includes any monsters, objects, or traps inside the bounds of that chunk. A chunk also keeps a map of the terrain in its area. For unpleasant historical reasons, all monsters/objects/traps in a chunk are stored in arrays and usually referred to by index; each square of a chunk knows the indexes (if any) of monsters/objects/traps contained in it. A chunk also stores AI pathfinding data for its contained area. All data in the ‘current’ chunk is lost when leaving the level.
The player is a global object containing information about, well, the player. All the information in the player is level-independent. This structure contains stats, any current effects, hunger status, sex/race/class, the player’s inventory, and a grab-bag of other information. Although there is a global player object, many functions instead take a player object explicitly to make them easier to test.
The Static Data
PWMAngband’s static data – player and monster races, object types, artifacts, et cetera – is loaded from the gamedata Files. Once loaded, this data is stored in global tables, sometimes referred to as the ‘info arrays’. These arrays are generally declared in the header files of the code that uses them most, but they are mostly initialized by the edit-file code. The sizes of these arrays are stored in a ‘maxima’ structure, called z_info.
The Z Layer
The lowest-level code in PWMAngband is the “Z” layer, which provides platform-independent abstractions and generic data structures. Currently, the Z layer provides:
|z-bitflag||Densely-packed bit flag arrays|
|z-util||Random utility macros|
Code in the Z layer may not depend on files outside the Z layer.
Certain game-specific abstractions are important and widely used in PWMAngband to glue the UI code to the game engine. These are the command queue, which sends player commands to the game engine, and events, which indicate to the UI that the state of the game changed.
The command queue
PWMAngband uses three types of files for storing data: gamedata files, which contain the game’s static data, pref files, which contain UI settings, and save files, which contain the state of a game in progress.
Gamedata files use a line-oriented format where fields are separated by colons. The parser for this format is in parser.h. These files are mostly loaded at initialization time (see init.c – init_angband) and used to fill in the static data arrays (see The Static Data).
Currently, a savefile is a series of concatenated blocks. Each block has a name describing what type it is and a version tag. The version tag allows for old savefiles to be loaded, although the load/save code will only write new savefiles. Numbers in savefiles are stored in little-endian byte order and strings are stored null-terminated.
The flow of control through PWMAngband is complicated and can be very non-obvious due to overuse of global variables as special-behavior hooks. That said, this section gives a high-level overview of the control flow of a game session.
Execution begins in main.c, which runs frontend-independent initialization code, then continues in the appropriate
main-xxx.c file for the current frontend. After the game engine is initialized, the player is loaded (or generated) and gameplay begins.
main.c and main-*.c
main() is the entry point for PWMAngband execution except on Windows, where main-win.c’s
WinMain() is used, and on Nintendo DS, where a special main() in main-nds.c is used. The
main() function is responsible for dropping permissions if PWMAngband is running setuid, parsing command line arguments, then finding a frontend to use and initializing it. Once
main() finds a frontend, it sets up signal handlers, sets up the display, then calls
dungeon.c – play_game
This function is responsible for driving the remaining initialization. It first calls init.c – init_angband, which loads all the gamedata files and initializes other static data used by the game. It then configures subwindows, loads a saved game if there is a valid save (see savefiles), sets up the RNG, loads pref files (see prefs.c – process_pref_file), and enters the game main loop (see dungeon.c – the game main loop).
init.c – init_angband
The init_angband() function in init.c is responsible for loading and setting up static data needed by the game engine. Inside init.c, there is a list of ‘init modules’ that have startup-time static data they need to initialize, these are registered in an array of module pointers in init.c, and init_angband() calls their initialization hooks before doing any other work. The init_angband() function then loads the top-level pref file (see pref files), initializes the command queue (see the command queue), then waits for the UI to enqueue either QUIT, NEWGAME, or LOADFILE. This function returns true if the player wants to roll a new character, and false if they want to load an existing character.
prefs.c – process_pref_file
The process_pref_file() function in prefs.c is responsible for loading user pref files, which can live at multiple paths. User preference files override default preference files. See pref files for more details.
Once the simulation is set up, the game main loop in dungeon.c – play_game is responsible for stepping the simulation.
dungeon.c – the game main loop
The main loop of the game is inside play_game() in typical understated PWMAngband style. This loop runs once per time that either the level is regenerated, the player dies, or the player quits the game. Each iteration through, the this loop runs the level main loop to completion for an individual level.
dungeon.c – the level main loop
The main loop for the level is implemented in dungeon() in dungeon.c. The dungeon() function is called when the player enters a level, and returns only when the player exits the level, either by changing levels, dying, or quitting. This function is responsible for tracking the player’s max level/depth, autosaving at level entry, and running the main simulation loop. Each iteration of the main simulation loop is one “turn” in PWMAngband parlance, or one step of the simulator. During each turn:
- All monsters with more energy than the player act
- The player acts
- All other monsters act
- The UI updates
- The world acts
- End-of-turn housekeeping is done
mon-melee2.c – process_monsters()
In PWMAngband, creatures act in order of “energy”, which roughly determines how many actions they can take per step through the simulation. The process_monsters() function in mon-melee2.c is responsible for walking through the list of all monsters in the current chunk (see the chunk) and having each monster act by calling process_monster(), which implements the highest level AI for monsters.
dungeon.c – process_player()
The process_player() function allows the player to act repeatedly until they do something that uses energy. Commands like looking around or inscribing items do not use energy; movement, attacking, casting spells, using items, and so on do. The rule of thumb is that a command that does not alter game engine state does not use energy, because it does not represent an action the character in the simulation is doing. The guts of the process_player() function are actually handled by process_command() in cmd-core.c, which looks up commands in the game_cmds table in that file.
Keeping the UI up to date
Four related horribly-named functions in player-calcs.h are responsible for keeping the UI in sync with the simulated character’s state:
|notice_stuff()||which deals with pack combining and dropping ignored items;|
|update_stuff()||which recalculates derived bonuses, AI data, vision, seen monsters, and other things based on the flags in player->upkeep->update;|
|redraw_stuff()||which signals the UI to redraw changed sections of the game state;|
|handle_stuff()||which calls update_stuff() and redraw_stuff() if needed.|
These functions are called during every game loop, after the player and all monsters have acted.
dungeon.c – process_world()
The process_world() function only runs every 10 turns. It is responsible for the day/night transition in town, restocking the stores, generating new creatures over time, dealing poison/cut damage, applying hunger, regeneration, ticking down timed effects, consuming light fuel, and applying a litany of spell effects that happen ‘at random’ from the player’s point of view.
prepare_next_level() in generate.c controls the process of generating or loading a level. To signal that run_game_loop() in game-world.c should call prepare_next_level(), game logic calls dungeon_change_level() in player-util.c to set the necessary data in the player structure. When a level change happens by traversing a staircase, some other data in the player structure is set to indicate what should be done to connect stairs. That doesn’t happen in dungeon_change_level() and is instead set directly, currently in do_cmd_go_up() and do_cmd_go_down() in cmd-cave.c.
With the default for non-persistent levels, loading only happens when returning to the town or when returning from a single combat arena. The code and global data for handling stored levels is in gen-chunk.c.
When a new level is needed, prepare_next_level() calls cave_generate(), also in generate.c. That initializes a global bit of state, a dun_data structure called dun declared in generate.h, for passing a lot of the details needed when generating a level. It then selects a level profile via choose_profile() in generate.c. The level profile controls the layout of the level. The available level profiles are those listed in list-dun-profiles.h and several aspects of each profile are configured at runtime from the contents of lib/gamedata/dungeon_profile.txt. With a profile selected, cave_generate() uses the profile’s builder function pointer to attempt to layout the new level. Those function pointers are initialized when list-dun-profiles.h is included in generate.c. The level layout functions all have names with the name of the profile followed by _gen, classic_gen() for classic levels as an example. Those functions are defined in gen-cave.c.
Three of the level layout functions, classic_gen(), modified_gen(), and moria_gen() follow the same basic procedure. They divide the level into a grid of rectangular blocks where, in general, each block can only contain one room though a room could occupy many blocks. They then try to randomly place rooms in those blocks until some criteria is met. Room selection is configurable from lib/gamedata/dungeon_profile.txt and uses the predefined room types listed in list-rooms.h. When building a room, those level layout functions use the convenience function, room_build() from gen-room.c. That, in turn, calls the appropriate function to build the type of room chosen. The names of the room building functions have build_ followed by the name of the room type, build_simple() for instance. Those functions are defined in gen-room.c. Once the rooms are built, there’s an initial pass to connect them with corridors. That happens in gen-cave.c’s do_traditional_tunneling(). A second pass, to try and ensure connectedness though vault areas can disrupt that, is then done with ensure_connectedness(). At that point, most other features (mineral veins, staircases, objects, and monsters) are added. Some features will have already been added through some of the types of rooms.
The other layout functions are more of a grab bag. They are all in gen-cave.c. Many of them have portions that are caverns or labyrinths. Those are generated using cavern_chunk() or labyrinth_chunk(), respectively, in gen-cave.c.
We try very hard to not let the game be disturbed by players logging in. Therefore a new connection passes through several states before it is actively playing.
First we make a new connection structure available with a new socket to listen on. This socket port number is told to the client via the pack mechanism. In this state the client has to send a packet to this newly created socket with its name and playing parameters. If this succeeds the connection advances to its second state. In this second state the essential server configuration like the map and so on is transmitted to the client. If the client has acknowledged all this data then it advances to the third state, which is the ready-but-not-playing-yet state. In this state the client has some time to do its final initializations, like mapping its user interface windows and so on.
When the client is ready to accept frame updates and process keyboard events then it sends the start-play packet.
This play packet advances the connection state into the actively-playing state. A player structure is allocated and initialized and the other human players are told about this new player. The newly started client is told about the already playing players and play has begun.
Apart from these four states there are also two intermediate states. These intermediate states are entered when the previous state has filled the reliable data buffer and the client has not acknowledged all the data yet that is in this reliable data buffer. They are so called output drain states. Not doing anything else then waiting until the buffer is empty.
The difference between these two intermediate states is tricky. The second intermediate state is entered after the ready-but-not-playing-yet state and before the actively-playing state. The difference being that in this second intermediate state the client is already considered an active player by the rest of the server but should not get frame updates yet until it has acknowledged its last reliable data.
Communication between the server and the clients is only done using UDP datagrams. The first client/serverized version of XPilot was using TCP only, but this was too unplayable across the Internet, because TCP is a data stream always sending the next byte. If a packet gets lost then the server has to wait for a timeout before a retransmission can occur. This is too slow for a real-time program like this game, which is more interested in recent events than in sequenced/reliable events. Therefore UDP is now used which gives more network control to the program.
Because some data is considered crucial, like the names of new players and so on, there also had to be a mechanism which enabled reliable data transmission. Here this is done by creating a data stream which is piggybacked on top of the unreliable data packets. The client acknowledges this reliable data by sending its byte position in the reliable data stream. So if the client gets a new reliable data packet and it has not had this data before and there is also no data packet missing inbetween, then it advances its byte position and acknowledges this new position to the server. Otherwise it discards the packet and sends its old byte position to the server meaning that it detected a packet loss.
The server maintains an acknowledgement timeout timer for each connection so that it can retransmit a reliable data packet if the acknowledgement timer expires.
Dungeon profile (dungeon_profile.txt)
The dungeon is divided into non-overlapping square blocks of block_size by block_size grids. When rooms are placed, each is assigned a rectangular chunk of blocks, and those assignments won’t leave a block assigned to more than one room. So…
block_size affects how densely the rooms can be packed and the maximum number of rooms possible;
rooms is the number of rooms to aim for;
unusual is a measure of how likely high rarity roooms are to appear – higher values make the rare rooms rarer;
rarity is the maximum rarity room allowed with this cave profile.
These are percentage chances:
rnd of choosing a random tunnel direction (as opposed to heading in the desired direction);
chg the chance of changing direction, at any tunnel grid;
con the chance of just terminating a tunnel;
pen the chance of putting a door in a room entrance;
jct the chance of a door at a tunnel junction.
Streamers are drawn as a random walk which stops at the dungeon edge.
den is the number of grids near any walk grid to make streamer;
rng is how far from the walk those grids can be;
mag and qua are the numbers of magma and quartz streamers per level;
1/mc and 1/qc are the chances of treasure in magma and quartz.
A number of stairs is randomly placed on a level.
up is the random value used for up staircases;
down is the random value used for down staircases.
min-level is the shallowest dungeon level on which the profile can be used
alloc is used to decide which profile to use. For a profile that has a positive value for alloc, the profile will be used for a level that satisfies the profile’s min-level with a probability of the value of alloc divided by the sum of the alloc values for all other possible profiles at that level. Except for the town profile, if alloc is zero or less than -1, the profile will not be used. If alloc is -1, the profile can only be selected by hard-coded tests in generate.c for the profile selection. If those tests do not already include the profile, using a value of -1 will be the same as using 0 for alloc. The hard-coded tests currently include checks for the
town, moria, and labyrinth profiles.
name is the room name, which must match the name in list-rooms.h so the correct room-building function can be called;
rating is the rating of the room (used only for template rooms);
height is the maximum height of the room, and define how much
space is allocated for that room;
width are the maximum width of the room;
level is the minimum depth at which this room can appear;
pit is 1 if the room is a pit/nest, 0 otherwise;
rarity is the room’s rarity – normally 0, 1 or 2 (see comments about profile rarity above). Some rooms are chosen by a different means; in this case rarity is usually 0.
cutoff is used to pick between rooms once a rarity is chosen: a random value from 0 to 99 is selected and a room may appear if its cutoff is greater than that value.
It is IMPORTANT that non-zero cutoffs appear in ascending order within the rooms of the same rarity for a given profile: a room with a smaller cutoff appearing after one with a larger cutoff will never be selected.
Note that getting a smaller cave profile cutoff or room cutoff after a larger one will result in the smaller one never appearing.
Cave generation (gen-cave.c)
In this file, we use the SQUARE_WALL flags to the info field in cave->squares. Those are usually only applied and tested on granite, but some (SQUARE_WALL_INNER) is applied and tested on permanent walls.
SQUARE_WALL_SOLID indicates the wall should not be tunnelled;
SQUARE_WALL_INNER marks an inward-facing wall of a room; SQUARE_WALL_OUTER marks an outer wall of a room.
We use SQUARE_WALL_SOLID to prevent multiple corridors from piercing a wall in two adjacent locations, which would be messy, and SQUARE_WALL_OUTER to indicate which walls surround rooms, and may thus be pierced by corridors entering or leaving the room.
Note that a tunnel which attempts to leave a room near the edge of the dungeon in a direction toward that edge will cause “silly” wall piercings, but will have no permanently incorrect effects, as long as the tunnel can eventually exit from another side. And note that the wall may not come back into the room by the hole it left through, so it must bend to the left or right and then optionally re-enter the room (at least 2 grids away). This is not a problem since every room that is large enough to block the passage of tunnels is also large enough to allow the tunnel to pierce the room itself several times.
Note that no two corridors may enter a room through adjacent grids, they must either share an entryway or else use entryways at least two grids apart. This prevents large (or “silly”) doorways.
Traditionally, to create rooms in the dungeon, it was divided up into “blocks” of 11×11 grids each, and all rooms were required to occupy a rectangular group of blocks. As long as each room type reserved a sufficient number of blocks, the room building routines would not need to check bounds. Note that in classic generation most of the normal rooms actually only use 23×11 grids, and so reserve 33×11 grids.
Note that a lot of the original motivation for the block system was the fact that there was only one size of map available, 22×66 grids, and the dungeon level was divided up into nine of these in three rows of three. Now that the map can be resized and enlarged, and dungeon levels themselves can be different sizes, much of this original motivation has gone. Blocks can still be used, but different cave profiles can set their own block sizes. The classic generation method still uses the traditional blocks; the main motivation for using blocks now is for the aesthetic effect of placing rooms on a grid.
Room generation (gen-room.c)
This file covers everything to do with generation of individual rooms in the dungeon. It consists of room generating helper functions plus the actual room builders (which are referred to in the room profiles in generate.c).
The room builders all take as arguments the chunk they are being generated in, and the co-ordinates of the room centre in that chunk. Each room builder is also able to find space for itself in the chunk using the find_space() function; the chunk generating functions can ask it to do that by passing too large centre co-ordinates.
This is the top level dungeon generation file, which contains room profiles (for determining what rooms are available and their parameters), cave profiles (for determining the level generation function and parameters for different styles of levels), initialisation functions for template rooms and vaults, and the main level generation function (which calls the level builders from gen-cave.c).
See the “vault.txt” file for more on vault generation. See the “room_template.txt” file for more room templates.