Revision as of 18:37, 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
  * Mostly Turn-based Multiplayer Timing - Isaac Kuo [mechdan@yahoo.com].txt Found a russian translation: http://www.rlgclub.ru/pmwiki.php?n=Main.ArticlesDevTurnBasedMultiplayer
  * Lake and Oasis Generator - Adam Szczepaniak [adamshc@wp.pl].txt
  * Fill-area-with-rooms and Maze - algorithms - Josh VertexNortmal Tippetts [vertexnormal@email.com].txt Found russian translation: http://www.rlgclub.ru/pmwiki.php?n=Main.ArticlesDevMazeGen
  * Recursive randomized world-map generation Phillip C. Culliton [pcullit@hotmail.com].txt
  * 3D Representation for Roguelike Worlds - Jimmy Babcock [jimmy_b@earthlink.net].txt
  * Random Dungeon Algo in QBasic - Andrew Collins [andrewcollins@hotmail.com].txt
  * Nest of Ants - Jakub Debski [jakub@mks.com.pl].txt
  * Passable Cave Building Algorithm - Josh Tippets [vertexnormal@email.com].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:

define HEAL 0
define SCORCH 1
define TICKLE 2
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:

--

        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.

Direct Screen Output.txt

Direct screen output

1. Introduction Here are instruction how to write to screen without involving BIOS or your system. I did this in my RL project. This may prove dangerous though. This information is true when and only when computer is in color text mode. If you plan to use it in other modes (graphics for example) strange things may attack your viewport(vacuum worms?). Memory location is varying depending on which mode is set in given time. I will give some Pascal code bits to help understand this method. Please forgive me my mediocre english.

2. Location The memory adresses (in hex) B800:0000 to B800:FFFF (be warned that in monochrome mode it would be B000:0000 to B000:FFFF) is belonging to graphics card. First byte indicates an ASCII characted being stored. Next one describes it's attributes (color, background color and blinking).

Second bit may need some detailed explanations:

Bits 7 6 5 4 3 2 1 0

    [ ][       ][          ]
     ^     ^             ^

blink-/ background color |

                      textcolor

It means that one may use colors 0-15 for text and 0-7 for background. Blinking may be used for seen invisible monsters for example. So how we declare our array?

3. Declaration In Pascal it could look like this: (I used 80x50 color text mode in example)

Const MinY = 1; {defined constants}

     MaxY = 50;
     MinX = 1;
     MaxX = 80;

Var TheScreen : Array[MinY..MaxY, MinX..MaxX] of Record

                                          Symbol : Char;
                                          Attrib : Byte
                                          End; Absolute $B800:$0000;

Note that Y coordinate preceeds X. Ever wondered why BASIC statement locate asks for Y as first parameter? Now this is an answer. But this has minor drawback. It uses entire screen! In most cases you would want to save some lines for message area. To do this adjust MinY, MaxY and add MaxX*2 bytes to start position in memory. To add space add the bottom simply decrease MaxY.

4. Example We want to display a white blinking G on black background at (57, 22). In pascal we make these assignments:

TheScreen[22, 57].Symbol := 'G'; TheScreen[22, 57].Attrib := 15+0*16+128;

Displaying letter Z at (X, Y) in color A on a background color of B without blinking: TheScreen[Y, X].Symbol := 'Z'; TheScreen[Y, X].Attrib := A+B*16+0;

Yes, this 0 is unnecessary but i wanted to point that no blinking was used. Note that you may display even control characters. Rogue used char 1 of ASCII. I've seen no other rouguelike that had the same image for player. In my opinion @ is much uglier.

5. Conclusion This is faster than anything else I've seen before (tested on 386DX gives great results!). Let the processor speed be used for other features. Undetected ingerence of other programs might force you to add screen redraw key to your roguelike (as is in ADOM). Code was not tested by any compiler, so it may contain errors. If this is the case - sorry. Hope this helps anyone.

NOTE: writing to screen this way will NOT move cursor. It also saves time :) but you may move it manually or even disable.

Micha??? Bieli???ski

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

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

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

A Solution: Run-Length Encoding

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

Algorithm 1: Compressing a dungeon, take 1

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

The algorithm to decompress it is even simpler:

Algorithm 2: Decompressing a dungeon, take 1

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

Fixing the Problems

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

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

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

Algorithm 3: Saving sparse data

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

Algorithm 4: Reading sparse data

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

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

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

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

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

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

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

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

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

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

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

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

6 Sample output

1 Introduction

Gcc has certain builtin functions known as __builtin_frame_address and __builtin_return_address.

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

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

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

2 Signal handlers

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

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

3 What is on the stack

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

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

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

4 When to stop

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

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

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

5 Coding it

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

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

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

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

ifdef WINDOWS
define handle_stack_address(X) \

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

\

          baseframe); \
  } \
  if (continue_stack_trace && \
      ((((unsigned long)__builtin_frame_address((X)) & 0xffff0000L)>&gt16)

== baseframe) && \

      ((X) < MAX_STACK_ADDR)) \
  { \
     stack_addr[(X)]= (unsigned long)__builtin_return_address((X)); \
     dlog(DEBUGSAVE,"files.c: handle_signal_abort: stack %d %08lx frame %d

%08lx\n", \

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

__builtin_frame_address((X))); \

  } \
  else if (continue_stack_trace) \
  { \
     continue_stack_trace = FALSE; \
  }

endif

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

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

define handle_stack_address(X) \

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

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

  { \
     stack_addr[(X)]= (unsigned long)__builtin_return_address((X)); \
     dlog(DEBUGSAVE,"files.c: handle_signal_abort: stack %d %08lx frame %d

%08lx\n", \

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

__builtin_frame_address((X))); \

  } \
  else if (continue_stack_trace) \
  { \
     continue_stack_trace = FALSE; \
  }

endif

5.2 The decoding routine for the addresses on the stack

/* this is a adapted version of addr2line */ /* addr2line.c -- convert addresses to line number and function name

  Copyright 1997, 98, 99, 2000 Free Software Foundation, Inc.
  Contributed by Ulrich Lauther &ltUlrich.Lauther@zfe.siemens.de>

  This file is part of GNU Binutils.

  This program is free software; you can redistribute it and/or modify
  it under the terms of the GNU General Public License as published by
  the Free Software Foundation; either version 2, or (at your option)
  any later version.

  This program is distributed in the hope that it will be useful,
  but WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  GNU General Public License for more details.

  You should have received a copy of the GNU General Public License
  along with this program; if not, write to the Free Software
  Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */

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

 bfd_vma vma;
 bfd_size_type size;

 if (dump_found) return;

 if ((bfd_get_section_flags (abfd, section) & SEC_ALLOC) == 0)
 {
   return;
 }

 vma = bfd_get_section_vma (abfd, section);
 if (dump_pc < vma)
 {
   return;
 }

 size = bfd_get_section_size_before_reloc (section);
 if (dump_pc >= vma + size)
 {
   return;
 }

 dump_found = bfd_find_nearest_line (abfd, section, dump_syms, dump_pc -

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

/* Read hexadecimal addresses from stdin, translate into

  file_name:line_number and optionally function name.  */

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

                              char *function_name, char *source_name, int

source_line)

{

  char addr_hex[100];
  sprintf(addr_hex,"%x", address);

  dump_pc = bfd_scan_vma (addr_hex, NULL, 16);

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

  if (! dump_found)
  {
     strcpy(function_name, "??");
     strcpy(source_name, "??");
     *source_line = 0;
  }
  else
  {
     if (functionname == NULL || *functionname == '\0')
     {
        strcpy(function_name, "??");
        if (dump_filename == NULL)
        {
           strcpy(source_name, "??");
        }
        else
        {
           strcpy(source_name, dump_filename);
        }
        *source_line = dump_line;
     }
     else
     {
        strcpy(function_name, functionname);
        if (dump_filename == NULL)
        {
           strcpy(source_name, "??");
        }
        else
        {
           strcpy(source_name, dump_filename);
        }
        *source_line = dump_line;
     }

     /* fflush() is essential for using this command as a server
        child process that reads addresses from a pipe and responds
        with line number information, processing one address at a
        time.  */
  }
  fflush (stdout);

}

void dump_stack(void) {

  s16b i;
  static unsigned long stack_addr[MAX_STACK_ADDR];
  bfd *abfd;
  char **matching;
  long storage;
  long symcount;

  bfd_init();

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

  handle_stack_address(0);  handle_stack_address(1);

handle_stack_address(2); handle_stack_address(3);

  handle_stack_address(4);  handle_stack_address(5);

handle_stack_address(6); handle_stack_address(7);

  handle_stack_address(8);  handle_stack_address(9);

handle_stack_address(10); handle_stack_address(11);

  handle_stack_address(12); handle_stack_address(13);

handle_stack_address(14); handle_stack_address(15);

  handle_stack_address(16); handle_stack_address(17);

handle_stack_address(18); handle_stack_address(19);

  handle_stack_address(20); handle_stack_address(21);

handle_stack_address(22); handle_stack_address(23);

  handle_stack_address(24); handle_stack_address(25);

handle_stack_address(26); handle_stack_address(27);

  handle_stack_address(28); handle_stack_address(29);

handle_stack_address(30); handle_stack_address(31);

  handle_stack_address(32); handle_stack_address(33);

handle_stack_address(34); handle_stack_address(35);

  handle_stack_address(36); handle_stack_address(37);

handle_stack_address(38); handle_stack_address(38);

  /* dump stack frame */
  i = MAX_STACK_ADDR-1;
  while ( (i >=0) && (stack_addr[i] == 0)) i--;

  if (i < 0)
  {
     dlog(DEBUGALWAYS,"files.c: dump_stack: unable to get any addresses

off the stack.\n");

     return;
  }
  abfd = bfd_openr (argv0, NULL);

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

%s\n", errmsg);

     return;
  }

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

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

     return;
  }

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

error = %s\n", errmsg);

     return;
  }

  if ((bfd_get_file_flags (abfd) & HAS_SYMS) == 0)
     return;

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

%s\n", errmsg);

     return;
  }

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

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

%s\n", errmsg);

     return;
  }

  for (; i>=0 ; i--)
  {
     {
        char function_name[2048];
        char source_name[2048];
        int source_line;
        
        translate_address (abfd, stack_addr[i], function_name,

source_name, &source_line);

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

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

                         i, stack_addr[i], function_name, source_name,

source_line);

     }
  }

/* and cleaning up afterwards */

  if (dump_syms != NULL)
  {
     free (dump_syms);
     dump_syms = NULL;
  }

  bfd_close (abfd);

}

5.3 The signal handler

Now define some signal handlers like this:

ifdef SIGFPE

   (void)signal(SIGFPE, handle_signal_abort);

endif

ifdef SIGILL

   (void)signal(SIGILL, handle_signal_abort);

endif

ifdef SIG

TRAP

   (void)signal(SIGTRAP, handle_signal_abort);

endif

ifdef SIGIOT

   (void)signal(SIGIOT, handle_signal_abort);

endif

ifdef SIGKILL

   (void)signal(SIGKILL, handle_signal_abort);

endif

and define a function handle_signal_abort like:

static void handle_signal_abort(int sig) {

  bool                 save_ok = FALSE;

  FILE                *fff = NULL;
  char                 filename[1024];
  s16b                 i;
  bool                 dump_ok = FALSE;

  /* Clear the bottom lines */
  Term_erase(0, 20, 80);
  Term_erase(0, 21, 80);
  Term_erase(0, 22, 80);

  /* Give a warning */
  Term_putstr(1, 20, -1, TERM_RED, "You suddenly see a gruesome SOFTWARE

BUG leap for your throat!");

  Term_xtra(TERM_XTRA_NOISE, 0);

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

if defined(MACINTOSH) && !defined(applec)

  /* Global -- "text file" */
  _ftype = 'TEXT';

endif

  /* Drop priv's */
  safe_setuid_drop();

  /* Open the non-existing file */
  fff = my_fopen(filename, "w");

  /* Grab priv's */
  safe_setuid_grab();

  /* Invalid file */
  if (fff)
  {
     fprintf(fff,"Your game has just crashed. Please forward the

following\n");

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

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

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

relevant:\n");

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

happened?\n\n");

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

VERSION_MINOR, VERSION_PATCH);

     fprintf(fff,"STACK TRACE:\n\n");

     dump_stack();

     fprintf(fff,"\nCONFIGURATION:\n\n");
     fprintf(fff, "debuglevel 0x%08lx\n", debuglevel);

ifdef ALLOW_COMPRESSION

     fprintf(fff,"compression support compiled in\n");

endif

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

5.4 Compilation

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

6 Sample output

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

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

Angband/64 beta 5 release 5 (2.7.10)

STACK TRACE:

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

CONFIGURATION:

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

DISPLAY MODULES:

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

OPTIONS SET:

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

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

Redefinable Keyboard Bindings - Stuart George [dfiber@mega-tokyo.com].

Your friend is a diehard rogue player, the VI keyboard mapping is second nature to her.

You have just finished your whizzbang roguelike game, only it doesnt support the VI mapping as you detest it with a passion!

If you dont want to alienate some players, you need to keep them happy. You need redefinable keyboard bindings.

This requires a two-tier representation of the key. An internal (to your game) representation and an external (eg: ncurses, dos, etc) representation.

In my roguelike I maintained an enumeration of valid keys.

enum InternalKeyBindings { ik_NullKey=0,

ik_KeyDown, ik_KeyLeft, ik_KeyRight, ik_KeyUp,

ik_MAX_KEYS };

external key values are then mapped to the internal key values.

define _ALIAS_COUNT 2

unsigned long lngKeyBinding[ik_MAX_KEYS][_ALIAS_COUNT];

The _ALIAS_COUNT in the array definition shows that we can store up to two different key values per internal binding, for example, Open Door and Bash Door, say 'o' and 'b', could be an alias for the same key.

For this to work properly we must translate our keypresses from external to internal.

For something like NCurses,

unsigned long ncurses_GetKey() { return getch(); }

unsigned long TranslateKey() { unsigned long lngKey; unsigned long lngReturnKey; unsigned long lngLoopCount; unsigned long lngAliasCount;

lngKey=ncurses_GetKey(); lngReturnKey=ik_NullKey;

for(lngLoopCount=1; lngLoopCount<ik_MAX_KEYS; lngLoopCount++) { for(lngAliasCount=1; lngAliasCount<_ALIAS_COUNT;

lngAliasCount++) {

if(lngKeyBinding[lngLoopCount][lngAliasCount]=lngKey) { lngReturnKey=lngLoopCount; /* break out of the loop faster/nicer */ lngAliasCount=_ALIAS_COUNT; lngLoopCount=ik_MAX_KEYS; } } }

return lngReturnKey; }

Now we have our translation working, we can assign keys for our VI key fans and our VI key haters!

void BindKeys(void) { /* binds VI only */ lngKeyBidning[ik_KeyUp][0]='i'; lngKeyBinding[ik_KeyUp][1]=0; lngKeyBidning[ik_KeyDown][0]='k'; lngKeyBinding[ik_KeyDown][1]=0; lngKeyBidning[ik_KeyLeft][0]='j'; lngKeyBinding[ik_KeyLeft][1]=0; lngKeyBidning[ik_KeyRight][0]='l'; lngKeyBinding[ik_KeyRight][1]=0;

/* the uppercase KEY_* are NCurses constants */ /* binds non VI arrows + number movement */ lngKeyBidning[ik_KeyUp][0]=KEY_UP; lngKeyBinding[ik_KeyUp][1]='8'; lngKeyBidning[ik_KeyDown][0]=KEY_DOWN; lngKeyBinding[ik_KeyDown][1]='2'; lngKeyBidning[ik_KeyLeft][0]=KEY_LEFT; lngKeyBinding[ik_KeyLeft][1]='4'; lngKeyBidning[ik_KeyRight][0]=KEY_RIGHT; lngKeyBinding[ik_KeyRight][1]='6';

/* binds both VI and non VI together */ lngKeyBidning[ik_KeyUp][0]='i'; lngKeyBinding[ik_KeyUp][1]=KEY_UP; lngKeyBidning[ik_KeyDown][0]='k'; lngKeyBinding[ik_KeyDown][1]=KEY_DOWN; lngKeyBidning[ik_KeyLeft][0]='j'; lngKeyBinding[ik_KeyLeft][1]=KEY_LEFT; lngKeyBidning[ik_KeyRight][0]='l'; lngKeyBinding[ik_KeyRight][1]=KEY_RIGHT; }

Now you just have to remember to work with internal keys instead of external.

if(keypress==ik_KeyDown) instead of a hardcoded keyboard scancode or a hardcoded NCurses constant.

There are other things you can add to this, such as checking for a key that is bound two or more times.

Ultimatly the next step is to have all your key bindings in a config file that your roguelike reads in on startup, that way the user can bind whatever keys they like however they like them.

For my roguelike I allowed the player to bind NCurses constants into the config file (KEY_UP, etc) isntead of making them hunt down obscure scancodes for keyup \0\P etc.

Adding Meta key / CTRL / ALT key support is also another issue worth considering.

(*nb* the above code was written off the top of my head at work, but should be pretty much correct. Enough to get you started anyway)

How to write a roguelike gameengine - Esa Ilari Vuokko [eivuokko@mbnet.fi].txt

Some ideas that could be useful ? As shared by Esa Ilari Vuokko. Comments and bugfixes ;) to eivuokko@mbnet.fi

     I've played roguelike games for 7 years now. First I hacked Moria,
  which I got from friend (no modem or net connection :(). Then I got
  Omega which I still play (newer version, thought ;). At that time I
  got rid of Basic I was programming with and got Turbo Pascal. Well,
  I tried to do some pathetic games myself but they were just dead
  as they were real mode programs. Then (not earlier) I got nethack
  which I didn't like at that time. I hated djgpp (it's not bad, it's
  ugly in msdos) so I was bounded to real mode. Then I got Linux and
  installed it few times with no success (one time I installed it on
  broken hd, guess did it work, no - it just paniced suddenly ;). And
  I played ADOM, a lot. And then little Nethack and Omega.

     Because Linux I got all so mighty gcc and make. After playing for a
  while with graphics stuff (in linux and in win) and in winenv doing
  some accounting program (with delphi, thought I quitted after it
  started compiling wrong - I mean(debugged) it) I got an idea. In an
  accounting program we move money from one account to another (I'm sorry
  I know finnish terminology better than english). Well those accounts
  must be linked list because : they must be easy to create, modify and
  delete. Nothing new - a linked list. Of course all objects in rg should
  be in linked lists. But the what if even attributes were linked lists ?
  So that we had a linked list which can store data (some 16 bytes is enough)
  and a name (string) and children list.

     Listing attributes, skills, and everything that describes object with
  such presentation would be quite flexible. But if one does such game,
  and many people contribute to it ? It can go way off road as everybody
  add something new. A bloated memory use, and unneeded complexity are
  real threats. As normally, say ADOM, player char needs more memory
  (more variables) than npc. But in this approach we give npc only those
  skills and attributes it needs and we are still able to use same routines
  on both, player and npc.

     Of course above system can be optimized. I've defined it like this :
  Okey, I've got a bit more complex.
        class List {

private: List *child,*next,*parent; int id;

                int data[4];
                Link(List *);
                Unlink(List *);
                Query(int,int,int,int,int);
          public:
                int *Data();
                char *Name();
                int *Data(char *);
                List *Name(char *);
                int *Data(int,int,int,int,int);
                List *Name(int,int,int,int,int);
                Item *Index(int);
                int Index(Item *);
                int Count();
                List *Add();
                List *Remove();
        } ;

     Quite clear, I think. Id can be converted (by another class) to char.
  Almost all ints are for quick query. I use dot as delimiter between child
  and parent and I don't have plurals.  "skill.weapon.blade.short".

     Then I wanted an engine that doesn't need special cases. It would be
  (sorry for saying this) stupid to do special levels, which have special
  if of switch statement in level code. How could one have such a really
  flexible system ? Well I read Thomas Biskup's ideas of JADE. I don't know
  whetever he meant the same as I with the mentioning everything to be
  event based. So what I'm chasing here is that every object should have
  message handler list, which would handle requests to do something.

    Say we have a character A. A has handler list of next functions
  (stacked):
      creature_shield_deflector,
      creature_ro_poison_res,
      creature_basic_poison,
      player_non_ai,
      basic_creature_handler.

  First a monster(mage) B would shoot an firebolt to A. Firebolt code would
  send a message to A that some fire damage is  coming. First this message 
  would reach first handler in list, creature_shield_deflector. That would 
  say "no,no fire damage" and that would be it, no damage to creature. Then
  B would throw a acidbolt. Well this time deflector would say nothing as 
  wouldn't other before basic_creature_handler. That would make some damage 
  to creature and spare some to inventory too (and send approciate messages 
  to items). Then would engine send TIMEUPDATE to creature, which would be 
  handled first by creature_basic_poison. Well it seems this creature has 
  poisoning and handler would notice that it just ending. First it sends to 
  creature A (self) damage message of poison, which would end to 
  creature_ro_poison_res, and no damage. Then it would return 
  UNLINK_AND_CONTINUE so that it would be removed from list and message 
  (TIMEUPDATE) would be sent on. Then message would reach basic_handler which
  would add some speed to energy (ADOM) or add a timepulse (nethack,angband).
  If it would be creature's turn to move, it would send message ACTION to 
  itself (creature A). That would be caught by player_non_ai which would wait 
  for keypress and then do whatever is defined and player wishes to do.

     Because paragraph above seems a bit unclear ;) I'll do an easier
  table here :
     1 creature_shield_deflector,
     2 creature_ro_poison_res,
     3 creature_basic_poison,
     4 player_non_ai,
     5 basic_creature_handler.

  Messages :
    Fire damage
      1 - take message (do nothing) return KEEP_AND_STOP -> that's it.
    Acid damage
      1 - no action, return KEEP_AND_CONTINUE
      2 - no action, return KEEP_AND_CONTINUE
      3 - no action, return KEEP_AND_CONTINUE
      4 - no action, return KEEP_AND_CONTINUE
      5 - Share damage to creature and inventory, send damage message to
          inventory. Return KEEP_AND_STOP.
    TIMEUPDATE
      1 - no action, return KEEP_AND_CONTINUE
      2 - no action, return KEEP_AND_CONTINUE
      3 - Check if it's poison time. If it is send poison damage to self:
             Poison damage
               1 - no action, return KEEP_AND_CONTINUE

2 - Take message (do nothing) and return KEEP_AND_STOP. If poison is diluted enough return UNLINK_AND_CONTINUE else return KEEP_AND_CONTINUE

      4 - no action return KEEP_AND_CONTINUE
      5 - Check whetever it's time to move or not (some way to count time
          compared to time). If it is send ACTION to self.
             ACTION
               1 - no action, return KEEP_AND_CONTINUE
               2 - no action, return KEEP_AND_CONTINUE
               3 - no action, return KEEP_AND_CONTINUE
               4 - Normal player's turn in roguelike games.

return KEEP_AND_STOP.

     KEEP_AND_CONTINUE, UNLINK_AND_STOP etc mean whatever function which
  handles handler lists should keep sending message on in list and if
  handler should be removed from list.

     Yes, I know, this is really heavy way to do things. But if we can count
  on fast 486, it is REALLY flexible. I think that with handlers lists and
  description lists we can mimic any game we want or make just about anything
  we want (well world conquest is a _bit_ hard maybe, but as rg game anything)

     I'm sorry if there's too many errors in my english. I didn't mean to
  be offensive either but I needed to make my point clear (if it can be
  done at all). If someone has implemented this allready, good, sorry to
  say that I were to late.

     I'm sorry if there is something that have been published before and
  I don't want to claim that I've been first to thing this kind of things
  but I haven't seen anything like this before (I haven't read too much).
  Anyway Copyright 2000 Esa Ilari Vuokko. I don't (of course) take any
  responsibility of anything you do or don't do with this text. It can be
  freely copied and published electronically as long as it isn't modified.

Heap Space Conservation - Steve Segreto [ssegreto@titan.com].

Or How to have LOTS of monsters and LOTS of treasure in your Roguelike.

   Here are some tips for conserving precious heap space, so that you

will be able to populate each of your dungeon levels with as many monsters and items as you want! This is a good alternative to having to write a protected mode program, and while it may be a little too slow for some 386s, the algorithms can be tuned as needed. The basic concept is that you will only store in RAM as little as you possibly need to know about all the monsters and items. All the rest of the stuff (specific information about a monster or item) you store on the player's hard drive. The speed versus memory usage trade-off is obvious. You will use a lot less RAM by only storing the indices into the disk files in a linked list in memory, but your game will be slightly slower because you must frequently return to the hard drive and read/write information from it (this is VERY slow compared to reading/writing from RAM).

Anyway, here is some sample code for storing indices for monsters and items using ANSI C and assuming that each of your dungeon levels is 80 cells by 25 cells, for a total of 2000 square cells (this may be smaller or larger than what you want for your roguelike). My ANSI C is pretty rusty (I prefer Pascal) so please be aware that this code does contain syntax errors.

/////////////////////////////////////////////////////////////////////////////////

// BEGIN CODE FRAGMENT /////////////////////////////////////////////////////////////////////////////////

   #define MAX_ROWS 25
   #define MAX_COLS  80
   typedef unsigned int word;   // 16-bit quantity
   typedef unsigned char byte; // 8-bit quantity
   typedef enum NodeTypes = { MONSTER, ITEMS }; // Different sorts of

data files you will have

/////////////////////////////////////////////////////////////////////////////////

   //  A singly linked list of indices.

/////////////////////////////////////////////////////////////////////////////////

   typedef struct index_list_node;
   typedef index_list_node *index_list_node_ptr;
   struct
   {
        word                       index;
        NodeTypes             node_type;
        index_list_node_ptr link;
    } index_list_node; // Size = 7 bytes
    // Related list functions are new_list(), free_list(),

insert_before(), insert_after(), is_empty(), is_full()

    //  advance_list(), reset_list(), read_list_from_disk(),

write_list_to_disk()

/////////////////////////////////////////////////////////////////////////////////

   //  Records to hold monsters and items on diskette.

/////////////////////////////////////////////////////////////////////////////////

   typedef struct
   {
         byte row, col, depth;
         char symbol; // Whatever data you will have to represent a

monster: name, hit points, AC, etc.

    }monster_record;

   typedef struct
   {
         byte row, col, depth;
         char symbol; // Whatever data you will have to represent an

item: weight, damage, etc.

   }item_record;

/////////////////////////////////////////////////////////////////////////////////

   // Global array of index_list_nodes for each square of the dungeon.
   // Initiallly this array will be MAX_ROWS * MAX_COLS * sizeof

(index_list_node) bytes large

   // 80 * 25 * 7 = 14,000 bytes plus 7 bytes for every monster/item

added.

   // Assuming about 150 monsters and 200 items per level, this gives

you 14,000 + (7 * 350)=16,450 bytes

/////////////////////////////////////////////////////////////////////////////////

   index_list_node object_array[MAX_ROWS][MAX_COLS];

/////////////////////////////////////////////////////////////////////////////////

   // Because the above list will only contain INDICES into permanent

disk files, deleting elements from the list

   // such as when an item is picked up or a monster slain, will be

extremely slow (because the entire level file

   // on disk will have to be re-written minus one single record). To

alleviate this, simply keep a second linked

   // index list of all the indices which need to be deleted from the

permanent disk file when the player leaves this

   // dungeon level (these indices have already been deleted from the

object_array linked lists.) Remember to

   // insert indices into this list EVERY time a monster is killed or

an item is picked up (you might want to

   // have a function delete_monster(which_row, which_col, what_index)

which removes the specified node

   // from the object_array[] linked list and also inserts it into the

deleted_list [Do you see why you need to

   // pass in what_index? That's right, so you can go to the

appropriate (what_row, what_col) element in object_array

   // and traverse that linked list until currPtr->index == what_index,

then you can delete this node and insert the

   // what_index into the deleted_list!] ).

/////////////////////////////////////////////////////////////////////////////////

    index_list_node deleted_list;

/////////////////////////////////////////////////////////////////////////////////

   // You will also have two disk files per dungeon level, one for

MONSTERS and one for ITEMS.

   // You must devise a naming scheme for each (LEVEL01.MON and

LEVEL01.ITM for example)

   // LEVEL01.MON is a random-access file of monster_records and

LEVEL01.ITM is a random-

   // access file of item_records, one record per monster on that level

and one record per item on the

   // level. Note that these disk files may be quite large

(sizeof(monster_record) * num_records bytes).

/////////////////////////////////////////////////////////////////////////////////

   // stock_depth()
   // Call this function at the start of the game or whenever the level

needs to be completely re-stocked:

/////////////////////////////////////////////////////////////////////////////////

   void stock_depth ()
   {
       // 1. Open the appropriate monster level file (LEVEL01.MON for

example)

       // 2. Read each monster_record one at a time into a local

variable, m

       // 3. Based on the m's (row, col, depth) triple, use the

appropriate element of the global object_array[].

       //     For example, if m.row = 10 and m.col = 10 then

object_array[10][10] would have a singly linked list

       //     of index_list_nodes.
       // 4. Insert the index into the linked list (use insert_after()

from the basic list routines above).

       // 5. Do the same thing for the item level file.
       item_record i;
       monster_record m;
       FILE *infile;
       word index = 0;

       // Add all the monsters to our array of linked lists.
       infile = fopen ("LEVEL01.MON") // This line is not syntactically

correct

       while (!eof(infile))
       {
           fread (infile, m); // Wrong also!
           insert_after (object_array[m.row][m.col], index, MONSTER);

// The index is the record number and the linked list is

// at (m.row, m.col)

           index++;  // Move on to the next record
        }

       // If there are not enough monsters on this level, ADD monsters

until there are enough.

       // Add all the items to our array of linked lists.
       index = 0;
       infile = fopen ("LEVEL01.ITM") // This line is not syntactically

correct

       while (!eof(infile))
       {
           fread (infile, m); // Wrong also!
           insert_after (object_array[i.row][i.col], index, ITEM); //

The index is the record number and the linked list is

// at (m.row, m.col)

           index++;  // Move on to the next record
        }
    }

/////////////////////////////////////////////////////////////////////////////////

   // change_depth()
   // Call this function every time the player changes dungeon levels,

including at the end of the game:

/////////////////////////////////////////////////////////////////////////////////

   void change_depth ()
   {
       // 1. Open the current monster level file (LEVEL01.MON for

example)

       // 2. Open a temporary file
       // 3. Read each record one at a time into a local variable, m.
       // 4. If this record number (index) is NOT in the deleted_list

(see above) then write this

       //     record to the temp file (otherwise DON'T write the record

to the temp file).

       // 5. Close and delete the monster level file.
       // 6. Rename the temp file to the same name as the monster level

file.

       // 7. Now the temp file contains all the records except those

which have been deleted (dead monsters).

       // 8. Do the same with the item level file.
       // 9. Call free_list() to destroy the linked index list.
       // 10. Based on the new depth, call stock_depth() with the new

depth number to load/build the new index_list.

/////////////////////////////////////////////////////////////////////////////////

   // square_has_monster()
   // Simply scan the linked list at object_array[which_row][which_col]

and return TRUE as soon as one of

   // the nodes has a node_type of MONSTER.
   // You can devise a similar function for square_has_item().

/////////////////////////////////////////////////////////////////////////////////

   boolean square_has_monster (byte which_row, byte which_col)
   {
       // List at this square is empty (square has neither monster nor

items)

       if (object_array[which_row][which_col] == NULL) return (FALSE);

       index_list_node currPtr = object_array[which_row][which_col];
       while (currPtr != NULL)
       {
            if (currPtr->node_type == MONSTER) return (TRUE);

            // Move down the list
           currPtr = currPtr->link;
       }
       return (FALSE);
   }

/////////////////////////////////////////////////////////////////////////////////

// END CODE FRAGMENT /////////////////////////////////////////////////////////////////////////////////

Handing Out Experience - Rick Carson.txt

Roguelikes are part of a family of games in which the participant builds something over time. Relatives are of course roleplaying games and other storytelling games. Distant relatives are games such as Civilization.

Since players often fail to achieve the primary goal (e.g. retrieve the artifact of lint removal which will cleanse the bellybuttons of everyone in the universe thereby ending world hunger) the secondary rewards (or payoffs (or utility for all you economists out there in RL land)) become very important.

Too much advancement too quickly (kill a kobold - get to 35th level) devalues

the payoff, whereas too slow an advancement (kill everything in the whole game and maybe get halfway to level 2) means that they never even get to feel rewarded.

Of course experience might be handed out for a range of activities, not just killing things. such a list is certainly not limited to: solving quests; receiving damage; causing damage; casting spells; using skills; getting treasure; idle gossip; donations to the (un)worthy cause of your choice; doing nothing or resting; healing; travelling, mapping, making other players laugh....

So lets consider the case of a fairly generic dungeon bashing roguelike.

The dungeon has sixteen levels, a predetermined number of monsters per

level, and unique monsters. There are no 'random' monsters. We'll call our theoretical roguelike Jiavlo and code it in Java. (Stop me if I infringe any copyrights ;-)

Experience is only handed out when we generate a monster killing event.

Our first realization is that in this scenario there are a fixed number of monsters, and that this means that there is an upper limit for how much experience the player will ever get.

We need to decide how many levels we want the players to be able to gain.

So what constitutes a good number of levels that could be gained?  Most

of the audience will have at least a passing familiarity with the D&D game family, in which you start at level one, and progress is technically unlimited,

but which is less meaningful once you get into double digits.  And certainly

once you get into the low twenties you are in danger of being accussed (unjustly of course) of being a 'power gamer'. So most of the target audience is going to be happy with a top level of around 15 to 30. Twenty is a nice round number in that range which should give a decent payoff in terms of achievement.

Note that the point is not to mirror any particular published system for which one runs the risk of being sued and losing the shirt off ones back,

but rather to recognise and take advantage of this subconscious assumption

that most people are going to make, ie that getting to level 20 is a superhuman feat and that getting to level 12 (say) is pretty spectacular.

The other thing to do is to make the experience scale exponential (this means that each level requires more experience to get to than the level before it). Mathematically there is no reason for this, but people will expect it, and because of their expectation they will not feel as much of a payoff if they get the same amount of experience for killing a dragon as a kobold. Because of this, I recommend using a spreadsheet to play around with the numbers till you some that you like. Hopefully you won't need a spreadsheet to follow this article though!

It is useful to consider the linear case here though, because it forms a basis from which you can build the exponential formula, and if you do so you will be much more likely to get a well balanced game. But before we look at the linear model, lets examine the constant model. This is even worse in terms of payoffs, but much simpler again to balance properly.

For every monster you kill you get 1 xp. There are 50 monsters per level. (Times 16 levels is 800 xp) We can now say something like, for every 40 xp you have, you go up a level.

(800 divided by 20).

Note that you start at level 1, so you would get to level 20 after killing 760 creatures, ie you max out your levels shortly before you kill the UberLintDaemon which drops the game ending artifact, so that you have time to enjoy maxing out on levels before the game ends.

If the monsters on deeper levels get harder to kill, then logically players would try to clear a level before progressing to the next in order to get the 'easiest' xp first (minimise risk, maximise payoff).

Note that we are requiring them to kill 40 monsters in order to advance to second level. This is far too harsh, and for many first time players this will take too long for them to get hooked. Ten is a much more reasonable number. And we want them to be able to get to say level 5 or 6 fairly quickly before it becomes hard slog. So lets break it down, lets say that by the end of dungeon level 15 they are level 20, and they gain a level per level they clear back till say the player is level 10. That means that we then need to plot the xp from 0 (at level 1) to 250 (which they have after clearing 5 levels at level 10). We could go back and rewrite our assumptions, and have them start at level 0, and then have them gain a level every 25 points.

That makes it nice and easy for us in terms of maths.

The effect this has on the game though, is to make the clearing of each level a hard thing at first, and then get easier halfway through each level.

This is actually not too bad in terms of payoffs, because the player begins

to notice that the monsters are easier to clear after going up the level.

So lets modify how players go up levels. Here is the table (level, xp required): 1 0 2 5 3 15 4 30 5 50 6 75 7 105 8 140 9 180 10 225 (and 50 per level after that).

So at the end of clearing level 1 (50xp), they are fifth level, clearing level 2 puts them at sixth level verging on seventh, etc. This uses a clear progression, in order to go up a level, you need as much extra xp as the last time you went up a level, plus five, until you get to needing 50 a level where it tops out).

Despite the plain maths behind this, I would be tempted to fiddle with it even more, because fifth level after clearing only one level of monsters seems 'too much'.

But lets take this 'constant' model, and see what happens when we make it 'linear'. We assume that all the monsters on level x of the dungeon are 'level x monsters' and we give x points for killing them. The maximum amount of experience in the game is now: 6800. The maths for working this out is starting to get more complicated, but the formula is: (((n squared) plus n) divided by 2) times the number of monsters per level). Where n is the number of levels, and the number of monsters per level is still 50.

Obviously we cannot now just multiply the cost of going up levels by 8.5

(6800 divided by 800) because that would mean we would need 85 xp to get

to second level, which means clearing all of level 1, and a third of level 2. All of a sudden things look a lot harder! One way of solving this, is to try to match monsters killed to levels gained, assuming that all the low level monsters are killed first. This is easier than it sounds for levels 10 through 20, because we already know that we want the player to advance at the mid point of the level. And this is not too hard to work out (especially with a spreadsheet).

&gtFrom 10th level and up (level, xp required): 10 900 11 1225 12 1600 13 2025 14 2500 15 3025 16 3600 17 4225 18 4900 19 5625 20 6400

(The formula for this is: (((n squared) plus n) / divided by 2) plus (25 times (n plus 1)) where n = level required minus 5. The minus five is because we have five more experience levels than the last level of the dungeon that we cleared)

Now if we want to keep the same progression, that is, getting to level five after clearing the first level of the dungeon (yuck!) we leave that bit of the table alone, and figure out a progression from 5th level to 10th level. Or, we can choose another formula to govern low level advancement,

such as: (n times n) plus (14 times n) minus 1, where n is the current

level which yields: 1 0 2 14 3 45 4 95 5 166 6 260 7 379 8 525 9 700

Which is a much nicer fit to the lower levels of the dungeon and how fast they should advance. Unfortunately I've just noticed that it bears a striking similiarity to the xp curve in Crawl. What a shame :-)

But of course noone wants to get 12 xp for killing a Dragon, so we need to think about how much xp we want to hand out for killing a monster of each level. I suggested at the start of the article that making it exponential is probably more in fitting with the players expectations. Lets say that on level one you get 1 xp per monster killed, and on level 16 you get 10, 000 xp per monster (so level 16 has half a million xp of monsters on it - suitably impressive amount :-)

A 'basic' formula for this would be: (n to the power of ((n minus 1) divided by (15 divided by 4)))

Which gives these results: 1 1 2 1.847849797 3 3.414548874 4 6.309573445 5 11.65914401 6 21.5443469 7 39.81071706 8 73.56422545 9 135.9356391 10 251.1886432 11 464.1588834 12 857.6958986 13 1584.893192 14 2928.644565 15 5411.695265 16 10000

You then need to figure out how many xp are needed for each level (use a spreadsheet!), and split the difference between levels, and then somehow figure out a formula for advancing. I came up with (2 to the power of n) plus (n cubed) minus (25 times n). Which is ok, but given more time we could come up with something better. In particular, I'd reduce the base number of the power to something in the range of 1.97 to 1.99 so as to get closer to the 'ideal' value for that last level (you would get to 20th level with three creatures remaining given the formula above).

Some things to think about: do the rewards actually match the difficulty.

For instance if a level 12 monster isn't really much harder to kill than

a level 8 monster, why hand out ten times as much xp for killing it?

In fact, the difficulty of balancing even a limited scenario as outlined above means that you are far better off having a 'complicated' function for handing out experience, than aiming for some mathematically pure function.

An example: Offense * Defense is a very good measure of combat capability (ignoring the effects of swarming, assume that the character can always retreat such that they only fight one monster at a time). Offense is the average damage they do (ie chance to hit times average damage times number of attacks) and defense is how much damage they can take on average (ie chance to avoid damage times hit points).

Example 1: a rat which does 1-2 points of damage, has a 1 in 3 chance of hitting, has no chance of dodging and 2 hitpoints would be worth 1 xp. ((1.5 times (1 divided by 3)) times 2) Example 2: a balrog which does 10-20 points of damage, has a 100% chance of hitting, gets three attacks a round, avoids (dodges/deflects/counterspells/whatever) 50% of attacks and has 100 hit points would be worth (15 times 3) times ((100 divided by 50) times 100) or 9000 xp. Actually, that might not be enough :-)

You can increase the spread by raising the amount of xp from the above formula by some power greater than 1, try 1.1 or 1.2. 9,000 to the power of 1.2 is 55,602 which should keep the players happy. Whereas 1 to the power of anything is still 1.

Other factors to consider are the dungeon level the character has gotten to, what resistances the monster has, whether the monster has ranged attacks (these are really nasty in roguelikes, you may wish to reward the players accordingly) and whether it drops items that help the player (which are a reward in themselves in that they improve the character) when it dies.

Of course killing an Elder Dragon and having the experience it gives you

reduced by 10% because it dropped a +1 dagger, would suck.

In terms of experience to go up levels, something to avoid is requiring as mush xp to go from 1 to 2 as from 2 to 3. This can happen when you use an exponential curve that doubles for a while. Just as a wild totally random example, take a fighter that needs 2000xp to get to level 2, and 4000xp to get to level 3, and 8000 xp to get to level 4 etc. Now think about this,

in order to get to level 2, the fighter had to gain only 2000xp, but this

is also the amount they need to gain in order to get to the next level, but now they have an extra levels worth of hitpoints, better chances to hit etc, which means that it is easier to get from 2 to 3 than it was to go from 1 to 2. And the game shouldn't get easier as they go up levels.

cheers,

Rick

Allocating Experience and Character Advancement - Matthias E. Giwer [mgiwer@ij.net].

First, a brief bit about my experience in this area:

I've been an active player of "pencil and paper" role playing games since 1987, encompassing more than thirty (truthfully, I've forgotten all the games I've played) different systems, as well as a number of "tactical" games such as BattleTech, Warhammer, etc.

I've spent (wasted :) hundreds of hours in roguelikes such as Larn, Moria, Nethack, (A-Z)ngband, ADOM, etc. I attempted to develop my own on several occasions, the most recent attempt being Saga, a Perl roguelike.

I do not claim to be the worlds most serious gamer, nor the worlds best software engineer, but I do feel I have enough experience on this subject to be able to offer some useful information.

Now, on to the meat:

How you implement character advancement will depend heavily on your choice of game mechanics. For example, is it a level based system where a 10th level being will be ten times more capable than a 1st level being? a hundred? Or is it entirely skills based, where facility with a particular weapon or ability is to be developed independently of any other capability?

The majority of current roguelikes seems to be dominated by levels and level/skills hybrids. This is fine, though while I personally advocate an entirely skills-based approach, it is truly a matter of taste.

The base idea is that individual actions performed by the characters will return (on success, failure or both) some measure of "experience", either generic or towards the skill governed by the action. In order to develop a mental yardstick, I usually try to get a firm idea of what a brand new, baseline character is capable of. In most roguelikes today, that would be a human fighter.

Next, try to imagine what this character would be capable of, if his abilities were taken to their absolute limits, without regard to items and equipment that may boost her capabilities. This should give you a continuum of capability that will let you look at, and gauge, difficulty of things like quests, unique creatures, and so on.

It also usually helps me to think of creatures that this character may face as based on this brand new beginning fighter. In other words, a Grey Kobold is about half the power of a beginning fighter, but an Elite Orc Guardsman is six times more powerful than the baseline.

Yes, there is a LOT of tweaking and experimentation involved to get it right. Also, many abilities can make combat orders of magnitude simpler (teleportation, ranged attacks, etc) so this has to be taken into account when trying to judge anything other than a raw fighter type. Again, there is no perfect measure, experimentation is the key to balance here.

If you wish to model the real world, most performance type skills (dancing, martial arts, typing, etc) are developed in terms of plateaus that may take months or years to break through, usually on a sliding scale of time. The first plateau might take only a few weeks to reach, but the next may take a few months, etc. Roguelikes (and many traditional RPG's) model this with each "level" requiring progressively larger amounts of experience points to reach.

However, because most games give out larger amounts of experience for more difficult and more powerful creatures, the result is that most characters end up on a hyper-accelerated track, and can reach quite amazing levels of skill in relatively short amounts of game time. Now, as a fantasy game goes, that is perfectly acceptable, but it does make it more difficult to judge when a player is ready to face the "Deep dwelling Thing from Beyond". Then again, people don't play roguelikes because they are easy. ;)

I would have no issue with this, if it was a one-time event. For example, the first time you wipe out a Grey Ooze, get the full experience value for it. For each one after, only bestow a standard action credit that doesn't change, for all actions of that type. New things, and new challenges help you grow a lot, practice helps you a little (which is why you have to keep at it).

An extension of this idea is experience for, say, casting spells. You get full experience value the first time you cast a new spell, but only a small "cast spell" value each time thereafter. The idea works for any ability that is action based, rather than intrinsic or "always-on".

For added realism (ha :), it may be worth investigating a "decay" function for skills and abilities that go unused for long periods of time, with the time before decay increasing the higher the level of skill.

Like the design of any game system, this article is two parts experience and one part prejudice. I hope that, at least, mentioning these issues will prompt roguelike designers to devote more thought game mechanics issues, and to question some accepted standards.

I do apologize if you were looking for code examples, but the entire issue of character development is so tightly bound to the specific system and other game mechanics to make even pseudo code examples just about worthless.

Feel free to write me with questions, comments, etc. Please keep the flames constructive, thanks! :)

-Matthias E. Giwer mgiwer@ij.net

Creating A Player - Brian Bucklew [bbucklew@inteletek.com].

Section 1 : The Definition

[Note : I will be using C++ Class definitions]

       So, let's pretend we have a nice endless dungeon filled with

vile demonic beasts, heaps of gold, and piles of flaming swords of instant monster to magic item transmutation. Mabey we even have an engine to make the ubiquitous '@' saunter around in this great dungeon.

       Now, what we really need is some way to make that little '@' into

a daring adventurer, with Herculean strength and an intelligence to rival Hawking (or perhaps the lack of the same...).

       First off, we need to have some basic statistics and attributes.

perhaps we need a Name, a Race, and a Class... We also need some numbers to represent the Hero's strength, and intelligence as well as his other important attributes.

       Now, in any RL, a player's Statistics are going to go up and

down during the course of play, whether it's from going up a level or getting hit by a Lecherous Walking Carrot Of Charisma Sapping. So we should really represent each score by two numbers, a current score and a base score:

class Stat {

       public:
       int     Base;
       int     Current;

}

       All of our calculations done in the game should be based off of the

current score, but the base score will allow us to revert to the Player's origional score or hit-point total after a magical-effect or damage wares off.

       Having the basic stat class, let's go ahead and derive a class to

contain a basic RL character:

class Player {

       public:
       char    Name[256];      // A String to hold the player's name
       int     Race;           // let's say, 0=Human 1=Elf 2=Frog...
       int     Class;          // hmm... 0=Fighter 1=Mage 2=Tourist...

       Stat    Str;            // How Strong
       Stat    Int;            // How Smart
       Stat    Dex;            // How Fast
       Stat    Hlt;            // How Healthy
       Stat    Cha;            // How Well-Liked

       Stat    HP;             // How much damage you can take
       Stat    AR;             // Your armor-rating
       Stat    SP;             // Spell-points... How many kobold you can toast

};

       That should be a good starting point for developing a unique character

representation for your RL...

Section 2 : The Creation

       The actual creation of the character is accomplished by somehow

assigning a score to each of the stats... There are two main ways to accomplish this; Random Rolling and Point Distribution.

       Random Rolling would display all of the statistics, and allow

the player to hit a key to "Roll" (or randomly assign numbers, say between 1 and 100) to each main statistic. The player would then continue rolling until they have a set of numbers that is agreeable to them.

       Point Distribution would give the player's a number of points, say

100, and allow them to distribute those points to their attributes in any way they wish; Thus allowing the player to design a character that they want to play.

Usually, the player's chosen race affects the statistics in some way. For instance if our player picked:

A Human - No change; Humans should be pretty standard fare. An Elf - +2 Dex, -2 Str; Elfs are quick, but weaker than humans A Frog - +2 Int, -2 Cha; Frogs are obviously intelligent, but ugly...

Classes are generally restricted by attributes...

Fighters - No basics; Everyone can pick up a stick and hit something... Mage - At least a 12 Int; A Mage has to read, at least... Tourist - At least a 12 Dex; You have to move fast, only 36 days left of

                             vacation...

The player might be given some basic equipment based on his class, and that's about it... That '@' has everything it needs to thump some Kobolds!

The Author: Brian Bucklew, 18 bbucklew@inteletek.com Current RL Project : Dungeon or "This game needs a new name"... :) Projected Beta Release : Early 98

Pretty Pictures - Darren Hebden [rogue@skoardy.demon.co.uk].txt

Some thoughts on Graphics in Roguelike Games. by Darren Hebden [rogue@skoardy.demon.co.uk]

Traditionally, if you suggested graphics to a roguelike- stalwart, you would have found yourself out on your ear for speaking such heresy. Many would argue that being text-based is a defining feature of the roguelike genre. Others want more and look upon graphics as a natural progression.

Many people (purveyors of quality knee-jerk reactions and 'The end is Nigh' flavoured rantings) warn of the old-style being phased out or graphic-based roguelikes lacking the same depth of text-based. Personally, I like to believe that both can exist quite happily and that the addition of graphics in roguelike games is a bonus, not a replacement. It is a new feature and it's use within the roguelikes is still being explored.

This document talks a little about the uses of graphics in roguelikes, the different styles and some graphic techniques. Not being an expert on all systems (or the one I own, come to that), I'll try to make my article non-machine-specific. If you know a little about the packages you own, you should be able understand my texts.

                             ----//----

Why Graphics.

PROS. 1) It's a "draw". The visual style attracts the eye to games that many of the uneducated heathens (sorry, I mean -- people who haven't encountered roguelike games before) would ignore and pass over because of their archaic text-editor style appearance.

2) It's expected. Unfortunately, the expectations of todays game player have been adversely influenced by big budget, multi-cd, flashy productions. I don't exactly find this a pleasant situation but ignoring it or "taking a stand" won't help you or your game.

3) So what's a 'Furgikan-bug'? Although a great deal of people are up on Tolkien lore and AD&D monster theory 101, but an unknown creature shown as a 'F' character on-screen may leave several of your players scratching their heads. A well-drawn image, however, is instantly recognisable and gives a better impression of the creatures appearance.

CONS. 1) Graphics kill the imagination. The original roguelike style counts on the players imagination to transform a simple red 'D' into the terrifying bulk of Fire Dragon flesh. No matter how detailed your graphics are, they may not be able to live up to the visions swirling around an over-active imagination.

2) Bigger programs. The storage of large amounts of graphics data all adds to the overall archive size for your game. It's very difficult to produce a competent roguelike game with a small selection of graphics without compromising the colour-depth or tile size. Whichever way you even things out, graphics mean an increased game footprint.

3) Bad graphics drag a game down. Good graphics can really add to the atmosphere of a game but in the same way, a bad set of graphics can seriously hamper a game which is technically competent and full of depth. Will you be able to supply good graphics for your game or would the game be better served staying with a text only display? Don't treat graphics like the current band-wagon to climb aboard.

                             ----//----

Graphic Styles.

Although all through this document I speak of older roguelikes being text based, simple texts characters _are_ a form of graphics. A 'g' from a gremlin may be missing a few limbs and that mad glint in his eye but people soon become lost within the game world and accept that a horde of crazed 'g's bearing down on a weakened adventurer is not a good sign.

There are several different styles that you can use when representing your dungeon on-screen.

1) Flat Tiles. The most typical use of graphics in roguelikes is a one-for-one replacement of the ascii-characters themselves. A wall character is replaced with a brick pattern, a water character by a lump of blue.

A little work is needed re-assigning what is displayed or how they are arranged on screen but often, this method restricts the artist in getting the best from the tile size and colour depth available. Due to the forced nature of the way the tiles may be arranged, the artist could be unable to introduce some details that would improve the overall look.

This style doesn't _have_ to suffer from badly arranged tiles if the artist uses the way the tiles are placed to his benefit and the programmer is willing to make slight alterations to get the best out of the tiles provided. The perfect solution is to be programmer and artist :-)

Badly drawn example... XXXXX

2) Pseudo-3D Flat Tiles. The next style is very similar to the first but instead of flat patterns for tiles, the impression of depth is given by drawing front edges on lower half of the tile for the walls. It's a cheap trick but is quite effective. The illusion is only spoiled by the fact that the player cannot walk behind the tiles as they occupy the same space as a normal wall tile. A little 'walk-behind' effect can be gained if the tiles are overlapped. It okay but you also begin to lose a little of the floorspace of the tile above.

All in all, a popular choice and for tiles that need a little more work when it comes to designing them to fit together. It means more graphics but generally, it's worth it.

Badly drawn example... XXXXX

3) Isometric Tiles. These tiles create the impression that the level is viewed from an angle of 45 degrees to the left/right. As they go, this style gives a very good illusion of depth (apart from the total lack of perspective, ofcourse).

A problem with this style is that these tiles really need to overlap. I've tried some experiments with not overlapping them and they looked very bizarre. The overlap causes a bit of lost floorspace of the tiles drawn above the walls but this can be reduced by having shorter walls.

As with the overlapping from the previous style, don't go over the top with the shortened walls though or you'll have levels looking like a stunted hedge-maze.

A solution would be to make any wall that overlaps a floorspace semi-transparent. This effect can be achieved by either some rather clever palette mixing tricks on the programmers side of things (which is rather a bit of overkill for a roguelike) or by a chess-board style hashing of the pixels over the overlapped area -- one pixel of the wall, one of the floor, etc. It is a bit of a cop-out but quite effective.

Badly drawn example... X

4) Tunnel Vision (or That-Style-From-Dungeon-Master). The player is presented with a full perspective view of a corridor/tunnel of the dungeon. Items in the distance are smaller and tunnels lead off from the original at right angles. Movement is generally made in steps and switching the direction viewed usually snaps round ninety degrees.

This style allows for more detail on the wall/floor tiles as the tiles closest to the player are quite large on screen. I've yet to see this used in a roguelike game although it has been suggested quite a few times. Other games have used this style and in some ways, you could argue that Dungeon Master, Eye of the Beholder, etc. are in essence roguelike.

One reason for it not being implemented is that the player can only see in one direction at a time. Usual roguelikes have forces coming at the player from all sides. This may put several players off due to the confusing nature of this 'realistic' feature. Other windows containing the left/right/back views may help this situation.

Badly drawn example... .........

                        |.......|
                        ||.....||
                        |||   |||
                        |||   |||
                        ||.....||
                        |.......|
                        .........

5) 3D Texture Mapped. The last style I'm going to cover is texture mapping. So far (without making a massive leap with the definition of the genre), no roguelike game has ever used texture mapped 3D graphics. I'm sure if you visualise a game like Quake, or whatever the current splurge of the month is, you'll realise what I'm getting at here.

One problem with texture mapping is that to get a good definition on the walls, floors, etc. the textures need to be of a fair size otherwise, close inspection of a wall reveals a horrible level of pixelisation. 3D accelerator cards (and a certain console) can provide techniques to smooth the textures but now we're getting into silly-land. Roguelike game with texture-mapped polygons needing a 3D accelerator card? Hmm. One day maybe...? ;-)

Anyway, it's really up to you as to what looks right and at what point it stops looking like a wall pattern and more like a bunch of large square pixels. Working towards high quality textures means bigger textures and even more space taken up by the graphics.

Obviously, programming such a view for just a roguelike game is no small fear either when compared to the original text-mode (or even the other styles mentioned in this document). How you present your 3D environment is up to you. Possible options are the fully submersing environments of Quake/Mario64. Or you could go for an isometric display such as Bullfrog's Dungeon Keeper.

Badly drawn example... Yeah, right.

                             ----//----

Issues

Some problems you might want to take into consideration when working on your graphics...

Colour Depth.

Colour depth is essentially how many colours you're allowed to create your wondrous and vivid roguelike graphics. Basically there is two camps. The programmers want the less number of colours possible and the artists generally want the most. The exception to the programmers is when the programmer in question doesn't care how much space the game takes or already has the code to handle higher colour depths. The exception with artist is when you find an artist who knows they can get the same effect with less colours.

A set of tiles that only use a palette of 16 colours but have been stored as in a graphic format that utilises 65,000 colours uses up more memory than exactly the same tile set in a format that only allows for only 16 colours needed. If your tiles only take up a small range of colours, that 16bit (or 24bit) mode could be a waste of time. And if you can get beautiful tiles with 16 colours, programmers will love you. :)

Again, it's a balance. Try some test tiles first. If you've got a list of the tiles needed, experiment with some fairly mis-matched sets and see how they stand up to the lower colour depths. If you're not happy with how they are working out, move up to the next depth. Remember though, an artist may have to compromise the graphics he/she creates to work within limits. Do the best you can with the tools available and the boundaries you are set.

Tile Size & Screen Size.

In a perfect world, all players would have limitless hard-drive space, screen-resolutions that stretch into the ten-thousands and download the several hundred meg your game takes up in a second. Problem is, it doesn't work like that. Once again, file-size is affected by the choice you make over tile sizes. Deciding to expand your tiles from 16x16 pixels to 32x32 pixels will increase the file space each tiles takes up by 4. If the programming has decided they want tiles for each of the five-hundred different flavours of gnome they've implemented, we're talking of a big increase.

Can you do everything you want with 16x16? Can you get all the detail you need and is the detail really necessary? In some cases, a good artist can 'imply' detail in a very small space. Do you really need to see the texture on the knight's chain mail or would a light grey mesh give the same impression?

Another point to take into consideration is the screen size. A small screen size and a large tile size could cause trouble and restrict the amount of 'dungeon' you can see at one time. Small tiles on a huge screen could mean the player has trouble making out the tiles and misses out important details. Again - balance.

See what the programmer wants. How many tiles do they want onscreen. Make sure that they understand how big that would allow you to make the tiles. A sample screen knocked up in five minutes is usually a good visual aid for both you and the programmer. Does it look right?

If there is a lot of other information needed onscreen, the amount of screen left over to the level window may be cut down. Make sure you take all of that into consideration.

Resizing or Reducing Colours.

Okay. You've created all your tiles. Five hundred gnomes of all shapes, sizes and colours. All in 64x64 pixel, 24bit colour tiles. The programmer gets in touch and tells you that they can't use them. They need 16x16, 16 colour. Bugger...

Well, you've got three choices - call it a day, move to Tibet and take up the serene life of a monk or restart from scratch or start reducing tile size and colour depth. In the extreme case stated above, the reduction is going to pretty much murder your graphics and perhaps restarting is the only way to go. In other situations, when you only need to reduce the colour depth or just resize, you might just get away with it.

One thing to remember when reducing colours, it always helps to choose a good utility/art package. The best way to test this is to use it with other graphics first. Choose a picture (maybe a scan of some sort) with a fair spread of colours and detail. Reduce the colours. If you're coming down from 24bit to 16bit, chances are you won't notice the reduction but down to anything less and the package has to create it's own palette of used colours.

Most often, it's a best-fit and most-used kind of technique. Some packages offer different methods for reduction and some use a dithering algorithms to fool the eye. Sometimes it even works. Remember though, you may be reducing the colours of some fairly small tiles and when they begin to repeat in the game, the pattern these dithered tiles create may become very noticeable. The key to reduction is getting a good palette. Again, this depends on the tool you use.

One thing I have noticed is once your package has reduce the colours, it tends to organise the colours in the palette in a manner which I find a little 'random'. Personally, I like my colours divided up into nice hue sets but after reduction, most packages generate light-to-dark range or that bizarre mac-style organisation that I dislike so much :) It's a little gripe but remember that if you're drawing more tiles after the reduction, finding the exact colour you're after may become a pain in the ass.

Resizing is another matter. Most resizing does cause your tiles to lose all their detail and essentially makes touching-up afterwards a must. Some packages anti-alias or blur the tiles to cover the loss of detail. This is all very nice within the tile but you've got tiles with areas that are supposed to be transparent (for overlaying onto floor tiles, etc.) then the program tends to blur the edges of the shapes and destroy the clean edge you need. A good package will allow you turn this off.

1001 Monsters.

Not just monsters but potions, swords, shields, helmets, scrolls, spell-books, traps, walls, floor, stairs, food... well, you get the idea. When you think of all the tiles you may be called on to draw, you start begin longing for those simple ascii-characters. When drawing your tiles, it's always a good start to have some sort of idea of how many monsters, etc. will be required. If you need several different types of mold (green mold, yellow mold, red mold, blah-blah- blah), you would probably be able to get away with the same graphic but with changes to the colour. It saves time and allows you concentrate on making the basic mold design stand out from your other creatures.

It is also useful to find a theme within creatures. If you need several ranks of orc, maybe changing their size and armour might help. If you have a set of monsters that have a specific trait (nether beasts, lava beasts), it'll help player recognition if you style those creatures similarly.

3D packages.

All styles can enjoy the benefits that using a 3D package can give. For the 2D bitmap tiles, building your objects and monsters with a 3D package means that size or colour depth isn't really an issue any more. The object you create can be rendered from any angle, at any size and with varying amounts of colour (if the package you're using is any good in the first place). And because the output is from the 3D package itself, outputting a smaller render will generally give a better result than trying to reduce the size of the tile with another graphics utility.

Ofcourse, the amount of work required initially is massively increased as you need to model all the objects you wish to show. The benefit comes from the flexibility afterwards. For the user wishing to create modeled creatures for a Quake-style roguelike, a 3D package is essential. I'm sure there are people out there who can quite happily create some very good models with a pencil and graph paper but with so many cheap and shareware modelers on the market, save yourself the bother.

Size matters?

Okay, first you're asked to draw a mouse and then you're asked for a poison breathing dragon. Do your work in scale? Draw a mouse that takes up a tile then draw a dragon that fills half the screen? 'Course not. If you're drawing a dragon that takes up a tile but a mouse in scale would be hard pushed to fill a pixel. It takes some getting used to be it's usually a good idea to throw scale out of the window. Just pretend that mouse is really, really, really close. :)

Conclusion.

As you've probably gathered by now, how you go about creating your graphics depends largely on the games needs. If you have been set limits either by the programmer or the hardware you're aiming for, always experiment to get the best you can from the tools you have available. If you're given an open-ended project with no definite requirements, planning will save you a lot of work in the long run. Decide which colour depth and tile size is best for the game and stick with it.

Whatever style you choose, its all a question of whether your roguelike needs these graphics. Do they honestly add something to the game? Ignore those who automatically scream 'no!' or have built up some kind of barrier to considering the option. Graphics are just another feature to add to your game. Like everything you add, whether it works or not is up to you.

Object Representation - Sean Middleditch [sean.middleditch@iname.com].

Representing objects in a roguelike. A difficult thing to do, in fact. When I started War of the Runes, I wasn't sure exactly how to go about doing it. Would everything be hard coded into the game? Would objects be malleable? What kinds of different objects need to be represented?

Well, for starts, I knew I didn't want anything to be hard coded. One thing about War of the Runes is that EVERYTHING would need to be able to be changed. So objects need to be stored in external files, with all descriptions of the object need to be stored; from description, to behavior, to properties. And this also means all objects needed to be malleable. the state of an object can change at any time through any number of ways. And what kinds of objects were there? There's weapons and armor, food and drink, doors, chests, bags, rings, books, anything that can exist in a real world.

So what is the best way to represent objects in a roguelike? Well, first we need to start with an object class:

class Object { public:

What kind of data do we need for objects? For starts, we need to know what the object is. We can do this with a name and a description;

char *Name, *Desc;

That's fairly self-explanatory. Information about where the object is would be useful, too:

int X, Y;

There are lots of different objects in the roguelike universe. Armor, weapons, books, rings, potions, lawn-chairs, etc. Each object can only be of one type.

int ObjType;

This field will be set to a value we define with #define's.

#OBJ_WEAPON 1 #OBJ_ARMOR 2 #OBJ_POTION 3

You get the idea. Every different type of object in the game would need a separate number. This will help in a LOT of areas. For example, characters can only equip items of type 2 (armor).

Since I'm sure some of you may be a bit confused (I know I'm not the best of teachers) why don't we start defining an example item before we continue? A longsword.

We'd set the Name field to point to "long sword". Simple enough. The Desc field would be "a long, sharp, metal stick". Well, you may want to use something other than that.

The X,Y coordinates can be set to whatever... let's say 2,10.

What about the object type? 1 (OBJ_WEAPON) of course!

Now what? What does a longsword do? The game knows it's a weapon, but the game needs more information than that.

Let's make a class to define what an object does.

class ObjArg { public:

Each ObjArg will define one aspect of an object. We'll need a way to store what each ObjArg defines.

int ArgType;

We'll give this meaning through the use of more defines.

#define OARG_ATTACK 1 #define OARG_DEFEND 2 #define OARG_HEAL 3

Now we know what an ObjArg defines. Now we need to store the actual definition. We'll do this by storing an array of 5 integers.

int Args[5];

And that's all there is to the ObjArg class. The meaning of the Args array's field will depend on the value of ArgType.

Now, we want every object to be pretty versatile, so we'll make it so every object has 5 of the ObjArg classes.

} Defines[5];

And that's all we need for a basic Object class

};

So how does the ObjArg class work? Well, for our longsword, we'll need only one. It's ArgType will be set OARG_WEAPON. Now what about the Args array? Let's say for ArgType 1 (weapon), the first field of Args is the number of damage dice, the second field is sides per die, the third field is damage modifier, and the fourth field is the modifier to the character's skill. The fifth field will be unused.

So, if we wanted long sword's to cause 1 to 8 damage, with no additional modifiers to damage or attack skill. So...

Args[0] = 1 Args[1] = 8 Args[2] = 0 Args[3] = 0

Now if the character equips the long sword and attacks, we'll first check to see what kind of object is in the character's hand. We see the ObjType field is set to 1 (weapon). OK, so he/she can attack with that object. Now we'll look through the Defines array until we find an ObjArg entry whose ArgType is set to 1 (attack). The game see that Defines[0].ArgType = 2, so we'll use that ObjArg to look up the weapon's statistics. The game checks Defines[0].Args[3] = 0, so there's no skill modifier. The game does whatever combat system and determines the character hit. It check the damage (Args fields 0, 1, 2) and sees that the long sword does 1d8+0 damage. The game rolls the damage, hurts the target, etc.

Well, that's all you need for simple objects. Although, you could do a LOT more, using the sample code I've given here as a base. For example, some ObjArgs are in effect whenever an item is equipped (the long sword's attack field, or armor's defend field). Some objects, like potions, don't effect unless a character uses the object (or in the case of objects with ObjType = 3, the character quaffs the potion). Only then will their ObjArg fields (like healing, in the case of a potion of healing) take effect. So you might want to store how many times an object can be used, and how many times it has been used.

The complete code for the Object class is:

define OBJ_WEAPON 1
define OBJ_ARMOR 2
define OBJ_POTION 3

define OARG_ATTACK 1
define OARG_DEFEND 2
define OARG_HEAL 3

class Object { public:

char *Name, *Desc;

int X, Y;

int ObjType;

class ObjArg { public:

int ArgType;

int Args[5]; } Defines[5]; };

If you have any questions, feel free to e-mail me at sean.middleditch@iname.com

The End

Inventory Abstraction - Kenneth Power [uncle_wiggly@bigfoot.com].

An Inventory tracks Items in Storage. Items are anything you deem trackable: gloves, clubs, food, coins, flowers. Storage is anything defined as able to hold items: chests, sacks, hands, buildings.

A basic Inventory does not care about extraneous fluff, such as container limitations. Keeping inventory implementation basic enables code reuse as discussed later.

Throughout this paper, psuedo code is used to model examples. The examples use the following sample item definition:

  define Item:
     variable Name

Tracking items There are two basic ways to track items. First is with a simple list, rather like writing a list of groceries. Lists usually are FIFO (First in First out) or LIFO (Last in First out). Other ways may exist. Indeed in some languages, there are very exotic forms of lists. A trouble with lists is the retrieval of information from the middle of the list. The list is examined from either end until the information is located.

Our example simple list:

  list define Inventory

Second is through a more complex scheme wherein more than the item is tracked. Also tracked is information about the item. This is so items may be grouped. Grouping has its pro's and con's like anything else. Use of grouping, for example, allows easier display of items (in my own opinion of course). In a way, grouping is a more esoteric list form, using such things as dictionaries, maps and other terms.

In this example, the items are tracked by their name. Example:

  list define Inventory:
     list define itemNames
     keyedList define qtys

Add items What use is an Inventory if you are not able to add items to it? Thus, the first function we define is the add() function.

In basic form, add() only wants to place the passed item to the list:

  List define Inventory:
     define add(item):
        insert item

With the complex form, add() is more detailed. Questions are raised: is the item already in inventory - this might affect or tracking feature-? Did I/you make an adjustment to the tracking feature if necessary? Note how this is done in the example:

list define Inventory:

  list define itemNames
     keyedList define qtys
     define add(item):
        if item is in me.itemNames       #do I exist?
           then me.qtys.key(item.name) = +1
        if item is not in me.itemNames   #I don't exist
           then me.qtys.key.add(item.name)
           me.itemNames.add(item.name)
           me.qtys.key(item.name) = +1

Remove items The remove() function is really the opposite of add(). Find the item passed and remove it from the list. Let's examin it with our two pseudo codes.

Of course, this example doesn't take into consideration language dependent behavior (C - did you fix your pointers?). Thus the abstraction is the same for add():

  List define Inventory:
     define remove(item):
        delete item

Here, as in the complex add() function, more work needs accomplished. We not only find the item, but we make certain our tracking feature is adjusted accordingly.

  list define Inventory:
     list define itemNames
     keyedList define qtys
     define remove(item):
     if item is in me.itemNames
        then me.qtys.key(item.name) = -1
        if me.qtys.key(item.name) == 0
           then me.qtys.delete(item.name)
     if item is not in me.itemNames
        then error

At the completion, our example would show the proper quantity for the item. Plus, if we have no more item in inventory, no quantity or listing will exist.

Display items (opt.) This is listed as optional, because you may not code Inventory display as part of your Inventory. It may be in your UI code. However, during testing, having a simple Inventory Display feature is very useful.

Like always, the simplest way is the list method. Merely iterate the list, printing each item:

  List define Inventory:
     define display():
        For each item in Inventory:
           print item.name

Because of our tracking feature, we need print item and qty. Otherwise uncertainty will exist. The only added feature of the complex over simple is the header printed "Item Qty".

  List define Inventory:
     define display():
        print "Item     Qty"
        for each item in me.itemNames:
           print item, me.qtys.key(item.name)

Possible benefits For developers using OO style languages (C++, SmallTalk, Java, etc), having a simple Inventory Object lets you easily include it in other areas of the game. Containers (combinations of Items and Inventory), Buildings (Structure and Inventory), and more can be made. Of course non-OO languages(C, Pascal, Basic) can use Inventory as functions in other parts of the game. The point is: once you define what a basic inventory will be in your game, find how to use it in more areas.

An Example Here is an example inventory, using the Python language. I find Python to be a grat language for prototyping. It is easy to spot errors, fix them, etc. Then you may easily recode in any other language.

The Item Object - class Item:

  def __init__(self, name):	#object constructor
     self.name = name

The Inventory Object - class Inventory:

  def __init__(self):
     self. NameList = []	#a list of item names
     self.qtys = {}		#a dictionary of item quantities
     self.contents = []	#a list of actual items
  def add(self, itemList = []):
     for item in itemList:
        #Check item is self
        if item is self:
           print 'Cannot store', item,' in itself!'
        if item in self.contents:
           print 'You already have this item!'
        else:
           #Check if item is in nameList
           if item.name in self.NameList:
              #merely insert
              self.qtys[item.name] = self.qtys[item.name] + 1
           #otherwise add to nameList
           else:
              self.qtys[item.name] = 1
              self.nameList.append(item.name)
           self.contents.append(item)
  def remove(self, item):
     #does item exist?
     If item not in self.contents:
        print item.name, 'is not in your inventory'
     else:
        self.qtys[item.name] = self.qtys[item.name] - 1
        if self.qtys[item.name] == 0:
           del self.qtys[item.name]
           self.NameList.remove(item.name)
        self.contents.remove(item)
  def display(self):
     #let's show everything!
     Print "Item\tQty"
     for item in self.NameList:
        print item,"\t", self.qtys[item]

More Info For information about Python, visit: http://www.python.org Please send all comments, queries, and error notifications to the author. Written by: Ken Power email: uncle_wiggly@bigfoot.com Version: 1.0 Date: Oct. 25, 1999

Creating Inventories - Erno Tuomainen [ernomat@evitech.fi].

----------------------------------------------------------------------------
           CREATING INVENTORIES - WHAT TOOLS ARE AVAILABLE
                       (C) 1997 Erno Tuomainen
                          ernomat@evitech.fi
                        16th of November 1997
----------------------------------------------------------------------------

I know that many of you wonder about this problem. Atleast I did so when starting my Roguelike project (Legend of Saladir). In this article I intend to give you some tools for making those inventories, it's not intended to be a complete tutorial for making player inventories, maybe later I can offer you some more routines/ideas related to this subject.

I assume that the reader of this article is not a total beginner (hey, you are starting to make your own game! :) and has a basic knowledge of C-language along with knowledge of pointers. And please, forgive me my bad english!

Without any more hassle, lets begin defining a basic item structure for all examples in this article. This is just an example, the item defined is not really useful in real development :)

  typedef struct ITEMTYPE
  {
     int itemtype;
     int weight;
     unsigned int attributes;
  } Titem;

So this is just a data structure which contains all the information needed for a particular item. Every item in the game has a similar (exactly!) structure.

There are basically two methods of creating the inventory list for player/monster.

1. Fixed size array

You allocate an array of for example 100 items. Obviously this has one big disadvantage, you can't carry more than 100 items if the programmer doesn't change the code and secondly this array always takes 100*sizeof(Titem) bytes of memory even if you were carrying just one item.

Player-information structure would look like this:

  typedef struct PLAYERTYPE
  {
     char name[100];   /* normal player information fields */
     int age;

     Titem inv[100];   /* inventory array containing 100 items (See Titem definition) */
  } Player;

So this is a structure which keeps all information about our player. You will have similar structures for your monsters/NPC's too, they might be a bit different but you can use the same methods for your monsters too.

So the size is constant. The good point is that additions and deletions to this list are easy, you can index it directly. However, you can't easily insert/delete items to/from the middle of the list. It requires rebuilding the array from the point where you are inserting. This is slow.

Another good point is that when you are going to save this structure, you just store this whole block into the file.

This kind of approach has it's own good uses, but I have a better method for the purpose we are talking about.

2. Dynamic memory allocation with linked lists

So what is this? Ok, you can guess from the name. Each time you need a new item added to the inventory you allocate space for it and link it to the inventory you already have for your player/monster.

This is a bit more complicated but it's not too hard when you go and think about it! When adding to the middle of the list, all you need to do is to go to the right place and move some pointers.

Now, keeping the above player structure mostly the same, but modifying only the inventory part we will get:

  typedef struct PLAYERTYPE
  {
     char name[100];   /* normal player information fields */
     int age;

     InvList *inv;  /* pointer to the start of inventory list */
  } Player;

What is the third field "InvList *" in the structure, I hear you ask.

"InvList" is also a structure, it defines ONE node for the inventory list. Node is one segment of the dynamic linked list. Look at this picture:

  +-------+      +-------+--+
  | start |----->| node 1| >---\    +-------+------+
  +-------+      +-------+--+   \-->| node 2| NULL |
                                    +-------+------+

This example resembles a linked list with TWO nodes, the first block named 'start' contains a pointer to the node 1, telling that the first node of the list is there. And again, you see that in 'node 1' there is a extra field which contains a pointer to the NEXT node or 0 (NULL) if the list ends there.

So the above "Player" structure contains just a POINTER to the players inventory list. It's a memory address holding the first node of the list if any (or NULL if inventory is empty!)

At this point, compare this method to the array method I showed you earlier. If items are stored in array they will be stored in sequential order in memory ( 1-2-3-4-5-6-..) as one big block next to each other. In the case of linked lists, the list consists of nodes, which can be all around in the memory, the order of the list is preserved with the pointers linking each node to another. This list is called as "one way linked-list" or "single linked list" meaning that you can traverse only to one direction along the list. There is also a list which contains a "previous" and "next" link. This is a "dual linked" or "two way linked" list. But I won't speak about it this time.

Now we have structures for the ITEM and the PLAYER. We must define the structure for InvList defining a one node of the list.

  typedef struct node
  {
     Titem item;
     struct node *next;
  } InvList;

  or like this:

  /* define a pointer to the list node */
  /* so we can use "Ipointer" instead of "struct node *" */
  typedef struct node *Ipointer;

  typedef struct node
  {
     Titem item;
     Ipointer next;
  } InvList;

I will use the first method.

The first field in the struct is the actual item stored in this node, and the "next" field contains an address to the NEXT node if there is such a node. (NULL telling that list is terminated here)

So basically this is a very simple idea, it requires a bit more work to maintain this kind of inventory, but it offers some advantage which are really good for Roguelike games. You can use this kind of list in many places. For example, I use it in these situations:

  List of monsters in the level
  List of items in the level
  List of items carried by the player
  List of items carried by monsters

So in my game, only limitation in the above situations is the amount of memory available. There can be for example 1000 items in a level.

This practise can be used in MANY other situations, in other programs too. It's all depends in your imagination and how you can make this thing useful in certain situations.

I must point however that this "linked list" method will make you some problems later on. Think about savegames. You must create a routine which saves each node from the list and when loading you must build the list again. Not a big deal, but it brings you again a bit more work to do :)

Now that we have the idea coverered, let's start writing some code for the list.

----------------------------------------------------------------------------
              WHAT FUNCTIONS DOES THIS KIND OF LIST NEED
----------------------------------------------------------------------------

First off, you need to initialize this list, you'll need node addition, node deletion and the routine for deleting the whole list. Let's create the actual code for these functions.

1) Initialization of the list

  void initialize_list(Player *player)
  {
     player->inv=NULL;
  }

This routine takes a pointer to the player structure and initializes the list pointer to NULL, telling that list does not exists yet. (so player has no items in inventory!)

Please note that you should not call this routine if you have items stored in the list. You will destroy the pointer to your list, thus you will have allocated memory which can't be freed because you lost the pointer.

2) Node addition

This routine adds a node to the list. I use the method where the last added node will be put to the BEGINNING of the list (thus to the field Player->inv) and this new node will point to the to the previous value of Player->inv. Like this:

  int add_node(Player *player, Titem newitem)
  {
     InvList *newnode;
     /* allocate memory for the new node */
     newnode=(InvList *)malloc(sizeof(InvList));

     /* if newnode == 0 then the memory is out or something is messed up */
     if(!newnode)
        return 0;

     /* now place the new data item to the item-field in space we allocated */
     /* remember, "newnode->item" is similar to "newitem", both are defined */
     /* by "Titem" */
     newnode->item=newitem;

     /* if player inventory does not yet exists */
     if(player->inv==NULL) {
        newnode->next=0;
        player->inv=newnode;
     }
     else {
        /* point the "next" field of "newnode" to the old player->inv */
        newnode->next=player->inv;
        /* point the player->inv field to the node we just created */
        player->inv=newnode;
     }
     return 1;
  }

The function returns 0 if the addition failed, otherwise 1.

3) Node deletion

This routine really depends on the fact how you want to delete the item from the list. I will create a routine which removes item with an index. For example, you might want to delete the fifth item from the list.

Here is an example, it's not the optimal routine, should be easy to understand

int delete_node(Player *player, int index) {

  InvList *node, *tmp;
  int count;

  /* again check first if the inventory exists */
  if(!player->inv)
     return 0;

  node=player->inv;

  /* if you are trying to delete the first node */
  if(index==0) {
     player->inv=node->next;
     free(node);

     /* we are done so return with success */
     return 1;
  }

  count=0;
  while(node) {
     /* remember the previous node */
     tmp=node;
     node=node->next;

     /* increase the item count in list */
     count++;
     if(count==index) break;
  }

  /* if trying to delete item over list boundaries */
  if(monesko>count) return 0;

  tmp->next=node->next;
  free(node);
  return 1;

}

4) Freeing the whole list at once

Here is a useful routine for freeing the whole list at once. Notice how I traverse on the list.

  void free_list(Player *player)
  {
     InvList *tmp, *freethis;

     /* put the start of inventory to temporary variable */
     tmp=player->inv;

     /* do until we reach NULL */
     while(tmp) {
        freethis=tmp;

        /* assign "tmp" with the next node, if there isn't a next node
           "tmp" will contain NULL */
        tmp=tmp->next;
        /* free the current node */
        free(freethis);
     }
     player->inv=NULL;
  }

The similar approach can be used for example when displaying the contents of the list.

----------------------------------------------------------------------------
                           SOMETHING EXTRA
----------------------------------------------------------------------------

Linked list is just one of the advanced data types (often called as Abstract Data Types, ADT), there are many other types of ADTs which can be useful in game programming. For example, Queue and Stack. Each of them have many uses, and again many ways to implement them. Some explanations.

Stack

Stack is a special case of a list. New items inserted to the stack will always go to the end of the list and when you take something out it will be taken from the end. So this type of list is called LAST IN FIRST OUT (LIFO). Stack has many uses.

  +-+----+
  |3|data| top/end of the stack (last added item)
  +-+----+
  |2|data|
  +-+----+
  |1|data|
  +-+----+
  |0|data| start of the stack
  +-+----+

So items will "pile up" in the stack. You'll get the most recent item when you get something from the stack.

One example from computer world. We want to check if a string is a palindrome: (string read forwards equals string read backwards)

  create 3 empty character stacks

  state1:
  for each_char_in_string do
     put_into_stack1(current char from string)
     put_into_stack2(current char from string)
     count=count+1
  end_do

  state2:
  while stack_2_has_something do
     put_into_stack3(take_from_stack2())
  end_do

  state3:
  while stack_1_has_something do
     if take_from_stack1() equals take_from_stack3()
        palindrome=true,
     else
        palindrome=false
  end do

for example for word "automatic" it would go like this:

  after state1
  stack 1 contains: automatic
  stack 2 contains: automatic
  after state2
  stack 1 contains: automatic
  stack 3 contains: citamotua
  in state3 we take from both stacks and compare them:
  ? a==c ?
  ? u==i ?
  and so on...

Queue

Again, queue is a special case of a list. Items placed into the queue will go to the end and items taken from the queue will be taken from the start.

      first                              last
     +------+------+------+------+------+------+         +------+
  <--| data | data | data | data | data | data | <-- add | new  |
     +------+------+------+------+------+------+         +------+

Good example taken from the Real Life(tm) could be a BANK QUEUE. You come to the bank and the desk you go has a long long and long queue (it's friday and the bank is going to close soon :), you will have to go to the end of the queue. When the bank clerk can, he/she takes a next customer from the first position of the queue.

The end?

This ends this part of the lesson. I've tried to provide you a method for creating dynamic inventories along with some knowledge of other advanced data types. It's up to you to decide how you make use of them.

I thank you for reading this, and apologise for any errors in C-examples I provided, there might be some since this text was written on a fly without any aid of C-compiler :)

If you have any questions, ideas for my game, or want to report a bug in my examples, please feel free to contact me via email.

  ernomat@evitech.fi

Also go see the homepage of my Roguelike project:

  The Legend of Saladir
  http://www.evitech.fi/~ernomat/saladir/main.html

This text is written specially for Darren Hebden's Roguelike News developers section. Visit Darren's great pages at

       "http://www2.krisalis.co.uk/wwwdheb/index.html"

----------------------------------------------------------------------------
(C) 1997 by Erno Tuomainen                      Sunday 16th of November 1997
----------------------------------------------------------------------------
            Do not modify or publish without my approval.

Equipment Wear and Tear - Michael Heinich [mheinich@yahoo.com].

 Every piece of equipment should have a durability. One example of this

system is demonstrated in a popular series of commercial hack and slash games with some Rogue-Like tendencies. Another example can be found in ADOM. Both of these implementations could be improved upon.

 In the commercial games, durability played a very important if limited role.

If an item's durability reached 0, it was broke beyond repair. This was normally kept as a ratio of current:maximum durability. The game allowed a character class a repair skill to partially repair an item. The drawback was that the maximum durability was reduced. Or a member of the town was able to provide this service. Found items had a lower then maximum durability and equipment that was used, lost durability during the course of weilding or wearing them. Durability also effected the value of the item in question. An item in great shape was worth more then the same item in bad repair. While the measurement system was easy to understand and to manage, it could still be improved upon.

 One area is in the item's use. The equipement was either broke or not. A

better method would be to reduce the effectivness of the item in question. Using a sword for example, as it becomes worn out, the sword may cause less damage because it has become dull with use. Or the sword may have an ever increasing change where it may break during an attack as it's durability decreases. An armor example would be that the protection a chain mail shirt provides may be reduced as it's durability worsens.

 ADOM does take some of these factors into consideration, but it can be

confusing to figure out the multitude of stats offered (some would say that this is one of it's strengths)and it lacks adequate skills or town services for the repairing of items. Usually it is usually better to replace an item then to repair it.

Here are some more ideas thrown out more or less at random that build on this concept. The use of durability can also open other possibilities for object descriptives and use. For example, a sword that is undamaged and is like brand new may have a desciption before identification of Shiny and Sharp, as the sword becomes used, the description may change to dull and nicked. Durability provides an interesting twist to potions or items made of glass. Potions may be in delicate containers. In Angband, potions sometimes break when they are subject to heat or cold attacks. But what if a potion is dropped or thrown. They should spill, spreading their contents over the floor, wall or monster. This could cause interesting effects if the Potion was healing or Acid. A Crystal Ball may not last too long under a heavy attack by giants or earth hounds. Just how sturdy is a Lantern full of Oil anyway? Why hasn't one of these broke after an attack, spilling flaming oil all over the user. Or throwing the lantern, to have it's flaming contents spill over the monster. This is much preffered to the Flask of Oil attack in Angband. Since it assumes that you have lit the Flask first somehow.

The code to add statistics for wear and tear should not be to hard to add to your Roguelike. Specially if you are using an Object Oriented programming language. You can just add an extra two lines to the Class for starters.

int CurrentWear, NoWear; // Measure how much wear and tear int Durability; // How durable is this item

In your object definition for a sword you would add the value for NoWear an the value for Durability. During the Object creation you would assign the value of NoWear to CurrentWear.

CurrentWear = NoWear; // set CurrentWear value to NoWear

Then when ever the item is used or after a certin number of uses, you would subtract from the value.

if (NumOfUses == 10) { CurrentWear--; if (possiblebreak(Sword.CurrentWear)) Sword.Status = BROKE; NumOfUses=0; }

I hope these meanderings showed you a new diminsion for your Game. The code examples were way oversimplified but will hopefully point you in the right direction.

Happy Coding!

Fractal Landscapes - Mike Anderson [mike@mikera.net].

30th October 1999

There's something special about fractals. Maybe it's the way that infinitely complex shapes appear out of the simplest mathematical formulae.....

Certainly beautiful, but why would you want to use them in your game? The answer, quite simply, is that they are perfect for generating realistic-looking landscapes. For example, real coastlines frequently exhibit fractal-like properties and fractal heightfields are often a good first approximation to the contours of mountainous terrain.

Here I'm going to present a basic fractal algorithm that was originally designed for generating random islands, seas and coastlines. With a few minor alterations, it could easily be adapted to producing all kinds of natural landscape patterns. My algorithm is vaguely based on the familiar "plasma" type of fractal heightfield, but modified to work with tiled maps.

I've included the source for a simple Java coastline generator applet at the end of this article. If you are impatient and want to see the thing working right away, just go to:

 http://www.mikera.net/code/coastline.html

The Fractal Algorithm

=========

One of the distinctive properties of fractal images is self-similarity. That is, a zoomed in version will look similar to the whole image. This algorithm achieves this effect by starting with a coarse map, and then enhancing it by applying increasing levels of random detail.

Let's say that you are considering a square area of your map with the corners labelled a, b, c and d :

a * b

* *

c * d

Each map square can have a different colour. I used green for land and blue for sea in the example applet.

The algorithm will then determine the map colours for the intermediate points marked "*". It does this by randomly choosing a colour from one of the adjacent corner squares. The "*" in the centre could take the colour of either a, b, c or d.

Thus a possible final result might be:

a a b

c b d

c c d

We have now defined smaller squares on the map. The algorithm can then be applied iteratively on a smaller scale. This process continues until the desired level of detail is achieved.

a*a*b

c*b*d

c*c*d

Note that for convenience, it is helpful to have a map size that is a power of two so that it can be repeatedly subdivided.

Example

=

Below shows the iterations for a 16*16 grid.

For viewing convenience, the larger tiles have been completely filled with the colour from the top-left corner, though this is not needed for the algorithm to work.

In addition, the map is considered to be toroidal, i.e. the points on the left edge are considered to be adjacent to those on the right edge, and similarly for top and bottom.

Step 1: a-------b#######

########

c#######d-------

1. 1. 1. 1. --------
        
        --------
        
        --------
        
        --------
        
        --------
        
        --------
        
        --------

(a, b, c and d mark the points that are coloured at the start. This can be done randomly, or they can be pre-set to create land masses)

Step 2:

########

1. 1. 1. 1. ----####
        
        ----####
        
        ----####
        
        ----####

####--------

1. 1. 1. 1. ----
        
        ----
        
        ----
        
        ----

Step 3:

########--

--##----######## --##----########

1. 1. 1. 1. ----####
        
        ----####
        
        --------##
        
        --------##

####--------

##----------

1. 1. 1. 1. ------
        
        ------
2. --########----
3. --########----

Step 4:

########---

########--

-##-----######## --##----#--#####

1. 1. 1. 1. ----####
        
        -----###
        
        --------##
-####--------#-

####--------

---####--------- ---###---------- -#--#--#--------

1. 1. 1. 1. -----#
        
        -#-----
2. -#########----
----######-----

Et voila - one random continent ready to be populated with thriving cities, dangerous mountain ranges and deep forests.

The Code

==

Here's a quick Java implementation of the fractal coastline algorithm. It generates a new landscape each time the applet is repainted.

The makeFractal(step) method does all the actual work. This method calls itself to handle finer detail levels.

=== CoastApp.java ====

package kult.quest;

import java.awt.*; import java.applet.*; import java.awt.event.*;

public class CoastApp extends Applet {

 // map size: must be a power of 2
 public static final int size=128;

 // allocate map storage
 public int[] map= new int[size*size];

 public void paint(Graphics g) {
   super.paint(g);

   // initial pattern (0=sea, 1=land)
   setCell(0,0,0);
   setCell(size/2,0,0);
   setCell(0,size/2,0);
   setCell(size/2,size/2,1);

   makeFractal(size/4);

   // draw the map
   for (int y=0; y<size; y++) for (int x=0; x<size; x++) {
     g.setColor( (getCell(x,y)==0) ? Color.blue : Color.green );
     g.fillRect(x*2,y*2,2,2);
   }
 }

 public void setCell(int x, int y, int c) {
   map[x+size*y]=c;
 }

 public int getCell(int x, int y) {
   return map[x+size*y];
 }

 // this routine builds the landscape....
 //   step = detail square width
 public void makeFractal(int step) {
 for (int y=0; y<size; y+=step) {
   for (int x=0; x<size; x+=step) {
     // The inner loop calculates (cx,cy)
     // this is the point from which to copy map colour

     // add random offsets
     int cx=x+ ((Math.random()<0.5) ? 0 : step);
     int cy=y+ ((Math.random()<0.5) ? 0 : step);

     // truncate to nearest multiple of step*2
     // since step*2 is the previous detail level calculated
     cx=(cx/(step*2))*step*2;
     cy=(cy/(step*2))*step*2;

     // wrap around to reference world as torus
     // also guarantees getCell() and setCell() are within bounds
     cx=cx%size;
     cy=cy%size;

     // copy from (cx,cy) to (x,y)
     setCell(x,y,getCell(cx,cy));
   }
 }

   // recursively calculate finer detail levels
   if (step>1) makeFractal(step/2);
 }

 // applet initialisation
 public void init() {
   super.init();

   // repaint on mouse clicks
   addMouseListener(new MouseAdapter()
     public void mouseClicked( MouseEvent e ) {
       repaint();
     }
   });
 }

 // main function allows applet to run as an application
 public static void main(String[] args) {

   // create a frame
   Frame f = new Frame("Fractal Coastlines");
   f.addWindowListener(new WindowAdapter() {
     public void windowClosing(WindowEvent e) {
       System.exit(0);
     }
   });

   // set up frame and add applet
   f.setSize(300,300);
   f.setLayout(new BorderLayout());
   CoastApp q=new CoastApp();
   q.init();
   f.add(q);

   // go live....
   f.show();
 }

}

Conclusion

==

Well, I hope I've given you a quick way to get some good-looking fractal landscapes. It is easy to extend this by adding different land types (forests, deserts etc). You could also enhance the method to include a height map by taking averages of adjacent points and adding random offsets.

In fact, I've implemented a fractal algorithm to generate the World Maps for Tyrant, my very own roguelike. You can see it in action at:

 http://www.mikera.net/tyrant/

This uses essentially the same method as the one described above, except that it uses a little bit of coding magic to make the landscapes look more realistic and textured. While it's still far from perfect, it does at least show there's scope for a lot of imaginative use of this technique.

Happy Coding.

Mike.

Any questions or comments:

 mike@mikera.net

Terrain Generator - Mixi Lauronen [mplauron@paju.oulu.fi].txt

I have experimented with the following algorithm:

1) Decide the range of land height values (I think 0-255 is conveninent)

2) Initialize the land area with a value of 0. (Arbitrarily, you can initialize it with the average of the height minimum and maximum)

3) Randomly set a rectangle of random size with a random value of (0-255) on the map, adding the value to every coordinate inside the rectangle's area. Arbitrarily the value can be anything between (-x to x). If the result is less than the minimum height or more than maximum height, readjust the value.

4) Repeat as many times as needed.

5) Apply a smoothing routine to every coordinate, thus simulating the effect of erosion. I use a simple method of setting the value of a land block to the average of (block+southern block+northern block+eastern block+western block).

6) Set the water level. Anything under that will be water.

Haven't implemented a river algorithm yet. Otherwise it seems to work fine, although it is a little bit slow (especially the smoothing routine). Of course the building blocks could be circles, ovals or single pixels, too.

Metaballs Dungeon.txt

The Metaballs Dungeon

The idea of the metaballs dungeon is to generate two dimensional meatballs to construct a cave-like dungeon that looks natural and rough but still constructed by... goblin hands! If anyone here has ever worked with a 3d raytracer you may know what i am talking about. Basically the idea is that in many 3-D raytracing applications you can place these metaballs in your scene. Each meta ball has x,y,z coordinate variables and a t--threshhold. If you have one metaball then the edge of the ball is mearly a distance away from the center equal to the threshhold. In case you havent already guessed this, we are thinking about doing this in 2d (x,y,t). So lets look at how that would look.

                       ####
                      #....#
                     #......#
                     #......#
                     #......#
                      #....#
                       ####
        (a better looking circle then above)

Now this is because we only have one ball. If we place another right next too the first, then in our 2-D scenerio we will say that for every square we look to see if there is a ball or are balls nearby. Nearby is defigned like this

If the square in question's distance to a ball's center is less then the ball's threshhold then that ball is "nearby".

Now if we have a vector of balls (x,y,t) that have contructed (I will explain later) then we want to find out what our betaballs dungeon looks like. We would do the following.

(slow version, could be optimized!! a lot!) For every square on our grid, we compile a list of the "nearby" balls. We then add the threshhold of every nearby ball to a temporary integer and then subtract the distance to every ball from this integer. If this number is positive then we have a floor tile. if not we have a wall tile. Its that simple. This algorthim could be optimized and the math is probably a little off. There are algorithms you can find through a google search that will probably be better/faster and offer you much more control. My simple example does work and has been tested on QBasic. I will probably implement this for some levels in my upcomming game CHAZM!

A sample might look like this. A nice smooth melted merge between balls. You could also experiment with using ellipes and rounded rectangles. There are algorithms for those out their too.

                     ################
                     #########....###
                     ##....##......##
                     #.............##
                     #.............##
                     #......##.....##
                     ##....####...###
                     ################
          (This was handdrawn as a representation only...)

If you cant visualize what this would look like with many rooms/balls then take a look here:

http://foresightsagas.com/software/chazm/metaballs_cave_example.htm

Laying out the Rooms

You could lay out the rooms in any way you want but personally i would advocate for a recursive flow.

call branch 2-4 times on randome angles at the center...

void branch(x,y,a){

 do{
   a += randombetweenr(-.2 radians, +.2radiant);
   step x and y forward 8-12 squares forward in the direction of angle

a

   then add room at location
   if (randombetween(0,6) == 2) branch(x,y,a);
   if (randombetween(0,6) == 3) return;
 }

}

thus you get a branching and twisting maze of caverns that go out quite far. You could also add other end conditions like hitting the edge of the screen or getting a cirtain distance from the original center.... If you have any questions you can ask me about this recursion.

I think this would work out great as a caves level. Any thoughts or questions: email me at comments (AT) foresightsagas .com

Thanks. And have fun making your RL.

By Thomas Gilray foresightsagas.com

Creating A Dungeon - Brian Bucklew [bbucklew@inteletek.com].

Section 1 : Creating A Map

       When creating a rogue-like game (RL from this point on), there

are several points you have to address. One of the first problems you are likely to encounter is the problem of generating a suitable dungeon level. Actually, not only do you need a level, you need a pretty much infinite supply of random levels all filled to the brim with monsters, treasure, traps and other various unsundries.

       Our first goal will be to actually create the maze, empty. Later

we can integrate code that stocks our dungeon, but for now our main goal will be to just get a pretty fair complex of passages and rooms.

       As with an programming problem there are many solutions, each

that generates a perfectly acceptable dungeon. The first method we will discuss is a recursive one.

Creating A Map : A Recursive Method

       This algorithm will be based around taking a solid chunk of rock,

let's say 256x256 and carving a dungeon out of it using rooms and passages. We'll try to stay as simplistic as possible at the beginning, though this algorithm can be expanded to generate many different dungeon types from caves to castles, with fairly minor changes to the basic code.

       So we begin with a 256x256 array of blocks, each filled with stone.

For our basic dungeon generation we will also need two functions:

MakeRoom(), which generates a random room and then calls: MakeHall(), which generates a hall of random length.

We will call MakeRoom() which will generate a randomly sized room, which will then call MakeHall() a randomly determined number of times out into the dungeon from the walls of the room. MakeHall() will generate a hall of a random length. At the hall's end, the hall will either 1:End 2:Call MakeHall() a random number of times in random directions or 3:Call MakeRoom(). Later we can improve the algorithm my making a hall stop if it hits another hall or room, or coding rooms so that they won't overlap, but for now this will suffice.

lets say, using pseudocode we have:

... StartX and StartY will be integers defining the seed location ... of each room and hall

... Direction will be an integer defining the direction the ... room or hall is facing

... RecurseDepth will be used to terminate the recursion at a specific ... depth

First we will define MakeRoom.

void MakeRoom( StartX, StartY, Direction, RecurseDepth ) {

       integer X1,Y1,X2,Y2; // These variables will be used to define
                            // the extents of the room

       // limit the recursion to some depth
       if( RecurseDepth > MAXRECURSEDEPTH ) return;

       DetermineExtents();

/* We need to take direction into account when determining the extents

       ... For Example:
       ( '#' = Rock '.' = open space, in standard RL convention )

       ##########
       ##########
       ##########
       #####X.... <--- Hall calls MakeRoom at X going west.
       ##########
       ##########
       ##########

       This is the situation we want to create when determining
       the extents:
       a = x1,y1
       b = x2,y2
       ##########
       ##########
       #a****####
       #****X....
       #****b####
       ##########
       ##########
       This is good...

       If we did not take direction into account, we would most
       likely end up with this:
       a = x1,y1
       b = x2,y2
       ##########
       ##########
       ###a****##
       ###**X....
       ###****b##
       ##########
       ##########
       This is bad...

/

       CreateTheRoom();

       for( x = x1 to x2 )
        for( y = y1 to y2 )
         Dungeon[x,y] = OpenSpace;

       integer R = Random(0,4); // Actually this is probably some non-linear
                                // random choice, but this will suffice.
                               
       for( x = 0 to R )
       {
               int hx,hy,hd;

               DetermineLocationOfHall();
               // Choose a spot along one of the walls,
               // Then determine the appropriate direction
               // (North,South,East or West) depending
               // on the chosen wall.

               MakeHall( hx,hy,hd, RecurseDepth+1 );
       }

}

Now, MakeHall which is comparatively simple:

void MakeHall( StartX, StartY, Direction, RecurseDepth ) {

       // Limit the recursion...
       if( RecurseDepth > MAXRECURSEDEPTH ) return;

       integer x1,y1;
       x1 = StartX;
       y1 = StartY;

       for( x = 1 to RandomLength )
       {
               if( x1 or y1 is out of bounds ) return;

               Dungeon[x1,y1] = OpenSpace;

               // Note:
               // For ease of stepping in a direction we will define
               // two arrays containing the X & Y deltas of each direction
               x1 += DirectionXDelta[Direction];
               y1 += DirectionYDelta[Direction];
       }

       RandomChoice = Random(1,3);

       if( RandomChoice == 1 ) return;

       if( RandomChoice == 2 )
        for( x = 1 to Random(0,3) )
         MakeHall( x1,y1, RandomDirection, RecurseDepth+1 );

       if( RandomChoice == 3 )
        MakeRoom( x1,y1, Direction, RecurseDepth+1 );

}

That's it... A simple recursive algorithm for carving out a dungeon. This is by no means an ideal algorthm and requires quite a bit of tweaking and a few algorithmic improvements to generate a really good dungeon, but this example serves to illustrate the method.

The Author: Brian Bucklew, 18 bbucklew@inteletek.com Current RL Project : Dungeon or "This game needs a new name"... :) Projected Beta Release : Early 98

The Building of Towns - Michael Blackney [michaelblackney@hotmail.com].

Introduction

  Most roguelikes of reasonable popularity contain towns, though
 not always in the design we are used to seeing them in real life.
 I for one am utterly confused by the first town in ADOM.  How is
 it that this small group of farmers and rations salesmen were not
 wiped out long ago by horrible dorn beasts?  How do they defend
 themselves?  And with the multitude of eager young adventurers at
 their doorstep, why has no one opened a sucker-market?
  In this article I intend on addressing these points, and other
 problems I have encountered with town-creation.  This method
 should, with few adjustments, work equally well with all sizes
 of towns and can be used both as a random-town generator (like in
 Angband) and to help with preset-town design (like in ADOM).
  For code excerpts I have used C++, as I favor it.  I could
 have used Pseudocode for those of you who don't understand C++, but
 then nobody would be happy.

Features
  Most of this article will refer to 'Feature's.  This is a class
 created for the town design stage.  A Feature represents an arbitrary
 feature in your town, be it a house, a forest or a grave.  You may
 even decide for consitency to make the Town a Feature as well.  A Feature
 upon creation often creates other Features which are part of it, such
 as a Castle Feature which creates a Moat, a Guardhouse and a Keep.
  A simple C++ interface for the class Feature could be as follows:
/-*/
 class Feature {
   public:
     // Construction / Destruction
     Feature( Level*l, char x1, char y1, char x2, char y2 )

: onlevel( l ), name( "" ), bounds( x1, y1, x2, y2 ) { create(); }

     virtual ~Feature( void );
     // public methods
     virtual void create( void ) = 0; // Specialized classes must override

// this method.

   protected:
     // inheritable data
     String name;
     Rectangle bounds;
     Level *onlevel;
   };
/*-/
  This class would interact with the Level class, which describes a 2d
 array of LevelElements where each LevelElement represents one game
 square.  The create() method would then alter the Level accordingly,
 adding walls, floor space, trees or whatever.

Natural Terrain
  All towns (which I intend on covering here) are situated in the
 'real' world that you have created, and as such all have surrounding
 terrain.  In fact many of the decisions to be made regarding the
 features found in your town will be affected by the terrain in and
 around the town.
  We all know that when people decide to establish a town, the terrain
 is already there.  For this reason, we should create the surrounding
 terrain first.
  One way of implementing this is to make a series of specialized
 Features each dealing with a different type of terrain.  Classes such
 as Clearing, Swamp, Coast and Hills are all examples of this.  These
 classes can then create the streams, forests and so forth.

TEST RUN::
  The following is an example of terrain creation.
  We begin with a blank 15x5 level like so:

xxxxxxxxxxxxxxx xxxxxxxxxxxxxxx x unallocated LevelElement xxxxxxxxxxxxxxx xxxxxxxxxxxxxxx xxxxxxxxxxxxxxx

  We then decide (using our special number generator) to create a
 grass field.  The GrassField class calls its version of create() which
 at first will do nothing more than filling the level with grass squares,
 like so:

............... ............... . grass ............... ............... ...............

  create() then has some decisions to make, such as how sparse vegetation
 is and how frequently streams occur.  Our GrassField decides to have a
 SmallStream and a few scattered trees.  Soon out GrassField looks like
 this:

............... .T....T..=...T. . grass .........===... T tree ..T....==...... = water (now part of SmallStream) .....==.....T..

  The actual generation of your terrain is up to you.  You can make this
 as simple or complicated as you wish.
  Now that we have a Level filled with adequate terrain, it is time to
 establish a settlement.

Your Town
  In order to make a sensible Town, it must be created and inhabited
 by your residents, with all of the benefits and drawbacks this brings.
 eg. If you wish to have thieves in your world, it makes sense to either
 have a thieving skill (such as ADOM's Pickpocketing) or to have houses
 where our friend the Aimless Merchant keeps all of his most valued
 posessions.  Otherwise our poor friend the thief would be out of a job.
 In order to know what types of features to create, we really should
 know the types of people who will be interacting with them.
  To get the ball rolling, I have created a small list of likely residents
 in a fantasy world.  In doing this, it becomes more clear what sorts of
 features I will expect to find in towns.

Professions (in no particular order)
   - Warriors         - Mages           - Scholars
   - Smiths           - Guides          - Alchemists
   - Rogues           - Bards           - Merchants
   - Assassins        - Paladins        - Monks
   - Priests          - Runesmiths      - Thieves
   - Druids           - Rangers         - Farmers
   - Men-at-Arms      - Knights         - Guards (and police)
   - Traders          - Pirates         - Masons
   - Healers          - and so on...

  Try to make the list smallish to begin with to speed things up a little,
 you can always return to this point if you think of more later.

Profession-Related Features
  For each possible profession in your rich and complex world, you
 will require a place for them to 'hang out'.  Examine your profession
 list and see what you can come up with.  For this I have separated
 my profession list into three categories: Class, Guild and Religion-
 based, though this is not really necessary.

 Class-based features
 - Taverns (for Bards and drunkards [warriors, rogues]),
 - Houses (for people to live in and thieves to steal from),
 - Library (for Scholars and Mages),
 - Hospital (for Healers),
 - xxxxsmiths (for Smiths),
 - Shops (for Merchants),
 - Ports (for Traders, Pirates, Rogues, &c.),
 - Farms (for Farmers),
 - Alpharmacy? (for Alchemists).

 Guilds
 - Barracks (for Men-at-Arms),
 - Thieves Guild,
 - Assassins Guild,
 - Runemasters Guild,
 - Gatehouse (for Guards),
 - School of Magic (for Mages),
 - Palaces, Castles, &c. (for Guards, Knights).

 Religions
 - Assorted Temples and Churches.  These should have variance to
   shew the alignments of your gods, eg.
   - Monastery,
   - Nunnery,
   - Cathedral,
   - Stone Circle (for Druids).

 Other
 - Inn,
 - Stables,
 - Asylum?,
 - Town Square.

  Now that we have a nice beginner's list of features for every fantasy
 denizen, we can flesh it out by adding some nice small details.  Many
 other types of features are required for efficient town life.  These
 quite frequently have to do with keeping the residents alive, or
 disposing with the dead.  Small additions such as wells and fountains
 can add much richness to a settlement; as can graveyards, statues,
 gibbets (and all other forms of public humiliation and execution), and
 so forth.

Town Themes
  Before taking the above information directly to coding, one key issue
 must be addressed: that of town themes.  In life, towns are frequently
 created for specific needs, be it a need for metals thereby necessitating
 a minetown or merely a need for clean water and safe refuge.
  If you wish to have more than one town in your game, it will be quite
 integral to their design to give them themes.  The best example of why
 town themes are important is to think briefly of what your towns would
 look like without them.  Imagine ten towns, all of roughly the same size,
 all with mines, all with markets, all with churches, all with guilds.
 These towns look artificial and can be much worse to play in than towns
 built completely randomly merely because of the cookie-cutter look they
 will have.
  I will assume here that if you do wish to have more than one town, you
 have a way of modelling the landscapes surrounding them, like the realm
 maps of ADOM, Omega, &c.  This is not required, though as themed towns
 can add a lot of flavour even to games like Vanillangband with only one
 town.
  It may be handy to make note of the types of terrain your denomination
 of humanoids may inhabit, and why they would be there.
   eg.  Human - Mainly near water, forests.  Have Castles on hills, Ports

near running water, only small towns in mountains. Dwarf - Mainly on hills. Have Mines in mountains. &c.

 Doing so will help the software in setting the theme for a town.
  Upon the decision to settle a specific area, the designer should examine
 the surrounding areas to see what a town here could add to life elsewhere.
 Is it a port for merchant ships? an oasis for passing travellers? a mine-
 town to supply precious metals to neighbors?  You will acquire a rough
 idea of how large a town will grow to be, given the amount the town
 is needed at its location and the theme of town created.  eg. If a town
 theme TouristTown is decided upon for an area with only a small
 surrounding population and no hot tourist spots (no dungeons, &c.) then
 the town will be quite small.  Whereas if a MineTown is decided upon and
 the mine is a necessary backbone for the arms and armour of a whole race,
 I would bet that it would be defended quite well, no matter how close
 they were to the enemy borders.
  Town themes also generally restrict the types of Features occuring in
 them.  It would be nothing short of disastrous to have your
 WitheredHouse near the StoneCircle filled with Cultists, only to have
 the evil random number generator put HappyJoesFriendlyInn between
 them.
  After the decision of what Theme to use has been made by the software
 for the town, it should then access a list of what features will be
 available for this theme.  You can do this any way you wish. For
 article continuity I will use a similar sort of list as Joseph Swing
 [JSwing@wport.com] used in his article on Continuous Content in dungeons,
 though I have adapted it to make use of my system of Features creating
 sub-Features.
  A sample list of a Human MineTown:

 Human MineTown
 .1 MineShaft ( exactly 1 )
 .2 Port ( if running water is available, maximum of 1 )
    .1 Market
 .3 Keep ( exactly 1 )
 .3 Tower
 .3 Castle ( if town is large, maximum of 1 )
    .1 City Walls ( exactly 1 )
    .2 Keep ( exactly 1 )
    .3 Gatehouse
    .3 Barracks
    .4 Tower
    .5 Tower
    .6 Tower
 .4 Temple ( or other religious site )
 .5 Tavern
 .5 Inn
    .1 Tavern
 .5 Shop
 .6 Shop
 .6 xxxsmith
 .6 Town Square
 .7 Farm
 .7 Farm
 .7 House
 .8 House
 .9 House

  The actual order of adding Features to your town is up to
 you. I suggest that you first create the important parts, such as
 mines, ports, and any other parts which depend on a certain type of
 terrain for positioning.  This is to ensure that you don't place
 another Feature where it will obscure access to the required terrain.
  You may wish to add (for added complexity) a system which records
 certain values for each town: foodAccess, shelter, defence, trade,
 and so on.  This will allow you to avoid adding redundant features,
 such as excessive shelter per resident, and more food than your
 residents can eat, trade or store.

Townspeople (t)
  Now that you have a reasonable idea of how you can design the towns,
 you now have the option of adding towns-people.  I say option, because it
 would be nice to have a version which doesn't create 'regular' inhabitants
 so you could adapt it to create ghost-towns, overrun towns, and more.
  This could easily be done by creating the class Town, then the derived
 classes PopulatedTown, GhostTown, &c.  Then all that these specialized
 versions need do is add the residents (possibly also knocking a few walls
 down for that 'derelict' look).  This is also a nice way to create over-
 run towns, such as the Human town taken over by Goblin Berserkers (or
 vice-versa).
  I will not go into the depths of creature behaviour here, though I
 will say that if you are going to this much trouble to make realistic
 towns, you really should think about adding at least a little depth
 and complexity to your creatures.
  You may also wish to consider racial tensions (if any) when creating
 your towns.  It is a fairly common fantasy convention that Dwarves
 don't really like anyone.  This could be taken into account when creating
 your towns, lowering the probability of other races living in a mainly
 Dwarvern town.  In the system I have developed, I take a creature's
 religious alignment to be much more important than their actual alignment.
 This allows creatures of all nationalities to befriend each other should
 they follow the same god: but creatures of opposed gods will certainly
 not tolerate living in the same town as each other.

Creation
  TEST RUN::

Below is a demonstration of the previous methods in action, of the steps

  an implementation of this might undergo.
 - Map.  We begin with a map, created by some other means, showing our
  lovely countryside, as below.  Take note that this is a 'Realm Map',
  such as in ADOM.

..^^....==... # Dungeon (or tower, ghost town, etc.) ^~^~.^~..=... . Clearing ^#~......==~~ T Forest .....TT...=== = River ......TT..~^^ ~ Hills .T.........~. ^ Mountains

 - Choose an area.  How you do this is up to you: you can use the RNG,
  or (my personal preference) you can have a Race(Human) class make the
  decision on where they would likely settle.  If you use this method
  you must choose at this point what race will be living here. We will
  create a Human city for this example. Here, the X marks the spot where
  we have decided to build.

..^^....==... ^~^~.^~..=... ^#~......==~~ X Proposed town site .....TT...=== ......TT..X^^ .T.........~.

 - Pick a Theme.  Examining the terrain around the designated area,
  we see that on four sides there are plains, on two sides there are
  rivers, and on one side each there are mountains and hills.  Given
  also that this site has high access (from the river) and is on
  hilly terrain, the designer decides to create a large city, which
  will contain mines, a castle for defense from the denizens of the
  dungeon '#' (and because, as was written above, Humans usually build
  their Castles on hills), and a port for trade.  We also decide now
  whether to create a populated town or not: for this example we will
  not make a population - this is really another topic, and dependant
  on how your creature system works.

 - Now we create the town, terrain first.  I will use (to save space
  here) a quarter-screen sized map, 40x12.  You may not wish to use
  elevation in your RL, but I have added here hills, marked with ':'.
  These have a few special rules: combat bonuses for creatures on
  elevated areas when in combat with those on normal ground; improved
  LOS and missile range.  Our terrain generator has created a HillyArea,
  which has then created a River, some Hills and a few scattered trees.

...............====............=======.. ................======================== . ground ..T................=============...:.=== : hill ......................:::T::......:::... T trees ...T...::.....:.......:::::......::::..: = water ....:::::....::......:T..:T:........:::: .....::....::::...........:.........:::: ...::::...:::.::::.............::....:.: ..........::...::.......:::............: ......::.T......:.......:::.....TT....:: ...........T.............::..........::: .................................:::::::

 - The Town.  We have the list of Features above, and by now you have
  likely added to the list some of your own favourites.  Now choose
  the first Feature from the list ( MineShaft ) and add it somewhere
  sensible (near hills).  We can then continue in the fashion described
  by Mr Swing ( 75% chance of choosing the next item, 25% chance of
  choosing the previous ), creating a Port and so on.

...............====............=======.. ................======================== a Mine ..T................=#===#=======...:.=== b Port ....................#b::#T::......:::... ...T...::.....:.....#+###::......::::..: ....:::::....::......:T..:T:........:::: .....::....::::...........:.........:::: ...::::...:::.::::.............::....:.: ..........::...::.......:::......##+###: ......::.T......:.......:::.....T#a..>#: ...........T.............::......######: .................................:::::::

   After a few more recursions, the town will hav begun to take shape.
  The map below shows what the town might look like after having created
  a castle.  Note that the castle walls do not fully include the Mine.
  This was due to the mine being close to the border of the map.
  Obviously there will be situations such as this, so your code might
  need a little tweaking.  Given the small scale of the map used, I will
  end the demonstration here, though on a larger map there would be
  sufficient room for adding the rest of the features on the list.
   The up staircases on the map below connect with to the second floor
  (where any guards would be) and the down staircases in the Mine and
  Keep can connect with Mines and Dungeons respectively.  There are
  enough articles on how to make these last two items: you shouldn't
  need my help.

  Ground Floor

...............====............=======.. ................======================== ..T........#+####..=#===#=======...:.=== a Gatehouses ......####.#a.#.#####.::####......:::... b Towers ...T..#<b####+#....c#+###:<#.....::::..: c City walls ....::#::+...::.........#:b#........:::: d Keep .....:##+#####:.........#+###..######::: ...::::#.#<..+::::g.......+a+..+<+.a#:.: .......#.#>.f#.::.......#+#########+###: e space (on a larger map ......:#.#####.:........#:b#....T#...>#: you would add .......#.......##########:<#.....######: shops, houses, .......#########........####.....::::::: an inn, and such.)

  Upstairs

xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx x Either unallocated xxxxxxxxxxx######xxx#####xxxxxxxxxxxxxxx tiles or 'air' tiles. xxxxxx######....#####...####xxxxxxxxxxxx xxxxxx#>................/.>#xxxxxxxxxxxx xxxxxx#..################..#xxxxxxxxxxxx xxxxxx########xxxxxxxxxx#..##########xxx xxxxxx#>..#xxxxxxxxxxxxx#.......>...#xxx xxxxxx#...#xxxxxxxxxxxxx#..#######..###x xxxxxx#####xxxxxxxxxxxxx#..#xxxxx#....#x xxxxxxxxxxxxxxxxxxxxxxxx#.>#xxxxx######x xxxxxxxxxxxxxxxxxxxxxxxx####xxxxxxxxxxxx

  That's it.  After creating your town, you have only the task
 of giving it some inhabitants of reasonable wit.  I hope that I
 have inspired a little something in some of you.  Please feel
 free to send me comments to me [michaelblackney@hotmail.com].

/-*/

Recursive Level Generation - Radomir 'The Sheep' Dopieralski [sheep@venus.wmid.amu.edu.pl]

Introduction.

This article contains some of my thoughts about level generation in roguelike games. It's inspired with an algorithm used in Alphaman to generate buildings, some articles red on Roguelike News and, that's a little odd, Bison and Yacc input files format. The ideas may seem a little complicated and hard to implement, but I hope the article proves useful in some way.

Overview.

The idea is to describe the level in form similar to BNF (Backus-Naur Form), used usually for describing context-free grammars.

It's natural for humans to describe large and complicated objects in terms of more simple ones. So we can describe a level. For example:

a level is either: a maze, a dungeon, a cave, a castle, etc...

a maze is a set of connected corridors and crossroads.

a corridor is a vertical or horizontal line of floor tiles, surrounded by walls on each side, opened at at least one end.

a crossroad is a single floor tile with walls around, opened in at least two directions.

a dungeon is a set of rooms, crossroads and corridors.

a room is either: a vault, a minor vault, an ordinary room. etc...

There are some rules not covered here. For example, we'd like to ensure each place of the level is reachable. It's not very easy to do, so we won't try to describe any level type, like in the example above. We'll try to only describe (and then generate) some special level type, constructed by dividing rooms.

Alphaman's buildings.

We will use an algorithm similar to this used in Alphaman. I'll first describe the original algorithm. It is quite simple:

1. Start with a large, empty room. XXXXXXXXXXXXXXXXX X...............X X...............X X...............X X...............X X...............X X...............X X...............X X...............X X...............X X...............X X...............X X...............X X...............X XXXXXXXXXXXXXXXXX

2. Pick an acxis (horizontal or vertical) and a point within the room (far from walls). Let's suppose we have picked horizontal axis and point marked with '1'. XXXXXXXXXXXXXXXXX X...............X X...............X X...............X X...............X X...............X X...............X X...............X X......1........X X...............X X...............X X...............X X...............X X...............X XXXXXXXXXXXXXXXXX

3. Make a wall in selected axis, crossing the chosen point, ending at the room's walls and with door in point '1'. XXXXXXXXXXXXXXXXX X...............X X...............X X...............X X...............X X...............X X...............X X...............X X######+########X X...............X X...............X X...............X X...............X X...............X XXXXXXXXXXXXXXXXX

4. You get two new rooms. Repeat the procedure with those of them, that arte large enough. XXXXXXXXXXXXXXXXX X...............X X...............X X###########+###X X...............X X...............X X...............X X...............X X######+########X X.........#.....X X.........+.....X X.........#.....X X.........#.....X X.........#.....X XXXXXXXXXXXXXXXXX

5. You end up with set of interconnected rooms, with exactly one way between every two rooms. Something like a tree.

The procedure is simple, but the result is not very nice. It's always a labirynth of rooms and you usually have to walk a lot to explore it. We'll try to make the result better.

Adding corridors.

We can try to add some corridors, so our level will look more naturally and there will be more connections between rooms. So, instead of adding a wall, we'll add two parallel walls, making a corridor. We also add doorways at the ends of the corridors, so there will be more connections. The algorithm goes like this:

1. Start with a large, empty room. XXXXXXXXXXXXXXXXX X...............X X...............X X...............X X...............X X...............X X...............X X...............X X...............X X...............X X...............X X...............X X...............X X...............X XXXXXXXXXXXXXXXXX

2. Pick an acxis (horizontal or vertical) and a point within the room (far from walls). Let's suppose we have picked horizontal axis and point marked with '1'. XXXXXXXXXXXXXXXXX X...............X X...............X X...............X X...............X X...............X X...............X X...............X X......1........X X...............X X...............X X...............X X...............X X...............X XXXXXXXXXXXXXXXXX

3. Make a corridor in selected axis, crossing the chosen point, ending at the room's walls. If the walls at it's ends are not permanent, make some doorways there. XXXXXXXXXXXXXXXXX X...............X X...............X X...............X X...............X X...............X X...............X X###############X X......1........X X###############X X...............X X...............X X...............X X...............X XXXXXXXXXXXXXXXXX

4. Make some doors along the corridor's walls. There should be at leas one door in each wall, so you make sure all the rooms are connected. XXXXXXXXXXXXXXXXX X...............X X...............X X...............X X...............X X...............X X...............X X####+######+###X X......1........X X###+###########X X...............X X...............X X...............X X...............X XXXXXXXXXXXXXXXXX

5. You get two new rooms. Repeat the procedure with those of them, that are large enough. XXXXXXXXXXXXXXXXX X...............X X###+###########X X...........2...X X#####+#####+###X X...............X X...............X X####+######+###X X......1........X X###+#####.#####X X........#3#....X X........#.+....X X........+.#....X X........#.#....X XXXXXXXXXXXXXXXXX

The result doesn't look so bad, especially if the rooms left at the end are big enough (in the example there isn't much place). But there is another problem -- how to fill the rooms with appropriate contents (that is items and monsters)? How to make sure the rooms are connected with some logic?

Level definitions.

Here's what we can do. We don't just split in two similar rooms. We will have to name these rooms and provide some rules how to split them. For example, for a scientific level in sf roguelike:

a level may: (put some probabilities here) be a scientific level;

a scientific level must: be at least SIZE large, but not larger than SIZE;

a scientific level may: consist of two scientific sections, divided (horizontally or vertically) with a scientific hall;

a scientific hall may: be a very wide corridor, with large doors at each end and at least one door at each side; there may be some plants or statues; there may be some scientific guards; there may be some scientific monsters; tehre may even be some scientific scientifists;

a scientific section may: consist of two scientific sections divided (horizontally or vertically) with a scientific corridor;

a scientific corridor may: be a wide corridor with open doorways at each end and at least one door at each side;

a scientific section must: be at least SIZE large, but not larger than SIZE;

a scientific section may: consist of two scientific labs divided (horizontally or vertically) with a scientific corridor;

a scientific lab must: be at least SIZE large, but not larger than SIZE;

a scientific lab may: consist of two scientific labs divided with a scientific wall;

a scientific wall may: be a wall with door in the middle;

a scientific lab may: be a room with tiled floor; there may be some scientific artifacts; there may be some scientific monsters; there may even be some scientific scientifists;

Building a level.

Now, let's see how to produce a random level from such an information. First, we want to build a level. So we look at the definitions and see that our level may be a scientific level with such-and-such probability. But there may be also other level definitions, so we have to choose (randomly) which level definition to choose. Let's suppose we have chosen the scientific level. We see that it has to be such-and-such big, so we provide an empty starting room of given size. Now we look into the definion and see that we have to split our level in two with a scientific hall and put a scientific section on each side. So we pick a point, pick an axis, put aour corridor in the middle and a scientific section at each side. It would be good to pay attention on the minimal size of each of the sections while picking a point to split the level. Then, we have to make our scientific sections. As we look into definitions, we see that we have two choices. So we pick randomly one of them. We can either split these sections into smaller ones, or into scientific labs. At some points, we'll have to do the second thing, because there will be no place to put a scientific section (which is supposedly larger than a lab). We continue down the tree of level fetures, until we arrive at the 'atom' ones, that is the features that doesn't consist of other features, and taht we can generate using other algorithms. Sometimes there may be need for the algorithm to 'back up' wrong decissions, because there is no way it can get to the atoms. This is because of the size limitations. It's a drawback and I don't know how to make sure it ever completes the level. But I believe it can be solved somehow.

Level representation.

With this algorithm you can use different level representations. The most common, simple two-dimensional array will do. But you can also have a linked list of features, or even a binary tree. If there were no doors at the ends of the corridors, you could even generete only these parts of the level you need at the moment, making all the fetures from the root of the tree to the node you want to know.

-- The Sheep

Finding Explorable Regions - Ross Morgan-Linial [rmorgan@jetcity.com].

This program takes a map and divides it into regions that are fully connected - that is, not split in half by walls, so the player can get anywhere in the region starting from a random point. I wrote it to determine if all of a dungeon level can be reached from the stairs, but you might find other uses for it; for example, you could use the results to find out where corridors need to be added to result in a fully connected level. Without further ado, here it is.

include <stdio.h>

/*

* This program divides a set of 'grids', which can be either wall or
* floor, into connected regions. Every grid in a region is connected
* to every other square in that region by vertical or horizontal (not
* diagonal) connections, and not connected to grids in any other
* region.
*
* We maintain a map that shows which region each grid is in. To avoid
* iterating over the entire map every time we discover two candidate
* regions are joined, we use a table that maps the numbers used on
* the grid to actual region numbers. At the end of the computation,
* we renumber the grid using this table.
*/

/* Change this to 1 to see how it works */

define debug 0

define MAP_WIDTH 12
define MAP_HEIGHT 12

/*

* Our map - 0 is wall, 1 is floor.
*
* We have to have a border of walls, or we may get strange errors.
*/

char grid[MAP_HEIGHT][MAP_WIDTH] = { {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0}, {0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0}, {0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0}, {0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0}, {0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0}, {0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0}, {0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0}, {0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0}, {0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0}, {0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0}, {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}};

define MAX_REGIONS 16
define NO_REGION 0 /* 0 is also a valid region */

int region_grid[MAP_HEIGHT][MAP_WIDTH]; int region_map[MAX_REGIONS]; int num_regions;

/*

* To reduce processing time, when two regions are found to connect
* (they're really the same region), we just mark them as the same
* without actually renumbering grids. At the end of the computation,
* or if we run out of region numbers, we use this function to update
* all grids to true region numbers. It also compacts the region
* numbers, so that afterwards all region numbers 0..num_regions-1
* are still used.
*/

void remap_regions(void) {

   int region_index[MAX_REGIONS];
   int region_index2[MAX_REGIONS];
   int new_regions;
   int x, y;
   int i;

   new_regions = 0;

   /*
    * Iterate through the regions, and assign a new number to each
    * non-remapped region so that they'll end up compacted.
    */
   for (i = 0; i < num_regions; i++)
   {
       /* Has this region not been mapped to another region? */
       if (region_map[i] == i)
       {
           /* No, it hasn't. Assign it a new region number. */
           if (debug)
           {
               printf("Mapping region: #%i -> #%i\n", i,             
                      new_regions);

}

           region_index[i] = new_regions++;
       }
       else
       {
           /* It's been renumbered. Check for processing errors. */
           if (region_map[region_map[i]] != region_map[i])
           {
               /*
                * We've encountered a bug: this region has been
                * mapped to a region that has also been mapped. Give
                * an error and abort.
                */
               fprintf(stderr, "Map %i->%i->%i\n", i, region_map[i],
                       region_map[region_map[i]]);
               abort();
           }

           /* Assign an in-bounds but otherwise meaningless value. */
           region_index[i] = NO_REGION;
       }
   }

   /*
    * Construct a table of the double-indirection through remapping
    * and compaction.
    */
   for (i = 0; i < num_regions; i++)
       region_index2[i] = region_index[region_map[i]];

   /* Renumber the grids, using the table we just computed. */
   for (y = 0; y < MAP_HEIGHT; y++)
       for (x = 0; x < MAP_WIDTH; x++)
           region_grid[y][x] = region_index2[region_grid[y][x]];

   /* Create a new do-nothing region mapping table. */
   for (i = 0; i < new_regions; i++)
       region_map[i] = i;

   /* Save the new number of regions. */
   num_regions = new_regions;

}

/*

* Join two candidate regions together. This just involves updating
* the region remapping table.
*/

void join_regions(int r1, int r2) {

   int i;
   int r1_map, r2_map;

   /* We have to operate on primary (unremapped) regions here */
   r1_map = region_map[r1];
   r2_map = region_map[r2];

   if (debug)
   {
       printf("Joining regions #%i (%i) and #%i (%i)\n", r1, r1_map,
              r2, r2_map);
   }

   /* Modify the region mapping table. */
   for (i = 0; i < num_regions; i++)
       if (region_map[i] == r2_map)
       {
           if (debug)
           {
               printf("Mapping region #%i (%i) -> #%i\n", i,
                      region_map[i], r1_map);
           }
           region_map[i] = r1_map;
       }

}

/*

* Create a new region.
*/

int new_region(void) {

   int i;

   /* If we're out of regions, compact them. */
   if (num_regions >= MAX_REGIONS)
   {
       if (debug)
           printf("Remapping regions\n");
       remap_regions();
   }

   /* If we're still out of regions, we have a problem. */
   if (num_regions >= MAX_REGIONS)
   {
       fprintf(stderr, "Too many regions\n");
       abort();
   }

   /* Allocate a new region. */
   i = num_regions++;
   region_map[i] = i;

   if (debug)
       printf("New region: #%i\n", i);

   return i;

}

void find_regions(void) {

   int x, y;
   int i;

   if (debug)
       printf("Clearing region grid\n");

   /* Clear the region grid to a valid (but meaningless) value. */
   for (y = 0; y < MAP_HEIGHT; y++)
       for (x = 0; x < MAP_WIDTH; x++)
           region_grid[y][x] = NO_REGION;

   /* Initialize the remapping table to a null map. */
   for (i = 0; i < MAX_REGIONS; i++)
       region_map[i] = i;

   /* Start with no regions. */
   num_regions = 0;

   /* Consider each grid, except the borders (leave them as walls) */
   for (y = 1; y < MAP_HEIGHT - 1; y++)
   {
       for (x = 1; x < MAP_WIDTH - 1; x++)
       {
           /* Skip wall grids. */
           if (!grid[y][x])
               continue;

           if (debug)
               printf("(%i, %i) ", x, y);

           /* 
            * Consider the possible combinations of left, above
            * grids.
            */
           if (!grid[y - 1][x])
           {
               if (!grid[y][x - 1])
               {
                   /* No floor left or above */
                   region_grid[y][x] = new_region();
               }
               else
               {
                   /* Floor left, but not above */
                   if (debug)
                   {
                       printf("Copying over #%i\n", 
                              region_grid[y][x - 1]);
                   }
                   region_grid[y][x] = region_grid[y][x - 1];
               }
           }
           else
           {
               if (!grid[y][x - 1])
               {
                   /* Floor above, but not left */
                   if (debug)
                   {
                       printf("Copying down #%i\n", 
                              region_grid[y - 1][x]);
                   }
                   region_grid[y][x] = region_grid[y - 1][x];
               }
               else
               {
                   /*
                    * Floor both left and above - are they the same 
                    * region?
                    */
                   if (region_map[region_grid[y - 1][x]] !=
                       region_map[region_grid[y][x - 1]])
                   {
                       /* No, join them. */
                       join_regions(region_grid[y - 1][x],
                                    region_grid[y][x - 1]);
                   }

                   /* They're now the same region, so copy one. */
                   if (debug)
                   {
                       printf("Copying down #%i\n", 
                              region_grid[y - 1][x]);
                   }
                   region_grid[y][x] = region_grid[y - 1][x];
               }
           }
       }
   }

   /* Do a final remapping, to make the region_grid[][] accurate. */
   remap_regions();

}

/*

* Print our results.
*/

void print_map(void) {

   int x, y;

   for (y = 1; y < MAP_HEIGHT - 1; y++)
   {
       for (x = 1; x < MAP_WIDTH - 1; x++)
       {
           if (grid[y][x])
           {
               printf("%c", 'A' + region_grid[y][x]);
           }
           else
               printf(" ");
       }
       printf("\n");
   }

}

int main(void) {

   find_regions();

   print_map();

   return 0;

}

Representing the Dungeon - Brian Bucklew [bbucklew@inteletek.com].

[Note: C++ Class Definitions Will Be Used Throughout]

Section 1 : The Question

       One of the most important things in writing a computer game of

any sort is the way in which you represent the universe the game takes place in. In a rogue-like, you will need to represent several things:

1. The Dungeon
2. The Slimy Things in The Dungeon
3. The Pointy Things with which a player kills Slimy Things
4. The Player that holds the Pointy Things

       This Article will cover #1: The Dungeon.

Section 2 : The Dungeon

       Alright, we need to find some way to represent the corridors and

rooms of The Dungeon itself. One of the easiest and most flexible methods of doing this is to create a two-dimensional array of cells. Each cell will be a wall, a floor, a door, a hideous spiked pit of death, or any number of other things we might want to represent as one tile:

class Tile {

       public:

       int Type;               // 0-Wall 1-Floor 2-Water 3-Open Door 4-Closed Door...
       unsigned int Flags;     // see below...

}

Section 2b : Bit-Flags

       One of the more important and space-saving methods of information tracking

is the use of bit-flags. As you know, a number in a computer is represented in binary, which is a series of ones and zeros... For instance the number 14 might be represented as: 00001110

Now, say we need to keep track of a number of things about a tile... Is it lit? Is it explored? Is is permenatly dark? Is it hairy?

We can use each individual bit in an integer to keep track of a true/false answer for questions like these.

So, how do you single out an individual bit? Well, bitwise operators come to save the day.

We can single out individual bits of a number by using the & (bitwise AND) operator. Each bit represents a power of two... So the first bit is 1, the second is 2 the third is 4 the fourth is 8 and so on... The & Operator takes two integers and returns an integer that only has 1 bits where the two origional integers BOTH had 1 bits... So to single out a bit, we take the variable containing the flags (Flags, in this case), and & it with the number represented by the bit we wish to read. If the returned number isn't zero, the flag is set, if it is zero the flag is not set...

This is a bit confusing, I'm sure, so here's some examples:

Example 1: (We'll use 16-bit integers to save space)

Flags : 0101000010010100

 We want This Bit-^
 It's the fifth bit, so 2^4 = 16.
 16 is 0000000000010000... so

 Flags & 16 = ?

 Flags:0101000010010100 
       &&&&&&&&&&&&&&&&
    16:0000000000010000
       ================
       0000000000010000;

 Which is greater than 0, so the flag is set...

Example 2:

Flags : 0101000010010100

 We want This Bit--^
 It's the fourth bit, so 2^3 = 8.
 8 is 0000000000001000... so

 Flags & 8 = ?

  Flags:0000000010010100
        &&&&&&&&&&&&&&&&
      8:0000000000001000
        ================
        0000000000000000;

 Which is 0, so the flag is not set...

Section 2c : Returning to The Dungeon...

       So we have our basic Tile class defined. All we need to do now is create

an array of these tiles:

       Tile Map[256][256];

Now, apply your favorite dungeon-generation method to this array of tiles and viola! You have a dungeon.

Section 3 : Positional Representation

       Anything in your Dungeon is going to have a position within the

Dungeon. This position is simply defined as an x and y coordinate within the 2D array of Tiles. If a player is at 16,19 we could look up the tile he is in using the line : Map[16][19], If the player is at 31,53 we could use Map[31][53]... So we can generalize and say that if the player had a position holding X and Y we could use the line : Map[Player.X][Player.Y];

We might also want to extend a position definition by giving it a facing...

8 1 2

\ | /
 \|/

7--*--3

 /|\
/ | \

6 5 4

So...

class Position {

       public:

       int X,Y;        // Our (X,Y) Coordinates
       int Facing;     // The direction this object is facing.

}

       Everything in your dungeon should have a position. Each Monster,

each item that is lying on the ground, and the player. This will allow you to keep track of each thing and their relations to one-another.

The Author: Brian Bucklew, 18 bbucklew@inteletek.com Current RL Project : Dungeon or "This game needs a new name"... :) Projected Beta Release : Early 98

Fun with dungeongeneration in QBasic - R.Alan Monroe.txt

I wondered what it would be like to do a random dungeon by repeatedly placing random sized "L" shaped hallways, each with a random 90 degree orientation, all over the map. Here's the results.

This method doesn't guarantee that all areas are reachable. You get a lot of cul-de-sacs, which could be good or bad depending on your game...

[fixed width font]

1. 1. 1. 1. ####### ######### ####### ########## # ##########
        
        ### ### ######## ####### ### ###### # ##########
        
        ######### ### ## ### ### ##### ### ###### # ### ######
        
        ## ## # ## ## # # ######
        
        ## # ### # ## ## ### ## # #
      2. ## # # # # #####
    2. #### # # # # ### ## ## # # #####
      1. # # # ## # # ## # # #####
    3. ## # ## # # # # #### # # # #####
      1. # ### # # ### ## # ## ##### #######
      2. ###### # # # # ## # ## ### ######
      3. ## #### # ##### ###### # #####
      4. # ############ ##### # ## # # ########### ########### #####
      5. ############## ########### # ########################## ######
        ########################## ############################ ######

1. 1. 1. 1. #################### ################################ #######
        
        ################ ### ### ############### ########### #######
        
        ############# ## ### ### ## #### # ##### #### ###### #######
        
        ######## ### ## ### ### ## ### ### # #### ## ### #######
  2. ####### # # ###
    1. 1. # ### # ## ## # # # ## #####
  3. # # ## # # ## ####
2. # #### # # ## # # ## ## # # ####
3. # #### # ## # ## ## # # # # ########
  1. 1. 1. # # ## # ### # # # ########
        #### ## # ## #####
        #### # ##### ### ###
      2. ## ##### ### ## #### # #####
        ## ## ###### # ### ## ####### # ### #### # # #####
        
        ##### # ###### # #### ## ####### # ###### ##### #########
        
        ####### ################## ####### # ############ #########
        #########################

1. 1. 1. 1. ##### ####################################
        
        ##### ############# #####################
        
        ############### ##### ######### ### # ###################
      2. ### ###### ## # # # ## ## ### # ### ###############
      3. # # # ### # # ## ## ######
      4. # # ## ## ### # ####### ######
      5. # ### ## ### # ###### ####
      6. ### ## #### # # ## ## ### #####
        # # ## # ## ## ## # # ## # #####
    2. ## ## # # ##
      1. # ### ### ## ## ####
        
        # ##### ### #### # ###
        
        ##### ##### #### ### ### # ### ###### ### ###### # ######
        
        ##### ##### #### ### ### ## #### ###### ########## # ######
        
        ########### ############ ############## ########### ## #######
        ############ ############## ########### ## #######

RANDOMIZE TIMER

DIM a(70, 20)

begin:

CLEAR CLS

FOR l = 1 TO 150

  x = INT(RND * 59) + 6
  y = INT(RND * 9) + 6
  d = INT(RND * 4)
  a(x, y) = 1
  SELECT CASE d
     CASE 0
        FOR i = 1 TO INT(RND * 5)
           a(x + i, y) = 1
           a(x, y - i) = 1
        NEXT i
     CASE 1
        FOR i = 1 TO INT(RND * 5)
           a(x + i, y) = 1
           a(x, y + i) = 1
        NEXT i
     CASE 2
        FOR i = 1 TO INT(RND * 5)
           a(x - i, y) = 1
           a(x, y - i) = 1
        NEXT i
     CASE 3
        FOR i = 1 TO INT(RND * 5)
           a(x - i, y) = 1
           a(x, y + i) = 1
        NEXT i
  END SELECT

NEXT l

FOR row = 1 TO 19

  FOR col = 1 TO 69
     IF a(col, row) = 0 THEN
        PRINT "#";
     ELSE
        PRINT " ";
     END IF
  NEXT col
  PRINT

NEXT row

WHILE INKEY$ = "" WEND

GOTO begin

Populating The Dungeon Of Items & NPC's - Stuart George [entropy@ihug.com.au].

By Stuart George :: [entropy@ihug.com.au] :: 3may99

I have to say up front, I have not looked in depth (if at all) at how other rogue likes approach this task. So my methods are probably not as fast or good as ones tried and tested in code like nethack + angband for the past N years they have been using it ;)

Quite often one of the first tasks in a rogue like is creating the mazes... Once you have created a working maze generation routine you have to fill it, both with items, traps, monsters, stairs, etc.

Kitting out your dungeon can be as hard or as easy as you like, but a lot of it has to do with how you generated your maze.

I'll discuss here how I've gone about doing it.

First I'll discuss how NOT to do it, I saw this example only once (in a quite basic "in development" game)... The dungeon was hewn from a static 128x128 grid and for placement of objects, a random position of x=rnd(128), y=rnd(128) was taken for every object wanting to be placed on the map, this x.y was then tested against the grid to see if it was a floor tile, if so was placed, and if not was repeatedly calling for random numbers for x.y and testing them all over the grid.

Needless to say, with lots of objects and a small dungeon, this could make the computer test locations for days until it got a match...

That is how NOT to do it, basically its a poor mans algorithm. (But as someone pointed out, its easy to do things this way and it does indeed work if you maze fills most of the confines of your 'grid')

When I generate the maze, i store in a list all the rooms created. Hallways are just "skinny" rooms in my view, so they all get put on the list.

This list is quite basic, its a linked list and contains the x1.y1-x2.y2 and a flag of every object and nothing else. the flag is just set when its wider or longer than 1 (ie flag is set when its not a "hall"), if you have to refer to the list often its easier to test a flag than to test x2-x1 + y2-y1 for every object..

When I want to add say, stairs up, i just randomly pick an object from my list, then once you have your "room" randomly pick an x.y within that room y=rnd(y2)+y1, x=rnd(x2)+x1 and place the object. repeat as necessary.

You can check for overlapping if you wish or simply stack items in a list.

Since hallways outnumber rooms by a great number, its nice to not always have everything generated in a hallway, thats why the flag is for, so when objects from the list are selected, you can give a greater chance to gen something in a room than in a hallway...

You could also store two lists, one for "rooms" and one for "halls".

My dungeons are created entirely by the RNG, so when i save/load a level I only need take note of the RNG seed before creation starts, since the same seed produces the same level, the object list gets rebuilt and thus you don't have to store that list.

You _do_ have to save the x.y positions of static things, ala traps (moving bear pits?) and stairs. monsters move (for the most part) so if they are not in the same spot, you could say they wandered about ;), and items, well they got picked up and moved and dropped ;). But these are weak excuses for cutting code really... ^_^

When going from 1 level to another you can dump the object list for the same reasons as the load/save given above.

This is of course, very simple and does not take into account someone with a digging wand adding a new corridor to your dungeon (since its user created, it wont be created with the RNG seed). Of course it would be easy to add the newly created portions to a list, stored with the RNG dungeon seed, etc.

I find this method quite good, its quick and easy to "spawn" monsters with this method..

The one thing I thought I should mention is the fact that my "rooms" and "hallways" are not connected. doors are placed in between as "connections" but they not connected on creation by "touching" each other, and thus doorways don't show up on my object list. (good or bad I don't know, but I'm very happy with my dun-gen routine, it also just means nothing will be placed over the top of a doorway)

A Method For Growing Rivers In A Randomly Generated World - Dana Larose [dana@pixelenvy.ca].txt

In response to a question on rec.games.roguelike.development, I coded up a demo on how one might make randomized rivers that originate in a part of the world that hasn't been generated yet.

The Problem

You are building a world region by region (as the player explores them), so you do not the the layout of the entire planet in advance. How to create long rivers that can span into regions that haven't be created yet? I'll present here an explanation of how this can be done and provide a demo written in Python.

Summary of Algorithm (Although it's simple enough to almost not qualify as an algorithm!)

Suppose you generate a 20X20 area of the world that looks like this:

. . . . . . . . ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ = water . . . . . . . . . ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ . = plains . . . . . . . . . . ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ # = trees . . . . . . . . . . . ~ ~ ~ ~ ~ ~ ~ ~ ~ ^ = hills/mountains . . . . . . . . . . . . ~ ~ ~ ~ ~ ~ ~ ~ ^ . . . . . . . . . . . . ~ ~ ~ ~ ~ ~ ~ ^ ^ . . . . . . . . . . . . ~ ~ ~ ~ ~ ~ ^ ^ ^ . . . . . . . . . . . . ~ ~ ~ ~ ~ ^ ^ ^ ^ . . . . . . . . . . . . ~ ~ ~ ~ ^ ^ ^ ^ ^ . . . # # # . . . . . . ~ ~ ~ ^ ^ ^ ^ ^ . . # # . . . . . . . . . ~ ~ ^ ^ ^ ^ ^ ^ # # # # . . . . . . . . . ~ ^ ^ ^ ^ ^ ^ ^ ^ # # # . . . . . . . . . ^ ^ ^ ^ ^ ^ ^ ^ ^ # # . . . . . . . . . ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . . . . . . . . . . ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . . . . . . . . . ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . . . . . . . . ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . . . . . . . ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . . . . . . ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . . . . .

Your world generation algorithm determines this lake/ocean will have a river flowing into it. Start drawing a river backwards from the ocean. For my simple demo, I used the following stopping condition for the river: If river was about to cross from an area of higher elevation to an area of lower elevation, terminate the loop. Additionally, I started with a 5% chance of terminating the river and each time the drawing loop iterates, I increase that by 5%.

One particular run of my demo made the following map:

. . . . . . . . ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ . . . . . . . . . ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ . . . . . . . . . . ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ . . . . . . . . . . . ~ ~ ~ ~ ~ ~ ~ ~ ~ . . . . . . . . . . . . ~ ~ ~ ~ ~ ~ ~ ~ ^ . . . . . . . . . . ~ . ~ ~ ~ ~ ~ ~ ~ ^ ^ . . . . . . . . ~ . . . ~ ~ ~ ~ ~ ~ ^ ^ ^ . . . . . . ~ . . . . . ~ ~ ~ ~ ~ ^ ^ ^ ^ . . . . ~ . . . . . . . ~ ~ ~ ~ ^ ^ ^ ^ ^ . ~ ~ # # # . . . . . . ~ ~ ~ ^ ^ ^ ^ ~ ~ . # # . . . . . . . . . ~ ~ ^ ~ ~ ~ ^ ^ # # # # . . . . . . . . . ~ ~ ^ ^ ^ ^ ^ ^ ^ # # # . . . . . . . . . ^ ^ ^ ^ ^ ^ ^ ^ ^ # # . . . . . . . . . ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . . . . . . . . . . ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . . . . . . . . . ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . . . . . . . . ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . . . . . . . ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . . . . . . ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . . . . .

If your river reaches the border of a region, again terminate it. (Note that it should also terminate before crossing into region that has already been generated, my demo doesn't do this). At this point, you need to store the fact that a river has terminated at a border of the region. Python is OOP-enabled, so it was quite easy for me to add this information to the region class. I stored the instance of the terrain, it's coordinates and the last move the drawing algorithm was about to make (so I can continue drawing it in the same general direction when it is time to build the next region).

When the player cross into an previously unexplored region, you will have to pass the details of already generated neighbouring regions, providing access to their lists of border features. If a neighbour is null, it hasn't been made yet and can be ignored. In the demo, when a new region is made, we see that it has a neighbour to the east, and that a river terminated at the border (row 12, column 0). After the new region is created, we need to draw a river starting at (row 12, column 19). Using the same algorithm, we draw until we hit a termination condition. In this case, the river started in the hills, so it will continue until it hits a border, or is about to cross from the hills (high elevation) to the plains (lower elevation).

A sample run of my demo produce: . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

# # # # # # # . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . .
# # # # # # ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^
# # . . . . . . . ^ ^ ^ ^ ^ ^ ^ ^ ^ ^
# # # # # # . . . . . ^ ^ ^ ^ ^ ^ ^ ^
# # # # # . . . . . ^ ^ ^ ^ ^ ^ ^ ^ ^
# # # # # # # ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^
# . . . . . . . . . . . ^ ^ ^ ^ ^ ^ ^
# # # # # # . ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^
# # # # # # . . . . . . . ^ ^ ^ ^ ^ ~
# . . . . . . ^ ^ ^ ^ ^ * ^ ^ ^ ^ * ^
# # # . . . . . . ^ ^ ^ ^ * ^ ^ * ^ ^
# # # # # # # . . ^ ^ ^ ^ ^ * * ^ ^ ^
# . . . . . . . . . . . ^ ^ ^ ^ ^ ^ ^
. . . . . . . . . ^ ^ ^ ^ ^ ^ ^ ^ ^ ^

. . . . . . . . . . . . ^ ^ ^ ^ ^ ^ ^ ^ . . . . . . . . ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^

(The river created is marked with *'s so they stand out a little better).

Putting them side by side: . . . . . . . . . . . . . . . . . . . . . . . . . . . . ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ~ ~ ~ ~ ~ ~ ~ ~ ~ ~

# # # # # # # . . . . . . . . . . . . . . . . . . . . . . . ~ ~ ~ ~ ~ ~ ~ ~ ~
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ~ ~ ~ ~ ~ ~ ~ ~
# # # # # # ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . . . . . . . . . . ~ . ~ ~ ~ ~ ~ ~ ~
# # . . . . . . . ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . . . . . . . . ~ . . . ~ ~ ~ ~ ~ ~
# # # # # # . . . . . ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . . . . . . ~ . . . . . ~ ~ ~ ~ ~
# # # # # . . . . . ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . . . . ~ . . . . . . . ~ ~ ~ ~
# # # # # # # ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . ~ ~ # # # . . . . . . ~ ~ ~
# . . . . . . . . . . . ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ~ ~ . # # . . . . . . . . . ~ ~
# # # # # # . ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ~ ~ ~ ^ ^ # # # # . . . . . . . . . ~
# # # # # # . . . . . . . ^ ^ ^ ^ ^ ~ ~ ^ ^ ^ ^ ^ ^ ^ # # # . . . . . . . . .
# . . . . . . ^ ^ ^ ^ ^ * ^ ^ ^ ^ * ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ # # . . . . . . . . .
# # # . . . . . . ^ ^ ^ ^ * ^ ^ * ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . . . . . . . . . .
# # # # # # # . . ^ ^ ^ ^ ^ * * ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . . . . . . . . .
# . . . . . . . . . . . ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . . . . . . . .
. . . . . . . . . ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . . . . . . .

. . . . . . . . . . . . ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . . . . . . . . . . . . . . ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . . . . .

A nice, slightly winding river is created in one region, then continued in the bordering region when it comes time to generate the neighbour.

Notes About The Demo - The demo was slapped together in about an hour, so please don't judge my coding skills on it! It probably has bugs, invalid assumptions, poor coding standards/styles, inefficiencies and/or redundant code!

- There are probably plenty of ways to generate nicer looking rivers, I just used a couple of ideas that popped into my head while coding. Mine often generates straight lines, which look silly (it took me a couple tries to get a nice looking river for this page). But again, that wasn't the point of the demo!

- The termination condititions could be improved. For instance, if you are stopping because you are about to cross into another region, you could back the drawing up one square so it doesn't look like the river originates at the border of two elevations.

- It would be neat to look for good likely termination points. Suppose a lake was generated at the same (or higher) elevation as the river, it would make a good candidate for a termination point. (Hmm - confusing terminology - when I speak of termination point, I mean where the algorithm stops drawing, which is the origin point for the river in the geographic sense)

- The demo doesn't generate terrain, I don't know if my roguelike is going to have random or fixed wildernesses, I just wanted to offer a solution to the question on the newsgroup.

- The demo is cooked to draw a river that starts at the lake and ends at the border of the first region (the cooked functions are labeled as such). See previous point.

- My method only draws rivers from the mouth of the river backwards to the spring, but it woulddn't take a great leap to make a version that draws from a spring to a terminatition point. Indeed, since you would be drawing into a region that has not been determined, you could force the generator to create a nice termination point for your river.

- Written and tested in Python 2.2.1, probably works with Python 2.x.x, might even work with Python 1.5.x

There are three main classes used in the demo:

Terrain - Represents an individual square of terrain. Uses fields ch (the character to display), type (the type of terrain and elevation - integer saying how high the terrain is. I used ocean/lake = 0, plains/trees = 1 and hills = 2. An interesting idea would be to store a floating point number and use that to determine where the river should flow from the geography of the land?

Region - stores information about the section of the world this represents. In the demo, this is essentially a collection of Terrain squares and a little additional info used in the demo (such as the border features of this region). In a full game, this would need to store a fair amount of additional information.

RegionGenerator - builds a region of land. Note that in the demo, the regions are cooked and the river in the first region is partially cooked.

The code is offered without warranty or guarantee as an idea for folks writing map generators. If you want to use a substantial part of the code in your game, please ask permission. Here is grow_river.py.txt (named so because browsers sometimes complain about .py extentions, save it your harddrive and rename it grow_river.py before running).

You can reach me at dana@pixelenvy.ca with questions, suggestions, etc.

@@ Line 10: / Line 10: @@
     * Recursive randomized world-map generation Phillip C. Culliton [pcullit@hotmail.com].txt
     * 3D Representation for Roguelike Worlds - Jimmy Babcock [jimmy_b@earthlink.net].txt
+   * Random Dungeon Algo in QBasic - Andrew Collins [andrewcollins@hotmail.com].txt
+   * Nest of Ants - Jakub Debski [jakub@mks.com.pl].txt
+   * Passable Cave Building Algorithm - Josh Tippets [vertexnormal@email.com].txt
 TODO:
@@ Line 6,903: / Line 6,906: @@
 --
 The Sheep
+= Finding Explorable Regions - Ross Morgan-Linial [rmorgan@jetcity.com]. =
+This program takes a map and divides it into regions that are fully
+connected - that is, not split in half by walls, so the player can
+get anywhere in the region starting from a random point. I wrote it
+to determine if all of a dungeon level can be reached from the
+stairs, but you might find other uses for it; for example, you could
+use the results to find out where corridors need to be added to
+result in a fully connected level. Without further ado, here it is.
+#include <stdio.h>
+/*
+ * This program divides a set of 'grids', which can be either wall or
+ * floor, into connected regions. Every grid in a region is connected
+ * to every other square in that region by vertical or horizontal (not
+ * diagonal) connections, and not connected to grids in any other
+ * region.
+ *
+ * We maintain a map that shows which region each grid is in. To avoid
+ * iterating over the entire map every time we discover two candidate
+ * regions are joined, we use a table that maps the numbers used on
+ * the grid to actual region numbers. At the end of the computation,
+ * we renumber the grid using this table.
+ */
+/* Change this to 1 to see how it works */
+#define debug 0
+#define MAP_WIDTH   12
+#define MAP_HEIGHT  12
+/*
+ * Our map - 0 is wall, 1 is floor.
+ *
+ * We have to have a border of walls, or we may get strange errors.
+ */
+char grid[MAP_HEIGHT][MAP_WIDTH] = {
+{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
+{0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0},
+{0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0},
+{0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0},
+{0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0},
+{0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 0},
+{0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0},
+{0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0},
+{0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0},
+{0, 1, 1, 1, 0, 0, 0, 0, 1, 1, 0, 0},
+{0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0},
+{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}};
+#define MAX_REGIONS 16
+#define NO_REGION   0   /* 0 is also a valid region */
+int region_grid[MAP_HEIGHT][MAP_WIDTH];
+int region_map[MAX_REGIONS];
+int num_regions;
+/*
+ * To reduce processing time, when two regions are found to connect
+ * (they're really the same region), we just mark them as the same
+ * without actually renumbering grids. At the end of the computation,
+ * or if we run out of region numbers, we use this function to update
+ * all grids to true region numbers. It also compacts the region
+ * numbers, so that afterwards all region numbers 0..num_regions-1
+ * are still used.
+ */
+void remap_regions(void)
+{
+    int region_index[MAX_REGIONS];
+    int region_index2[MAX_REGIONS];
+    int new_regions;
+    int x, y;
+    int i;
+    new_regions = 0;
+    /*
+     * Iterate through the regions, and assign a new number to each
+     * non-remapped region so that they'll end up compacted.
+     */
+    for (i = 0; i < num_regions; i++)
+    {
+        /* Has this region not been mapped to another region? */
+        if (region_map[i] == i)
+        {
+            /* No, it hasn't. Assign it a new region number. */
+            if (debug)
+            {
+                printf("Mapping region: #%i -> #%i\n", i,
+                       new_regions);
+			}
+            region_index[i] = new_regions++;
+        }
+        else
+        {
+            /* It's been renumbered. Check for processing errors. */
+            if (region_map[region_map[i]] != region_map[i])
+            {
+                /*
+                 * We've encountered a bug: this region has been
+                 * mapped to a region that has also been mapped. Give
+                 * an error and abort.
+                 */
+                fprintf(stderr, "Map %i->%i->%i\n", i, region_map[i],
+                        region_map[region_map[i]]);
+                abort();
+            }
+            /* Assign an in-bounds but otherwise meaningless value. */
+            region_index[i] = NO_REGION;
+        }
+    }
+    /*
+     * Construct a table of the double-indirection through remapping
+     * and compaction.
+     */
+    for (i = 0; i < num_regions; i++)
+        region_index2[i] = region_index[region_map[i]];
+    /* Renumber the grids, using the table we just computed. */
+    for (y = 0; y < MAP_HEIGHT; y++)
+        for (x = 0; x < MAP_WIDTH; x++)
+            region_grid[y][x] = region_index2[region_grid[y][x]];
+    /* Create a new do-nothing region mapping table. */
+    for (i = 0; i < new_regions; i++)
+        region_map[i] = i;
+    /* Save the new number of regions. */
+    num_regions = new_regions;
+}
+/*
+ * Join two candidate regions together. This just involves updating
+ * the region remapping table.
+ */
+void join_regions(int r1, int r2)
+{
+    int i;
+    int r1_map, r2_map;
+    /* We have to operate on primary (unremapped) regions here */
+    r1_map = region_map[r1];
+    r2_map = region_map[r2];
+    if (debug)
+    {
+        printf("Joining regions #%i (%i) and #%i (%i)\n", r1, r1_map,
+               r2, r2_map);
+    }
+    /* Modify the region mapping table. */
+    for (i = 0; i < num_regions; i++)
+        if (region_map[i] == r2_map)
+        {
+            if (debug)
+            {
+                printf("Mapping region #%i (%i) -> #%i\n", i,
+                       region_map[i], r1_map);
+            }
+            region_map[i] = r1_map;
+        }
+}
+/*
+ * Create a new region.
+ */
+int new_region(void)
+{
+    int i;
+    /* If we're out of regions, compact them. */
+    if (num_regions >= MAX_REGIONS)
+    {
+        if (debug)
+            printf("Remapping regions\n");
+        remap_regions();
+    }
+    /* If we're still out of regions, we have a problem. */
+    if (num_regions >= MAX_REGIONS)
+    {
+        fprintf(stderr, "Too many regions\n");
+        abort();
+    }
+    /* Allocate a new region. */
+    i = num_regions++;
+    region_map[i] = i;
+    if (debug)
+        printf("New region: #%i\n", i);
+    return i;
+}
+void find_regions(void)
+{
+    int x, y;
+    int i;
+    if (debug)
+        printf("Clearing region grid\n");
+    /* Clear the region grid to a valid (but meaningless) value. */
+    for (y = 0; y < MAP_HEIGHT; y++)
+        for (x = 0; x < MAP_WIDTH; x++)
+            region_grid[y][x] = NO_REGION;
+    /* Initialize the remapping table to a null map. */
+    for (i = 0; i < MAX_REGIONS; i++)
+        region_map[i] = i;
+    /* Start with no regions. */
+    num_regions = 0;
+    /* Consider each grid, except the borders (leave them as walls) */
+    for (y = 1; y < MAP_HEIGHT - 1; y++)
+    {
+        for (x = 1; x < MAP_WIDTH - 1; x++)
+        {
+            /* Skip wall grids. */
+            if (!grid[y][x])
+                continue;
+            if (debug)
+                printf("(%i, %i) ", x, y);
+            /*
+             * Consider the possible combinations of left, above
+             * grids.
+             */
+            if (!grid[y - 1][x])
+            {
+                if (!grid[y][x - 1])
+                {
+                    /* No floor left or above */
+                    region_grid[y][x] = new_region();
+                }
+                else
+                {
+                    /* Floor left, but not above */
+                    if (debug)
+                    {
+                        printf("Copying over #%i\n",
+                               region_grid[y][x - 1]);
+                    }
+                    region_grid[y][x] = region_grid[y][x - 1];
+                }
+            }
+            else
+            {
+                if (!grid[y][x - 1])
+                {
+                    /* Floor above, but not left */
+                    if (debug)
+                    {
+                        printf("Copying down #%i\n",
+                               region_grid[y - 1][x]);
+                    }
+                    region_grid[y][x] = region_grid[y - 1][x];
+                }
+                else
+                {
+                    /*
+                     * Floor both left and above - are they the same
+                     * region?
+                     */
+                    if (region_map[region_grid[y - 1][x]] !=
+                        region_map[region_grid[y][x - 1]])
+                    {
+                        /* No, join them. */
+                        join_regions(region_grid[y - 1][x],
+                                     region_grid[y][x - 1]);
+                    }
+                    /* They're now the same region, so copy one. */
+                    if (debug)
+                    {
+                        printf("Copying down #%i\n",
+                               region_grid[y - 1][x]);
+                    }
+                    region_grid[y][x] = region_grid[y - 1][x];
+                }
+            }
+        }
+    }
+    /* Do a final remapping, to make the region_grid[][] accurate. */
+    remap_regions();
+}
+/*
+ * Print our results.
+ */
+void print_map(void)
+{
+    int x, y;
+    for (y = 1; y < MAP_HEIGHT - 1; y++)
+    {
+        for (x = 1; x < MAP_WIDTH - 1; x++)
+        {
+            if (grid[y][x])
+            {
+                printf("%c", 'A' + region_grid[y][x]);
+            }
+            else
+                printf(" ");
+        }
+        printf("\n");
+    }
+}
+int main(void)
+{
+    find_regions();
+    print_map();
+    return 0;
+}
+= Representing the Dungeon - Brian Bucklew [bbucklew@inteletek.com]. =
+[Note: C++ Class Definitions Will Be Used Throughout]
+Section 1 : The Question
+        One of the most important things in writing a computer game of
+any sort is the way in which you represent the universe the game takes
+place in. In a rogue-like, you will need to represent several things:
+#1. The Dungeon
+#2. The Slimy Things in The Dungeon
+#3. The Pointy Things with which a player kills Slimy Things
+#4. The Player that holds the Pointy Things
+        This Article will cover #1: The Dungeon.
+Section 2 : The Dungeon
+        Alright, we need to find some way to represent the corridors and
+rooms of The Dungeon itself. One of the easiest and most flexible methods
+of doing this is to create a two-dimensional array of cells. Each cell will
+be a wall, a floor, a door, a hideous spiked pit of death, or any number of
+other things we might want to represent as one tile:
+class Tile
+{
+        public:
+        int Type;               // 0-Wall 1-Floor 2-Water 3-Open Door 4-Closed Door...
+        unsigned int Flags;     // see below...
+}
+Section 2b : Bit-Flags
+        One of the more important and space-saving methods of information tracking
+is the use of bit-flags. As you know, a number in a computer is represented
+in binary, which is a series of ones and zeros... For instance the number
+might be represented as:
+00001110
+Now, say we need to keep track of a number of things about a tile... Is it
+lit? Is it explored? Is is permenatly dark? Is it hairy?
+We can use each individual bit in an integer to keep track of a true/false
+answer for questions like these.
+So, how do you single out an individual bit? Well, bitwise operators come to
+save the day.
+We can single out individual bits of a number by using the & (bitwise AND)
+operator. Each bit represents a power of two... So the first bit is 1, the
+second is 2 the third is 4 the fourth is 8 and so on... The & Operator
+takes two integers and returns an integer that only has 1 bits where the two
+origional integers BOTH had 1 bits... So to single out a bit, we take the
+variable containing the flags (Flags, in this case), and & it with the number
+represented by the bit we wish to read. If the returned number isn't zero,
+the flag is set, if it is zero the flag is not set...
+This is a bit confusing, I'm sure, so here's some examples:
+Example 1: (We'll use 16-bit integers to save space)
+Flags : 0101000010010100
+  We want This Bit-^
+  It's the fifth bit, so 2^4 = 16.
+is 0000000000010000... so
+  Flags & 16 = ?
+  Flags:0101000010010100
+        &&&&&&&&&&&&&&&&
+:0000000000010000
+        ================
+        0000000000010000;
+  Which is greater than 0, so the flag is set...
+Example 2:
+Flags : 0101000010010100
+  We want This Bit--^
+  It's the fourth bit, so 2^3 = 8.
+is 0000000000001000... so
+  Flags & 8 = ?
+   Flags:0000000010010100
+         &&&&&&&&&&&&&&&&
+:0000000000001000
+         ================
+         0000000000000000;
+  Which is 0, so the flag is not set...
+Section 2c : Returning to The Dungeon...
+        So we have our basic Tile class defined. All we need to do now is create
+an array of these tiles:
+        Tile Map[256][256];
+Now, apply your favorite dungeon-generation method to this array of tiles and
+viola! You have a dungeon.
+Section 3 : Positional Representation
+        Anything in your Dungeon is going to have a position within the
+Dungeon. This position is simply defined as an x and y coordinate within
+the 2D array of Tiles. If a player is at 16,19 we could look up the tile
+he is in using the line : Map[16][19], If the player is at 31,53 we could
+use Map[31][53]... So we can generalize and say that if the player had
+a position holding X and Y we could use the line : Map[Player.X][Player.Y];
+We might also want to extend a position definition by giving it a facing...
+  1  2
+ \ | /
+  \|/
+--*--3
+  /|\
+ / | \
+  5  4
+So...
+class Position
+{
+        public:
+        int X,Y;        // Our (X,Y) Coordinates
+        int Facing;     // The direction this object is facing.
+}
+        Everything in your dungeon should have a position. Each Monster,
+each item that is lying on the ground, and the player. This will allow you
+to keep track of each thing and their relations to one-another.
+The Author:
+Brian Bucklew, 18
+bbucklew@inteletek.com
+Current RL Project : Dungeon or "This game needs a new name"... :)
+Projected Beta Release : Early 98
+= Fun with dungeongeneration in QBasic - R.Alan Monroe.txt =
+I wondered what it would be like to do a random dungeon by repeatedly
+placing random sized "L" shaped hallways, each with a random 90 degree
+orientation, all over the map. Here's the results.
+This method doesn't guarantee that all areas are reachable. You get a
+lot of cul-de-sacs, which could be good or bad depending on your
+game...
+[fixed width font]
+#####################################################################
+#####################################################################
+################### ####### ######### ####### ########## # ##########
+################### ### ### ########  ####### ### ###### # ##########
+########  ######### ### ##   ### ###    ##### ### ###### # ### ######
+########      ##    ##  #         ##       ##         #     #  ######
+########  ##         #       ###  #            ## ## ### ##   #     #
+#####     ##        #                    #  #                 # #####
+####     ####  # #  #          #            ###   ## ## #     # #####
+######   #                  #  #        ##   #     #    ## #  # #####
+####      ##   # ## #  #    #  #       #### #   #             # #####
+#####  #  ###  # #                      ### ##  #  ##  #####  #######
+#####     ###### #      #      #     #   ##     #  ##  ###     ######
+#####         ##       ####     #      #####        ######   #  #####
+#####  # ############ ##### #  ## #  # ########### ###########  #####
+#####  ############## ########### # ########################## ######
+###### ########################## ############################ ######
+#####################################################################
+#####################################################################
+#####################################################################
+####### #################### ################################ #######
+####### ################ ### ###  ############### ########### #######
+####### ############# ## ### ###  ## #### # ##### #### ###### #######
+####### ########  ### ## ### ###  ## ###    ### # #### ## ### #######
+###     #######   #                          #                    ###
+#####  # ###          # ##   ##    # # #                  ##    #####
+###                 #     #   ##   #         #              ##   ####
+##     # #### #        #   ## #      #       ##     ##  # #      ####
+##     # #### #  ##      # ##     ##     # #         #    #  ########
+###### #                 # ## #  ###  #  #                #  ########
+#######    ####            ##         #                  ##     #####
+###########       #### #              #####  ###                  ###
+#####    ##      #####     ###                 ##     ####  #   #####
+######## ## ##   ######  # ###  ##  ####### #  ###    ####  # # #####
+######## ##### # ######  # #### ##  ####### #  ###### ##### #########
+######## ####### ################## ####### #  ############ #########
+########################################### #########################
+#####################################################################
+#####################################################################
+#####################################################################
+######################### #####  ####################################
+########################  #####  #############  #####################
+####### ###############   #####  ######### ###  # ###################
+#####     ### ###### ##    #     # # ## ## ###  # ### ###############
+##### # #  #     ###                    #          #     ## ## ######
+##### # #         ## ##       ###                    # ####### ######
+##### #          ### ##       ###                    #  ######   ####
+#####     ###    ##            ####         #  #     ##  ## ### #####
+####### #      # ##        #  ## ##     ##  # #      ##    #    #####
+####          ## ##        #                #                      ##
+######                #     ###           ### ##     ##          ####
+######     # #####                  ###   ####     #              ###
+###### ##### ##### #### ### ### #   ### ###### ### ######   #  ######
+###### ##### ##### #### ### ### ## #### ###### ##########   #  ######
+###### ########### ############ ############## ########### ## #######
+################## ############ ############## ########### ## #######
+#####################################################################
+RANDOMIZE TIMER
+DIM a(70, 20)
+begin:
+CLEAR
+CLS
+FOR l = 1 TO 150
+   x = INT(RND * 59) + 6
+   y = INT(RND * 9) + 6
+   d = INT(RND * 4)
+   a(x, y) = 1
+   SELECT CASE d
+      CASE 0
+         FOR i = 1 TO INT(RND * 5)
+            a(x + i, y) = 1
+            a(x, y - i) = 1
+         NEXT i
+      CASE 1
+         FOR i = 1 TO INT(RND * 5)
+            a(x + i, y) = 1
+            a(x, y + i) = 1
+         NEXT i
+      CASE 2
+         FOR i = 1 TO INT(RND * 5)
+            a(x - i, y) = 1
+            a(x, y - i) = 1
+         NEXT i
+      CASE 3
+         FOR i = 1 TO INT(RND * 5)
+            a(x - i, y) = 1
+            a(x, y + i) = 1
+         NEXT i
+   END SELECT
+NEXT l
+FOR row = 1 TO 19
+   FOR col = 1 TO 69
+      IF a(col, row) = 0 THEN
+         PRINT "#";
+      ELSE
+         PRINT " ";
+      END IF
+   NEXT col
+   PRINT
+NEXT row
+WHILE INKEY$ = ""
+WEND
+GOTO begin
+= Populating The Dungeon Of Items & NPC's - Stuart George [entropy@ihug.com.au]. =
+By Stuart George :: [entropy@ihug.com.au] :: 3may99
+I have to say up front, I have not looked in depth
+(if at all) at how other rogue likes approach this task.
+So my methods are probably not as fast or good as ones
+tried and tested in code like nethack + angband for the
+past N years they have been using it ;)
+Quite often one of the first tasks in a rogue like
+is creating the mazes... Once you have created
+a working maze generation routine you have to fill
+it, both with items, traps, monsters, stairs, etc.
+Kitting out your dungeon can be as hard or as easy
+as you like, but a lot of it has to do with how you
+generated your maze.
+I'll discuss here how I've gone about doing it.
+First I'll discuss how NOT to do it, I saw this example
+only once (in a quite basic "in development" game)...
+The dungeon was hewn from a static 128x128 grid
+and for placement of objects, a random position of
+x=rnd(128), y=rnd(128) was taken for every object
+wanting to be placed on the map, this x.y was then
+tested against the grid to see if it was a floor tile,
+if so was placed, and if not was repeatedly calling for
+random numbers for x.y and testing them all over the grid.
+Needless to say, with lots of objects and a small dungeon, this
+could make the computer test locations for days until it got a
+match...
+That is how NOT to do it, basically its a poor mans algorithm.
+(But as someone pointed out, its easy to do things this way
+and it does indeed work if you maze fills most of the confines
+of your 'grid')
+When I generate the maze, i store in a list all the
+rooms created.  Hallways are just "skinny" rooms in my
+view, so they all get put on the list.
+This list is quite basic, its a linked list and contains
+the x1.y1-x2.y2 and a flag of every object and nothing else.
+the flag is just set when its wider or longer than 1
+(ie flag is set when its not a "hall"), if you have to refer
+to the list often its easier to test a flag than to test
+x2-x1 + y2-y1 for every object..
+When I want to add say, stairs up, i just randomly pick
+an object from my list, then once you have your "room"
+randomly pick an x.y within that room  y=rnd(y2)+y1, x=rnd(x2)+x1
+and place the object. repeat as necessary.
+You can check for overlapping if you wish or simply stack items
+in a list.
+Since hallways outnumber rooms by a great number, its nice to
+not always have everything generated in a hallway, thats why
+the flag is for, so when objects from the list are selected,
+you can give a greater chance to gen something in a room than
+in a hallway...
+You could also store two lists, one for "rooms" and one for "halls".
+My dungeons are created entirely by the RNG, so when i save/load
+a level I only need take note of the RNG seed before creation
+starts, since the same seed produces the same level, the object
+list gets rebuilt and thus you don't have to store that list.
+You _do_ have to save the x.y positions of static things, ala
+traps (moving bear pits?) and stairs. monsters move (for the most
+part) so if they are not in the same spot, you could say
+they wandered about ;), and items, well they got picked
+up and moved and dropped ;).  But these are weak excuses for
+cutting code really... ^_^
+When going from 1 level to another you can dump the object list
+for the same reasons as the load/save given above.
+This is of course, very simple and does not take into account
+someone with a digging wand adding a new corridor to your dungeon
+(since its user created, it wont be created with the RNG seed).
+Of course it would be easy to add the newly created portions
+to a list, stored with the RNG dungeon seed, etc.
+I find this method quite good, its quick and easy to "spawn"
+monsters with this method..
+The one thing I thought I should mention is the fact that my
+"rooms" and "hallways" are not connected. doors are placed
+in between as "connections" but they not connected on creation
+by "touching" each other, and thus doorways don't show up on my
+object list. (good or bad I don't know, but I'm very happy
+with my dun-gen routine, it also just means nothing will
+be placed over the top of a doorway)
+= A Method For Growing Rivers In A Randomly Generated World - Dana Larose [dana@pixelenvy.ca].txt =
+In response to a question on rec.games.roguelike.development, I coded up a demo
+on how one might make randomized rivers that originate in a part of the world
+that hasn't been generated yet.
+The Problem
+You are building a world region by region (as the player explores them), so
+you do not the the layout of the entire planet in advance. How to create long
+rivers that can span into regions that haven't be created yet? I'll present
+here an explanation of how this can be done and provide a demo written in
+Python.
+Summary of Algorithm (Although it's simple enough to almost not qualify as an
+algorithm!)
+Suppose you generate a 20X20 area of the world that looks like this:
+. . . . . . . . ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~          ~ = water
+. . . . . . . . . ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~          . = plains
+. . . . . . . . . . ~ ~ ~ ~ ~ ~ ~ ~ ~ ~          # = trees
+. . . . . . . . . . . ~ ~ ~ ~ ~ ~ ~ ~ ~          ^ = hills/mountains
+. . . . . . . . . . . . ~ ~ ~ ~ ~ ~ ~ ~
+^ . . . . . . . . . . . . ~ ~ ~ ~ ~ ~ ~
+^ ^ . . . . . . . . . . . . ~ ~ ~ ~ ~ ~
+^ ^ ^ . . . . . . . . . . . . ~ ~ ~ ~ ~
+^ ^ ^ ^ . . . . . . . . . . . . ~ ~ ~ ~
+^ ^ ^ ^ ^ . . . # # # . . . . . . ~ ~ ~
+^ ^ ^ ^ ^ . . # # . . . . . . . . . ~ ~
+^ ^ ^ ^ ^ ^ # # # # . . . . . . . . . ~
+^ ^ ^ ^ ^ ^ ^ ^ # # # . . . . . . . . .
+^ ^ ^ ^ ^ ^ ^ ^ ^ # # . . . . . . . . .
+^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . . . . . . . . . .
+^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . . . . . . . . .
+^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . . . . . . . .
+^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . . . . . . .
+^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . . . . . .
+^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . . . . .
+Your world generation algorithm determines this lake/ocean will have a river
+flowing into it. Start drawing a river backwards from the ocean. For my
+simple demo, I used the following stopping condition for the river: If river
+was about to cross from an area of higher elevation to an area of lower
+elevation, terminate the loop. Additionally, I started with a 5% chance of
+terminating the river and each time the drawing loop iterates, I increase that
+by 5%.
+One particular run of my demo made the following map:
+. . . . . . . . ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
+. . . . . . . . . ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
+. . . . . . . . . . ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
+. . . . . . . . . . . ~ ~ ~ ~ ~ ~ ~ ~ ~
+. . . . . . . . . . . . ~ ~ ~ ~ ~ ~ ~ ~
+^ . . . . . . . . . . ~ . ~ ~ ~ ~ ~ ~ ~
+^ ^ . . . . . . . . ~ . . . ~ ~ ~ ~ ~ ~
+^ ^ ^ . . . . . . ~ . . . . . ~ ~ ~ ~ ~
+^ ^ ^ ^ . . . . ~ . . . . . . . ~ ~ ~ ~
+^ ^ ^ ^ ^ . ~ ~ # # # . . . . . . ~ ~ ~
+^ ^ ^ ^ ~ ~ . # # . . . . . . . . . ~ ~
+^ ~ ~ ~ ^ ^ # # # # . . . . . . . . . ~
+~ ^ ^ ^ ^ ^ ^ ^ # # # . . . . . . . . .
+^ ^ ^ ^ ^ ^ ^ ^ ^ # # . . . . . . . . .
+^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . . . . . . . . . .
+^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . . . . . . . . .
+^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . . . . . . . .
+^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . . . . . . .
+^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . . . . . .
+^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . . . . .
+If your river reaches the border of a region, again terminate it. (Note that it
+should also terminate before crossing into region that has already been
+generated, my demo doesn't do this). At this point, you need to store the fact
+that a river has terminated at a border of the region. Python is OOP-enabled,
+so it was quite easy for me to add this information to the region class.
+I stored the instance of the terrain, it's coordinates and the last move the
+drawing algorithm was about to make (so I can continue drawing it in the same
+general direction when it is time to build the next region).
+When the player cross into an previously unexplored region, you will have to
+pass the details of already generated neighbouring regions, providing access to
+their lists of border features. If a neighbour is null, it hasn't been made yet
+and can be ignored. In the demo, when a new region is made, we see that it has
+a neighbour to the east, and that a river terminated at the border (row 12,
+column 0). After the new region is created, we need to draw a river starting at
+(row 12, column 19). Using the same algorithm, we draw until we hit a
+termination condition. In this case, the river started in the hills, so it will
+continue until it hits a border, or is about to cross from the hills (high
+elevation) to the plains (lower elevation).
+A sample run of my demo produce:
+. . . . . . . . . . . . . . . . . . . .
+. . . . . . . . . . . . . . . . . . . .
+. . . . . . . . . . . . . . . . . . . .
+# # # # # # # # . . . . . . . . . . . .
+# . . . . . . . . . . . . . . . . . . .
+# # # # # # # ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^
+# # # . . . . . . . ^ ^ ^ ^ ^ ^ ^ ^ ^ ^
+# # # # # # # . . . . . ^ ^ ^ ^ ^ ^ ^ ^
+# # # # # # . . . . . ^ ^ ^ ^ ^ ^ ^ ^ ^
+# # # # # # # # ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^
+# # . . . . . . . . . . . ^ ^ ^ ^ ^ ^ ^
+# # # # # # # . ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^
+# # # # # # # . . . . . . . ^ ^ ^ ^ ^ ~
+# # . . . . . . ^ ^ ^ ^ ^ * ^ ^ ^ ^ * ^
+# # # # . . . . . . ^ ^ ^ ^ * ^ ^ * ^ ^
+# # # # # # # # . . ^ ^ ^ ^ ^ * * ^ ^ ^
+# # . . . . . . . . . . . ^ ^ ^ ^ ^ ^ ^
+# . . . . . . . . . ^ ^ ^ ^ ^ ^ ^ ^ ^ ^
+. . . . . . . . . . . . ^ ^ ^ ^ ^ ^ ^ ^
+. . . . . . . . ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^
+(The river created is marked with *'s so they stand out a little better).
+Putting them side by side:
+. . . . . . . . . . . . . . . . . . . . . . . . . . . . ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
+. . . . . . . . . . . . . . . . . . . . . . . . . . . . . ~ ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
+. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ~ ~ ~ ~ ~ ~ ~ ~ ~ ~
+# # # # # # # # . . . . . . . . . . . . . . . . . . . . . . . ~ ~ ~ ~ ~ ~ ~ ~ ~
+# . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ~ ~ ~ ~ ~ ~ ~ ~
+# # # # # # # ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . . . . . . . . . . ~ . ~ ~ ~ ~ ~ ~ ~
+# # # . . . . . . . ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . . . . . . . . ~ . . . ~ ~ ~ ~ ~ ~
+# # # # # # # . . . . . ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . . . . . . ~ . . . . . ~ ~ ~ ~ ~
+# # # # # # . . . . . ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . . . . ~ . . . . . . . ~ ~ ~ ~
+# # # # # # # # ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . ~ ~ # # # . . . . . . ~ ~ ~
+# # . . . . . . . . . . . ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ~ ~ . # # . . . . . . . . . ~ ~
+# # # # # # # . ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ~ ~ ~ ^ ^ # # # # . . . . . . . . . ~
+# # # # # # # . . . . . . . ^ ^ ^ ^ ^ ~ ~ ^ ^ ^ ^ ^ ^ ^ # # # . . . . . . . . .
+# # . . . . . . ^ ^ ^ ^ ^ * ^ ^ ^ ^ * ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ # # . . . . . . . . .
+# # # # . . . . . . ^ ^ ^ ^ * ^ ^ * ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . . . . . . . . . .
+# # # # # # # # . . ^ ^ ^ ^ ^ * * ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . . . . . . . . .
+# # . . . . . . . . . . . ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . . . . . . . .
+# . . . . . . . . . ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . . . . . . .
+. . . . . . . . . . . . ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . . . . . .
+. . . . . . . . ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ . . . . .
+A nice, slightly winding river is created in one region, then continued in the
+bordering region when it comes time to generate the neighbour.
+Notes About The Demo
+- The demo was slapped together in about an hour, so please don't judge my
+coding skills on it! It probably has bugs, invalid assumptions, poor coding
+standards/styles, inefficiencies and/or redundant code!
+- There are probably plenty of ways to generate nicer looking rivers, I just
+used a couple of ideas that popped into my head while coding. Mine often
+generates straight lines, which look silly (it took me a couple tries to get a
+nice looking river for this page). But again, that wasn't the point of the demo!
+- The termination condititions could be improved. For instance, if you are
+stopping because you are about to cross into another region, you could back the
+drawing up one square so it doesn't look like the river originates at the border
+of two elevations.
+- It would be neat to look for good likely termination points. Suppose a lake
+was generated at the same (or higher) elevation as the river, it would make a
+good candidate for a termination point. (Hmm - confusing terminology - when I
+speak of termination point, I mean where the algorithm stops drawing, which is
+the origin point for the river in the geographic sense)
+- The demo doesn't generate terrain, I don't know if my roguelike is going to
+have random or fixed wildernesses, I just wanted to offer a solution to the
+question on the newsgroup.
+- The demo is cooked to draw a river that starts at the lake and ends at the
+border of the first region (the cooked functions are labeled as such). See
+previous point.
+- My method only draws rivers from the mouth of the river backwards to the
+spring, but it woulddn't take a great leap to make a version that draws from a
+spring to a terminatition point. Indeed, since you would be drawing into a
+region that has not been determined, you could force the generator to create a
+nice termination point for your river.
+- Written and tested in Python 2.2.1, probably works with Python 2.x.x, might
+even work with Python 1.5.x
+There are three main classes used in the demo:
+Terrain - Represents an individual square of terrain. Uses fields ch (the
+character to display), type (the type of terrain and elevation - integer
+saying how high the terrain is. I used ocean/lake = 0, plains/trees = 1 and
+hills = 2. An interesting idea would be to store a floating point number and
+use that to determine where the river should flow from the geography of the
+land?
+Region - stores information about the section of the world this represents. In
+the demo, this is essentially a collection of Terrain squares and a little
+additional info used in the demo (such as the border features of this region).
+In a full game, this would need to store a fair amount of additional
+information.
+RegionGenerator - builds a region of land. Note that in the demo, the regions
+are cooked and the river in the first region is partially cooked.
+The code is offered without warranty or guarantee as an idea for folks writing
+map generators. If you want to use a substantial part of the code in your game,
+please ask permission. Here is grow_river.py.txt (named so because browsers
+sometimes complain about .py extentions, save it your harddrive and rename it
+grow_river.py before running).
+You can reach me at dana@pixelenvy.ca with questions, suggestions, etc.

Difference between revisions of "User:Duerig"

Revision as of 18:37, 1 May 2008

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

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

Roguelike_Skeleton_Blah_Documentation_Erik_Inge_Bols???_knan_mo.himolde.no_.txt

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

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

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

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

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

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

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

Direct Screen Output.txt

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

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

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

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

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

Redefinable Keyboard Bindings - Stuart George [dfiber@mega-tokyo.com].

How to write a roguelike gameengine - Esa Ilari Vuokko [eivuokko@mbnet.fi].txt

Heap Space Conservation - Steve Segreto [ssegreto@titan.com].

Handing Out Experience - Rick Carson.txt

Allocating Experience and Character Advancement - Matthias E. Giwer [mgiwer@ij.net].

Creating A Player - Brian Bucklew [bbucklew@inteletek.com].

Pretty Pictures - Darren Hebden [rogue@skoardy.demon.co.uk].txt

Object Representation - Sean Middleditch [sean.middleditch@iname.com].

Inventory Abstraction - Kenneth Power [uncle_wiggly@bigfoot.com].

Creating Inventories - Erno Tuomainen [ernomat@evitech.fi].

Equipment Wear and Tear - Michael Heinich [mheinich@yahoo.com].

Fractal Landscapes - Mike Anderson [mike@mikera.net].

=========

=

==

=== CoastApp.java ====

==

Terrain Generator - Mixi Lauronen [mplauron@paju.oulu.fi].txt

Metaballs Dungeon.txt

More Continuous Content - Joseph Swing [JSwing@wport.com].

Creating A Dungeon - Brian Bucklew [bbucklew@inteletek.com].

The Building of Towns - Michael Blackney [michaelblackney@hotmail.com].

Recursive Level Generation - Radomir 'The Sheep' Dopieralski [sheep@venus.wmid.amu.edu.pl]

Finding Explorable Regions - Ross Morgan-Linial [rmorgan@jetcity.com].

Representing the Dungeon - Brian Bucklew [bbucklew@inteletek.com].

Fun with dungeongeneration in QBasic - R.Alan Monroe.txt

Populating The Dungeon Of Items & NPC's - Stuart George [entropy@ihug.com.au].

A Method For Growing Rivers In A Randomly Generated World - Dana Larose [dana@pixelenvy.ca].txt

Navigation menu

Search