Sureal Time - Damian Bentley [Damian.Bentley@dsto.defence.gov.au].

COPYRIGHT AND LICENSE The Sureal Time algorithm is a part of Interhack. Interhack is copyright (c) 1996- 1999 by Damian Bentley. Please contact bendchon@mehta.anu.edu.au for a copy of the license. Basically feel free to copy and pass this document on - Sureal Time is something that anyone making a roguelike game can use.

INTRODUCTION This document describes the Sureal Time algorithm. What is it, and why was it developed? There is a group of games available today referred to as roguelike games. They consist of a set of levels (in most cases, dungeons), with a player running around killing monsters, performing tasks, and in general having a good time. In many cases they are text based, and almost all are single player. With single player roguelike games, movement is usually turn based. In other words, the player makes a move, and then all the monsters make their moves. In the development of a multi player version of a roguelike game this becomes a problem as will be discussed later. One solution to this problem is described here. Sureal Time is the combination of real time movement and turn based movement. It was developed by many people who have worked on Interhack, with each change or idea adding to the advantages of the algorithm. Feedback on Sureal Time is appreciated, including ways in which to improve this document, or questions that have not been answered by this document.

THE PROBLEM As it turns out, the problem is quite simple. But first we shall start with current methods in single player roguelike games. With a single player making moves, it is quite easy to create a simple loop where the player makes a move until the die, quit or save. Then everything else that happens in the game happens. That is: monsters move, checks will be made to make sure the player is alive, and so on. Given that some roguelike games require some thought at some stages (oh heck I am almost dead, what can I do), this is good because a player can stop and think for as long as they want before making a move. However when there are several players, problems crop up. If two players are in the same room, what happens to movement? Does one player make a move, then the other player? Can both players move at any time they want? If a player has a fast connection, do they move faster? What happens to players that have intrinsic speed? All these problems need to be solved in a way that is fair to players. In addition to the problem described above, there are other aspects to be looked at. For instance, what happens when a player looses a connection, and how do monsters now attack players? One of the most important parts of the Sureal Time algorithm is in handling events when a players keyboard action lags behind. What does a player do if a move is forced in Sureal Time? So the problem is this: When there are two or more players in close proximity to each other, how should movement occur?

POSSIBLE SOLUTIONS The first and most obvious solution to the problem is to use real time. Each player has a certain amount of time to make a move before all the monsters and other events occur. It does not matter if the player has a fast or slow connection. It does not matter home many players are in the game. All players are placed on the same level of game play. Real time has one major drawback: A player can not stop and think about what move to make next. If a player wishes to spend a minute looking through their inventory to see what they can drop, they are still under the influence of the real time - they could be attacked at any point in time. Another alternative is fully turn-based movement. If there are three players A, B and C, player A makes a move, then player B, and finally player C. This repeats over and over again. This allows players to stop and think about their next move. There is one very obvious problem with this solution. If player B stops and looks through their inventory, player C and player A, are kept waiting for possibly long periods of time. Both real time and turn-based movement have their advantages. Real time allows the game to flow on no matter what is happening. Turn based allows players to stop and think about how the next move should be made. So why not combine both of these solutions to form what shall be called Sureal Time. Essentially Sureal Time is like adding a real-time time limit onto turn based movement.

SUREAL TIME So now for the gory details of how to actually make Sureal Time work. First we need to look at players that are grouped, and isolated players. If a player is on a level with no other players, there is no need to use anything other than turn-based movement. The simple turn based movement is sufficient to cover this case, as it allows a player to play at their own pace. If there are two players on a level, it is more likely that they will need some sort of movement control. When and where does this take place? If one player is on one side of the level, and the other player is on the other side of the level, they are not going to interact with each other much. So even though two players are on the same level, they may not need to have movement control. When is movement control needed? As two players get closer and closer, their actions are going to start to effect each other. A player that zaps a wand or casts a spell might effect the other player. So if we determine the largest area of affect for most events a player can cause, a boundary is formed. If this boundary is 16 units, when a player is within 16 units to another player, both players now have some form of movement control. When two players are further apart than this, they live in their own little turn-based world. Now lets consider three players: A, B and C. If player A is within 16 units of player B, and player B is within 16 units of player C, but player A and player C are outside the 16 unit range, what happens? Simply all three players come under the same movement control. This is a simple case. Next, consider four players: A, B, C and D. What if player A and player B are together, and player C and player D are together. However these two groups of players are not within the same 16 units. It would not be fair to place all four players in the same movement control, so two different "forms" of movement control are used. Now we can bring this al together into a simple set of two rules:

Rule 1) A player that is outside a radius of 16 units of all other players on the same level is placed in a turn based movement. Rule 2) Players or groups of players that are within 16 units of another player or group of players are placed in the same group. These groups are "controlled movement" groups.

The next aspect of Sureal Time is what happens to players that have movement control? First of all, if no players in the controlled group move, nothing happens. This means that players could talk to each other to determine what should happen next. Players would be able to check their inventory for a particular item.

Rule 3) When groups are in controlled movement, if no players move, then no turns are made in the game.

When a player makes a move, what determines how and when other players move? The first part in answer to this question is related to the speed of the connection a player has. A player with a fast connection would be able to make moves faster. A player with a slow connection would make fewer moves. In addition to this aspect, players can sometimes be "faster" in the game: intrinsic speed. When several players are connected to a machine, the speed of a connection can be obtained. Obviously the slowest connection is the best one to select for the speed of a group of players, because it makes all movement fair on all players. If a player has an intrinsic speed, all other players' base connection speed is modified to reflect this.

Rule 4) All players have a base connection speed. In a group of players, the slowest connection speed is selected as the timeout basis for movement. Rule 5) The base connection speed is only ever increased. Rule 6) A player with an intrinsic of speed modifies the base connection speed of all other players in a group.

So what happens if a player does not move at all, and another player close to them moves? In this case the player that does not move has a certain amount of time to move after the other player has moved. Once this time has ended, they will be forced to move. This introduces a whole new problem, as to what moves are made when a player is forced to move. The moves that are forced by the computer are usually "intelligent". For example, a player that is in combat will remain in combat unless they are badly injured or in need of food badly. These rules are expanded in detail later. Once a player that is being forced to move, and has made more than thirty moves, they are automatically saved. In addition there is also the problem of a player that has lost their connection and then enters into Sureal Time. If it is know that a player has lost their connection they are automatically saved. Otherwise the player makes forced moves until they have exceeded the thirty moves limit, and are saved by default.

Rule 7) After a player in a group makes a move, all other players must move within a certain time. Rule 8) Players that do no move within the time limit are forced to move, with the computer making an intelligent move, such as attacking the last attacked monster (see forced move rules). Rule 9) If a player is forced to move more than 30 times in a row, they are automatically saved. Rule 10) If a player looses their connection, they are automatically saved. Rule 11) A player can enter into Sureal Time even if they are not moving.

In some cases a lag in the connection between the client and server could cause a players key-press to arrive at the server after a forced move has occurred. If the key-press arrives within a certain amount of time after the forced move, it is ignored. This ignore time can be set by the player.

Rule 12) After a forced move, all key-presses from the player forced to move will be ignored for an amount of time specified by the user.

Additionally there is also a reaction time involved. This is considered a "fair" time by which most players will see another player move, think of an appropriate move, and make the move. This reaction time makes a player being forced to move slower than a player moving by its self. Due to this slower speed, a player being forced to move has a tally for forced moves to be made. All moves on this tally will be made unless the player being forced to move presses a key to move.

Rule 13) A reaction time will be added to the time before a player is forced to move. The reaction time should allow for a player to see a move, think of a move, and make it. Rule 14) For every move that forces a move on another player, the player that is forced to move will have a tally kept. This tally will be reduced every time the player is forced to move. When it reaches zero no more forced moves will be made. Rule 15) A player that makes a move will reduce their forced move tally to zero.

That appears to be most of the main parts of Sureal Time. There are some additional problems that do begin to appear. For instance, what happens with monsters no there is more than one player? As said earlier, monster AI has to be much better than before, and able to cope with the problem where they might have three of four players attacking them at once. The solution is fairly simple. Every monster is "attached" to the monster that is closest to them. In the case where two players are of equal distance, one of those players is selected at random. Some people consider this to be unfair for the monster: If two players are close (but not next to) a monster, both could attack it. However if you consider both these players would more than likely be in Sureal Time, the monster would receive at least as many moves as a forced move player would. As two or more players get closer to a monster, it will become "unfair" for the monster. Monster may need to be harder to kill, or attack in a group. This aspect of the game design is left to the designer to decide. A combination of more monsters, monsters that attack in a group, and smarter monsters is recommended.

Rule 16) Every monster is attached to the player they are closest to. Rule 17) When the player a monster is attached to makes a move, the monster makes a move.

These 17 rules are a fairly good summery of Sureal Time. In addition to these rules, an appendix at the end includes a set of rules recommended for forced moves. It seems fairly simple, however putting these rules into practice is tricky, as will be seen in the example source code.

EXAMPLE SOURCE CODE Before providing sources that implement Sureal Time, there are a few things to say. To start with, this code only shows how the movement aspect of Sureal Time works. Aspects such as the monster movement are left out. In addition, rule 12 of Sureal Time (key presses ignored for a certain time) has not been delt with. This is viewed as a small addition to the source code - something has to be left out to challenge people. Writing Sureal Time code is not something to be undertaken lightly. The original version of the source code was written in Java, and did not use millisecond timers. The second version was in c/c++ and had a few bugs, and found a few problems in the original implementation. What is provided here is the third version of Sureal Time. All up development took about 20 hours. Most of the source code is documented, however the algorithm basically follows along the following lines:

1. Continue looping until input is received (from the keyboard). Simulates incoming data from players. (This looping should be based on a sleep loop. The next event to occur is set as the length of time to sleep. If no events are selected, sleep continuously until an input is received). 2. If the key-press is 'Q' quite the program. 3. If the key-press is for a player, store the keypress (the player is no longer forced to move). 4. If the sleep time has ended, check for forced moves. If there are forced moves, make them. 5. If the sleep time has ended, make moves, and update the details of players. If other players are on the timer that a player has just moved on, set the forced move timer for each player.

The first file is the Sureal Time header file "sureal.h". Cut and paste this to a file. The second file is "sureal.c" containing the main source for the algorithm. Again cut and paste into a file. Compile this code with your preferred compiler: "cc -o sureal sureal.c" Once this has been done, run the program with "sureal". When running, press 'Q' and enter to quit. In the configuration below, press '2' then enter. This simulates a move by player 2. There are three players in this example: 0, 1 and 2. 0 and 1 are on the same timer. If you enter '0', player 1 will eventually be forced to move. To see more of what is happening, recompile the source code: "cc -DDEBUG -o sureal sureal.c".

1. ifndef _sureal_h_
2. define _sureal_h_
1. include <sys/time.h>
2. include <unistd.h>

// Redefine a few of the timer functions

1. ifdef timerisset
2. undef timerisset
3. endif
4. ifdef timercmp
5. undef timercmp
6. endif
7. ifdef timerclear
8. undef timerclear
9. endif
1. define timerisset(tvp)\

((tvp).tv_sec || (tvp).tv_usec)

1. define timercmp(tvp, uvp, cmp)\

((tvp).tv_sec cmp (uvp).tv_sec ||\ (tvp).tv_sec == (uvp).tv_sec &&\ (tvp).tv_usec cmp (uvp).tv_usec)

1. define timerclear(tvp)\

((tvp)->tv_sec = (tvp)->tv_usec = 0)

// Add a few timer functions

1. define timershow(tvp)\

(tvp).tv_sec << "-" << (tvp).tv_usec

{(tvp)->tv_sec += (uvp).tv_sec;\ (tvp)->tv_usec += (uvp).tv_usec;\ if ((tvp)->tv_usec > 1000000) {\ (tvp)->tv_usec -= 1000000;\ ((tvp)->tv_sec)++; }; }

1. define timersub(tvp, uvp)\

{(tvp)->tv_sec -= (uvp).tv_sec;\ (tvp)->tv_usec -= (uvp).tv_usec;\ if ((tvp)->tv_usec < 0) {\ (tvp)->tv_usec += 1000000;\ ((tvp)->tv_sec)--; }; }

typedef struct timeval Timeval;

class CSureal { public:

```   int key;            // == 0 when no key has been pressed
int STTimer;        // Timer player is associated with
Timeval STTimeout;  // Timeout value (connection speed)
Timeval STNext;     // When the next move can be made
Timeval STForced;   // When the player is forced to move
int STForcedRemain; // Forced moves yet to be made
int STnForced;      // Number of contiguous forced moves
CSureal(int a, Timeval b) {
key = 0; STTimer = a; STTimeout = b;
STnForced = 0; STForcedRemain = 0;
timerclear(&STNext); timerclear(&STForced); };
CSureal(int a, long b, long c) {
key = 0; STTimer = a;
STTimeout.tv_sec = b; STTimeout.tv_usec = c;
timerclear(&STNext); timerclear(&STForced);
STnForced = 0; STForcedRemain = 0; };
```

};

// This is just a list of sureal time class for simulation

1. define NPLAYERS 3

CSureal list[NPLAYERS] = {

```   CSureal(1, 2, 0),
CSureal(1, 3, 0),
CSureal(2, 4, 0)
```

};

1. define MAXFORCED 10

// These are the functions for use in sureal time Timeval * sleepTime(); void keyPressed(int, int); void forcedMoves(); void makeMoves();

1. endif

1. include <sys/types.h>
2. include <sys/time.h>
3. include <iostream.h>
4. include <unistd.h>
5. include <stdlib.h>
6. include <time.h>
1. include "sureal.h"

int main() {

```   srand(time(NULL));
while (1) {
// Sleep until the next action happens
```
1. ifdef DEBUG
```       cout << "Sleeping\n";
```
1. endif
```       fd_set rfds; FD_ZERO(&rfds); FD_SET(0, &rfds);
int retval;
retval = select(1, &rfds, NULL, NULL, sleepTime());
```
1. ifdef DEBUG
```       cout << "Awake\n";
```
1. endif
```       // Deal with any key presses
if (retval > 0) {
int c;
do {
c = cin.get();
if (c == 'Q') return 0;
if (c >= '0' && c <= ('0'+NPLAYERS-1))
keyPressed(c-'0',65);
} while (c != 10);
}
```
```       // Check for forced moves
forcedMoves();
```
```       // Make other moves
makeMoves();
}
return 0;
```

}

// sleepTime returns minimum time until next expected action // it returns NULL when no action is expected Timeval st; Timeval * sleepTime() {

```   Timeval zt; timerclear(&zt);
Timeval ct; gettimeofday(&ct, NULL);
int stSet = 0;
timerclear(&st);
```
```   for (register int i = 0; i < NPLAYERS; i++) {
if (timercmp(list[i].STNext, ct, >) &&
(timercmp(list[i].STNext, st, <) || stSet == 0)) {
st = list[i].STNext;
stSet = 1;
}
if (timercmp(list[i].STForced, ct, >) &&
(timercmp(list[i].STForced, st, <)
|| stSet == 0)) {
st = list[i].STForced;
stSet = 1;
}
}
```
```   timersub(&st, ct);
```
1. ifdef DEBUG
```   cout << "Sleeping for " << timershow(st) << endl;
```
1. endif
```   if (timercmp(st, zt, <))
return NULL;
return &st;
```

}

// Player p has pressed key void keyPressed(int p, int k) {

```   // if player already pressed a key, ignore this key press
if (list[p].key != 0) return;
// The player is no longer forced to move
timerclear(&(list[p].STForced));
// Store the keypress
list[p].key = k;
// Reset the contiguous count of forced moves
list[p].STnForced = 0;
// Reset the remaining forced moves to be made
list[p].STForcedRemain = 0;
Timeval ct; gettimeofday(&ct, NULL);
cout << "Player " << p << " pressed key "
<< timershow(ct) << endl;
```

}

// Force a player to move void forcedMoves() {

```   Timeval ct; gettimeofday(&ct, NULL);
Timeval zt; timerclear(&zt);
for (register int i = 0; i < NPLAYERS; i++)
if (timercmp(list[i].STForced, ct, <) &&
timercmp(list[i].STForced, zt, !=)) {
// The player is no longer forced to make a move
timerclear(&(list[i].STForced));
// Player can move after their timeout finishes
timerclear(&(list[i].STNext));
if (list[i].STTimer != i)
```

(list[list[i].STTimer].STTimeout))

```           else
for (register j = 0; j < NPLAYERS; j++)
if (j != i && list[j].STTimer == i) {
```

(list[list[i].STTimer].STTimeout))

```                       break;
}
```
```           // Add one to count of contiguous forced moves
// If player more than MAXFORCED moves, they quit
if (list[i].STnForced++ > MAXFORCED)
cout << "Player " << I
<< " now forced to quit\n";
```
```           // Make sure no other forced moves to be made
cout << "Player " << i << " forced at   "
<< timershow(ct) << endl;
list[i].STForcedRemain--;
if (list[i].STForcedRemain < 0)
list[i].STForcedRemain = 0;
if (list[i].STForcedRemain > 0) {
Timeval ft; gettimeofday(&ft, NULL);
```

list[list[i].STTimer].STTimeout);

```               timeradd(&ft, LEADWAY);
list[i].STForced = ft;
```
1. ifdef DEBUG
```               cout << "Setting forced timer again for "
<< I << " to " << timershow(ft) << endl;
```
1. endif
```           }
}
```

}

// Make moves if player has pressed key and timeout finished void makeMoves() {

```   Timeval ct; gettimeofday(&ct, NULL);
Timeval zt; timerclear(&zt);
for (register int i = 0; i < NPLAYERS; i++)
if (list[i].key != 0
&& timercmp(list[i].STNext, ct, <=)) {
// The player is no longer forced to make a move
timerclear(&(list[i].STForced));
// Player can move after their timeout finishes
timerclear(&(list[i].STNext));
if (list[i].STTimer != i)
```

(list[list[i].STTimer].STTimeout))

```           else
for (register j = 0; j < NPLAYERS; j++)
if (j != i && list[j].STTimer == i) {
```

(list[list[i].STTimer].STTimeout))

```                       break;
}
cout << "Player " << i << " moved at    "
<< timershow(ct) << endl;
list[i].key = 0;
```
```           // If other players on our timer, force them to
// move in the near future
for (register int j = 0; j < NPLAYERS; j++)
if (j != I &&
list[j].STTimer == list[i].STTimer &&
list[j].key == 0 &&
timercmp(list[j].STNext, ct, <)) {
if (list[j].STForcedRemain < 1) {
Timeval ft; gettimeofday(&ft,
```

NULL);

```                           timeradd(&ft,
```

list[list[j].STTimer].STTimeout);

```                           timeradd(&ft, LEADWAY);
list[j].STForced = ft;
}
list[j].STForcedRemain++;
```
1. ifdef DEBUG
```                       cout << "Setting forced timer for "
<< j << " to "
<< timershow(ft) << endl;
cout << "\tForced count: "
<< list[j].STForcedRemain
<< endl;
```
1. endif
```                   }
}
```

}

APPENDIX A - SUREAL TIME RULES The following are all of the Sureal Time rules without any explanations:

Rule 1) A player that is outside a radius of 16 units of all other players on the same level is placed in a turn based movement. Rule 2) Players or groups of players that are within 16 units of another player or group of players are placed in the same group. These groups are "controlled movement" groups. Rule 3) When groups are in controlled movement, if no players move, then no turns are made in the game. Rule 4) All players have a base connection speed. In a group of players, the slowest connection speed is selected as the timeout basis for movement. Rule 5) The base connection speed is only ever increased. Rule 6) A player with an intrinsic of speed modifies the base connection speed of all other players in a group. Rule 7) After a player in a group makes a move, all other players must move within a certain time. Rule 8) Players that do no move within the time limit are forced to move, with the computer making an intelligent move, such as attacking the last attacked monster (see forced move rules). Rule 9) If a player is forced to move more than 30 times in a row, they are automatically saved. Rule 10) If a player looses their connection, they are automatically saved. Rule 11) A player can enter into Sureal Time even if they are not moving. Rule 12) After a forced move, all key-presses from the player forced to move will be ignored for an amount of time specified by the user. Rule 13) A reaction time will be added to the time before a player is forced to move. The reaction time should allow for a player to see a move, think of a move, and make it. Rule 14) For every move that forces a move on another player, the player that is forced to move will have a tally kept. This tally will be reduced every time the player is forced to move. When it reaches zero no more forced moves will be made. Rule 15) A player that makes a move will reduce their forced move tally to zero. Rule 16) Every monster is attached to the player they are closest to. Rule 17) When the player a monster is attached to makes a move, the monster makes a move.

APPENDIX B - FORCED MOVEMENT RULES The following are a relatively "intelligent" set of rules to follow when a player is forced to move. It is more than likely that other rules may need to be included. I would like to hear comments on this section:

Rule 1) When no other rules apply, a player repeats their last action. A player that was moving, continues to move, a player that was attacking, continues to attack. Rule 2) It is not safe for a player to attack or move if they are hungry, or lacking hit points. Rule 3) A player is lacking hit points if they have less than 10% or their total. Rule 3) If a player is confused, stunned, or blind, they wait unless the opportunity exists to attack safely. Rule 4) A player that is not in attack mode, and is hungry eats. Rule 5) A player that is almost fainting eats. Rule 6) If a moving player comes to a door they open it (open, lock pick, keys, kick). Rule 7) If a moving player comes to a dead end, they search for 15 units of time until something changes. If nothing changes, they player resumes in the opposite direction. Rule 8) If something changes while searching the player continues in that direction. Rule 9) A player that can not move left, goes forward. A player that can not move forward, moves right. A player than can not move right turns around and goes back the way they came. Rule 10) If a moving player enters a room, they will seek out the best items from any objects. Rule 11) A moving player will try to remain in Sureal Time, following other players. Rule 12) If a player sees a monster it will attack at long distance first (throwing weapons, potions, zapping known wands). Rule 13) While in close attack, monsters will use weapons, spells, wands etc. The method of attack selected is that which is considered best for the situation. In most cases weapon based attack should be selected as the best method. However a wizard with 10% failure rate on magic missile may opt to use that spell. Rule 14) Players forced to move will not use objects being carried unless for offensive or defensive purposes. If an object is unknown, it will not be used.

Monsters Who Carry - James Burton [burton@cs.stanford.edu].

In _Civilization and its Discontents_, Sigmund Freud describes Man as a kind of "cybernetic god" -- by ourselves we are weak, vulnerable, and impotent, but with our machines we can move mountains, build or destroy worlds, and make Roguelike games in our spare time. This is a vitally important observation in Roguelikes, where the power of a character can be summed up in two things: a) Their own statistics, and b) what they're carrying. A mighty wizard with Raal's Tome of Destruction is a lot more powerful than one without, as is a plevel 50 warrior with Ringil and Speed Boots a lot more frightening than a plevel 50 warrior with chainmail and a whip.

And so it should be with monsters, and is in some (NetHack) games. That gnome is easy bait -- until he fires up his lightsaber.

You should *strongly* consider allowing monsters both to carry and _use_ objects, and to drop them afterwards. For one, it provides a lot more variety. Second, it adds realism, in that it makes creatures with *hands* much more intimidating. In Roguelike World, a sabre-tooth tiger is more dangerous than a small kobold because it is faster and stronger. In the Real World (or at least the version that has small kobolds in it), our kobold is the deadlier because he could carry *and use* something much nastier than sabre-teeth. Third, it adds variety. Having hundreds of monsters is cool. But if you let them hold an item (and a good item system will have thousands of different items, by combining different traits together, as in the "Whip of Freezing" and so on), then you have hundreds of thousands of combinations. Let them hold multiple items, and pick new items up, and the variety is astronomical -- and has a real impact on gameplay.

Now for some coding ideas. In my own game (not yet released), I have decided that creatures should have the same ability to wear/wield/carry items as the player -- unless it is biologically or mentally unable to (more on this below). Why is it that in so many games the player is a walking blacksmith's shop, but the creatures seem to have no material needs except bags full of gold? Since I also leave open the ability to hold one item inside another item, and even put creatures into items (like tigers into cages), I find a *tree* structure to be most efficient.

Everyone learns (or should learn) all about making trees in their first computer course, and all about the optimising of trees in their first theory course, so I won't go too deep into the data structure (look on the Internet if you need it). For this article, I am defining a tree as a collection of objects such that each object has exactly one "parent" object, except for one object which is the "root" of the tree. A parent can have any number of children, including none. The resulting shape looks like a tree, hence the name.

I like objects, so that's how I define my structures. The first object I need is a Unit, which is my name for an "Item or Creature". So into Units we put information that applies to both: weight, name, etc. Actually I implement these not as data but as virtual functions along the lines of getWeight() and getName() -- this latter method is more "OO", but I could understand if you used variables instead for the sake of efficiency. I also keep a small array of all the possible child nodes -- I use an array because I keep an arbitrary limit of no more than 20 child nodes, and though a list would be more efficient it's also complicated. I then subclass this into Items and Creatures. You might think of subclassing items into Weapons, Armor, and so on, but I didn't find it worth it. It *is* worth it to subclass "Creature" into "Player", though. So you get an object definition something like this:

OBJECT: Unit {

1. Array of child units

UnitPtr children[MAX_UNITS]

1. Keep reference to the parent too -- this is technically unnecessary and

requires a bit more care in your

1. tree-manipulation functions, but you'll thank me the first time you have a

unit and want to know what

1. its parent is. If parent is NULL then the unit is on the map somewhere.

UnitPtr parent

1. Some tree functions you should implement

detach() # Detach node from its parent destroy() # Destroy this and all children attach(UnitPtr newParent) # Attach to another node, detaching if necessary replace(UnitPtr newUnit) # Put the new unit in this position, and delete self

1. Common unit functions

getWeight() # Object weight getTotalWeight() # Weight of object and all its children getName() . }

OBJECT: Creature EXTENDS Unit { move() # Move the creature getHPs() # Get creature hit points . }

OBJECT: Item EXTENDS Unit { itemType # It's more OO to subclass items, but what the heck damage # In the case of weapons isWielded # Boolean, if true then the parent (a creature) is wielding this. The value is . # meaningless unless the parent is a creature . }

I won't get into all the cool things you can do with trees: how easy it is to move nodes around, and recurse or iterate over them, and so on -- instead, I will recommend that you put some time into adding some good tree manipulation functions, probably build right into the Unit class (but *not* as virtual methods, as they shouldn't need to be overridden, and you really want these to be efficient as you'll be using them a lot). The four functions I stuck into the Unit object above should be a good start. Do make sure if you have a limit on child nodes that methods like "attach" can fail gracefully, because at some point something in your program is going to try to exceed that limit (you could of course always test before attaching a new child, but why bother when you can just put the test in the attach routine itself?).

I will point out what I found most useful about trees in a roguelike game: that you can deal with only the root node, and it will affect all the child nodes. For example, let's say I drop a chest. That means detaching the chest from my own inventory hierarchy (so it becomes the root node of its own tree), and put it on the ground (the map, of course, can hold pointers to Units -- that's how creatures and items are held on the map!). The cool thing: all the child nodes go with it, so the items in the chest are moved automatically, in constant time!

Now how do we return this to the question of monsters? In my trees, there are clearly four kinds of relationships: an item can contain an item, an item can contain a creature, a creature can contain an item, and a creature can contain a creature. I interpret each of these differently. An item containing an item I think of as physical containment -- like a sword in a chest, a scroll in a bag, and so on (I suppose I could also see it as a battery in a flashlight or a bullet in a gun, but there aren't such things in my game). An item containing a creature refers to some kind of caging -- a bird in a birdcage or a ghost in a magic ghosttrap, etc. A creature containing an item is obvious -- that's the creature's inventory! And a creature containing a creature means the contained creature is swallowed (or would; I don't actually use this anywhere in the game).

So what happens if a monster is killed? Simple: he simply transforms into (is replaced with) a corpse, which is an item. Or more specifically, a

• container* item, like a chest or bag. See? All the things he is carrying,

by the definitions we're using, become items contained by the corpse. This way we avoid the clutter you get in, say, Angband, where the last act of a powerful unique is apparently to throw his belongings all over the room (since you don't have stacks of items on the floor in Angband). Getting items from the corpse is handled just like getting them from a treasure chest (and can be quite as dangerous).

So now we've handled data structures, but how do we decide what monsters actually carry? There are three relationships a monster can have with an item, and for each of them I have a flag. First, is it possible for the monster to carry it? This usually involves having hands, though I suppose telekinesis works. Second, where applicable, is it possible for a monster to use it? Helmets require appropriately-shaped heads, scrolls require the ability to read, etc. Third, is there a chance that the monster will start out with it?

I implement these first two as flags, and the third as a pair of numbers: the average number of items the creature has (i.e. "from 0 to 6"), and the dungeon level equivalent of the items (i.e. a kobold only gets the kind of items you find on level 1). The items are generated randomly when the monster is created, plus a few rules are applied to preserve sanity (no creature carries more than one armor or more than two weapons; only unique creatures can start out with artifacts, etc.) Et voila! I also keep a flag to let some monsters carry only one item, and can't fight while carrying -- this is great for animals that can only carry things in their mouths.

Of course, mosters should be able to acquire objects, and perhaps steal them as well (hello Green Glutton Ghosts or the Nymphs of Nethack). That is easy enough to manage, and also lets monsters get items way out of their depth ("The kobold hits! Snicker-snack!"). Again, sanity should be applied -- monsters should have no better idea of what an item is than the player would (depending on how you handle identification), they should not be able to touch items inimical to themselves (evil monsters should not touch holy weapons, goblins are not likely to go around swinging Orcrist), and so on.

Care must be taken that game-balance is not hurt. The biggest danger is when small creatures have powerful items. It's very cool when our small kobold has a big weapon, but if you can stand a few meters away and magic missile him to death, then you have a free major item. And in most roguelikes a really good artifact would increase the power of a low-level character many times over. Luckily, a well-balanced and realistic monsters definition file will handle most of that. Normally the little guys won't get the big weapons, and if they occasionally do that's just interesting, and good (or disasterous) luck for the player -- much like Wormtongue throwing the Palantir at Gandalf without knowing what it was. The other thing is that the tough guys are going to be a *lot* tougher in this system (which by my book is a good thing). Imagine an Angband Nazgul if he was also guaranteed to be carrying a few "good" or "excellent" items on him.

The rest you can think of yourself: like destroying the other creature's items and so on. Heck, if a fire-breathing dragon can burn up all my scrolls, I want to be able to destroy his scrolls with a wand of fire. I would also point out that the more things a monster carries, the more fun it is to play a thief. On the flip side, you could make a really good-aligned character like a paladin very strong, but unable on moral grounds to remove items from corpses.

Compressing Savefiles - Ross Morgan-Linial [rmorgan@fhcrc.org].txt

(or, It's a Big World Out There)

It's fairly easy to write a simple algorithm for reading and writing savefiles. Just dump all your data structures in a fixed order, and then read them in later (although, if your data structures have pointers, it's a bit more complicated - but that deserves another article). However, the problem with this simple algorithm is that the savefiles can be _big_. If you plan to save 100 levels, each 20x80 tiles, and each tile takes 10 bytes, that's 1.6 megabytes right there... and that's just for the maps.

A Solution: Run-Length Encoding

Fortunately, there is a very simple algorithm that can achieve enormous compression on the average map. That algorithm is called run-length encoding. The basic idea is simple. Most of the tiles in your dungeon will be walls or floors, and these walls and floors will tend to be grouped together in blocks. Instead of writing one byte to indicate the type of each tile in your dungeon, you use two bytes to indicate the type of a sequence of tiles. The first byte indicates how many consecutive tiles (in a left-to-right, top-to-bottom traverse of the map) are the type indicated by the second byte. Therefore, the basic algorithm to compress your dungeon is simple:

Algorithm 1: Compressing a dungeon, take 1

```  For each tile in the dungeon, in some order
If that tile is the same as the last tile and the tile count is < 255
Increment the tile count
Otherwise
Output the tile count and the type of the last tile
Set the tile count to 1
Output the tile count and the type of the last tile
```

The algorithm to decompress it is even simpler:

Algorithm 2: Decompressing a dungeon, take 1

```  Until you reach the end of the dungeon
For a number of tiles equal to the run count
Set that tile to the tile you read
```

Fixing the Problems

If you try the preceding algorithms, you'll find that they work well, but there is some room for improvement. Some data in each tile can be compressed more effectively than with RLE, and some data just isn't amenable to RLE encoding and tends to break the coding into a succession of one-tile entries.

Most games keep the data about in a monster's or object's location in two places: in the data structure representing the monster or object, and in the data structure representing the map. Because the information about the monsters and objects on the map has to be saved anyway, we can completely omit the monster and object information from the map portion of the savefile. When we read in the savefile, we will reconstruct the data about monsters and objects on the map from the data about the monsters and objects themselves. This will save two two-byte or four-byte fields, and allow the RLE algorithm to compress the map more effectively.

Some data fields usually have a constant value, or a value that can be easily computed from other values in the tile structure. We can save space, and make the RLE more effective, by omitting these values and only saving the exceptional values in the savefile. The easiest way to do this is emit a string of X-Y-value groups into the savefile, followed by a sentinel element:

Algorithm 3: Saving sparse data

```  For each tile in the dungeon, in some order
Compute the expected value of the data
If the value is not the expected value
Emit the X and Y coordinates of the current tile
Emit the actual value of the data
Emit a sentinel value larger than any possible real X
```

```  For each tile in the dungeon, in some order
Set the value of the data to the expected value
Repeat until the sentinel is read
If the X coordinate is the sentinel, stop
Set the data at the indicated tile to the real value read
```

An alternative, if exceptional values are more common, is to emit a bit-packed array (bit map) indicating which tiles have unusual values, followed by the values in order.

One final trick, which might reduce the size of savefiles, is to run-length encode the various fields of the map data separately. If the fields don't tend to have the same runs, this significantly reduces the size of the RLE data. On the other hand, it might not. The only way to find out is to try it and see.

Stacktraces in gcc-compiled programs in Win32 and Linux-executables - Jurriaan Kalkman [thunder7@xs4all.nl].txt

============================================================

Copyright (c) 2000 Jurriaan Kalkman Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.1 or any later version published by the Free Software Foundation; with no Invariant Sections, with no Front-Cover Texts, and with no Back-Cover Texts. A copy of the license is available on the Internet at http://www.gnu.org or is available on demand from the author.

============================================================

So you've made this great rogue-like, and it seems to crash now and again. Perhaps you're not as great a coder as you thought :-). Or, you develop it under GNU/Linux, and most other people run it under Windows, and it crashes.

If it crashes and you have the debugger GDB handy, you can type 'bt' to get a nice stack-trace, so you can see what routines called the one that caused the crash. This is often very useful information. Consider the situation where you have a routine that changes some part of the dungeon (lighting a square for example) and you find out that once in a while it is called with an x-coordinate of 0, and this causes a crash. It would be very useful to know from where this routine is called, particularly if it is called from 60 places or so and you cannot check them all.

There is a solution for that, if you use gcc. It works under any compiler that is gcc-based, but requires signals to be available. These environ- ments include any unix-system I know of, DOS (DJGPP) and win32 (cygwin32). OS/2 has a gcc-compiler, but it doesn't support signals, I've been told.

1 Introduction 2 Signal handlers 3 What is on the stack 4 When to stop 5 Coding it

``` 5.1 The windows 'get-an-address-off-the-stack macro'
5.2 The decoding routine for the addresses on the stack
5.3 The signal handler
5.4 Compilation
```

6 Sample output

1 Introduction

These functions allow you to determine which functions were calling the crashing function.

All examples and files are taken from Angband/64, which can be found at http://www.xs4all.nl/~thunder7. Added to this article are bits and pieces of files in the source-archive. If you want to know more, read the whole source. Compile it, experiment with it, then go code your own.

The beauty of this solution is that you can let your program read it's own executable-file, and use the debug-information that is in there to display what was going on at the moment of the crash. This in contrast with my earlier attempt at this, where you needed an extra file, gene- rated at compile time, to translate addresses into function names.

2 Signal handlers

First of all, you need a signal-handler for signals like

SIGFPE (floating point error) SIGKILL (^c or something like it) SIGSEGV (pointer gone wild) etc.

3 What is on the stack

Then you need to find out what are the addresses on the stack. This looks simple:

these functions return 32 bits addresses. (except if you're on Alpha :-) )

4 When to stop

now the problem is when to stop, or, how deep is the stack?

In GNU/Linux and DOS, this is simple: as soon as __builtin_return_address returns 0, the end is reached.

In win32 (or at least the cygwin32 cross-compiler I use here), this is more of a problem, I've found out that there is no 0 at the end, it simply crashes. So I've used the second builtin function there, called __builtin_frame_address, and with trial and error found out that it seems to work quite well if you make sure you only follow __builtin_return_address as long as the upper 2 bytes from __builtin_return_address match the upper 2 bytes from __builtin_frame_address. This means you stay in the same frame. Now I'm no expert, and I cannot explain why this is so. It works for me, YMMV.

5 Coding it

Grabbing these addresses should not be done with subroutines, because that would introduce another frame on the stack :-). So there are some huge macro-definitions needed.

Then we borrow (a lot of) code from the addr2line program in the GNU binutils suite. The addr2line program prints out the name of the source- file, the exact linenumber and the name of the function, when you supply the name of the executable and the address. Both are known, so we are in business.

I suggest first reading the source for the addr2line program. It's only about 350 lines, and is really easy to understand. Then you'll be able to see that all I added in files.c is just a simplification: I've deleted the argument/option parsing, I've deleted the logic that let addr2line handle files in a non-standard object-format, I've copied together some procedures, and now there is just something like 85 lines left.

1. ifdef WINDOWS
```  if (baseframe == 0L) \
{ \
baseframe=((baseframe & 0xffff0000L) >> 16); \
dlog(DEBUGSAVE,"files.c: handle_signal_abort: baseframe now %08lx\n",
```

\

```          baseframe); \
} \
if (continue_stack_trace && \
```

== baseframe) && \

```      ((X) < MAX_STACK_ADDR)) \
{ \
dlog(DEBUGSAVE,"files.c: handle_signal_abort: stack %d %08lx frame %d
```

%08lx\n", \

```                     (X), __builtin_return_address((X)), (X),
```

```  } \
else if (continue_stack_trace) \
{ \
continue_stack_trace = FALSE; \
}
```
1. endif

note that we use baseframe to check if we stay in the same frame. This is based upon experimentation at my side.

```  if (continue_stack_trace && ((unsigned long)__builtin_frame_address((X))
```

!= 0L) && ((X) < MAX_STACK_ADDR)) \

```  { \
dlog(DEBUGSAVE,"files.c: handle_signal_abort: stack %d %08lx frame %d
```

%08lx\n", \

```                     (X), __builtin_return_address((X)), (X),
```

```  } \
else if (continue_stack_trace) \
{ \
continue_stack_trace = FALSE; \
}
```
1. endif

5.2 The decoding routine for the addresses on the stack

```  Copyright 1997, 98, 99, 2000 Free Software Foundation, Inc.
Contributed by Ulrich Lauther &ltUlrich.Lauther@zfe.siemens.de>
```
```  This file is part of GNU Binutils.
```
```  This program is free software; you can redistribute it and/or modify
the Free Software Foundation; either version 2, or (at your option)
any later version.
```
```  This program is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.
```
```  You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */
```

/* Look for an address in a section. This is called via bfd_map_over_sections. */ static void find_address_in_section (bfd *abfd, asection *section, PTR data) {

``` bfd_vma vma;
bfd_size_type size;
```
``` if (dump_found) return;
```
``` if ((bfd_get_section_flags (abfd, section) & SEC_ALLOC) == 0)
{
return;
}
```
``` vma = bfd_get_section_vma (abfd, section);
if (dump_pc < vma)
{
return;
}
```
``` size = bfd_get_section_size_before_reloc (section);
if (dump_pc >= vma + size)
{
return;
}
```
``` dump_found = bfd_find_nearest_line (abfd, section, dump_syms, dump_pc -
```

vma, &dump_filename, &functionname, &dump_line); }

```  file_name:line_number and optionally function name.  */
```

/* changed, it takes a single address as argument */ static void translate_address (bfd *abfd, int address,

```                              char *function_name, char *source_name, int
```
• source_line)

{

```  char addr_hex[100];
```
```  dump_pc = bfd_scan_vma (addr_hex, NULL, 16);
```
```  dump_found = false;
```
```  if (! dump_found)
{
strcpy(function_name, "??");
strcpy(source_name, "??");
*source_line = 0;
}
else
{
if (functionname == NULL || *functionname == '\0')
{
strcpy(function_name, "??");
if (dump_filename == NULL)
{
strcpy(source_name, "??");
}
else
{
strcpy(source_name, dump_filename);
}
*source_line = dump_line;
}
else
{
strcpy(function_name, functionname);
if (dump_filename == NULL)
{
strcpy(source_name, "??");
}
else
{
strcpy(source_name, dump_filename);
}
*source_line = dump_line;
}
```
```     /* fflush() is essential for using this command as a server
with line number information, processing one address at a
time.  */
}
fflush (stdout);
```

}

void dump_stack(void) {

```  s16b i;
bfd *abfd;
char **matching;
long storage;
long symcount;
```
```  bfd_init();
```
```  /* clean the stack addresses if necessary */
for (i=0; i < MAX_STACK_ADDR; i++)
{
}
```
```  handle_stack_address(0);  handle_stack_address(1);
```

```  handle_stack_address(4);  handle_stack_address(5);
```

```  handle_stack_address(8);  handle_stack_address(9);
```

```  handle_stack_address(12); handle_stack_address(13);
```

```  handle_stack_address(16); handle_stack_address(17);
```

```  handle_stack_address(20); handle_stack_address(21);
```

```  handle_stack_address(24); handle_stack_address(25);
```

```  handle_stack_address(28); handle_stack_address(29);
```

```  handle_stack_address(32); handle_stack_address(33);
```

```  handle_stack_address(36); handle_stack_address(37);
```

```  /* dump stack frame */
while ( (i >=0) && (stack_addr[i] == 0)) i--;
```
```  if (i < 0)
{
dlog(DEBUGALWAYS,"files.c: dump_stack: unable to get any addresses
```

off the stack.\n");

```     return;
}
abfd = bfd_openr (argv0, NULL);
```
```  if (abfd == NULL)
{
cptr errmsg = bfd_errmsg( bfd_get_error() );
dlog(DEBUGALWAYS,"files.c: dump_stack: abfd == NULL; bfd error =
```

%s\n", errmsg);

```     return;
}

if (bfd_check_format (abfd, bfd_archive))
{
cptr errmsg = bfd_errmsg( bfd_get_error() );
dlog(DEBUGALWAYS,"files.c: dump_stack: bfd_check_format return-value
```

!= 0; bfd error = %s\n", errmsg);

```     return;
}

if (! bfd_check_format_matches (abfd, bfd_object, &matching))
{
cptr errmsg = bfd_errmsg( bfd_get_error() );
dlog(DEBUGALWAYS,"files.c: dump_stack: format doesn't match; bfd
```

error = %s\n", errmsg);

```     return;
}

if ((bfd_get_file_flags (abfd) & HAS_SYMS) == 0)
return;
```
```  storage = bfd_get_symtab_upper_bound (abfd);
if (storage < 0)
{
cptr errmsg = bfd_errmsg( bfd_get_error() );
dlog(DEBUGALWAYS,"files.c: dump_stack: storage < 0; bfd error =
```

%s\n", errmsg);

```     return;
}

dump_syms = (asymbol **) xmalloc (storage);

symcount = bfd_canonicalize_symtab (abfd, dump_syms);
if (symcount < 0)
{
cptr errmsg = bfd_errmsg( bfd_get_error() );
dlog(DEBUGALWAYS,"files.c: dump_stack: symcount < 0; bfd error =
```

%s\n", errmsg);

```     return;
}
```
```  for (; i>=0 ; i--)
{
{
char function_name[2048];
char source_name[2048];
int source_line;

```

source_name, &source_line);

```        dlog(DEBUGALWAYS,"files.c: stack_dump: stack frame %2d address
```

%08lx = %s (%s %d) \n",

```                         i, stack_addr[i], function_name, source_name,
```

source_line);

```     }
}
```

/* and cleaning up afterwards */

```  if (dump_syms != NULL)
{
free (dump_syms);
dump_syms = NULL;
}
```
```  bfd_close (abfd);
```

}

5.3 The signal handler

Now define some signal handlers like this:

1. ifdef SIGFPE
```   (void)signal(SIGFPE, handle_signal_abort);
```
1. endif
1. ifdef SIGILL
```   (void)signal(SIGILL, handle_signal_abort);
```
1. endif
1. ifdef SIG

TRAP

```   (void)signal(SIGTRAP, handle_signal_abort);
```
1. endif
1. ifdef SIGIOT
```   (void)signal(SIGIOT, handle_signal_abort);
```
1. endif
1. ifdef SIGKILL
```   (void)signal(SIGKILL, handle_signal_abort);
```
1. endif

and define a function handle_signal_abort like:

static void handle_signal_abort(int sig) {

```  bool                 save_ok = FALSE;
```
```  FILE                *fff = NULL;
char                 filename[1024];
s16b                 i;
bool                 dump_ok = FALSE;
```
```  /* Clear the bottom lines */
Term_erase(0, 20, 80);
Term_erase(0, 21, 80);
Term_erase(0, 22, 80);
```
```  /* Give a warning */
Term_putstr(1, 20, -1, TERM_RED, "You suddenly see a gruesome SOFTWARE
```

```  Term_xtra(TERM_XTRA_NOISE, 0);
```
```  /* Access the help file */
strcpy(filename, ANGBAND_DIR_USER);
strcat(filename, "crash.txt");
```
1. if defined(MACINTOSH) && !defined(applec)
```  /* Global -- "text file" */
_ftype = 'TEXT';
```
1. endif
```  /* Drop priv's */
safe_setuid_drop();
```
```  /* Open the non-existing file */
fff = my_fopen(filename, "w");
```
```  /* Grab priv's */
safe_setuid_grab();
```
```  /* Invalid file */
if (fff)
{
```

following\n");

```     fprintf(fff,"information to the maintainer (email to
```

thunder7@xs4all.nl)\n\n");

```     fprintf(fff,"\nAlso, please add any information you feel is
```

relevant:\n");

```     fprintf(fff,"especially, what were you doing at the time this
```

happened?\n\n");

```     fprintf(fff,"Angband/64 beta %d release %d (%d.%d.%d)\n\n",
VERSION_BETA, VERSION_RELEASE, VERSION_MAJOR,
```

VERSION_MINOR, VERSION_PATCH);

```     fprintf(fff,"STACK TRACE:\n\n");
```
```     dump_stack();
```
```     fprintf(fff,"\nCONFIGURATION:\n\n");
fprintf(fff, "debuglevel 0x%08lx\n", debuglevel);
```
1. ifdef ALLOW_COMPRESSION
```     fprintf(fff,"compression support compiled in\n");
```
1. endif

and so on. An emergency-save routine is also nice to have here! At the end, make sure your program ends with something like exit(1).

5.4 Compilation

You'll need to make sure bfd.h can be found when compiling, and link with -lbfd -liberty. I won't deny that the last two can be a bit of a bother. They come out of the binutils-suite, which can be found on any gnu-repository. They are, however, *not* included in binary distributions of binutils, you'll have to build your own from source. On GNU/Linux building binutils is straightforward (./configure; make; make install) but I had to go to some lengths to get those libraries for go32 and cygwin32. Ah well, sensible people use GNU/Linux anyway.

6 Sample output

Your game has just crashed. Please forward the following information to the maintainer (email to thunder7@xs4all.nl)

Also, please add any information you feel is relevant: especially, what were you doing at the time this happened?

Angband/64 beta 5 release 5 (2.7.10)

STACK TRACE:

CONFIGURATION:

debuglevel 0x80000040 compression support compiled in using other RNG monster flow support compiled in

DISPLAY MODULES:

main-xaw compiled in main-x11 compiled in main-gcu compiled in

OPTIONS SET:

Quick messages Display coordinates on screen Print experience needed to advance Auto open doors when colliding Pick things up by default &ltetc. Angband/64 has a *lot* of options.>