Difference between revisions of "User:Duerig/Archive5"
(→Direct Screen Output.txt: remove dup) |
|||
| Line 1,895: | Line 1,895: | ||
items from corpses. | items from corpses. | ||
= Compressing Savefiles - Ross Morgan-Linial [rmorgan@fhcrc.org].txt = | = Compressing Savefiles - Ross Morgan-Linial [rmorgan@fhcrc.org].txt = | ||
Latest revision as of 00:53, 9 May 2008
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)>>16)
== 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 <Ulrich.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 <etc. Angband/64 has a *lot* of options.>