Difference between revisions of "User:Duerig"

From RogueBasin
Jump to navigation Jump to search
(Removed LOS by Tobias Downer. Already on site.)
(Checked AI, Randomiser)
Line 8: Line 8:
TODO:
TODO:
   * Add a link to blah.tar.gz
   * Add a link to blah.tar.gz
  * add a link to name.zip for Random Name Generation Using Regular Expressions


= Representing Magick Spells - Sean Middleditch [sean.middleditch@iname.com].txt =
= Representing Magick Spells - Sean Middleditch [sean.middleditch@iname.com].txt =
Line 531: Line 532:
sprintf() ing a string before passing it to WriteStr is a good thing. Look
sprintf() ing a string before passing it to WriteStr is a good thing. Look
to the bottom of player.c for an example.
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!

Revision as of 16:18, 1 May 2008

Here is a list of articles from the old roguelikedevelopment.org that I am trying to salvage:

Cannot Find: 

  * How to finish your roguelike - Peter Farabaugh [pete@tbe.net].txt Found a russian translation: http://www.rlgclub.ru/pmwiki.php?n=Main.ArticlesDevRlgFinish
  * User Interface in Roguelikes - Jim Babcock [jimmy_b@earthlink.net].txt Found a russian translation: http://www.rlgclub.ru/pmwiki.php?n=Main.ArticlesDevUserInterface
  * Roguelike Step by Step Guide.txt

TODO: 

  * Add a link to blah.tar.gz
  * add a link to name.zip for Random Name Generation Using Regular Expressions

Representing Magick Spells - Sean Middleditch [sean.middleditch@iname.com].txt

This article describes the basics of representing and using Magick Spells in roguelikes. The general techniques are very similar to those used in my article on Object representation.

For starts, we need a class to hold the information for a specific spell.

class Spell { public:

OK. Now, let's give the spell a name.

char *Name;

There. Now, every magick spell costs Mana Points (well, if you're using a magick system similar to most others). So we need to define the spell's cost in MP.

int MPCost;

Also, every spell has a level: how difficult a spell it is. Only more powerful casters can use more powerful spells.

int Level;

There. Now all we need to know is what in Gehenna the spell does. We'll make a sub-class called Effect to store this information.

class Effect: { friend Spell;

OK, so what does a specific spell do? We'll make a simple int to describe what a specific Effect describes.

int Type;

So what does Type mean? We'll use some #define's to specify.

#define HEAL 0 #define SCORCH 1 #define TICKLE 2 #define CREATE_OBJ 3

You can of course add as many as you want. Now, we know what an Effect does, but that's not enough. For example, for a HEAL Effect, how much HP does it heal? We could base everything of level (making a rigid and uniform magick system, which may be what you want: predictability), or we could give each Effect a set of arguments to define in more detial what it does. We'll do this through the use of 5 int's.

int Args[5];

What do the fields of Args mean? That's based on what Type is equal to. For an Effect with Type HEAL, we might say that:

Args[0] is Number of Dice Args[1] is Sides per Die Args[3] is Roll Mod

So an Effect of type HEAL with Args[0] = 2, Args[1] = 6, Args[3] = 2 would heal 2d6+2 HP. Pretty simple, eh?

Anyways, we can close of the Effect class. We want each Spell to have 5 Effect's (so every spell can have lots of flexibility).

} Effects[5];

We can now close of the Spell class.

};

So that's all there is to a basic magick class.

Casting the spell is just as simple. Make a function called Cast or whatever (I used an object method inside the Spell class, since I'm a C++ OOP freak). The function would take as arguments the spell to cast, the target, etc.

void Cast ( Spell *SpellToCast, int TX, int TY );

Then we go with a big, evil, switch statement based on effect. This actually works VERY well. The flexibility is astounding...

Of course, how each spell takes effect is based on how you've programmed the rest of your roguelike. Because of the OO nature of WotR, I found it very easy to create simple object Methods for spell effects.

For the HEAL Spell Effect Type, you might to do something as simple as loop through all the Characters (NPC's and Players) in the target loc (defined by TX and TY), and heal them based on the arguments listed above... 2d6+2, or whatever.

Anyways, this is just the basics. The advanced stuff all depends on your magick system and how you programmed the rest of the game.

The complete source for the Spell class is:

  1. define HEAL 0
  2. define SCORCH 1
  3. define TICKLE 2
  4. define CREATE_OBJ 3

class Spell { public: char *Name;

int MPCost; int Level;

class Effect: { friend Spell;

int Type;

int Args[5]; } Effects[5]; };

Any questions, comments, threats, etc., e-mail me at sean.middleditch@iname.com Well, I don't really want any threats.

The End


RL Dev Code 0.6 - Kornel _ Anubis_ Kisielewicz [kisiel@fulbrightweb.org].txt

         RL Developer Code
         Version 0.6.0
         Designed by Kornel \"Anubis\" Kisielewicz
         (kisiel@fulbrightweb.org)

Hey, I noticed that both Angband and NetHack users have their own GeekCode. Why not us? ;). This is the first draft, and it\'s realy RLDev specific. I think that a Roguelike Dev Code will be especialy useful, because it may make us more aware of the others ideas. I\'m open to all new ideas, or corrections. In all project specific questions answer about your current project. A sample of the code is on the bottom of the document.

I encourage to at least post your code once, so someone can collect them and post somewhere :).

1. General info about the developers methods

\"L\": Language used to program your roguelike project.

L:C C L:C++ C++ L:VC++ Visual C++ L:Java Java L:FP FreePascal L:TP Turbo Pascal L:DP Delphi (Pascal) L:Pyt Python ?L I still didn\'t decide !L I\'m a designer [more]

\"E\": Experience in programing.

E+++ I\'m a professional programmer E++ I program as a part time job E+ I program quite well, as a hobby E- I\'ve read a few books and made some programs E-- I\'ve made a few simple programs E--- I\'m learning while I write a roguelike

!E I\'m just a designer ;) ?E What do I need programming for?

\"T\": Time invested in rl-development. Choose the most true one :).

T+++ Every minute of my spare time! T++ Most of my free time T+ Regulary T- From time to time T-- As a recreation T--- Rarely

!T I don\'t write yet!

\"R\": Rewrites. A rewrite is writing your code from scratch, using only old libraries, and fragments of the old code.

R+++ more than 5 R++ 3-4 rewrites R+ 1-2 rewrites R- not yet R-- I\'ve just started R--- I do not program yet

?R What are rewrites? !R My game doesn\'t need rewrites, cause I write error-free!

\"P\": Porting to other systems

P+++ My game will be ported to most known platforms P++ Linux and DOS/Win P+ I try to keep the code portable. P- Why the hell? I write only for Linux/DOS (you may recompile it though) P-- DOS/WIN only P--- Windows only!

!P I use Java (or something similar)

\"D\": Importance of design before programming

D+++ I had a detailed DesignDoc before I started programming D++ I had many notes and information before I started coding D+ I keep my designdoc ahead of the project, but update it regulary D- I had a few notes before I started coding D-- I had a general image of what I\'m trying to do

!D Who the hell needs a DesignDoc? I make everything on the fly! ?D What\'s a DesignDoc?

\"G\": The generic engine, that is, how generic your game will be.

G+++ You will be able to make a hard-sci-fi game out of my engine, by just changing the info-files! G++ My engine is very generic -- you will be able to make a different game by changing the info files G+ I have info files for maps, monsters, items and dungeon generators G- I have a few general info files G-- I keep everything in the code

!G Why the hell generic engine? I wan\'t to make a GAME.

\"F\": Favourite Roguelike

F:ToME F:ADoM F:V Vanilla Angband F:*band *bands in general F:Rogue Yeah :). F:Moria F:NHack NetHack F:Hack F:GH Gearhead F:DC DeadCold [more]

\"RL\": Your roguelike definition

RL+++ A roguelike MUST be ASCII, MUST be a dungeon crawl, and MUST be based on a system similar to AD&D, and MUST be permadeath. RL++ A roguelike has to be ASCII, has to be random, and have experience levels, and permadeath. RL+ A roguelike has to be ASCII or use tiles, must have dungeons, and focus on killing things for experience. It has to be permadeath too. RL- A roguelike may have graphics but has to be rather dungeon themed permadeath game. RL-- A roguelike is a game that focuses on randomness, and features permadeath. RL--- A roguelike is a game inspired by other roguelike games.

!RL This is completely unimportant ?RL What is a roguelike actually?

\"RLA\": Roguelike community activity

RLA+++ I\'ve created a popular game, or host one of the main roguelike sites on the web. RLA++ I\'ve created a roguelike dedicated webpage (focusing not only on my game) RLA+ I\'m a FAQ maintainer, or wrote a roguelike article, or created a roguelike document RLA- I play roguelikes and post on a few roguelike newsgroups RLA-- I post on one roguelike newsgroup

!RLA Who is that guy?


2. Project specific questions

\"W\": World of the game, the genre

W:F Fantasy W:DF DarkFantasy W:AF Alternative Fantasy W:SF Science Fiction W:HSF Hard Science-Fiction W:MH Mecha W:M Modern W:CP CyberPunk W:G Generic engine (give eventual default genre in bracets)

\"Q\": Quests in your project

Q+++ The plot is the master! You will have random interesting quests in my game. Q++ I will add many pre-written quests. Q+ I will add a few quest for flavor, or even ToME-like random quests. Q- Maybe a few quests for flavor Q-- Kill Sauron. Kill Morgoth. Q--- No quests -- just Hack\'n\'slash.

!Q Who the hell needs quests? ?Q What is a quest?

\"AI\": Approach to AI in your project

AI+++ AI is the key! The creatures will behave diablo inteligently and talk to you with Bot-generated messages. They will use military tactics, recognize dangers, and create traps. AI++ The NPCs will behave quite reasonable, will flee, band together, pickup and use items. AI+ The creatures will use items like wands, staves and the like. AI- The creatures will be able to pickup and equip items. AI-- No monster-inventory -- just Hack\'n\'Slash AI--- Kill player. Kill player.

\"GFX\": Approach to graphics

GFX+++ The game will be graphical with nice graphics GFX++ The hame will have tiled graphics GFX+ Some popular freeware tiles GFX- Somewhere in the future I plan to add graphics GFX-- I\'d like graphics, but I\'m a poor artist

!GFX Pure ASCII rulez!

\"SFX\": Approach to sound

SFX+++ Digitalized Speech and Music is my aim SFX++ I will add many wave files and maybe some music SFX+ Just a few Sound-Effects SFX- Maybe in the future SFX-- I\'d like sound, but I\'m a poor at that

!SFX A roguelike with sound? Buhahahaha...

\"RN\": Approach to randomness in your project

RN++++ The whole world will be random, random quests, random dialogs, random plot RN+++ Same as above, but the plot will be fixed RN++ The world will be fixed, but there will be random quests, dungeons and items and monsters RN+ Random dungeons+items+monster placement RN- Just the dungeons and monster placement RN-- I plan to make everything fixed

\"PO\": Popularity of current project

PO+++ I have fan-sites of my playable roguelike (reserved for ToME, NetHack, ADoM, Angband and the like :) PO++ I have a playable version on the web that can be enjoyed PO+ I have a playable version on the web that can be looked at PO- I have a designer version on the web (dungeon+items+npcs and the like) PO-- I have a few design programs (map-view, dungeon generator) PO--- I haven\'t published anything

!PO I didn\'t do anything yet!

\"Hp\": Hitpoint treatment in the roguelike

Hp+++ A 1-st level character has a few hitpoints, a 50th level character has a few hundred... Hp++ I keep the hitpoints rather lower. Hp+ The player rarely recieves hit-points, I don\'t use a level system. Hp- Fully skillbased Hp-- Fully skillbased and advancement doesn\'t make you realy powerfull

!Hp I don\'t use hitpoints!

\"Re\": Realism in the roguelike

Re+++ You can die because of disease, rusty weapon wounds, or the after-effects of an out-dated portion of speed Re++ Each fight is dangerous Re+ I\'d rather not let the player kill hordes of monsters Re- I like to keep things real as in NetHack Re-- I like to keep things real as in Angband Re--- Who needs realism? It\'s the hack\'n\'slash that counts!

\"S\": Seriousness of the world

S+++ THE GAME. You think it\'s funny? You\'re talking to me? S++ The game has to be serious. I want to make an atmosphere... S+ (ADoM) From time to time a funny in-game situation is fun S- I like to keep the world rather not gloomy S-- (ZAngband) Lets keep it easy, sometimes a Barney, or Bull Gates is fun to kill S--- (NetHack) Why the hell? Let\'s have nuclear scientists, tourists, photo-cameras and sinks in a dark dungeon

regards, and I\'m waiting for your codes and opinions :), -- Kornel \"Anubis\" Kisielewicz RLDev Code v.0.6 

    L:FP E+ T+ R+++ P+ D++ G++ RL-- RLA++ F:ADoM
    GenRogue 0.16 V8 ( http://genrogue.felis7.civ.pl/ )
    W:DF Q+++ AI++ !GFX !SFX RN+++ PO--- Hp-- Re+++ S+++

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.

  1. 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!

Retrieved from "http://roguebasin.com/index.php?title=User:Duerig&oldid=12819"