View source for User:Duerig/Archive5

= Roguelike_Skeleton_Blah_Documentation_Erik_Inge_Bols???_knan_mo.himolde.no_.txt =

------------------------------------------------------------
NB. If you wish to get hold of Bzip2, please pop along to...
http://www.muraroa.demon.co.uk/
------------------------------------------------------------

Okay. Basically, what works well as of the current version is map
generation, line of sight (everything not in LOS is greyed out) and config
file for key setup. The player, item and inventory structs and functions
have been started. Spells, monsters and combat are just stubs.

- Map generation is by far the most complex part of this. The GenerateRoom
routine (in map-internal.c) creates weird cave-looking rooms by a
conceptually simple method:

 //pseudocode
 while (room < target_room_size and squares_left)
  pick_random_square_from_stack_and_delete_from_stack
  add_surrounding_squares_to_stack

(actually, I use one stack and an array of pointers to places in that
stack, but the above is the underlying principle)

- config.c implements a simple parser for configuration files, that
probably can be extended to other uses than key configuration.

- The Player and Creature structs have identical upper parts, so that
one can use most routines for both by typecasting (Creature)player ...

- Almost everything in the game is in a linked list or contains one or
more linked lists. See lists.c and lists.h .

- One of the last things I did to this source was rewriting many routines
to use a "tagitems" calling convention, that is:

  createBlah (TAG_UGLINESS, 500, TAG_MONTY_PYTHON_FACTOR, 2.1);
   // (identifier, value) pairs, instead of fixed parameters that will
   // change dozens of times during developement

- creature.c allocates the correct amount of memory for a creature, but
does nothing more as of yet.

- pl_item.c and item.c is in its infancy. It has a demo item defined, and
allocates it to the player, and successfully displays it in the player's
inventory. Fragile. But item.h is quite well-developed, and ought to give
anyone ideas...

- lists.c contains your basic single-linked lists code + the NextTagItem
code.

- magic.c, help.c, combat.c, timer.c are just stubs.

- output.c / output.h / ncurses.c  encapsulates most of the
ncurses-specific stuff for easy porting.

- map.c ... Map_Scanfor was designed to scan for any interesting parameter
inside maps, but are currently not used for much besides finding a good
place for a corridor. map.c contains all routines that should be visible
outside map generation. GenerateCorridor currently uses a hit-and-miss
approach (copy map to temp_map -> run generatecorridor -> if grind to a
halt, try again -> if not copy temp_map to map) and can be improved much,
I suppose.

- types.h defines own UBYTE, BYTE, ULONG, LONG etc. types, also for easy
porting.

- I'm currently undecided on what's the best approach: Defining "id" in
all object structures or defining it in the "node" structure. It must be
defined in any case, so we can find a specific object that we don't have a
pointer to by some FindObject routine (to avoid passing a million pointers
around). (started, see FindWindow in output.c)

- writing colored strings to the screen is currently accomplished by
calling WriteStr as usual, with strings of the format "<White>Bob
<Yellow>the Big" ... WriteStr does not do %s and such expansion, so
sprintf() ing a string before passing it to WriteStr is a good thing. Look
to the bottom of player.c for an example.

= Random Name Generation Using Regular Expressions - Brian Robinson [bcr19374@pegasus.cc.ucf.edu]. =

Rationale

	One of the things that makes roguelike games interesting is the
use of unique items and beings.  Having Ringil by your side in Angband is
much more fun than having a sword or even a sword +1.  And its much more
satisfying to get rid of Wormtongue than another "seedy looking human."
In the case of Angband, many of the unique names were derived from the
works of J. R. Tolkien and are used to evoke the same kind of atmosphere
used in his books.  Tolkien provides a rich background for a game, and
plenty of names.  However, what do you do if you want to create your own
game world from scratch?  You could write a few novels and use the
characters and items from them, or instead you could try to use a random
name generator.
	A random name generator is a program or part of a program that
can produce names randomly.  The names can be used for anything, from
naming individual beings like monsters and shopkeepers, to naming
artifacts, to naming towns and regions.  However, some tweaking may be
neccasary for different purposes.  For instance, Brian might be a good
name for an orc, and a decent name for a city, but the amulet of Brian
just doesn't sound that great.  One characteristic that a good name
generator should have is flexibility.  It should be able to produce names
of different forms with ease.

Regular Expressions

	One way of accomplishing this is to use regular expressions.  If
you've taken a discrete structures class or are a *nix guru, you probably
already know what these are.  For those that do not, I will provide a
brief explanation.  A regular expression is a string, or a sequential
series of letters and symbols, that describes the form a word may take,
or in technical terms, a language.  One special letter used in
regular expressions is called the null symbol, or a blank.  It is usually
denoted by a greek lambda, but I will use a 0 instead.  Each letter and
each grouping of letters within a regular expression is also a regular
expression.
	Some regular expressions have only one interpretation; for
instance, the regular expression "bab" can only represent "bab".
However, we can use a number of operators to give regular expressions
more options.  The first operator we will look at is the "or" operator,
commonly written as |.  Or basically means that of the two expressions on
either side of it, only one will be selected.  So, if my regular
expression is "b|a", there are two valid words in this language, "b", and
"a".  I can also use parantheses just as in math to group letters, so
"(b|a)b" has two valid words, "bb" and "ab".  
	There are two other operators in classic regular lanugages.  One
is the "and" operator, but it is implicit in the form I am using here.
Basically, whenever an expression is placed next to another expression,
they are anded, which means that they occur together in the order they
were first written.  The other is *, but rather than using * (which can
generate infinitely long words), we will look at the use of numbers as
operators.  Consider the regular expression "a3".  This is analogous to a
to the third power in standard math, and the result of this regular
expression is "aaa".  
	One useful technique we can use with regular expressions is
substitution.  Substitution basically maps a single letter to a regular
expression.  So, if I make a substitution of the form "D=(a|b)" and then
write "Db" it would be the same as if I had written "(a|b)b".  This is
particularly applicable to random name generation.  Consider the
substitution "V=(a|e|i|o|u)".  Now whenever we use a "V" in our regular
expression what it really means is to insert a vowel.  Similarly, we can
define the consonants as "C=(b|c|d|f|g|h|j|k|l|m|n|p|q|r|s|t|v|w|x|y|z)".

Actually Making Some Names!

	Now we can do something interesting.  Lets define a new regular
expression, "CVC".  This is a very simple thing to type, and yet we can
now generate words such as "bob", "sig", "mop", "non", etc.  There are
very many combinations here!  Lets try another: "C(V2)C".  Here we use the
numerical operator.  Substituting the V,  we expand this as
"C((a|e|i|o|u)2)C", so we must select our vowel first, then place it 2
times, rather than placing 2 different vowels.  This regular expression
will create names like "baab", "look", "hiig", etc.  Lets look at one more
before moving on: "(C|0)VCV".  This regular expression can create names
like "moli" and well as "ago" because of the "C|0" part.  Using the null
along with an or operator can be a powerful tool and give you many
options.
	Now that you see how to create some basic names, lets take it a
little further.  You may have noticed that some of the output names I
listed above seem unrealistic; they don't sound like real names.  How can
we improve this?  Well, substitution is again our friend.  I'm going to
define two new substitutions, P for prefix and S for suffix.  The idea
comes from looking at names.  Take a few, like "Brian", "Scott", "Steve",
"Frank", "Casandra", and "Kristen".  These names all have letter
combinations in the beginning or end that we are used to seeing, like
"br" in "Brian" or "nk" in "Frank".  What we do is take these prefixes
and suffixes and map them into a substitution.  So we get 
"P=(br|sc|st|fr|kr)" and "S=(tt|nk|dra|sten)".
	Now lets play with our new toys.  Remember how the names from
"CVC" were not very impressive?  Well, lets see what we come up with when
we use "(C|P)V(C|S)": "lott", "brik", "stink", "wodra", "juk", "kosten".
With the exception of "stink", these are some pretty good names, and the
regular expression for generating them was pretty simple.  To eliminate
names like "stink", we can use a filter which eliminate a set of words we
don't want to appear.  I cover the implementation of such a filter below.

Implementation

	In my implementation, as I mentioned, I treat the concatenation
operator as explicit.  This simplifies things in the code, but makes it
just a little more complex for the person creating the regular
expressions.  Basically, you need to use some more parentheses than you
might expect.  Consider the example above of "C(V2)C".  You might expect
to be able to get the same effect without the parentheses.  But due to the
string implementation, without the parentheses odd things can happen, such
as both the consonant and the vowel being duplicated.
	Now, with that caveat, lets proceed.  I have a Java class that
takes a regular expression as an argument to its constructor.  Every time
you want a name in that format, you can call the getName() method, and a
random name of that type will be generated.  Most of the work in the class
takes place in a private method called parse() which is called by
getName().  I will analyse this line by line below so you can understand
what is happening.

--
      public String parse(String s)
      {
         int index;
         char current;
         StringBuffer b;
         Vector leaves;
      
         leaves = new Vector();
         b = new StringBuffer();
         index = 0;
--

	This code sets up the variables used throughout the method and
initializes them.  Index keeps track of where we are in the regular
expression string s.  Current is a temp variable to let us examine each
character seperately.  B is a buffer used for temporary string storage.
Leaves is a Vector that will contain all the possible outcomes of the or's
in this expression.  I call it leave because it is like leaves of a tree.
The expression "a|b|c" could be represented as:

                                  *
                                 /|\
                                / | \
                               a  b  c

--
         while (index < s.length())
         {
            current = s.charAt(index);
            if (Character.isLetter(current))
            {
               b.append(current);
               index++;
            }
--
	This sets up a while loop that will run until index is greater
than or equal to the length of the string.  Current is assigned the
character at index and we start figuring what we want to do.  First off,
if current is a letter, we add it to the buffer and increment the index,
then restart the loop.

--
            else if (current == '|')
            {
               leaves.add(b);
               b = new StringBuffer();
               index++;
            }

--
	If current is an or operator, we add the string in our buffer to
the leaves Vector and create a new buffer.  We increment the index and
loop.

--
            else if (current == '(')
            {
               int count = index + 1;
               int openParens = 1;
               while (openParens > 0)
               {
                  if (s.charAt(count) == '(')
                  {
                     openParens++;
                  }
                  else if (s.charAt(count) == ')')
                  {
                     openParens--;
                  }
                  count++;
               }
               count--;
               b.append(parse(s.substring(index + 1, count)));
               index = count + 1;
            }
--
	Slightly more complex than the previous parts, when we see an open
parentheses, we need to find it's matching closing parentheses.  We can't
just use the first one we find because we want to support nested
parentheses.  Once we know where the parentheses open and close, we take
whats in the parentheses and parse it just as we do the whole string.  The
result of that parsing is added to our current buffer.  We then increment
the index past the close parentheses and loop.

--
            else if (Character.isDigit(current))
            {
               int count = index + 1;
            
               if (current != '0')
               {
                  while (   (count < s.length()) 
                         && (Character.isDigit(s.charAt(count))))
                  {
                     count++;
                  }
--
	If we have a number, we want to determine what the number is.
Although I don't know how often people are going to need to use numbers
larger than 9, the support is there for anything an int can handle.  Also,
since we are using '0' as our null character, we have to take special note
of it here.  The while loop above simply counts the number of digits we
have in a row.

--
                  Integer exponent;
                  try
                  {
                     exponent = Integer.decode(s.substring(index,count));
                  }
                     catch (NumberFormatException ex)
                     {
                        exponent = new Integer(0);
                     }
--
	This is Java's way of converting a String to an int.  Its a little
more complicated than atoi(), but not so bad.

--
                  StringBuffer temp = new StringBuffer();
                  for(int i = 0; i < exponent.intValue(); i++)
                  {
                     temp.append(b);
                  }
                  b = temp;
--
	Here we simply copy our whole buffer over as many time as
specified by the exponent.  Not that this will affect everything since
either the beginning of the regular expression or since the last or
operator.  This is somewhat of a kludge, but it works if you use
parentheses to segregate exponents.

--
               }
               index = count;
            }
         }
--
	Finally, we need to set the index equal to count.  If we
encountered a '0', count will be (index + 1), so the '0' is skipped.  If
it was any other number, count will be the place in the expression where
the digits stopped.  The final end brace above closes our while loop.

--
         if (leaves.size() == 0)
         {
            return b.toString();
         }
--
	If leaves is empty, that means there was no or operator in the
expression.  We simply return the buffer because there is nothing to
choose between.

--
         else
         {
            leaves.add(b);
            int whichString = generator.nextInt(leaves.size());
            return (leaves.get(whichString)).toString();
         }
      }
--
	If leaves is not empty, we need to choose one of the possible
outcomes of the or operator.  Each possibility should be weighted equally,
but the random number generator in Java is not perfect for small numbers.
However, you will always get correct, if not uniformly distributed names
from it.  Here we add the final string from the buffer, choose a random
index of the Vector leaves, and return that index as the name we've
generated.
	There's a little more to the class, but not much.  Just a
constructor and the getName() method which simply calls parse().  You may
want to add the ability to do substitutions before returning the final
name, or you may chose to do them after the return with a special
substitution class.  That should be simple enough to implement that I need
not discuss it here.

Filtering

	Some people may be content to have names like "stink" appear
in their game, but others may not.  Specifically, parents may not
like for their children to be exposed to profanity within a game,
even if it is not used as such.  Fortunately, its relatively simple to
provide a filter in a name generator to prevent these sorts of
names from being created.  Here's some Java pseudocode of how to use the
filter:

do
{
  String name = nameGenerator.getName();
} until (!filter.isBad(name));

	Now, writing the filter is a little more difficult than
using it.  In Java, its still pretty simple.  I'll post the entire
source here minus the actual words being filtered:

   import java.util.*;
   class Filter extends Hashtable
   {
      public Filter()
      {
         String[] badWords = 
         {/* fill with bad words in lowercase */};
      
         for(int i = 0; i < badWords.length; i++)
         {
            put(badWords[i], new Object());
         }
      }
      public boolean isBad(String s)
      {
         return (get(s.toLowerCase()) != null);
      }
   }

	This class extends the built in Java Hashtable class.  It
creates an array of Strings which are all profane.  It then puts
them into the hash table.  When you want to check to see if a word
is one you wish to filter, it simply hashes it and sees if the
word exists in the table or not.  You could also employ any
storage/search combination you prefer, but this is so easy to
implement in Java it seemed it was the way to go.

Conclusion

	Hopefully you know a bit more about generating random
names after reading this article.  I have provided source for
everything I have discussed below.  If you have any questions or
comments, feel free to email me at bcr19374@pegasus.cc.ucf.edu.

Download Source.

= Randomiser Algorithms - Simon McGregor [londonien@hotmail.com]. =

Frequently, in a roguelike game, the programmer will want to do various
pseudo-random things. As well as simply generating random numbers, they 
may want to have subroutines for picking a random set of things from a 
list, shuffling a list, picking an item fairly from a weighted list, 
and so on.

Although it is easy to come up with "random" algorithms for doing this, 
mere randomness and/or intricacy does not guarantee fairness. Moreover, 
if the algorithms are used frequently, their efficiency can be an 
important issue. The following algorithms are both reasonably efficient 
and fair...

I have written the algorithms both in a Basic-style pseudocode and in 
native C. The C code for these algorithms is amazingly small.

The proof-of-fairness for these algorithms is available on request from:
  londonien@hotmail.com
and illustrates the value of applied maths in even quite simple computer 
science.

N.B. For the following algorithms, the function "random(x)" is assumed 
to produce a fair random number between 0 and x-1.

BAG-PICK ALGORITHM

This algorithm picks a random subset of size "x" from the numbers "0" 
to "n-1". It is conceptually equivalent to picking a bunch of things 
from a bag without replacement. It is not THE most efficient approach 
for a static array, but has the edge because it can be applied to a 
linked list instead of numbers, with very little modification.

***************
Pseudocode 
***************

  max:=n;
  remaining:=x;
  current:=0;
  while (remaining > 0)
    if (random(max) < remaining) then
      ADD (current) TO OUTPUT LIST
      remaining:=remaining-1;
    end if
    max:=max-1;
    current:=current+1;
  end while

***************
C Code
***************

  void BagPick(int *dest, int n, int x)
  {
    int i;
    for(i=0;x>0;i++) {
      if (random(n--) < x) *dest++=x--;
    }
  }

SHUFFLE ALGORITHM

This algorithm shuffles a list "array" of length "n". Unlike more 
complex and seemingly-random algorithms, it is truly random, and 
optimally efficient.

***************
Pseudocode 
***************

  for f:=0 to n 
    SWAP array[f] WITH array[random(f)];
  end for

***************
C Code
***************

  void Shuffle(void *array, int n, size_t size)
  // "size" is the size, in chars, of an array element
  {
    int f,g;
    char *temp,*p;
  
    temp=malloc(size);
    p=array;
    for(f=0;f<n;f++) {
      g=random(f);
      memcpy(temp,&p[g*size]);
      memcpy(&p[g*size],&p[f*size]);
      memcpy(&p[f*size],temp);
    }
    free(temp);
  } 

FOR FURTHER THOUGHT

Another useful randomiser technique is to be able to associate a 
random seed with a "meaningful" text string, so that randomly generated 
entities such as dungeons, levels, planets, NPCs, species and so on can 
be given a name which completely specifies their generated 
characteristics. This technique will feature heavily in Dimensions, and 
hopefully I will find time later to post and comment on suitable 
algorithms based on this idea.

= ModuloN - Christopher J Martens [CMartens@mail2Canada.com].txt =

The Modulo-N Randomization Algorithm

Warning: This article does discuss a lot of math, but nothing we didn't sleep
through in elementary school.

Wordy Introduction:

There is a paradoxical need for randomized, "unpredictable" input generated from
ordered, "predictable" systems. Although both theoretically and practically
impossible, several methods to randomly generate numbers do exist; one such is
the modulo-n pseudo-random algorithm, employed in many facets of computer
science such as public key cryptography and statistical analysis to name a few.

The underlying principle of the system is to generate a sequence of numbers with
no discernable pattern. A seed value is provided to the algorithm to establish a
starting point and the algorithm presents a numeric sequence of finite length.

This algorithm, or another similar to it, is usually included in software
development environments. The purpose of this article is to shed some light on
the workings of the algorithm.

The equation:

This method of random numbers is something you've probably worked with already.
However many treat it like a black box, knowing inputs and outputs but not the
actual workings, and up until four months ago, so did I.

The basic framework of the theorem is this:

X = (Y) MOD (N)

Simply put, X will be the remainder after dividing C by N (Y/N).

Now, you probably know that the range of values possible for X will be 0 to N-1.
For instance:

Y = 21, N = 7 : X = 0
Y = 23, N = 7 : X = 2
Y = 27, N = 7 : X = 6
Y = 28, N = 7 : X = 0

Obviously, the afforementioned equation is not really a useful equation. The
actual modulo-n equation is this:

NewValue = [ (A * OldValue) + B ] MOD (N)

To get this to work, we need four values: A, B, OldValue and N. The old value
you've probably heard of before. It's sometimes called the seed value.

This still follows the same principle as the first equation, except that the Y
variable from the first equation changes as numbers are generated
(ie. A * OldValue + B = Y). Let me demonstrate using this equation...

Assuming A = 13, B = 3, N = 2^3 = 8

We'll need a seed number. I'll pick 6 for now.

N = [ ( 13 * 6 ) + 3 ] MOD 8 = 81 MOD 8 = 1

Now throw this newly generated number back into the equation as the seed...

N = [ ( 13 * 1 ) + 3 ] MOD 8 = 16 MOD 8 = 0

And again, doing the same...

N = [ ( 13 * 0 ) + 3 ] MOD 8 = 3
N = [ ( 13 * 3 ) + 3 ] MOD 8 = 2
N = [ ( 13 * 2 ) + 3 ] MOD 8 = 5
N = [ ( 13 * 5 ) + 3 ] MOD 8 = 4
N = [ ( 13 * 4 ) + 3 ] MOD 8 = 7
N = [ ( 13 * 7 ) + 3 ] MOD 8 = 6 <= Same as original seed
N = [ ( 13 * 6 ) + 3 ] MOD 8 = 1 <= Notice the beginning of a pattern?


So the actual sequence of numbers generated by the algorithm is 1, 0, 3, 2, 5,
4, 7, 6, 1, 0, 3, 2, 5, 4, 7, 6 and so on and so forth. These are technically
random.

Observations/Discussion:

There may be a bit of a detectable sequence (1 to 0, 3 to 2, 5 to 4, 7 to 6),
but in real life when larger numbers are used, it is very difficult to detect
any pattern. Also, it is important to remember how you're using these numbers.
For all the C/C++ goons out there, what do we do once we get a number from the
rand() function? We force it to the range of values we want for the specific
purposes we want these random numbers for.

Example code fragment:

// Format generated number between Max and Min.
int x = rand() % (Max - Min) + Min;

By doing this, we increase the "randomness" of the whole process, because the
chances of getting the exact same number from the generator for the exact same
purpose are pretty low. However, at some point there'll be a pattern setting,
but there are many ways to either get around them or prevent them altogether,
many of which are common knowledge.

Additionally, there are a few things I've found out that could be helpful.
Variable A *really* needs to be a prime number, otherwise you might get a value
for A being wholly divisible by N and then that would shorten the sequence
prematurely. This is also the case for B, but the need for this has to be
emphasized. If the previous number was 0 and B / N leaves no remainder then you
will get B MOD N to be 0; which is the exact same as the value before it. In
short, the whole algorithm crashes to a halt and keeps outputting 0 until you
manually provide a new seed.

Another interesting thing to notice is that when everything works perfectly, you
will always get N unique sequence steps. That is, if N = 8, you'll get 8
discreet steps before the sequence repeats itself. If this is the case, then the
sequence generated will have to include every possible value from 0 to N-1
before it repeats.

It is also beneficial to have N as a power of 2. If N = 2^m, then every number
generated will fit into an allocated space inside memory of 'm' bits. That way,
you can create random numbers that are guaranteed to fit into a specific
variable type, be it a byte (8 bits) a word (16 bits) or a double word (32 bits).

Conclusions:

I've written a little program for C++ which I've experimented with, try it out
if you're curious. (My apologies to those who do not use C++, although it
should be easy to figure out) It's far from bulletproof, however, especially if
you enter character input.

#include <iostream.h>

void main( void )
{
int A, B, N, seed;

// Display cheesy intro
cout << "Modulo-N Algorithm Demonstration:\n"
<< "Please enter required parameters\n";

// Get intro values
cout << "A = ";
cin >> A;

cout << "B = ";
cin >> B;

cout << "N = ";
cin >> N;

cout << "Seed value = ";
cin >> seed;

// Generate random numbers
cout << "Generating numbers...\n\n";

int count = 0;

while( count <= N )
{
// Generate the number
seed = ( ( A * seed ) + B ) % N;

// Display the number
cout << seed << ", " << flush;

// Advance the count
count++;
}

cout << "Done!" << endl;

return;

}

Anyways, I'd better quit. Hopefully, this satifies some curiosity as to why and
how the random number generator inside a computer works and maybe give some
insight into how to use it effectively. Please email me and let me know if
something didn't make sense and/or what I could do to make this little article
clearer and more coherent.

Cheers,

Chris Martens
CMartens@mail2canada.com 

= Random Names - Gero Kunter [kunter@mathematik.uni-marburg.de]. =

One of the typical features of a roguelike game is that as many features as 
possible have random appearances. So it may seem a logical conclusion to add 
random names to the inhabitants of your virtual world as well. 

However, you should consider to which extend you want to give names to NPCs. 
Is it really necessary to have a name for every single orc, every single rat 
and every single bandit? But then again, powerful creatures, such as dragons, 
certainly deserve a well-sounding name. And of course, every shopkeepers would 
dishonour their profession without one. I think it is a good idea to have 
names for important and unique characters - people who give quests to the 
player, or potential companions. But your opinion may vary, of course.

But how do you generate random names?

You can employ powerful algorithms which will use a given set of data strings 
to generate random strings that are similar to the initial data. But there are 
simpler ways. In my project, I used two approaches, which I will outline 
below.


    Combinations of given first and surnames

This method is quite simple. It uses three seperate lists with strings: one 
with male and one with female first names, and one with surnames. The 
following pseudo-code algorithm retrieves a new, random name. 

    switch Gender { 
        case male   : S = male_firstnames [random]
        case female : S = female_firstnames [random]
    } 
    RandomName = S + " " + surnames [random]

If you need "Nordic" names like "Kunt Barnesson" or "Gudrun     
Ingridsdotir"., you could use a variation of this:

    switch Gender { 
        case male   : S = male_names [random] + " " + male_names [random] + 
                        "sson" 
        case female : S = female_names [random] + " " + female_names         
                        [random] + "sdotir" 
    }
    
You could add a control structure in which you keep track of the names that 
have already been generated, to prevent the algorithm from returning the same 
name twice:

    for i = 0 to 15 {
        for j = 0 to 15 {
            combination_given [i] [j] [male] = FALSE
            combination_given [i] [j] [female] = FALSE
        }
    }

    [...]

    repeat
        i = random
        j = random
    until combination_given [i] [j] [Gender] = FALSE
    combination_given [i] [j] [Gender] = TRUE

    switch Gender {
        case male   : S = male_firstnames [i]
        case female : S    = female_firstnames [i]
    }
    RandomName = S + " " + surnames [j]

In a proper program, you would probably use a bit-coded flags to check which 
combinations have been generated.


    Completely random names

The second algorithm described here doesn't use combinations of given names, 
but generates them completely from scratch. The idea is to put together 
combinations of vowels and consonants to generate words that might be names. 
By using specific sets of sounds, you can control the "flavour" of the names, 
and you can combine it with gender endings.

First, you should define the vowel and consonant set:

    vowels = "aeiou"
    consonants = "bcdfghjklmnpqrstvwxyz"

Then, you generate a word, alternating between random vowels and random 
consonants.:

    S = ""
    for i = 1 to random {
        S = S + vowels [random] + consonants [random]
    }
    switch Gender {
        case male   : S = S + 'us'
        case female : S = S + 'a'
    }

If you want to add a surname, just repeat the above snippet without the gender 
ending.

In this crude version, the algorithm will return rather ugly, artificially 
sounding names. You could alter this by changing the probability for some 
sounds, by using different vowel and consonant sets:

    vowels = "aaaeeeiiou"
    consonants = "bbbcdddffgghjkllmmmnnnppqrrssstttvwxyz"

These sets would make "a" and "e" three times and "i" two times as likely as 
"o" and "u", with the corresponding values for the consonants. You could also 
completely leave out some sounds.

The method above always returns names beginning with a vowel and ending in a 
consonant (forgetting about the gender endings for now). To change this, you 
could add after the first line a structure like the following:

    switch random {
        case 1  : S = consonants [random]
        case 2  : { do nothing }
    }

If properly implemented, the algorithm will give quite good - and sometimes 
even funny - names. I'll give you a list of random samples of names my 
implementation has come up with:

    Salopatan Dolot
    Lucara Vanibo
    Xyxelan Ubem
    Irabon Seboribal
    Abasixi Abubodul
    Sasipabi Itatop
    Latanybor Ocifil
    Obi Onu
    Laso Pubyl

But my absolute favourite was Eri Fuzibidusi!


    Titles

For a fantasy world, you may also want to add impressive titles. For example, 
your player might meet a veteran soldier in some tavern. It would be nice if 
he would be called something like "Olaran Ozatar, the Ogreslayer", wouldn't 
it?

This can be easily done, with a modification of the first method described 
above. Let's define a list of suffixes:

    suffixes = ("slayer", "hunter", "friend", "hater", "seeker")

Assuming that you have your creature names stored in a similar list, you can 
simply generate a title by

    title = "the " + creaturenames [random] + suffixes [random]


If you combine the methods as described here, it shouldn't be a problem to 
come up with as many exciting names as your roguelike game will ever ask for!

= Time Tracking - Gwidon S. Naskrent [naskrent@skrzynka.pl].txt =

When creating a roguelike, more often than not you are presented with 
the challenging task of devising an interesting world in which the 
game takes place. And, naturally, most beings in most worlds, even if
they are immortal, need to keep the flow of time for personal, 
governmental (taxes) and religious (feasts) purposes. This article 
deals with issues commonly encountered upon adding a time dimension to
your game.

Most assuredly, you are not bound to design your time according to the
traditional sense, with seconds, minutes and hours. But for the 
simplicity of the discussion, we will assume that you operate in a 
framework that consists of time units that everyone knows - seconds 
that make minutes, minutes that make hours, hours that make days and 
days that make years. We'll also assume that typical Earth standards 
are in force, with the exception that a year is always 365 days 
(not 365.24624 as in reality).

After determining how are your time units structured, it is important 
to decide what within the game will you use to represent it. The 
simplest approach is to assign a different variable to each of the 
various units; a signed char (byte) to seconds, minutes and hours, and 
an unsigned int to days. This simple solution has, however, a 
significant drawback: you waste storage space. It's certainly not a 
big waste, but helps to forget about memory issues and develop bad 
programming habits.

Therefore, a more efficient way to approach our problem will be the
introduction of *scalar time*. Scalar time is an uniform figure; it
represents the amount of basic time units - in our case seconds - that
have elapsed from a specific point in time. This point can be purely
arbitrary, but should be antecedent to the start of your adventure, so
as to avoid 'negative time', if possible. The variable type for scalar
time should be a 32-bit int (it is a good idea to make it a signed 
int, to avoid problems with negative time). 32 bits are, surprisingly 
enough, sufficient to cover a period exceeding 68 Earth years, 
probably more than the longest lifetime of a typical adventurer in 
danger-ridden dungeons. If you still think it's not enough, you can 
make the variable unsigned and double the available period. You can 
even increase the variable length to 64 bits, and it will cover (gasp) 
some 292 trillion years. Now THAT should be enough even if your game 
starts at Big Bang...


Basic Timekeeping

We'll start the coding part by defining some basic quantities:

#define MINUTE 60
#define HOUR (60 * MINUTE)
#define DAY (24 * HOUR)
#define YEAR (365 * DAY)

These will be helpful in adding or substracting larger amounts of time
to/from our scalar clock.

Next, we must write a function that will do for us the dirty work of
calculating actual time representation. Programmers call that 
'breaking down' of the scalar value. Assuming the time units are 
always of equal length, we can achieve the task very easily without 
resorting to floating point arithmetics.

Here's a function I used in GSNband (slightly changed)

int break_scalar_time (int what)
{
	switch (what)
	{
	case SEC:	
	    return (sc_time % MINUTE);
	case MINUTE:
	    return ((sc_time / MINUTE) % 60);
	case HOUR:
	    return ((sc_time / HOUR) % 24);
	case DAY:
	    return ((sc_time / DAY) % 365);
	case YEAR:
	    return (sc_time / YEAR);
	default:
	return (0);
	}
}	    

(sc_time is my 32-bit time variable; SEC, MINUTE etc. are #defined modes
the function is called with; they may be any value you want).

In short, to calculate the remainder corresponding to any unit, we first
divide the scalar time by the amount of base units correspoding to that
unit (note that in the first case sc_time is equivalent to sc_time / 1),
and then take the modulus of it and the amount of units it takes to fill
the next higher unit. The last case does not include the modulus, since
there is no higher unit that a year, and we immediately know how many
years have passed on our clock.

This is a rather unoptimised function that will not work well in a 
compiling environement that generates lots of extra code for each 
function call. It that case, it is better to rewrite the function header 
using pointers, like this:

int break_scalar_time (int *sec, int *min, int *hour, int *day, int *year)

And then call it after having initialized the variables:

int sec, min, hour, day, year;
break_scalar_time (&sec, &min, &hour, &day, &year);

Yet another solution would be a structure to keep the information 
returned, or even better an union (since all the fields are of equal 
length).


Months and Weeks

The next thing you want is a calendar. Unless, of course, the inhabitants
of your world customarily refer to the likes of 'day 164 of the year'. 
For a calendar, you'll need months and perhaps weeks (if each months 
contains an equal number of weeks).

If you wanted to emulate the Gregorian calendar (without a leap day), 
your best bet would be to make two arrays like this:

char *month_names[12] =
{
   "January", "February" ... 
}

int month_table[12] = /* No. of first day of each month in a year (0-364) */
{  
   0, 31, 59 ...
};

(we're counting from 0 to be in common with the values break_scalar_time()
returns)

And then we can calculate the month and day of month like this (with the result
in out_str):

int day, month, i, j;
int year_day = break_scalar_time(DAY);
char *p;
char *out_str;

for (i=0; i <= 12; i++)
{
if (year_day >= month_table[i])
   {
      month = i;
      day = year_day - month_table[i] + 1;
      
      /* Take account of annoying English */
      p = "th";
      j = day % 10;
      if ((day / 10) == 1) /* nothing */;
      else if (j == 1) p = "st";
      else if (j == 2) p = "nd";
      else if (j == 3) p = "rd";

      (void)sprintf (out_str, "%d%s day of %s", day, p, month_names[i]);
    }
}


What To Do With Time?

After we've written our timekeeping routines, we must consider how 
much time will elapse while the player is doing something, IOW, how 
fast will the game time progress. If you game employs large wilderness 
areas, you will probably want to hasten time flow while the player is 
there. OTOH, in a dungeon settings time should pass more slowly.

First, define the area of the basic grid of your dungeon, if you 
haven't already. For example, in Angband this is 10 feet (somewhat 
over three metres). How fast can you expect the player to cover a 
distance of ten feet, moving at a somewhat cautious pace? What about 
combat - how long does a blow take? (I based time elapsed between blows 
on dexterity and weapon weight.) Do monsters act in a separate time 
piece or does time not move while they have a turn? How fast do you use 
magical items? Change levels? Eat something? (think about weight/volume)
Etc. etc. Providing for all actions the player may undertake is vital 
if you want the time flow to correspond, at least vaguely, to what 
you've been doing. 


Some other ideas employing the concept of (recurring) time:

- Shops that are open 7/11 or on certain weekdays
- NPCs that can be had only at specific hours (otherwise they sleep, 
  work, wander away etc.)
- Quests given may be restricted to a deadline
- Artifacts that activate a set number of times per day (or, if that's
  too sparse, per hour). Same goes for recharging time.
- Your character may have to spend a few hours, or even days, to learn
  new spells at a guild.
- Article prices fluctuate over time (probably in a random way, unless 
  you have an economy model handy. :)
- Delayed magical effects, like a retarded fireball or a time 
  bomb/grenade (the concept of delayed function calls probably merits 
  its own article)

Not to mention time travel...

Any questions, corrections or notes? Mail naskrent@artemida.amu.edu.pl

------
This article is (c) 2000 by Gwidon S. Naskrent. Any further copying,
publication or revisal is subject to the explicit permission of the
author, except when the copying or revisal occurs in the context of your
viewing this page in a web browser.
------

= 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".

	Now for a few quick hints and tips on how to modify the source code. First of all, 
in most cases you should only need to modify the header file "sureal.h". NPLAYERS is the 
number of players in the "game". If you increase this, do not forget to add another element 
to the array of players created just below the NPLAYERS define. For each player created, 
the first number is the id / timer the player is on. The last two numbers are the 
seconds:milliseconds for the players timeout.
	LEADWAY is what has been called in this document the "reaction time". The 
greater this value, the longer period of time the player has to respond to a move made by 
another player. A side effect of this is if a player is forced to move, it will take longer 
before the forced move is made if LEADWAY is increased. MAXFORCED specifies the 
number of moves before a player would be forced to quit. In the code below this has been 
set to 10 so as to speed the results up.
	The CSureal class is where all the important timers and numbers are kept track of. 
Refer to the comments in the header file as to what each of these variables are. For most of 
the rest of the source code in "sureal.c" please refer to the comments. It looks complicated 
mainly because of the need for milli second timing.
	The only thing to really take note of in the actual source code is the select() call 
from the main function. This call has been used for two purposes. Firstly it allows 
millisecond timing. Secondly, it can be combined with a socket setup such that connections 
and data from the outside world are received here. Essentially by pressing a key the user is 
simulating incoming data from a player.
	My final comment is this: Do not just look at the sources. Try it out to see how it 
works. Most likely some of you will have trouble of some sort. Please contact 
bendchon@mehta.anu.edu.au and report any problems or bugs so this document 
can be kept up to date and others have fewer problems.

-------------------------------------------------------------
#ifndef _sureal_h_
#define _sureal_h_

#include <sys/time.h>
#include <unistd.h>

// Redefine a few of the timer functions
#ifdef timerisset
#undef timerisset
#endif
#ifdef timercmp
#undef timercmp
#endif
#ifdef timerclear
#undef timerclear
#endif

#define timerisset(tvp)\
	((tvp).tv_sec || (tvp).tv_usec)
#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)
#define timerclear(tvp)\
	((tvp)->tv_sec = (tvp)->tv_usec = 0)

// Add a few timer functions
#define timershow(tvp)\
	(tvp).tv_sec << "-" << (tvp).tv_usec
#define timeradd(tvp, uvp)\
	{(tvp)->tv_sec += (uvp).tv_sec;\
	(tvp)->tv_usec += (uvp).tv_usec;\
	if ((tvp)->tv_usec > 1000000) {\
	    (tvp)->tv_usec -= 1000000;\
	    ((tvp)->tv_sec)++; }; }
#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
#define NPLAYERS	3
CSureal list[NPLAYERS] = {
    CSureal(1, 2, 0),
    CSureal(1, 3, 0),
    CSureal(2, 4, 0)
};

Timeval LEADWAY = {0, 500000};
#define MAXFORCED	10

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

#endif


-------------------------------------------------------------
#include <sys/types.h>
#include <sys/time.h>
#include <iostream.h>
#include <unistd.h>
#include <stdlib.h>
#include <time.h>

#include "sureal.h"

int main() {
    srand(time(NULL));
    while (1) {
        // Sleep until the next action happens
#ifdef DEBUG
        cout << "Sleeping\n";
#endif
        fd_set rfds; FD_ZERO(&rfds); FD_SET(0, &rfds);
        int retval;
        retval = select(1, &rfds, NULL, NULL, sleepTime());
#ifdef DEBUG
        cout << "Awake\n";
#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);
#ifdef DEBUG
    cout << "Sleeping for " << timershow(st) << endl;
#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));
            timeradd(&(list[i].STNext), ct);
            if (list[i].STTimer != i)
                timeradd(&(list[i].STNext), 
(list[list[i].STTimer].STTimeout))
            else
                for (register j = 0; j < NPLAYERS; j++)
                    if (j != i && list[j].STTimer == i) {
                        timeradd(&(list[i].STNext), 
(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);
                timeradd(&ft, 
list[list[i].STTimer].STTimeout);
                timeradd(&ft, LEADWAY);
                list[i].STForced = ft;
#ifdef DEBUG
                cout << "Setting forced timer again for "
                     << I << " to " << timershow(ft) << endl;
#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));
            timeradd(&(list[i].STNext), ct);
            if (list[i].STTimer != i)
                timeradd(&(list[i].STNext), 
(list[list[i].STTimer].STTimeout))
            else
                for (register j = 0; j < NPLAYERS; j++)
                    if (j != i && list[j].STTimer == i) {
                        timeradd(&(list[i].STNext), 
(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++;
#ifdef DEBUG
                        cout << "Setting forced timer for "
                             << j << " to "
                             << timershow(ft) << endl;
                        cout << "\tForced count: "
                             << list[j].STForcedRemain
                             << endl;
#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
{
# Array of child units
UnitPtr children[MAX_UNITS]

# Keep reference to the parent too -- this is technically unnecessary and
requires a bit more care in your
# tree-manipulation functions, but you'll thank me the first time you have a
unit and want to know what
# its parent is.  If parent is NULL then the unit is on the map somewhere.
UnitPtr parent

# 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

# 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
      Read a run count
      Read a tile
      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

Algorithm 4: Reading sparse data
   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
      Read the X coordinate
      If the X coordinate is the sentinel, stop
      Read the Y coordinate
      Read the real value
      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 GNU/Linux '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
--------------
Gcc has certain builtin functions known as __builtin_frame_address
and __builtin_return_address.

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:

__builtin_return_address(0) is the current address (say function C)
__builtin_return_address(1) is the address in function B which called C
__builtin_return_address(2) is the address in function A which called B

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. 

5.1 The windows 'get-an-address-off-the-stack macro'
----------------------------------------------------

#ifdef WINDOWS
#define handle_stack_address(X) \
   if (baseframe == 0L) \
   { \
      baseframe=(unsigned long)__builtin_frame_address(0); \
      baseframe=((baseframe & 0xffff0000L) >> 16); \
      dlog(DEBUGSAVE,"files.c: handle_signal_abort: baseframe now %08lx\n",
\
           baseframe); \
   } \
   if (continue_stack_trace && \
       ((((unsigned long)__builtin_frame_address((X)) & 0xffff0000L)>&gt16)
== baseframe) && \
       ((X) < MAX_STACK_ADDR)) \
   { \
      stack_addr[(X)]= (unsigned long)__builtin_return_address((X)); \
      dlog(DEBUGSAVE,"files.c: handle_signal_abort: stack %d %08lx frame %d
%08lx\n", \
                      (X), __builtin_return_address((X)), (X),
__builtin_frame_address((X))); \
   } \
   else if (continue_stack_trace) \
   { \
      continue_stack_trace = FALSE; \
   }
#endif

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

5.2 The GNU/Linux 'get-an-address-off-the-stack macro'
------------------------------------------------------

#define handle_stack_address(X) \
   if (continue_stack_trace && ((unsigned long)__builtin_frame_address((X))
!= 0L) && ((X) < MAX_STACK_ADDR)) \
   { \
      stack_addr[(X)]= (unsigned long)__builtin_return_address((X)); \
      dlog(DEBUGSAVE,"files.c: handle_signal_abort: stack %d %08lx frame %d
%08lx\n", \
                      (X), __builtin_return_address((X)), (X),
__builtin_frame_address((X))); \
   } \
   else if (continue_stack_trace) \
   { \
      continue_stack_trace = FALSE; \
   }
#endif

5.2 The decoding routine for the addresses on the stack
-------------------------------------------------------

/* this is a adapted version of addr2line */
/* addr2line.c -- convert addresses to line number and function name
   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
   it under the terms of the GNU General Public License as published by
   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);
}

/* Read hexadecimal addresses from stdin, translate into
   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];
   sprintf(addr_hex,"%x", address);

   dump_pc = bfd_scan_vma (addr_hex, NULL, 16);

   dump_found = false;
   bfd_map_over_sections (abfd, find_address_in_section, (PTR) NULL);

   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
         child process that reads addresses from a pipe and responds
         with line number information, processing one address at a
         time.  */
   }
   fflush (stdout);
}

void dump_stack(void)
{
   s16b i;
   static unsigned long stack_addr[MAX_STACK_ADDR];
   bfd *abfd;
   char **matching;
   long storage;
   long symcount;

   bfd_init();

   /* clean the stack addresses if necessary */
   for (i=0; i < MAX_STACK_ADDR; i++)
   {
      stack_addr[i] = (unsigned long)0;
   }

   handle_stack_address(0);  handle_stack_address(1);
handle_stack_address(2);  handle_stack_address(3);
   handle_stack_address(4);  handle_stack_address(5);
handle_stack_address(6);  handle_stack_address(7);
   handle_stack_address(8);  handle_stack_address(9);
handle_stack_address(10); handle_stack_address(11);
   handle_stack_address(12); handle_stack_address(13);
handle_stack_address(14); handle_stack_address(15);
   handle_stack_address(16); handle_stack_address(17);
handle_stack_address(18); handle_stack_address(19);
   handle_stack_address(20); handle_stack_address(21);
handle_stack_address(22); handle_stack_address(23);
   handle_stack_address(24); handle_stack_address(25);
handle_stack_address(26); handle_stack_address(27);
   handle_stack_address(28); handle_stack_address(29);
handle_stack_address(30); handle_stack_address(31);
   handle_stack_address(32); handle_stack_address(33);
handle_stack_address(34); handle_stack_address(35);
   handle_stack_address(36); handle_stack_address(37);
handle_stack_address(38); handle_stack_address(38);

   /* dump stack frame */
   i = MAX_STACK_ADDR-1;
   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;
         
         translate_address (abfd, stack_addr[i], function_name,
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:

#ifdef SIGFPE
    (void)signal(SIGFPE, handle_signal_abort);
#endif

#ifdef SIGILL
    (void)signal(SIGILL, handle_signal_abort);
#endif

#ifdef SIG
TRAP
    (void)signal(SIGTRAP, handle_signal_abort);
#endif

#ifdef SIGIOT
    (void)signal(SIGIOT, handle_signal_abort);
#endif

#ifdef SIGKILL
    (void)signal(SIGKILL, handle_signal_abort);
#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
BUG leap for your throat!");
   Term_xtra(TERM_XTRA_NOISE, 0);

   /* Access the help file */
   strcpy(filename, ANGBAND_DIR_USER);
   strcat(filename, "crash.txt");

#if defined(MACINTOSH) && !defined(applec)
   /* Global -- "text file" */
   _ftype = 'TEXT';
#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)
   {
      fprintf(fff,"Your game has just crashed. Please forward the
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);

#ifdef ALLOW_COMPRESSION
      fprintf(fff,"compression support compiled in\n");
#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:

stack frame 10 address 0804abb1 = _start (?? 0) 
stack frame  9 address 401fb213 = ?? (?? 0) 
stack frame  8 address 08117a69 = main
(/home/jurriaan/games/myang/src/main.c 640) 
stack frame  7 address 0810b4b7 = play_game
(/home/jurriaan/games/myang/src/dungeon.c 2084) 
stack frame  6 address 0810a355 = handle_dungeon
(/home/jurriaan/games/myang/src/dungeon.c 1386) 
stack frame  5 address 08109ee7 = process_player
(/home/jurriaan/games/myang/src/dungeon.c 1116) 
stack frame  4 address 08109545 = process_command
(/home/jurriaan/games/myang/src/dungeon.c 717) 
stack frame  3 address 080f8565 = do_cmd_wizard
(/home/jurriaan/games/myang/src/wizard2.c 3264) 
stack frame  2 address 080f72fb = wiz_create_crash
(/home/jurriaan/games/myang/src/wizard2.c 2411) 
stack frame  1 address 402019b8 = ?? (?? 0) 
stack frame  0 address 080b1b10 = handle_signal_abort
(/home/jurriaan/games/myang/src/files.c 4302) 

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.>
========================================================================