Encounters

A turn in Telengard proceeds in sequential phases: the encounter phase, the looting phase, the special feature phase and the command phase.

The encounter phase handles your interaction with the dungeon's inhabitants, including combat.

Every encounter phase there is a 30% chance that you will encounter a monster.  If you do not encounter a monster, then you proceed directly to the looting phase.

Otherwise, you still have an 80% chance of avoiding the encounter if you have the Invisibility spell effect active.

If you do not avoid an encounter, then the next step is to determine what kind of monster you have encountered.

1d20 is rolled and the monster class is determined from the following table

Generally, the higher the number, the more powerful the creature.

If you have the Fear spell effect active, then monsters 1-4 are excluded from the possibilities (it will just re-roll again if it gets one).  This will have the effect of making your average difficulty monster higher, but it will protect you from Hobbits, which will frequently steal your items.

Now that the monster type has been determined, it is possible that you can sneak up on it undetected. A 1d20 is rolled, and if the value is <= your elven cloak bonus you will have the option to avoid combat entirely and go straight to the looting phase.  Essentially, once you get a +20 elven cloak, you will never have to fight again in a normal encounter if you don't want to.  You don't lose out on any loot by doing this, just whatever experience (and damage) you would have gotten during the fight.

If you have been seen or chose to fight, then the level of the monster will be determined by the following formula:

level = floor ((random ^ 1.5) * (depth * 2 + 2) + 1)

where random is a random number evenly distributed in the interval [0, 1) and depth is what dungeon level you are on.  This implies, for example, that the maximum level creature you will encounter on dungeon level 1 is level 4.  The exponentiation tends to distribute the level toward the lower end.

For example on dungeon level 1, the distribution is like this:

Level 1 Monster ~ 39.7%
Level 2 Monster ~ 23.3%
Level 3 Monster ~ 19.5%
Level 4 Monster ~ 17.5%

Here is a somewhat awkward part of the process: if the monster is undead and you have the Light effect active, then there is a 20% chance that the encounter phase will be reset back to the point where the monster class is chosen.  This leads to the possibility of sneaking up on the monster multiple times in a single encounter.  It seems to me like this check would make more sense before the dexterity roll, not after, but this is how the original source is.  I suspect this not intentional and is a minor bug, but it has no real negative impact.

At this point, the monster you have encountered is announced and becomes visible.

If you have the Time Stop spell effect active, and the monster is not immune to the effect (Dwarves, Giants, Specters, Vampires, Demons and Dragons are immune), then combat is aborted and you go straight to the looting phase after seeing your enemy.

The monster's hit points are now calculated according to the formula below:

hp = floor((random ^ 0.5) * level * type + 1)

where level is the monster's level as determined above and type is the number of the monster in the table.  This implies that the maximum health a level 1 dragon can have is 20.  The exponent serves to distribute the monster's health toward the higher end of the range.

For example, a level 1 hobbit will have the following hp distribution:

1 hp ~ 6.3%
2 hp ~ 18.7%
3 hp ~ 31.3%
4 hp ~ 43.7%

There is now a 5% chance that a special encounter will happen where the monster will either heal you, steal an item or give you an item, with equal probability.

If that 5% chance fails, these things can still happen depending on the monster type and your charisma.

Elves will heal you to full health (4 * charisma)% of the time.  If your charisma is maxed out at 18, then elves will heal you a bit over 72% of the time (since they may also heal you based on the check above). Your charisma does not affect the rate at which other monsters will heal you.

Hobbits will steal an item from you (100 - 5 * charisma)% of the time.  If your charisma is maxed out at 18, then they will steal from you only a bit over 10% of the time (since they may also steal from you based on the check above).  Your charisma does not affect the rate at which other monsters steal from you.

Dragons will try to give a piece of equipment to you if a 1d30 roll is <= your charisma.  A piece of equipment (not a consumable like a scroll or potion) will be chosen at random.  If the dragon's level is higher than that piece of equipment's bonus, then the dragon will give you a replacement for that item that is better than what you have and at most the dragon's level.  If you already have something in that slot with a bonus at or better than the dragon's level, no gift will be given, and you'll have to fight the dragon.  Your charisma does not affect the rate at which other monsters will give you gifts.

If a special event successfully occurred, then you go to the looting phase and don't need to fight. Otherwise an initiative roll is done to determine who is first to act: you or the monster.

You will go first (50 + 2 * dexterity)% of the time.

The next post will go into one aspect of combat: fighting.

Random Hell

Programming with Elm so far has been quite nice, but now that I'm starting on combat, I'm hitting an awkward spot.

The problem is that, since this is an RPG, it relies heavily on random number generation.  A random number generator can't be used directly by a pure function, so all RNG must come over a signal.

Suppose we have a simple procedure like this:

Check if the character is standing in a room with a pit feature.
If so, roll 1d20 and compare it to the sum of the character's dexterity and elven boots bonus.
If it is greater, inflict 3d6 damage on the character, check for death, and drop him a level deeper in the dungeon if he survives.

This procedure requires up to 4 rolls: 1 for the dexterity check and 3 for the damage taken.

My first pass at the problem was to have a random signal triggered every 1/100 second and a ROLL game state that waits for the next random signal and passes it to a provided continuation.

So for the above example, there would ultimately be four continuations, one for the remaining tasks to perform after each roll.  This is just a very simple procedure.  There are others that take dozens of continuations to express.  It started getting gross quickly.  A complaint against typical asynchronous programming is "Callback Hell," but this was feeling like a different incarnation of the same thing. Maybe it was "Random Hell."

I ended up making some helper functions like

roll10 : (Float -> Float -> Float -> Float -> Float -> Float -> Float -> Float -> Float -> Float -> GameState -> GameState) -> GameState -> GameState

that would handle batching up 10 rolls in a single continuation.

This made it a bit less obnoxious, but there were still problems.  Constantly updating the game state 100 times a second, which would then recalculate the scene graph and check for updates, was using enough CPU to get my laptop's fan going pretty hard.  I then sampled the graphics output only 10 times a second, which lightened the load, but introduced some noticeable delay between key presses and updates.

I ended up abandoning this idea and going with a new one that is based a bit more on real life.

Consider something like the weather.  We might model it as a stochastic process with many independent random inputs.  There is not really a concept of a single randomness generator and a sequence of "rolls" that are done.  Instead, there are many sources of randomness that all combine in parallel to influence the weather.

I took that idea and turned it into a "randomness context" or RandomCtx in the game state.  The idea was that any state transition would no longer need to only partially complete with a continuation since every possible random event would have its own randomness source's current value in the RandomCtx.

For the pit example, there would be four named independent events in the RandomCtx: for example, clumsinessAroundPits, pitReactionTime, distraction,  and groundSoftness.  clumsinessAroundPits could be the randomness source in the calculation if the character falls in or not and the other 3 can be the 3 randomness sources that determine how much damage is taken after falling in.

Now, 100 times a second, a random signal can fire, but it is folded back on itself to gradually fill up the whole RandomCtx before it loops around and starts filling up another one.  The resulting signal is filtered so only complete contexts remain, which slows the rate down to about 10 times a second currently.  Sampling the graphics output is no longer necessary, and there are no more continuations. Everything has what it needs all at once.

So far it seems a lot better, although it does make it impossible to have potentially infinite processes like the teleport procedure that keeps teleporting the character as long as he keeps failing a 20% chance roll. In principle this can continue any amount of time, although the limit of the probability approaches zero as the number of teleports approaches infinity.  I think I can give up some game features to simplify most of them, though.  I can always put the continuation-based approach back in for the features that need an unbounded number of rolls to implement.

Line of Sight and Movement

Now that the dungeon map is complete, it's time to actually explore it from the inside.

An important feature of Telengard is your character's limited vision. He can not see through doors or walls and can only clearly see the feature of the room he is in. Using a Light spell will allow him to see whether or not visible rooms have features or not, but it will not reveal what they are.

Your character can see the walls of rooms at most one step away in any direction on the same level. Since a room's south and east walls are actually the north and west walls of its adjacent rooms, this means that all rooms in the square with corner offsets at (-1, -1) and (2, 2) may need to be checked.

The presence of some walls or doors blocks the visibility of others, though.  There are two important cases:

1) An adjacent wall blocks the view of an entire quadrant of the potentially visible area:

An adjacent wall blocks the view of 5 other walls

2) An "nearby" wall blocks the view of a corner wall.

A "nearby" wall blocks the view of a corner wall

All other cases are rotations or mirror images of these.  This makes it possible to separate the drawing into four quadrants.

Drawing can be done a quadrant at a time

First the adjacent boundary of the quadrant is checked.  If it is non-empty, then draw it and you are done with that quadrant.  If it is empty, then draw the far center wall and check each of the two "nearby" walls in that quadrant.  Draw the nearby wall if it is there or corner wall it obscures if it is not.

The tricky part in practice comes from the asymmetry of rooms only storing their north and west walls. That means that quadrants 1 and 2 will be similar and 3 and 4 will be similar, with quadrants 3 and 4 needing extra offsets to the south or east when checking rooms.

The code I'm using for this now is:

There are a lot of indices and opportunities for typos or errors.  If the area to be drawn was any larger, I'd want to convert this to something more general.

The original BASIC source is similar, but draws in a different order.  This requires multiple checks of adjacent walls instead of one, but the drawing of the map is slow enough in the original game that it may be desired to draw it in a particular order for effect.

I have not implemented the Light spell, but the idea is similar for showing or obscuring room features.

Movement is simpler than line of sight.  For normal movement on a level, only one boundary needs to be checked in the direction of movement (where south and east movement is checked against the north boundary of the adjacent room to the south or the west boundary of the adjacent wall to the east).  If the boundary is not a wall, then the character can move that direction and its position can be updated.

If it is a wall, the character may still be able to pass through it if the "Astral Walk" spell effect is active and the movement doesn't take the character out of the (1, 1) (200, 200) square.  The "Pass Wall" spell can also be cast to allow movement one room in any direction that leaves the character in bounds.

Movement between dungeon levels is done via stairways, pits, elevators, teleportals, gray misty cubes and the teleport spell.

You can voluntarily ascend stairways that lead up.  Similarly, you can voluntarily descend stairways that lead down.  You can go either direction on bidirectional stairways.

When you encounter a pit, there is a chance you may fall into it if you don't have the Levitation spell effect active.  A 1d20 roll is performed against the sum of your dexterity and elven boots bonus.  If it is greater than the sum, then you will fall in and suffer 3d6 damage.  It's possible to be immune to falling in pits if the sum is high enough.  If you don't fall in, you will have the option of climbing down voluntarily.  Whether you fall in or climb down, you will end up at the same (x, y) position on the lower dungeon level.

An elevator always transports you to the same (x, y) position on the higher dungeon level.  Its effect can not be avoided, but it does no damage.

Teleportals take you to a different location with some degree of randomness.  Your new coordinates are initially computed deterministically.

x' = (x + z * 8 + y * 13) mod 200 + 1
y' = (y + z * 6 + x * 17) mod 200 + 1

For the change in the z coordinate, take the two lowest-order bits of x + y.

00 -> Go up a level
01 -> Stay on the same level
10 -> Go down a level
11 -> Go down two levels

The z value is clipped to be between 1 and 50 if the change takes it out of bounds.

Randomness enters because there is a 20% chance that you will do an additional "hop" from the new coordinates, and another 20% chance from there, etc. as part of the single teleport.  So the same teleportal is likely to leave you at the same place most of the time, but there is a chance you'll end up somewhere else.  (Note that this is a different phenomenon than a teleportal landing you on top of another teleportal for another trip.)

Gray misty cubes usually allow you to specify which level you want to travel to by entering it on the keyboard.  However, there is a 20% chance that you will be transported to a random level 1d50.  All travel by cube, random or not, is vertical only.  There is no x y motion when using a cube to move between levels.

The teleport spell allows you to specify x y and z offsets from your current position to teleport to.  If they take you out of bounds, the spell will fail.  The spell can also fail based on the distance traveled and your level.  In particular, if

sqrt (dx^2 + dy^2 + 5 * dz^2) - .1 > 5 * your_level

then you are not powerful enough to succeed.

From my reading of the source, this seems to sum up all movement related aspects of Telengard.

The Dungeon

Today I opened a git for the project at https://github.com/gbush235711/elm-telengard.  To view the interactive map, click here.

Probably the most interesting feature of Telengard is its procedurally-generated map.

It is huge.  Compared to other games of its time like Wizardry and Ultima whose dungeon levels were usually about 20x20, Telengard features 50 levels of 200x200 dungeon maps for a total of 2 million rooms.  Assuming one byte of storage per room, that is closing in on 2 MB of storage needed to hold the map.  That would have required about 12 floppy disks and a whole lot of load time and disk swapping during the game.

This is not necessary, though, since the map is not stored anywhere.  Instead, it is generated by an algorithm.

The inputs are an x, y and z coordinate, where the x and y coordinates represent a location on a particular level of the dungeon and the z coordinate is depth in the dungeon.  Moving to the right on the screen increases the x coordinate (I'll call this east) and moving down on the screen increases the y coordinate (I'll call this south).  Descending a stairway increases the z coordinate.  New players begin their journey at (25, 13, 1) and are restricted to the cuboid with corners at (1, 1, 1) and (200, 200, 50).

From a room's coordinates a value is calculated that can be used to determine what the room's boundaries are and what feature it contains.

q = x * xo + y * yo + z * zo + (x + xo) * (y + yo) * (z + zo)

where xo = 1.6915, yo = 1.4278 and zo = 1.2462.

The basic idea behind the rest of the algorithm is that the fractional part of q will vary in unpredictable seeming ways as the inputs change.

So to continue, the fractional part of q is multiplied by 4694 and truncated, resulting in a 13-bit positive integer from 0 to 4693.

h = floor(frac(q) * 4694)

The lowest order bits determine what the north and west boundaries are (the south and east boundaries are just the north and west boundaries of the adjacent rooms).  The highest order bits are used to determine if a feature is present in the room.

12 | 11 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0
     feature?        |    unused     |  west | north

00 = Empty
01 = Empty
10 = Door
11 = Wall

If the feature field is zero or > 5, then there is no feature in the room.  Otherwise q is used again to determine what the feature is.

ft = floor(frac(10 * q) * 15) + 1

This generates a number between 1 and 15 which is decoded as follows:

1 = Elevator
2 = Pit
3 = Teleporter
4 = Stairway down
5 = Altar
6 = Fountain
7 = Gray misty cube
8 = Throne
9 = Small box with buttons
10 = Elevator
11 = Pit
12 = Teleporter
13 = Stairway down
14 = Altar
15 = Fountain

Notice that cubes, thrones and boxes only occur once while the others occur twice, which will make them about half as common.

This is not quite the end of the story.  The room still needs some fix-up to match up and down staircases between levels and handle the edges of the dungeon cuboid.

West walls are added to all rooms on columns 1 and 201, and north walls are added to all rooms on rows 1 and 201.  This will effectively create a square wall surrounding the user-accessible area between (1, 1, z) and (200, 200, z).  (The west walls at (201, y, z) are (200, y, z)'s east walls and the north walls at (x, 201, z) are (x, 200, z)'s south walls.)

For dungeon levels beneath level 1, the next level up at the same (x, y) is checked for a stairway down.  If it exists, then the room's feature will be be overwritten with a stairway up so it matches.  The exception is if the room's feature is a stairway down.  In that case its feature will be a stairway that goes both up and down.

On dungeon level 1, all elevators are converted to stairways up.  (And these are the only stairways up on level 1, since no linking with stairways down on the higher level is done on level 1).

On dungeon level 50, all stairways down are removed and pits are converted to elevators.

Most of the dungeon is varied in random-seeming ways, but the algorithm does have some patterns that appear.  In particular, some rows and columns can have long stretches of the same feature.  Check out this area of the level 4 map, for instance:

Both the row and column here continue across the map with long stretches of repeated features.  Others can be found like this.  Try finding some like this using my interactive map if you want.

Next up, I will probably implement the movement and line-of-sight rules in order to allow a hero to explore the dungeon, but with no monsters or treasure yet (awwwww....).

What is this?

This blog documents my project to port the Commodore 64 version of the classic RPG Telengard to the web using the Elm programming language.

Released for the C64 in 1983, Telengard was one of the first RPGs I ever played, so it has a lot of nostalgia for me.  I also think there is merit in fully documenting an early piece of computer gaming history.  Finally, there are good technical reasons for choosing this game to port.

For performance reasons, most C64 games are written directly in assembly language, but Telengard is largely written in BASIC, with only a few minor assembly routines.  This makes it comparatively easy to reverse-engineer the code in order to do the port.  Also, since it runs on a computer with only 64K of addressable memory, it should be a relatively small project (which is good, because I have real life, too).

Elm, on the other hand, is only a couple years old.  It is a language designed to experiment with functional reactive programming (FRP) on the web.  I think statically typed functional languages like Haskell, OCaml or F# are nice because their programs are quite high-level and resemble mathematical specifications more than a list of commands.  Higher-order functions (functions that take functions as arguments) often allow you to write very concise and reusable code, and lazy evaluation can help you write code that works on infinite data structures in a natural way.

However, building user interfaces in functional languages is an area of active research.  A UI is usually modeled using mutable state that changes in response to asynchronous events like user input or a timer.  But functions that mutate state and have time-dependent behavior aren't really "pure" from the functional perspective.  FRP is one approach to working around this by allowing special functions (signals) to be functions of time.  Your program, using signals for input (like the mouse, keyboard or timer), then becomes a function of time that produces an output signal (like a scene to be drawn on the screen).  The compiler takes care of all the details of mutable state and event propagation, and your program remains a pure function.

Since I enjoy functional programming, am interested in FRP, and would like to help contribute to programming language research in my own small way, implementing in Elm seems like a good choice.

I'll document my progress here as I make it.