Skip to content


Subversion checkout URL

You can clone with
Download ZIP
Fetching contributors…

Cannot retrieve contributors at this time

201 lines (152 sloc) 8.539 kb

Design notes

Here is a rationale for some design decisions and implementation details. Not all of the sketched features are implemented and not everything is implemented as described.

Level generation

Each level is generated by an algorithm inspired by the original Rogue, as follows:

  • The available area is divided into a 3 by 3 grid where each of the 9 grid cells has approximately the same size.

  • In each of the 9 grid cells one room is placed at a random location. The minimum size of a room is 2 by 2 floor tiles. A room is surrounded by walls, and the walls still have to fit into the assigned grid cells.

  • Rooms that are on horizontally or vertically adjacent grid cells may be connected by a corridor. Corridors consist of 3 segments of straight lines (either "horizontal, vertical, horizontal" or "vertical, horizontal, vertical"). They end in openings in the walls of the room they connect. It is possible that one or two of the 3 segments have length 0, such that the resulting corridor is L-shaped or even a single straight line.

  • Corridors are generated randomly in such a way that at least every room on the grid is connected, and a few more might be. It is not sufficient to always connect all adjacent rooms.

  • Stairs up and down are placed. Stairs are always located in two different randomly chosen rooms.

Field Of View

The algorithm used is a variant of Shadow Casting. We first compute fields that are reachable (have unobstructed line of sight) from the hero's position. Later, from this information we compute the fields that are visible (not hidden in darkness, etc.).

As input to the algorithm, we require information about fields that block light. As output, we get information on the reachability of all fields. We assume that the hero is located at position (0, 0) and we only consider fields (line, row) where line >= 0 and 0 <= row <= line. This is just about one eighth of the whole hero's surroundings, but the other parts can be computed in the same fashion by mirroring or rotating the given algorithm accordingly.

  fov (blocks, maxline) =
     shadow := \empty_set
     reachable (0, 0) := True
     for l \in [ 1 .. maxline ] do
        for r \in [ 0 .. l ] do
          reachable (l, r) := ( \exists a. a \in interval (l, r) \and
                                a \not_in shadow)
          if blocks (l, r) then
             shadow := shadow \union interval (l, r)
          end if
        end for
     end for
     return reachable

  interval (l, r) = return [ angle (l + 0.5, r - 0.5),
                             angle (l - 0.5, r + 0.5) ]
  angle (l, r) = return atan (r / l)

The algorithm traverses the fields line by line, row by row. At every moment, we keep in shadow the intervals which are in shadow, measured by their angle. A square is reachable when any point in it is not in shadow --- the algorithm is permissive in this respect. We could also require that a certain fraction of the field is reachable, or a specific point. Our choice has certain consequences. For instance, a single blocking field throws a shadow, but the fields immediately behind the blocking field are still visible.

We can compute the interval of angles corresponding to one square field by computing the angle of the line passing the upper left corner and the angle of the line passing the lower right corner. This is what interval and angle do. If a field is blocking, the interval for the square is added to the shadow set.

Once we compute the reachable fields using FOV, it is possible to compute what the hero can actually see. Fields adjacent to the hero (also diagonally) can always be seen (except for walls). Fields that have light and are reachable can also be seen. We treat floor of rooms as having light, whereas corridors and rock are dark.

Walls reflect light. They can be seen only if an adjacent floor field can also be seen. In particular, walls cannot be seen when passing a corridor on the outside of a room, but can be seen from the inside of a room.

Monster movement

Not all monsters use the same algorithm to find the hero. Some implemented and unimplemented methods are listed below:

  • Random The simplest way to have a monster move is at random.

  • Sight If a monster can see the hero (as an approximation, we assume it is the case when the hero can see the monster), the monster should move toward the hero.

  • Smell The hero leaves a trail when moving toward the dungeon. For a certain timespan (100--200 moves), it is possible for certain monsters to detect that a hero has been at a certain field. Once a monster is following a trail, it should move to the neighboring field where the hero has most recently visited.

  • Noise The hero makes noise. If the distance between the hero and the monster is small enough, the monster can hear the hero and moves into the approximate direction of the hero.

Dungeon tiles

Abstract musings for now; not implemented.

The hero and the monsters (later, in short, 'monsters') can transform a tile, which can be represented by a graph, with edges labeled by prerequisites and cost of transformation. Monsters can also melee across a tile border, and it's always permitted (e.g. fighting a ghost embedded in a wall) and the kind of the tiles involved is irrelevant.

For tile design, I disregard sound and the monster's sense of hearing, because sound is best conveyed to the player through sound effects, not by painting tiles, and this requires lots of work. Acoustics is quite complex, too. Right now, sound ignores tiles and sound cues are given as text messages, e.g., when a monster attacks or is hit or when distant (but not too distant?) monsters fight or when a level is eerie silent, when the hero enters.

Monsters can interact directly and non-destructively with dungeon tiles in the following ways: they can move trough, see through, shoot through and smell (or inhale) across.

Three different kinds of things can pass through a tile:

  • objects: big, slow, pushy things (monsters passing through tiles and throwing objects from inventory across tiles)

  • projectiles and gases: monsters shooting small, fast and sharp things (arrows and bolts from the quiver) and monsters inhaling tiny, slow particles (smells, smoke, fog, poisonous gases)

  • light: monsters seeing clearly across a tile (light that just leaks through a cloth or produces a distorted image though a waterfall does not count)

For simplicity I assume that if big objects can move through, small objects can as well (no Kevlar curtains nor automatic doors). Also, I merged projectiles and gases, assuming that if small objects can get through, so can tiny objects (no self-sealing rubber walls) and the reverse (no vents in walls).

I can find no such simplifications for light. I only assume that the light that carries the picture is in itself too weak to illuminate any tile (so you can stand in a pitch dark corridor and observe a nearby sunny room). Consequently, room lighting and monster field of view calculations are very loosely coupled.

Below are tables with examples of different tile kinds.

The case of tiles that can be shot through and smelled through:

               can see through    cannot see through

can pass       floor, open door   curtain, waterfall

cannot pass    fence, grate       grate with waterfall

The case of tiles that cannot be shot through and that block smell:

               can see through    cannot see through

can pass       none               none

cannot pass    crystal, glass     rock, closed door

Note that acid pools and pits do not count as "cannot pass" tiles. First, axes and rocks can be thrown across (or into) them. Second, the hero and monsters can be pushed into them (and perish). The player cannot steer the hero into the acid pool not by physical impossibility, but by the self preservation instinct of the hero. So, an acid pool is in the same category as empty floor and it's up to the monster AI routines to check if the monster has wings (and a brain of any size) before entering. Such tiles should probably be marked as "damage this large unless flying". Similarly with water and swimming, lava pool and fire resistance, poison cloud and poison resistance, etc. No action is forbidden there, but each action has consequences.

Jump to Line
Something went wrong with that request. Please try again.