Technical Documentation

The following information is accurate as of version 0.5.0.

Topics covered in this section:

• Some algorithms used in Shuruppak
• Description of the Finite State Machine used for entity AI
• Entity senses

The field of view algorithm used in Shuruppak is based on "FOV using recursive shadowcasting" by Björn Bergström.[1] It is used to determine the player's and all entities' field of view. For the entities, this may generate input for the finite state machine that handles their AI (see below). It is also used for calculation of fields of light, even though the player is currently the only light source in the game.

For calculating a walkable path between two map coordinates, the established A* algorithm[2] is implemented. Usually the calculated path is the shortest path from the source to the target.

This algorithm is used by the Approach state to determine how to proceed to the previously detected goal. The cEscaper controller, responsible for the fleeing guard encountered right at the beginning of the game, also uses A*.

Closely related to A*, Dijkstra's algorithm[3] is another way to solve the shortest-path problem. While A* calculates exactly one path from the source to the target, Dijkstra calculates the distance from the source for every cell on the map.

In Shuruppak this algorithm is, maybe somewhat surprisingly, used to model sound propagation. In future, it might also be used for a Flee state to determine where the nearest door can be found.

I can't really remember when I first encountered the algorithm used to calculate the level heightfields. It was frequently used in the demo scene,[4] and my first implementation must have been something like fourteen or fifteen years ago. We used to refer to it as a "plasma" algorithm, but a more scientific name would be "Fractal Sub-Division" or "Diamond-Square"[5] algorithm.

The dungeon generator algorithm currently in use is based on "Random Dungeon Design" by Jamis Buck.[6] It creates rather beautiful dungeons with a nice amount of variation by creating a perfect maze first, removing and truncating some dead ends, and overlaying the maze with rooms. It has, however, two disadvantages.

Firstly, my implementation is quite slow, even though I've added a couple of speed improvements like only allowing even room heights and widths. It still takes too much time to create a level. Secondly, the generator does not allow for themed levels, something that I quite like.

A new level generator is scheduled for a later version (see Version plan).

The actions and behaviours of all entities (and items as well, even though this is currently not used in Shuruppak) is driven by a non-determinitisic finite state machine (FSM). The default AI has five possible states: Idle, Approach, Attack, Gather, and Equip. For more advanced AIs, additional states may be added.

The turn of an entity lasts until a state has called an action function that causes the entity to be rescheduled in the event queue. Transitions usually do not count into this, so it is possible for an entity to pass through several states in one turn.

Before the FSM is evoked, an observe function is called that checks for several environment conditions such as the proximity of the current enemy or the presence of treasure on the current field. These observations serve as input to the FSM. In addition to this, input may also be generated outside of the entity's turn -- for example, if the entity is damaged by another entity, this may be passed to the FSM as an observation as well.

The observe function depends on the properties for the entity. For example, INPUT_TREASURE_HERE may only be generated for an entity which has the FLAG_PICKSUP property.

This is the default state, and the one other states usually fall back to.

It processes the following inputs:

• INPUT_PROXIMITY (current enemy is next to the entity) -> Attack
• INPUT_SAW_ENEMY (current enemy is in FOV) -> Approach
• INPUT_FOUND_TRACK (current tile contains a smellable track) -> Approach
• INPUT_HEARS_SOMETHING (a sound has reached to entity) -> Approach
• INPUT_TREASURE_DETECTED (some treasure is in FOV) -> Approach
• INPUT_TREASURE_HERE (some treasure is on the current tile) -> Gather
• INPUT_PICKEDUP (items have been picked up, but not been checked yet) -> Equip

Note that there are several inputs that cause a transition to the Approach state. The transition table contains probability values for each of the possible inputs, so it is not determined which transition is chosen transition in the event of multiple inputs.

If no input is provided, the state calls AI_Amble () to perform a random step.

The Approach state tries to move the entity to the position specified by a former input. It uses the A* pathfinding algorithm to determine a possible path. Former path calculations are stored, so A* is only called when first entering this state or if the calculated path is blocked, which may be caused by another entity that has moved into the way. The path is also recalculated if the enemy is seen at a location different from the stored position.

Approach processes the following inputs:

• INPUT_PROXIMITY (current enemy is next to the entity) -> Attack
• INPUT_TREASURE_HERE (some treasure is on the current tile) -> Gather
• INPUT_SAW_ENEMY (current enemy is in FOV) -> Approach
• INPUT_POSITION_REACHED (current position is target position) -> Idle

If no input is provided, the state calls AI_Approach () to advance on the current path.

This state causes a mêlée attack move against the current enemy. Missile attacks are not included yet (see the Version plan for the implementation schedule), it is assumed that the target is within range without explicitely checking.

Attack processes the following input:

• INPUT_PROXIMITY (current enemy is next to the entity) -> Attack

Note that the self-referring transition triggered by INPUT_PROXIMITY makes a call to AI_Attack (), which causes the entity to be rescheduled in the event queue.

If no input is provided, the state falls back to Idle without any action.

This state tries to pick up treasure at the current location.

It processes the following inputs:

• INPUT_PROXIMITY (current enemy is next to the entity) -> Attack
• INPUT_TREASURE_HERE (some treasure is on the current tile) -> Gather

Note that INPUT_TREASURE_HERE causes a self-referring transition to Gather, which triggers a call to AI_Gather (). The entity's turn is ended by that call, and the entity is rescheduled.

If no input is provided, the state falls back to Idle without any action.

This state determines whether items that have been recently picked up are worth equipping. This decision is made by comparing the content of each potential slot for a new item with the new item itself. cThing.IsBetter () is called to make this comparison.

Equip processes the following inputs:

• INPUT_PROXIMITY (current enemy is next to the entity) -> Attack
• INPUT_PICKEDUP (items have been picked up, but not been checked yet) -> Equip

If no input is provided, the state falls back to Idle without any action.

The entities in Shuruppak have a couple of senses available to them that allow them to take note of their environment, and the location of the player in particular.

Not all of the following senses are available to every entity in the game. Most humanoids don't have a smelling sense developed enough to allow tracking by scent, while a bat is virtually blind; a slime blob is deaf and without sight, but has an organ that enables it to sense a heat source.

If you go through the list of senses below, you will notice that there is no tactile sense. It might be possible to think of situations where such a sense would apply in a dungeon setting, such as vibrations or such, but I don't think that it would add much really. All this sense would do, as I see it, is reduplicate some effects of the other senses already implemented.

Entities with this sense are able to detect their enemy if there is no wall or similar obstacle between them. Each entity has its own field of view (FOV) that is updated whenever the entity makes a movement. At the time being this is sufficient, as the world does not allow dynamic changes of obstructions yet. However, if doors are introduced, it will become necessary to update the FOVs of all entities whenever a door is opened or closed.

It is possible to reduce the PC's visibility by hiding in the shadows, i.e. staying close to walls and avoiding carrying a light source. Usually entities move toward the last space where they were able to observe their enemy, even if the enemy has moved away already.

Technically Sight is implemented by using the Recursive Shadowcasting algorithm. The shadowcaster takes note of entities and treasures on each of the cells covered and creates inputs for the FSM accordingly.

The actions of the PC create some noise of different amplitudes. Equipping a torch is barely audible, while yelling makes quite some noise. The noisiness of the PC's movements is determined by the equipment -- clothes generate significant less noise than a ring mail.

Sound is propagated along the rooms and corridors of the current level, decreasing in amplitude in proportion to distance from the source and with each diffraction. If an entity has the Hearing sense, it may notice a sound and try to approach the source of the sound.

The PC is not the only possible source of sounds. If guards, for example, spot the PC by sight, they shout out an alert, which other entities may hear, consequently approaching the position of the guard. PCs that don't pay attention to this may find themselves quickly surrounded by alerted enemies. Another possible use of this model is to allow the player to create distractions by creating a loud noise at some distance from the player (for example, an explosion). This feature is not implemented yet, however.

To model sound propagation, Dijkstra's Algorithm is used. Each sound has a certain volume, and the calculation of the distances is capped by that volume. Whenever the pathfinding algorithm has to change the direction from the sound source, the volume is decreased, the amount depending on the angle between the new next direction and the last direction. This approach tries to emulate the decreased amplitudes of sounds that pass around corners by reflection and diffraction.

While the model is not physically accurate, it works well enough for the purposes of the game. However, it takes up a significant amount of CPU cycles for each turn of the player.

Some ideas were taken from "Sound Propagation in 3D Environments" by Chirs Carollo.[7]

Whenever the player moves from one cell to another, a scent track is stored for the old tile indicating the direction of the PC's movement. An entity that has the Scent sense will be able to smell these tracks and thus quite effectively persue the PC around the levels, even if it will not always take the shortest path towards the player.

It is quite simple to create items like scent bombs that attract the scent marks of all surrounding tiles, thus obscuring the path the player has taken. This idea is not implemented yet, though.

Currently no attempt is made to model scent dispersion -- once a scent track is laid out, it will stay there forever, and neighbouring cells are completely unaffected. I haven't decided yet whether it is desirable to change this simple for a more complex behaviour: it works reasonably well, is simple, and takes up hardly any CPU cycles.

Infrared is a quite simple sense. It simply checks whether the heat source is within the FOV of an entity with this sense, and if so, an input for the FSM is generated to move towards the sensed position. Accordingly, the influences of shadows and light sources on the enemy's visibility are negated by infrared sensing.

It might be worthwhile remodelling this sense so that the Infrared sense is obscured by other heat sources, like a burning torch or a fireball.

Telepathy is the only sense that is not affected by level features at all. An entity with this sense is able to take notice of the enemy as soon as it is within its sensing range and will always try to approach to the exact location of the enemy. This is a sense typically found with supernatural entities such as demons or undead creatures.

The path to the target is determined using the A* algorithm. Due to the fact that the target position is frequently updated, the path has also to be recalculated regularly, which may take some CPU time. Fortunately there should not be many entities with this sense, given their considerable danger level.

[1] Bergström, Björn (2001), "FOV using Recursive Shadowcasting".

[2] Cf. Lester, Patrick (2004), "A* Pathfinding for Beginners".

[3] Cf. Morris, John (1998), "Dijkstra's Algorithm".

[4] See, for example, scene.org.

[5] Cf. Martz, Paul (1997), "Generating Random Fractal Terrain".

[6] Buck, Jamies (2003), "Random Dungeon Design".

[7] Carollo, Chris (2002), "Sound Propagation in 3D Environments". (Powerpoint presentation)