Difference between revisions of "User:Duerig"

From RogueBasin
Jump to navigation Jump to search
(Half way through checking map. Map is all that is left)
m (Permission to transfer articles)
 
(10 intermediate revisions by 2 users not shown)
Line 1: Line 1:
Attention! The reason that these articles were not transferred to RogueBasin and are in danger of being lost for good is because the admins could not secure the author's permission for being transferred from the old site to the new one. IF YOU ARE AN AUTHOR: Please let me know on this page that you give your permission. If you do that, I can pull the articles from the archive pages and integrate them into the wiki.
List of authors who have given permission:
  * Steve Segreto (Permission Granted) N.B. My article is extremely dated by now and probably useless to most everybody
List of authors who have not given permission (alphabetical order by first name):
  * Adam Szczepaniak
  * Andrew Collins
  * Brian Bucklew
  * Brian Robinson
  * Christopher J Martens
  * Damian Bentley
  * Dana Larose
  * Darren Hebden
  * Erik_Inge_Bols???_knan_mo.himolde.no
  * Erno Tuomainen
  * Esa Ilari Vuokko
  * Gero Kunter
  * Gwidon S. Naskrent
  * Isaac Kuo
  * Jakub Debski
  * James Burton
  * Jim Babcock
  * Joseph Swing
  * Josh Tippets
  * Judy Wray
  * Jurriaan Kalkman
  * Kenneth Power
  * Kornel Anubis Kisielewicz
  * Matthias E. Giwer
  * Michael Blackney
  * Michael Heinich
  * Mike Anderson
  * Mixi Lauronen
  * Peter Farabaugh
  * R.Alan Monroe
  * Radomir 'The Sheep' Dopieralski
  * Rick Carson
  * Ross Morgan-Linial
  * Sean Middleditch
  * Simon McGregor
  * Steve Segreto
  * Stu George
  * Thomas Gilray
  * Unknown ( Direct Screen Output.txt )
Here is a list of articles from the old roguelikedevelopment.org that I am trying to salvage:
Here is a list of articles from the old roguelikedevelopment.org that I am trying to salvage:


Cannot Find:
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
   * 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
   * Recursive randomized world-map generation Phillip C. Culliton [pcullit@hotmail.com].txt
  * 3D Representation for Roguelike Worlds - Jimmy Babcock [jimmy_b@earthlink.net].txt


TODO:
TODO:
Line 15: Line 54:
   * add a link to name.zip for Random Name Generation Using Regular Expressions
   * add a link to name.zip for Random Name Generation Using Regular Expressions


= Representing Magick Spells - Sean Middleditch [sean.middleditch@iname.com].txt =
Found Articles:
 
   * [[User:Duerig/Archive0]]
This article describes the basics of representing and using Magick Spells in roguelikes.
   * [[User:Duerig/Archive1]]
The general techniques are very similar to those used in my article on Object
   * [[User:Duerig/Archive2]]
representation.
   * [[User:Duerig/Archive3]]
 
   * [[User:Duerig/Archive4]]
For starts, we need a class to hold the information for a specific spell.
   * [[User:Duerig/Archive5]]
 
   * [[User:Duerig/Archive6]]
class Spell {
   * [[User:Duerig/Archive7]]
public:
   * [[User:Duerig/Archive8]]
 
   * [[User:Duerig/Archive9]]
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:
 
                                  *
                                /|\
                                / | \
                              a  b  c
 
--
        while (index < s.length())
        {
            current = s.charAt(index);
            if (Character.isLetter(current))
            {
              b.append(current);
              index++;
            }
--
This sets up a while loop that will run until index is greater
than or equal to the length of the string.  Current is assigned the
character at index and we start figuring what we want to do.  First off,
if current is a letter, we add it to the buffer and increment the index,
then restart the loop.
 
--
            else if (current == '|')
            {
              leaves.add(b);
              b = new StringBuffer();
              index++;
            }
 
--
If current is an or operator, we add the string in our buffer to
the leaves Vector and create a new buffer.  We increment the index and
loop.
 
--
            else if (current == '(')
            {
              int count = index + 1;
              int openParens = 1;
              while (openParens > 0)
              {
                  if (s.charAt(count) == '(')
                  {
                    openParens++;
                  }
                  else if (s.charAt(count) == ')')
                  {
                    openParens--;
                  }
                  count++;
              }
              count--;
              b.append(parse(s.substring(index + 1, count)));
              index = count + 1;
            }
--
Slightly more complex than the previous parts, when we see an open
parentheses, we need to find it's matching closing parentheses.  We can't
just use the first one we find because we want to support nested
parentheses.  Once we know where the parentheses open and close, we take
whats in the parentheses and parse it just as we do the whole string.  The
result of that parsing is added to our current buffer.  We then increment
the index past the close parentheses and loop.
 
--
            else if (Character.isDigit(current))
            {
              int count = index + 1;
           
              if (current != '0')
              {
                  while (  (count < s.length())
                        && (Character.isDigit(s.charAt(count))))
                  {
                    count++;
                  }
--
If we have a number, we want to determine what the number is.
Although I don't know how often people are going to need to use numbers
larger than 9, the support is there for anything an int can handle.  Also,
since we are using '0' as our null character, we have to take special note
of it here.  The while loop above simply counts the number of digits we
have in a row.
 
--
                  Integer exponent;
                  try
                  {
                    exponent = Integer.decode(s.substring(index,count));
                  }
                    catch (NumberFormatException ex)
                    {
                        exponent = new Integer(0);
                    }
--
This is Java's way of converting a String to an int.  Its a little
more complicated than atoi(), but not so bad.
 
--
                  StringBuffer temp = new StringBuffer();
                  for(int i = 0; i < exponent.intValue(); i++)
                  {
                    temp.append(b);
                  }
                  b = temp;
--
Here we simply copy our whole buffer over as many time as
specified by the exponent.  Not that this will affect everything since
either the beginning of the regular expression or since the last or
operator.  This is somewhat of a kludge, but it works if you use
parentheses to segregate exponents.
 
--
              }
              index = count;
            }
        }
--
Finally, we need to set the index equal to count.  If we
encountered a '0', count will be (index + 1), so the '0' is skipped.  If
it was any other number, count will be the place in the expression where
the digits stopped.  The final end brace above closes our while loop.
 
--
        if (leaves.size() == 0)
        {
            return b.toString();
        }
--
If leaves is empty, that means there was no or operator in the
expression.  We simply return the buffer because there is nothing to
choose between.
 
--
        else
        {
            leaves.add(b);
            int whichString = generator.nextInt(leaves.size());
            return (leaves.get(whichString)).toString();
        }
      }
--
If leaves is not empty, we need to choose one of the possible
outcomes of the or operator.  Each possibility should be weighted equally,
but the random number generator in Java is not perfect for small numbers.
However, you will always get correct, if not uniformly distributed names
from it.  Here we add the final string from the buffer, choose a random
index of the Vector leaves, and return that index as the name we've
generated.
There's a little more to the class, but not much.  Just a
constructor and the getName() method which simply calls parse().  You may
want to add the ability to do substitutions before returning the final
name, or you may chose to do them after the return with a special
substitution class.  That should be simple enough to implement that I need
not discuss it here.
 
Filtering
 
Some people may be content to have names like "stink" appear
in their game, but others may not.  Specifically, parents may not
like for their children to be exposed to profanity within a game,
even if it is not used as such.  Fortunately, its relatively simple to
provide a filter in a name generator to prevent these sorts of
names from being created.  Here's some Java pseudocode of how to use the
filter:
 
do
{
  String name = nameGenerator.getName();
} until (!filter.isBad(name));
 
Now, writing the filter is a little more difficult than
using it.  In Java, its still pretty simple.  I'll post the entire
source here minus the actual words being filtered:
 
  import java.util.*;
  class Filter extends Hashtable
  {
      public Filter()
      {
        String[] badWords =
        {/* fill with bad words in lowercase */};
     
        for(int i = 0; i < badWords.length; i++)
        {
            put(badWords[i], new Object());
        }
      }
      public boolean isBad(String s)
      {
        return (get(s.toLowerCase()) != null);
      }
   }
 
This class extends the built in Java Hashtable class.  It
creates an array of Strings which are all profane.  It then puts
them into the hash table.  When you want to check to see if a word
is one you wish to filter, it simply hashes it and sees if the
word exists in the table or not.  You could also employ any
storage/search combination you prefer, but this is so easy to
implement in Java it seemed it was the way to go.
 
Conclusion
 
Hopefully you know a bit more about generating random
names after reading this article.  I have provided source for
everything I have discussed below.  If you have any questions or
comments, feel free to email me at bcr19374@pegasus.cc.ucf.edu.
 
Download Source.
 
= Randomiser Algorithms - Simon McGregor [londonien@hotmail.com]. =
 
Frequently, in a roguelike game, the programmer will want to do various
pseudo-random things. As well as simply generating random numbers, they
may want to have subroutines for picking a random set of things from a
list, shuffling a list, picking an item fairly from a weighted list,
and so on.
 
Although it is easy to come up with "random" algorithms for doing this,
mere randomness and/or intricacy does not guarantee fairness. Moreover,
if the algorithms are used frequently, their efficiency can be an
important issue. The following algorithms are both reasonably efficient
and fair...
 
I have written the algorithms both in a Basic-style pseudocode and in
native C. The C code for these algorithms is amazingly small.
 
The proof-of-fairness for these algorithms is available on request from:
  londonien@hotmail.com
and illustrates the value of applied maths in even quite simple computer
science.
 
N.B. For the following algorithms, the function "random(x)" is assumed
to produce a fair random number between 0 and x-1.
 
BAG-PICK ALGORITHM
 
This algorithm picks a random subset of size "x" from the numbers "0"
to "n-1". It is conceptually equivalent to picking a bunch of things
from a bag without replacement. It is not THE most efficient approach
for a static array, but has the edge because it can be applied to a
linked list instead of numbers, with very little modification.
 
***************
Pseudocode
***************
 
  max:=n;
  remaining:=x;
  current:=0;
  while (remaining > 0)
    if (random(max) < remaining) then
      ADD (current) TO OUTPUT LIST
      remaining:=remaining-1;
    end if
    max:=max-1;
    current:=current+1;
  end while
 
***************
C Code
***************
 
  void BagPick(int *dest, int n, int x)
  {
    int i;
    for(i=0;x>0;i++) {
      if (random(n--) < x) *dest++=x--;
    }
  }
 
SHUFFLE ALGORITHM
 
This algorithm shuffles a list "array" of length "n". Unlike more
complex and seemingly-random algorithms, it is truly random, and
optimally efficient.
 
***************
Pseudocode
***************
 
  for f:=0 to n
    SWAP array[f] WITH array[random(f)];
  end for
 
***************
C Code
***************
 
  void Shuffle(void *array, int n, size_t size)
  // "size" is the size, in chars, of an array element
  {
    int f,g;
    char *temp,*p;
 
    temp=malloc(size);
    p=array;
    for(f=0;f<n;f++) {
      g=random(f);
      memcpy(temp,&p[g*size]);
      memcpy(&p[g*size],&p[f*size]);
      memcpy(&p[f*size],temp);
    }
    free(temp);
  }
 
FOR FURTHER THOUGHT
 
Another useful randomiser technique is to be able to associate a
random seed with a "meaningful" text string, so that randomly generated
entities such as dungeons, levels, planets, NPCs, species and so on can
be given a name which completely specifies their generated
characteristics. This technique will feature heavily in Dimensions, and
hopefully I will find time later to post and comment on suitable
algorithms based on this idea.
 
= ModuloN - Christopher J Martens [CMartens@mail2Canada.com].txt =
 
The Modulo-N Randomization Algorithm
 
Warning: This article does discuss a lot of math, but nothing we didn't sleep
through in elementary school.
 
Wordy Introduction:
 
There is a paradoxical need for randomized, "unpredictable" input generated from
ordered, "predictable" systems. Although both theoretically and practically
impossible, several methods to randomly generate numbers do exist; one such is
the modulo-n pseudo-random algorithm, employed in many facets of computer
science such as public key cryptography and statistical analysis to name a few.
 
The underlying principle of the system is to generate a sequence of numbers with
no discernable pattern. A seed value is provided to the algorithm to establish a
starting point and the algorithm presents a numeric sequence of finite length.
 
This algorithm, or another similar to it, is usually included in software
development environments. The purpose of this article is to shed some light on
the workings of the algorithm.
 
The equation:
 
This method of random numbers is something you've probably worked with already.
However many treat it like a black box, knowing inputs and outputs but not the
actual workings, and up until four months ago, so did I.
 
The basic framework of the theorem is this:
 
X = (Y) MOD (N)
 
Simply put, X will be the remainder after dividing C by N (Y/N).
 
Now, you probably know that the range of values possible for X will be 0 to N-1.
For instance:
 
Y = 21, N = 7 : X = 0
Y = 23, N = 7 : X = 2
Y = 27, N = 7 : X = 6
Y = 28, N = 7 : X = 0
 
Obviously, the afforementioned equation is not really a useful equation. The
actual modulo-n equation is this:
 
NewValue = [ (A * OldValue) + B ] MOD (N)
 
To get this to work, we need four values: A, B, OldValue and N. The old value
you've probably heard of before. It's sometimes called the seed value.
 
This still follows the same principle as the first equation, except that the Y
variable from the first equation changes as numbers are generated
(ie. A * OldValue + B = Y). Let me demonstrate using this equation...
 
Assuming A = 13, B = 3, N = 2^3 = 8
 
We'll need a seed number. I'll pick 6 for now.
 
N = [ ( 13 * 6 ) + 3 ] MOD 8 = 81 MOD 8 = 1
 
Now throw this newly generated number back into the equation as the seed...
 
N = [ ( 13 * 1 ) + 3 ] MOD 8 = 16 MOD 8 = 0
 
And again, doing the same...
 
N = [ ( 13 * 0 ) + 3 ] MOD 8 = 3
N = [ ( 13 * 3 ) + 3 ] MOD 8 = 2
N = [ ( 13 * 2 ) + 3 ] MOD 8 = 5
N = [ ( 13 * 5 ) + 3 ] MOD 8 = 4
N = [ ( 13 * 4 ) + 3 ] MOD 8 = 7
N = [ ( 13 * 7 ) + 3 ] MOD 8 = 6 <= Same as original seed
N = [ ( 13 * 6 ) + 3 ] MOD 8 = 1 <= Notice the beginning of a pattern?
 
 
So the actual sequence of numbers generated by the algorithm is 1, 0, 3, 2, 5,
4, 7, 6, 1, 0, 3, 2, 5, 4, 7, 6 and so on and so forth. These are technically
random.
 
Observations/Discussion:
 
There may be a bit of a detectable sequence (1 to 0, 3 to 2, 5 to 4, 7 to 6),
but in real life when larger numbers are used, it is very difficult to detect
any pattern. Also, it is important to remember how you're using these numbers.
For all the C/C++ goons out there, what do we do once we get a number from the
rand() function? We force it to the range of values we want for the specific
purposes we want these random numbers for.
 
Example code fragment:
 
// Format generated number between Max and Min.
int x = rand() % (Max - Min) + Min;
 
By doing this, we increase the "randomness" of the whole process, because the
chances of getting the exact same number from the generator for the exact same
purpose are pretty low. However, at some point there'll be a pattern setting,
but there are many ways to either get around them or prevent them altogether,
many of which are common knowledge.
 
Additionally, there are a few things I've found out that could be helpful.
Variable A *really* needs to be a prime number, otherwise you might get a value
for A being wholly divisible by N and then that would shorten the sequence
prematurely. This is also the case for B, but the need for this has to be
emphasized. If the previous number was 0 and B / N leaves no remainder then you
will get B MOD N to be 0; which is the exact same as the value before it. In
short, the whole algorithm crashes to a halt and keeps outputting 0 until you
manually provide a new seed.
 
Another interesting thing to notice is that when everything works perfectly, you
will always get N unique sequence steps. That is, if N = 8, you'll get 8
discreet steps before the sequence repeats itself. If this is the case, then the
sequence generated will have to include every possible value from 0 to N-1
before it repeats.
 
It is also beneficial to have N as a power of 2. If N = 2^m, then every number
generated will fit into an allocated space inside memory of 'm' bits. That way,
you can create random numbers that are guaranteed to fit into a specific
variable type, be it a byte (8 bits) a word (16 bits) or a double word (32 bits).
 
Conclusions:
 
I've written a little program for C++ which I've experimented with, try it out
if you're curious. (My apologies to those who do not use C++, although it
should be easy to figure out) It's far from bulletproof, however, especially if
you enter character input.
 
#include <iostream.h>
 
void main( void )
{
int A, B, N, seed;
 
// Display cheesy intro
cout << "Modulo-N Algorithm Demonstration:\n"
<< "Please enter required parameters\n";
 
// Get intro values
cout << "A = ";
cin >> A;
 
cout << "B = ";
cin >> B;
 
cout << "N = ";
cin >> N;
 
cout << "Seed value = ";
cin >> seed;
 
// Generate random numbers
cout << "Generating numbers...\n\n";
 
int count = 0;
 
while( count <= N )
{
// Generate the number
seed = ( ( A * seed ) + B ) % N;
 
// Display the number
cout << seed << ", " << flush;
 
// Advance the count
count++;
}
 
cout << "Done!" << endl;
 
return;
 
}
 
Anyways, I'd better quit. Hopefully, this satifies some curiosity as to why and
how the random number generator inside a computer works and maybe give some
insight into how to use it effectively. Please email me and let me know if
something didn't make sense and/or what I could do to make this little article
clearer and more coherent.
 
Cheers,
 
Chris Martens
CMartens@mail2canada.com
 
= Random Names - Gero Kunter [kunter@mathematik.uni-marburg.de]. =
 
One of the typical features of a roguelike game is that as many features as
possible have random appearances. So it may seem a logical conclusion to add
random names to the inhabitants of your virtual world as well.
 
However, you should consider to which extend you want to give names to NPCs.
Is it really necessary to have a name for every single orc, every single rat
and every single bandit? But then again, powerful creatures, such as dragons,
certainly deserve a well-sounding name. And of course, every shopkeepers would
dishonour their profession without one. I think it is a good idea to have
names for important and unique characters - people who give quests to the
player, or potential companions. But your opinion may vary, of course.
 
But how do you generate random names?
 
You can employ powerful algorithms which will use a given set of data strings
to generate random strings that are similar to the initial data. But there are
simpler ways. In my project, I used two approaches, which I will outline
below.
 
 
    Combinations of given first and surnames
 
This method is quite simple. It uses three seperate lists with strings: one
with male and one with female first names, and one with surnames. The
following pseudo-code algorithm retrieves a new, random name.
 
    switch Gender {
        case male  : S = male_firstnames [random]
        case female : S = female_firstnames [random]
    }
    RandomName = S + " " + surnames [random]
 
If you need "Nordic" names like "Kunt Barnesson" or "Gudrun   
Ingridsdotir"., you could use a variation of this:
 
    switch Gender {
        case male  : S = male_names [random] + " " + male_names [random] +
                        "sson"
        case female : S = female_names [random] + " " + female_names       
                        [random] + "sdotir"
    }
   
You could add a control structure in which you keep track of the names that
have already been generated, to prevent the algorithm from returning the same
name twice:
 
    for i = 0 to 15 {
        for j = 0 to 15 {
            combination_given [i] [j] [male] = FALSE
            combination_given [i] [j] [female] = FALSE
        }
    }
 
    [...]
 
    repeat
        i = random
        j = random
    until combination_given [i] [j] [Gender] = FALSE
    combination_given [i] [j] [Gender] = TRUE
 
    switch Gender {
        case male  : S = male_firstnames [i]
        case female : S   = female_firstnames [i]
    }
    RandomName = S + " " + surnames [j]
 
In a proper program, you would probably use a bit-coded flags to check which
combinations have been generated.
 
 
    Completely random names
 
The second algorithm described here doesn't use combinations of given names,
but generates them completely from scratch. The idea is to put together
combinations of vowels and consonants to generate words that might be names.
By using specific sets of sounds, you can control the "flavour" of the names,
and you can combine it with gender endings.
 
First, you should define the vowel and consonant set:
 
    vowels = "aeiou"
    consonants = "bcdfghjklmnpqrstvwxyz"
 
Then, you generate a word, alternating between random vowels and random
consonants.:
 
    S = ""
    for i = 1 to random {
        S = S + vowels [random] + consonants [random]
    }
    switch Gender {
        case male  : S = S + 'us'
        case female : S = S + 'a'
    }
 
If you want to add a surname, just repeat the above snippet without the gender
ending.
 
In this crude version, the algorithm will return rather ugly, artificially
sounding names. You could alter this by changing the probability for some
sounds, by using different vowel and consonant sets:
 
    vowels = "aaaeeeiiou"
    consonants = "bbbcdddffgghjkllmmmnnnppqrrssstttvwxyz"
 
These sets would make "a" and "e" three times and "i" two times as likely as
"o" and "u", with the corresponding values for the consonants. You could also
completely leave out some sounds.
 
The method above always returns names beginning with a vowel and ending in a
consonant (forgetting about the gender endings for now). To change this, you
could add after the first line a structure like the following:
 
    switch random {
        case 1  : S = consonants [random]
        case 2  : { do nothing }
    }
 
If properly implemented, the algorithm will give quite good - and sometimes
even funny - names. I'll give you a list of random samples of names my
implementation has come up with:
 
    Salopatan Dolot
    Lucara Vanibo
    Xyxelan Ubem
    Irabon Seboribal
    Abasixi Abubodul
    Sasipabi Itatop
    Latanybor Ocifil
    Obi Onu
    Laso Pubyl
 
But my absolute favourite was Eri Fuzibidusi!
 
 
    Titles
 
For a fantasy world, you may also want to add impressive titles. For example,
your player might meet a veteran soldier in some tavern. It would be nice if
he would be called something like "Olaran Ozatar, the Ogreslayer", wouldn't
it?
 
This can be easily done, with a modification of the first method described
above. Let's define a list of suffixes:
 
    suffixes = ("slayer", "hunter", "friend", "hater", "seeker")
 
Assuming that you have your creature names stored in a similar list, you can
simply generate a title by
 
    title = "the " + creaturenames [random] + suffixes [random]
 
 
If you combine the methods as described here, it shouldn't be a problem to
come up with as many exciting names as your roguelike game will ever ask for!
 
= Time Tracking - Gwidon S. Naskrent [naskrent@skrzynka.pl].txt =
 
When creating a roguelike, more often than not you are presented with
the challenging task of devising an interesting world in which the
game takes place. And, naturally, most beings in most worlds, even if
they are immortal, need to keep the flow of time for personal,
governmental (taxes) and religious (feasts) purposes. This article
deals with issues commonly encountered upon adding a time dimension to
your game.
 
Most assuredly, you are not bound to design your time according to the
traditional sense, with seconds, minutes and hours. But for the
simplicity of the discussion, we will assume that you operate in a
framework that consists of time units that everyone knows - seconds
that make minutes, minutes that make hours, hours that make days and
days that make years. We'll also assume that typical Earth standards
are in force, with the exception that a year is always 365 days
(not 365.24624 as in reality).
 
After determining how are your time units structured, it is important
to decide what within the game will you use to represent it. The
simplest approach is to assign a different variable to each of the
various units; a signed char (byte) to seconds, minutes and hours, and
an unsigned int to days. This simple solution has, however, a
significant drawback: you waste storage space. It's certainly not a
big waste, but helps to forget about memory issues and develop bad
programming habits.
 
Therefore, a more efficient way to approach our problem will be the
introduction of *scalar time*. Scalar time is an uniform figure; it
represents the amount of basic time units - in our case seconds - that
have elapsed from a specific point in time. This point can be purely
arbitrary, but should be antecedent to the start of your adventure, so
as to avoid 'negative time', if possible. The variable type for scalar
time should be a 32-bit int (it is a good idea to make it a signed
int, to avoid problems with negative time). 32 bits are, surprisingly
enough, sufficient to cover a period exceeding 68 Earth years,
probably more than the longest lifetime of a typical adventurer in
danger-ridden dungeons. If you still think it's not enough, you can
make the variable unsigned and double the available period. You can
even increase the variable length to 64 bits, and it will cover (gasp)
some 292 trillion years. Now THAT should be enough even if your game
starts at Big Bang...
 
 
Basic Timekeeping
 
We'll start the coding part by defining some basic quantities:
 
#define MINUTE 60
#define HOUR (60 * MINUTE)
#define DAY (24 * HOUR)
#define YEAR (365 * DAY)
 
These will be helpful in adding or substracting larger amounts of time
to/from our scalar clock.
 
Next, we must write a function that will do for us the dirty work of
calculating actual time representation. Programmers call that
'breaking down' of the scalar value. Assuming the time units are
always of equal length, we can achieve the task very easily without
resorting to floating point arithmetics.
 
Here's a function I used in GSNband (slightly changed)
 
int break_scalar_time (int what)
{
switch (what)
{
case SEC:
    return (sc_time % MINUTE);
case MINUTE:
    return ((sc_time / MINUTE) % 60);
case HOUR:
    return ((sc_time / HOUR) % 24);
case DAY:
    return ((sc_time / DAY) % 365);
case YEAR:
    return (sc_time / YEAR);
default:
return (0);
}
}    
 
(sc_time is my 32-bit time variable; SEC, MINUTE etc. are #defined modes
the function is called with; they may be any value you want).
 
In short, to calculate the remainder corresponding to any unit, we first
divide the scalar time by the amount of base units correspoding to that
unit (note that in the first case sc_time is equivalent to sc_time / 1),
and then take the modulus of it and the amount of units it takes to fill
the next higher unit. The last case does not include the modulus, since
there is no higher unit that a year, and we immediately know how many
years have passed on our clock.
 
This is a rather unoptimised function that will not work well in a
compiling environement that generates lots of extra code for each
function call. It that case, it is better to rewrite the function header
using pointers, like this:
 
int break_scalar_time (int *sec, int *min, int *hour, int *day, int *year)
 
And then call it after having initialized the variables:
 
int sec, min, hour, day, year;
break_scalar_time (&sec, &min, &hour, &day, &year);
 
Yet another solution would be a structure to keep the information
returned, or even better an union (since all the fields are of equal
length).
 
 
Months and Weeks
 
The next thing you want is a calendar. Unless, of course, the inhabitants
of your world customarily refer to the likes of 'day 164 of the year'.
For a calendar, you'll need months and perhaps weeks (if each months
contains an equal number of weeks).
 
If you wanted to emulate the Gregorian calendar (without a leap day),
your best bet would be to make two arrays like this:
 
char *month_names[12] =
{
  "January", "February" ...
}
 
int month_table[12] = /* No. of first day of each month in a year (0-364) */
{ 
  0, 31, 59 ...
};
 
(we're counting from 0 to be in common with the values break_scalar_time()
returns)
 
And then we can calculate the month and day of month like this (with the result
in out_str):
 
int day, month, i, j;
int year_day = break_scalar_time(DAY);
char *p;
char *out_str;
 
for (i=0; i <= 12; i++)
{
if (year_day >= month_table[i])
  {
      month = i;
      day = year_day - month_table[i] + 1;
     
      /* Take account of annoying English */
      p = "th";
      j = day % 10;
      if ((day / 10) == 1) /* nothing */;
      else if (j == 1) p = "st";
      else if (j == 2) p = "nd";
      else if (j == 3) p = "rd";
 
      (void)sprintf (out_str, "%d%s day of %s", day, p, month_names[i]);
    }
}
 
 
What To Do With Time?
 
After we've written our timekeeping routines, we must consider how
much time will elapse while the player is doing something, IOW, how
fast will the game time progress. If you game employs large wilderness
areas, you will probably want to hasten time flow while the player is
there. OTOH, in a dungeon settings time should pass more slowly.
 
First, define the area of the basic grid of your dungeon, if you
haven't already. For example, in Angband this is 10 feet (somewhat
over three metres). How fast can you expect the player to cover a
distance of ten feet, moving at a somewhat cautious pace? What about
combat - how long does a blow take? (I based time elapsed between blows
on dexterity and weapon weight.) Do monsters act in a separate time
piece or does time not move while they have a turn? How fast do you use
magical items? Change levels? Eat something? (think about weight/volume)
Etc. etc. Providing for all actions the player may undertake is vital
if you want the time flow to correspond, at least vaguely, to what
you've been doing.
 
 
Some other ideas employing the concept of (recurring) time:
 
- Shops that are open 7/11 or on certain weekdays
- NPCs that can be had only at specific hours (otherwise they sleep,
  work, wander away etc.)
- Quests given may be restricted to a deadline
- Artifacts that activate a set number of times per day (or, if that's
  too sparse, per hour). Same goes for recharging time.
- Your character may have to spend a few hours, or even days, to learn
  new spells at a guild.
- Article prices fluctuate over time (probably in a random way, unless
  you have an economy model handy. :)
- Delayed magical effects, like a retarded fireball or a time
  bomb/grenade (the concept of delayed function calls probably merits
  its own article)
 
Not to mention time travel...
 
Any questions, corrections or notes? Mail naskrent@artemida.amu.edu.pl
 
------
This article is (c) 2000 by Gwidon S. Naskrent. Any further copying,
publication or revisal is subject to the explicit permission of the
author, except when the copying or revisal occurs in the context of your
viewing this page in a web browser.
------
 
= Sureal Time - Damian Bentley [Damian.Bentley@dsto.defence.gov.au]. =
 
COPYRIGHT AND LICENSE
The Sureal Time algorithm is a part of Interhack. Interhack is copyright (c) 1996-
1999 by Damian Bentley. Please contact bendchon@mehta.anu.edu.au for a copy
of the license. Basically feel free to copy and pass this document on - Sureal Time is
something that anyone making a roguelike game can use.
 
INTRODUCTION
This document describes the Sureal Time algorithm. What is it, and why was it
developed? There is a group of games available today referred to as roguelike games. They
consist of a set of levels (in most cases, dungeons), with a player running around killing
monsters, performing tasks, and in general having a good time. In many cases they are text
based, and almost all are single player.
With single player roguelike games, movement is usually turn based. In other
words, the player makes a move, and then all the monsters make their moves. In the
development of a multi player version of a roguelike game this becomes a problem as will
be discussed later.
One solution to this problem is described here. Sureal Time is the combination of
real time movement and turn based movement. It was developed by many people who have
worked on Interhack, with each change or idea adding to the advantages of the algorithm.
Feedback on Sureal Time is appreciated, including ways in which to improve this
document, or questions that have not been answered by this document.
 
 
THE PROBLEM
As it turns out, the problem is quite simple. But first we shall start with current
methods in single player roguelike games.
With a single player making moves, it is quite easy to create a simple loop where
the player makes a move until the die, quit or save. Then everything else that happens in the
game happens. That is: monsters move, checks will be made to make sure the player is
alive, and so on. Given that some roguelike games require some thought at some stages (oh
heck I am almost dead, what can I do), this is good because a player can stop and think for
as long as they want before making a move.
However when there are several players, problems crop up. If two players are in
the same room, what happens to movement? Does one player make a move, then the other
player? Can both players move at any time they want? If a player has a fast connection, do
they move faster? What happens to players that have intrinsic speed? All these problems
need to be solved in a way that is fair to players.
In addition to the problem described above, there are other aspects to be looked at.
For instance, what happens when a player looses a connection, and how do monsters now
attack players? One of the most important parts of the Sureal Time algorithm is in handling
events when a players keyboard action lags behind. What does a player do if a move is
forced in Sureal Time?
So the problem is this: When there are two or more players in close proximity to
each other, how should movement occur?
 
 
POSSIBLE SOLUTIONS
The first and most obvious solution to the problem is to use real time. Each player
has a certain amount of time to make a move before all the monsters and other events
occur. It does not matter if the player has a fast or slow connection. It does not matter home
many players are in the game. All players are placed on the same level of game play.
Real time has one major drawback: A player can not stop and think about what
move to make next. If a player wishes to spend a minute looking through their inventory to
see what they can drop, they are still under the influence of the real time - they could be
attacked at any point in time.
Another alternative is fully turn-based movement. If there are three players A, B
and C, player A makes a move, then player B, and finally player C. This repeats over and
over again. This allows players to stop and think about their next move. There is one very
obvious problem with this solution. If player B stops and looks through their inventory,
player C and player A, are kept waiting for possibly long periods of time.
Both real time and turn-based movement have their advantages. Real time allows
the game to flow on no matter what is happening. Turn based allows players to stop and
think about how the next move should be made. So why not combine both of these
solutions to form what shall be called Sureal Time. Essentially Sureal Time is like adding a
real-time time limit onto turn based movement.
 
 
SUREAL TIME
So now for the gory details of how to actually make Sureal Time work. First we
need to look at players that are grouped, and isolated players. If a player is on a level with
no other players, there is no need to use anything other than turn-based movement. The
simple turn based movement is sufficient to cover this case, as it allows a player to play at
their own pace.
If there are two players on a level, it is more likely that they will need some sort of
movement control. When and where does this take place? If one player is on one side of the
level, and the other player is on the other side of the level, they are not going to interact
with each other much. So even though two players are on the same level, they may not need
to have movement control.
When is movement control needed? As two players get closer and closer, their
actions are going to start to effect each other. A player that zaps a wand or casts a spell
might effect the other player. So if we determine the largest area of affect for most events a
player can cause, a boundary is formed. If this boundary is 16 units, when a player is within
16 units to another player, both players now have some form of movement control. When
two players are further apart than this, they live in their own little turn-based world.
Now lets consider three players: A, B and C. If player A is within 16 units of
player B, and player B is within 16 units of player C, but player A and player C are outside
the 16 unit range, what happens? Simply all three players come under the same movement
control. This is a simple case.
Next, consider four players: A, B, C and D. What if player A and player B are
together, and player C and player D are together. However these two groups of players are
not within the same 16 units. It would not be fair to place all four players in the same
movement control, so two different "forms" of movement control are used.
Now we can bring this al together into a simple set of two rules:
 
Rule 1) A player that is outside a radius of 16 units of all other players on the same level is
placed in a turn based movement.
Rule 2) Players or groups of players that are within 16 units of another player or group of
players are placed in the same group. These groups are "controlled movement" groups.
 
The next aspect of Sureal Time is what happens to players that have movement
control? First of all, if no players in the controlled group move, nothing happens. This
means that players could talk to each other to determine what should happen next. Players
would be able to check their inventory for a particular item.
 
Rule 3) When groups are in controlled movement, if no players move, then no turns are
made in the game.
 
When a player makes a move, what determines how and when other players
move? The first part in answer to this question is related to the speed of the connection a
player has. A player with a fast connection would be able to make moves faster. A player
with a slow connection would make fewer moves. In addition to this aspect, players can
sometimes be "faster" in the game: intrinsic speed.
When several players are connected to a machine, the speed of a connection can be
obtained. Obviously the slowest connection is the best one to select for the speed of a group
of players, because it makes all movement fair on all players. If a player has an intrinsic
speed, all other players' base connection speed is modified to reflect this.
 
Rule 4) All players have a base connection speed. In a group of players, the slowest
connection speed is selected as the timeout basis for movement.
Rule 5) The base connection speed is only ever increased.
Rule 6) A player with an intrinsic of speed modifies the base connection speed of all other
players in a group.
 
So what happens if a player does not move at all, and another player close to them
moves? In this case the player that does not move has a certain amount of time to move
after the other player has moved. Once this time has ended, they will be forced to move.
This introduces a whole new problem, as to what moves are made when a player is forced
to move.
The moves that are forced by the computer are usually "intelligent". For example,
a player that is in combat will remain in combat unless they are badly injured or in need of
food badly. These rules are expanded in detail later. Once a player that is being forced to
move, and has made more than thirty moves, they are automatically saved.
In addition there is also the problem of a player that has lost their connection and
then enters into Sureal Time. If it is know that a player has lost their connection they are
automatically saved. Otherwise the player makes forced moves until they have exceeded
the thirty moves limit, and are saved by default.
 
Rule 7) After a player in a group makes a move, all other players must move within a
certain time.
Rule 8) Players that do no move within the time limit are forced to move, with the
computer making an intelligent move, such as attacking the last attacked monster (see
forced move rules).
Rule 9) If a player is forced to move more than 30 times in a row, they are automatically
saved.
Rule 10) If a player looses their connection, they are automatically saved.
Rule 11) A player can enter into Sureal Time even if they are not moving.
 
In some cases a lag in the connection between the client and server could cause a
players key-press to arrive at the server after a forced move has occurred. If the key-press
arrives within a certain amount of time after the forced move, it is ignored. This ignore time
can be set by the player.
 
Rule 12) After a forced move, all key-presses from the player forced to move will be
ignored for an amount of time specified by the user.
 
Additionally there is also a reaction time involved. This is considered a "fair" time
by which most players will see another player move, think of an appropriate move, and
make the move. This reaction time makes a player being forced to move slower than a
player moving by its self. Due to this slower speed, a player being forced to move has a
tally for forced moves to be made. All moves on this tally will be made unless the player
being forced to move presses a key to move.
 
Rule 13) A reaction time will be added to the time before a player is forced to move. The
reaction time should allow for a player to see a move, think of a move, and make it.
Rule 14) For every move that forces a move on another player, the player that is forced to
move will have a tally kept. This tally will be reduced every time the player is forced to
move. When it reaches zero no more forced moves will be made.
Rule 15) A player that makes a move will reduce their forced move tally to zero.
 
That appears to be most of the main parts of Sureal Time. There are some
additional problems that do begin to appear. For instance, what happens with monsters no
there is more than one player? As said earlier, monster AI has to be much better than
before, and able to cope with the problem where they might have three of four players
attacking them at once.
The solution is fairly simple. Every monster is "attached" to the monster that is
closest to them. In the case where two players are of equal distance, one of those players is
selected at random. Some people consider this to be unfair for the monster: If two players
are close (but not next to) a monster, both could attack it. However if you consider both
these players would more than likely be in Sureal Time, the monster would receive at least
as many moves as a forced move player would.
As two or more players get closer to a monster, it will become "unfair" for the monster.
Monster may need to be harder to kill, or attack in a group. This aspect of the game design
is left to the designer to decide. A combination of more monsters, monsters that attack in a
group, and smarter monsters is recommended.
 
Rule 16) Every monster is attached to the player they are closest to.
Rule 17) When the player a monster is attached to makes a move, the monster makes a
move.
 
These 17 rules are a fairly good summery of Sureal Time. In addition to these
rules, an appendix at the end includes a set of rules recommended for forced moves. It
seems fairly simple, however putting these rules into practice is tricky, as will be seen in
the example source code.
 
 
 
EXAMPLE SOURCE CODE
Before providing sources that implement Sureal Time, there are a few things to
say. To start with, this code only shows how the movement aspect of Sureal Time works.
Aspects such as the monster movement are left out. In addition, rule 12 of Sureal Time (key
presses ignored for a certain time) has not been delt with. This is viewed as a small addition
to the source code - something has to be left out to challenge people.
Writing Sureal Time code is not something to be undertaken lightly. The original
version of the source code was written in Java, and did not use millisecond timers. The
second version was in c/c++ and had a few bugs, and found a few problems in the original
implementation. What is provided here is the third version of Sureal Time. All up
development took about 20 hours.
Most of the source code is documented, however the algorithm basically follows
along the following lines:
 
1. Continue looping until input is received (from the keyboard). Simulates incoming data
from players. (This looping should be based on a sleep loop. The next event to occur is set
as the length of time to sleep. If no events are selected, sleep continuously until an input is
received).
2. If the key-press is 'Q' quite the program.
3. If the key-press is for a player, store the keypress (the player is no longer forced to
move).
4. If the sleep time has ended, check for forced moves. If there are forced moves, make
them.
5. If the sleep time has ended, make moves, and update the details of players. If other
players are on the timer that a player has just moved on, set the forced move timer for each
player.
 
The first file is the Sureal Time header file "sureal.h". Cut and paste this to a file.
The second file is "sureal.c" containing the main source for the algorithm. Again cut and
paste into a file. Compile this code with your preferred compiler: "cc -o sureal sureal.c"
Once this has been done, run the program with "sureal". When running, press 'Q'
and enter to quit. In the configuration below, press '2' then enter. This simulates a move by
player 2. There are three players in this example: 0, 1 and 2. 0 and 1 are on the same timer.
If you enter '0', player 1 will eventually be forced to move. To see more of what is
happening, recompile the source code: "cc -DDEBUG -o sureal sureal.c".
 
Now for a few quick hints and tips on how to modify the source code. First of all,
in most cases you should only need to modify the header file "sureal.h". NPLAYERS is the
number of players in the "game". If you increase this, do not forget to add another element
to the array of players created just below the NPLAYERS define. For each player created,
the first number is the id / timer the player is on. The last two numbers are the
seconds:milliseconds for the players timeout.
LEADWAY is what has been called in this document the "reaction time". The
greater this value, the longer period of time the player has to respond to a move made by
another player. A side effect of this is if a player is forced to move, it will take longer
before the forced move is made if LEADWAY is increased. MAXFORCED specifies the
number of moves before a player would be forced to quit. In the code below this has been
set to 10 so as to speed the results up.
The CSureal class is where all the important timers and numbers are kept track of.
Refer to the comments in the header file as to what each of these variables are. For most of
the rest of the source code in "sureal.c" please refer to the comments. It looks complicated
mainly because of the need for milli second timing.
The only thing to really take note of in the actual source code is the select() call
from the main function. This call has been used for two purposes. Firstly it allows
millisecond timing. Secondly, it can be combined with a socket setup such that connections
and data from the outside world are received here. Essentially by pressing a key the user is
simulating incoming data from a player.
My final comment is this: Do not just look at the sources. Try it out to see how it
works. Most likely some of you will have trouble of some sort. Please contact
bendchon@mehta.anu.edu.au and report any problems or bugs so this document
can be kept up to date and others have fewer problems.
 
-------------------------------------------------------------
#ifndef _sureal_h_
#define _sureal_h_
 
#include <sys/time.h>
#include <unistd.h>
 
// Redefine a few of the timer functions
#ifdef timerisset
#undef timerisset
#endif
#ifdef timercmp
#undef timercmp
#endif
#ifdef timerclear
#undef timerclear
#endif
 
#define timerisset(tvp)\
((tvp).tv_sec || (tvp).tv_usec)
#define timercmp(tvp, uvp, cmp)\
((tvp).tv_sec cmp (uvp).tv_sec ||\
(tvp).tv_sec == (uvp).tv_sec &&\
(tvp).tv_usec cmp (uvp).tv_usec)
#define timerclear(tvp)\
((tvp)->tv_sec = (tvp)->tv_usec = 0)
 
// Add a few timer functions
#define timershow(tvp)\
(tvp).tv_sec << "-" << (tvp).tv_usec
#define timeradd(tvp, uvp)\
{(tvp)->tv_sec += (uvp).tv_sec;\
(tvp)->tv_usec += (uvp).tv_usec;\
if ((tvp)->tv_usec > 1000000) {\
    (tvp)->tv_usec -= 1000000;\
    ((tvp)->tv_sec)++; }; }
#define timersub(tvp, uvp)\
{(tvp)->tv_sec -= (uvp).tv_sec;\
(tvp)->tv_usec -= (uvp).tv_usec;\
if ((tvp)->tv_usec < 0) {\
    (tvp)->tv_usec += 1000000;\
    ((tvp)->tv_sec)--; }; }
 
typedef struct timeval Timeval;
 
class CSureal {
public:
    int key;            // == 0 when no key has been pressed
    int STTimer;        // Timer player is associated with
    Timeval STTimeout;  // Timeout value (connection speed)
    Timeval STNext;    // When the next move can be made
    Timeval STForced;  // When the player is forced to move
    int STForcedRemain; // Forced moves yet to be made
    int STnForced;      // Number of contiguous forced moves
    CSureal(int a, Timeval b) {
        key = 0; STTimer = a; STTimeout = b;
        STnForced = 0; STForcedRemain = 0;
        timerclear(&STNext); timerclear(&STForced); };
    CSureal(int a, long b, long c) {
        key = 0; STTimer = a;
        STTimeout.tv_sec = b; STTimeout.tv_usec = c;
        timerclear(&STNext); timerclear(&STForced);
        STnForced = 0; STForcedRemain = 0; };
};
 
// This is just a list of sureal time class for simulation
#define NPLAYERS 3
CSureal list[NPLAYERS] = {
    CSureal(1, 2, 0),
    CSureal(1, 3, 0),
    CSureal(2, 4, 0)
};
 
Timeval LEADWAY = {0, 500000};
#define MAXFORCED 10
 
// These are the functions for use in sureal time
Timeval * sleepTime();
void keyPressed(int, int);
void forcedMoves();
void makeMoves();
 
#endif
 
 
-------------------------------------------------------------
#include <sys/types.h>
#include <sys/time.h>
#include <iostream.h>
#include <unistd.h>
#include <stdlib.h>
#include <time.h>
 
#include "sureal.h"
 
int main() {
    srand(time(NULL));
    while (1) {
        // Sleep until the next action happens
#ifdef DEBUG
        cout << "Sleeping\n";
#endif
        fd_set rfds; FD_ZERO(&rfds); FD_SET(0, &rfds);
        int retval;
        retval = select(1, &rfds, NULL, NULL, sleepTime());
#ifdef DEBUG
        cout << "Awake\n";
#endif
 
        // Deal with any key presses
        if (retval > 0) {
            int c;
            do {
                c = cin.get();
                if (c == 'Q') return 0;
                if (c >= '0' && c <= ('0'+NPLAYERS-1))
                    keyPressed(c-'0',65);
            } while (c != 10);
        }
 
        // Check for forced moves
        forcedMoves();
 
        // Make other moves
        makeMoves();
    }
    return 0;
}
 
// sleepTime returns minimum time until next expected action
// it returns NULL when no action is expected
Timeval st;
Timeval * sleepTime() {
    Timeval zt; timerclear(&zt);
    Timeval ct; gettimeofday(&ct, NULL);
    int stSet = 0;
    timerclear(&st);
 
    for (register int i = 0; i < NPLAYERS; i++) {
        if (timercmp(list[i].STNext, ct, >) &&
          (timercmp(list[i].STNext, st, <) || stSet == 0)) {
          st = list[i].STNext;
          stSet = 1;
        }
        if (timercmp(list[i].STForced, ct, >) &&
          (timercmp(list[i].STForced, st, <)
            || stSet == 0)) {
          st = list[i].STForced;
          stSet = 1;
        }
    }
 
    timersub(&st, ct);
#ifdef DEBUG
    cout << "Sleeping for " << timershow(st) << endl;
#endif
    if (timercmp(st, zt, <))
        return NULL;
    return &st;
}
 
// Player p has pressed key
void keyPressed(int p, int k) {
    // if player already pressed a key, ignore this key press
    if (list[p].key != 0) return;
    // The player is no longer forced to move
    timerclear(&(list[p].STForced));
    // Store the keypress
    list[p].key = k;
    // Reset the contiguous count of forced moves
    list[p].STnForced = 0;
    // Reset the remaining forced moves to be made
    list[p].STForcedRemain = 0;
    Timeval ct; gettimeofday(&ct, NULL);
    cout << "Player " << p << " pressed key "
        << timershow(ct) << endl;
}
 
// Force a player to move
void forcedMoves() {
    Timeval ct; gettimeofday(&ct, NULL);
    Timeval zt; timerclear(&zt);
    for (register int i = 0; i < NPLAYERS; i++)
        if (timercmp(list[i].STForced, ct, <) &&
            timercmp(list[i].STForced, zt, !=)) {
            // The player is no longer forced to make a move
            timerclear(&(list[i].STForced));
            // Player can move after their timeout finishes
            timerclear(&(list[i].STNext));
            timeradd(&(list[i].STNext), ct);
            if (list[i].STTimer != i)
                timeradd(&(list[i].STNext),
(list[list[i].STTimer].STTimeout))
            else
                for (register j = 0; j < NPLAYERS; j++)
                    if (j != i && list[j].STTimer == i) {
                        timeradd(&(list[i].STNext),
(list[list[i].STTimer].STTimeout))
                        break;
                    }
 
            // Add one to count of contiguous forced moves
            // If player more than MAXFORCED moves, they quit
            if (list[i].STnForced++ > MAXFORCED)
                cout << "Player " << I
                    << " now forced to quit\n";
 
            // Make sure no other forced moves to be made
            cout << "Player " << i << " forced at  "
                << timershow(ct) << endl;
            list[i].STForcedRemain--;
            if (list[i].STForcedRemain < 0)
                list[i].STForcedRemain = 0;
            if (list[i].STForcedRemain > 0) {
                Timeval ft; gettimeofday(&ft, NULL);
                timeradd(&ft,
list[list[i].STTimer].STTimeout);
                timeradd(&ft, LEADWAY);
                list[i].STForced = ft;
#ifdef DEBUG
                cout << "Setting forced timer again for "
                    << I << " to " << timershow(ft) << endl;
#endif
            }
        }
}
 
// Make moves if player has pressed key and timeout finished
void makeMoves() {
    Timeval ct; gettimeofday(&ct, NULL);
    Timeval zt; timerclear(&zt);
    for (register int i = 0; i < NPLAYERS; i++)
        if (list[i].key != 0
            && timercmp(list[i].STNext, ct, <=)) {
            // The player is no longer forced to make a move
            timerclear(&(list[i].STForced));
            // Player can move after their timeout finishes
            timerclear(&(list[i].STNext));
            timeradd(&(list[i].STNext), ct);
            if (list[i].STTimer != i)
                timeradd(&(list[i].STNext),
(list[list[i].STTimer].STTimeout))
            else
                for (register j = 0; j < NPLAYERS; j++)
                    if (j != i && list[j].STTimer == i) {
                        timeradd(&(list[i].STNext),
(list[list[i].STTimer].STTimeout))
                        break;
                    }
            cout << "Player " << i << " moved at   "
                << timershow(ct) << endl;
            list[i].key = 0;
 
            // If other players on our timer, force them to
            // move in the near future
            for (register int j = 0; j < NPLAYERS; j++)
                if (j != I &&
                    list[j].STTimer == list[i].STTimer &&
                    list[j].key == 0 &&
                    timercmp(list[j].STNext, ct, <)) {
                        if (list[j].STForcedRemain < 1) {
                            Timeval ft; gettimeofday(&ft,
NULL);
                            timeradd(&ft,
list[list[j].STTimer].STTimeout);
                            timeradd(&ft, LEADWAY);
                            list[j].STForced = ft;
                        }
                        list[j].STForcedRemain++;
#ifdef DEBUG
                        cout << "Setting forced timer for "
                            << j << " to "
                            << timershow(ft) << endl;
                        cout << "\tForced count: "
                            << list[j].STForcedRemain
                            << endl;
#endif
                    }
        }
}
 
 
APPENDIX A - SUREAL TIME RULES
The following are all of the Sureal Time rules without any explanations:
 
Rule 1) A player that is outside a radius of 16 units of all other players on the same level is
placed in a turn based movement.
Rule 2) Players or groups of players that are within 16 units of another player or group of
players are placed in the same group. These groups are "controlled movement" groups.
Rule 3) When groups are in controlled movement, if no players move, then no turns are
made in the game.
Rule 4) All players have a base connection speed. In a group of players, the slowest
connection speed is selected as the timeout basis for movement.
Rule 5) The base connection speed is only ever increased.
Rule 6) A player with an intrinsic of speed modifies the base connection speed of all other
players in a group.
Rule 7) After a player in a group makes a move, all other players must move within a
certain time.
Rule 8) Players that do no move within the time limit are forced to move, with the
computer making an intelligent move, such as attacking the last attacked monster (see
forced move rules).
Rule 9) If a player is forced to move more than 30 times in a row, they are automatically
saved.
Rule 10) If a player looses their connection, they are automatically saved.
Rule 11) A player can enter into Sureal Time even if they are not moving.
Rule 12) After a forced move, all key-presses from the player forced to move will be
ignored for an amount of time specified by the user.
Rule 13) A reaction time will be added to the time before a player is forced to move. The
reaction time should allow for a player to see a move, think of a move, and make it.
Rule 14) For every move that forces a move on another player, the player that is forced to
move will have a tally kept. This tally will be reduced every time the player is forced to
move. When it reaches zero no more forced moves will be made.
Rule 15) A player that makes a move will reduce their forced move tally to zero.
Rule 16) Every monster is attached to the player they are closest to.
Rule 17) When the player a monster is attached to makes a move, the monster makes a
move.
 
 
APPENDIX B - FORCED MOVEMENT RULES
The following are a relatively "intelligent" set of rules to follow when a player is
forced to move. It is more than likely that other rules may need to be included. I would like
to hear comments on this section:
 
Rule 1) When no other rules apply, a player repeats their last action. A player that was
moving, continues to move, a player that was attacking, continues to attack.
Rule 2) It is not safe for a player to attack or move if they are hungry, or lacking hit points.
Rule 3) A player is lacking hit points if they have less than 10% or their total.
Rule 3) If a player is confused, stunned, or blind, they wait unless the opportunity exists to
attack safely.
Rule 4) A player that is not in attack mode, and is hungry eats.
Rule 5) A player that is almost fainting eats.
Rule 6) If a moving player comes to a door they open it (open, lock pick, keys, kick).
Rule 7) If a moving player comes to a dead end, they search for 15 units of time until
something changes. If nothing changes, they player resumes in the opposite direction.
Rule 8) If something changes while searching the player continues in that direction.
Rule 9) A player that can not move left, goes forward. A player that can not move forward,
moves right. A player than can not move right turns around and goes back the way they
came.
Rule 10) If a moving player enters a room, they will seek out the best items from any
objects.
Rule 11) A moving player will try to remain in Sureal Time, following other players.
Rule 12) If a player sees a monster it will attack at long distance first (throwing weapons,
potions, zapping known wands).
Rule 13) While in close attack, monsters will use weapons, spells, wands etc. The method
of attack selected is that which is considered best for the situation. In most cases weapon
based attack should be selected as the best method. However a wizard with 10% failure rate
on magic missile may opt to use that spell.
Rule 14) Players forced to move will not use objects being carried unless for offensive or
defensive purposes. If an object is unknown, it will not be used.
 
= Monsters Who Carry - James Burton [burton@cs.stanford.edu]. =
 
In _Civilization and its Discontents_, Sigmund Freud describes Man as a kind
of "cybernetic god" -- by ourselves we are weak, vulnerable, and impotent,
but with our machines we can move mountains, build or destroy worlds, and
make Roguelike games in our spare time.  This is a vitally important
observation in Roguelikes, where the power of a character can be summed up
in two things: a) Their own statistics, and b) what they're carrying.  A
mighty wizard with Raal's Tome of Destruction is a lot more powerful than
one without, as is a plevel 50 warrior with Ringil and Speed Boots a lot
more frightening than a plevel 50 warrior with chainmail and a whip.
 
And so it should be with monsters, and is in some (NetHack) games.  That
gnome is easy bait -- until he fires up his lightsaber.
 
You should *strongly* consider allowing monsters both to carry and _use_
objects, and to drop them afterwards.  For one, it provides a lot more
variety.  Second, it adds realism, in that it makes creatures with *hands*
much more intimidating.  In Roguelike World, a sabre-tooth tiger is more
dangerous than a small kobold because it is faster and stronger.  In the
Real World (or at least the version that has small kobolds in it), our
kobold is the deadlier because he could carry *and use* something much
nastier than sabre-teeth.  Third, it adds variety.  Having hundreds of
monsters is cool.  But if you let them hold an item (and a good item system
will have thousands of different items, by combining different traits
together, as in the "Whip of Freezing" and so on), then you have hundreds of
thousands of combinations.  Let them hold multiple items, and pick new items
up, and the variety is astronomical -- and has a real impact on gameplay.
 
Now for some coding ideas.  In my own game (not yet released), I have
decided that creatures should have the same ability to wear/wield/carry
items as the player -- unless it is biologically or mentally unable to (more
on this below).  Why is it that in so many games the player is a walking
blacksmith's shop, but the creatures seem to have no material needs except
bags full of gold?  Since I also leave open the ability to hold one item
inside another item, and even put creatures into items (like tigers into
cages), I find a *tree* structure to be most efficient.
 
Everyone learns (or should learn) all about making trees in their first
computer course, and all about the optimising of trees in their first theory
course, so I won't go too deep into the data structure (look on the Internet
if you need it).  For this article, I am defining a tree as a collection of
objects such that each object has exactly one "parent" object, except for
one object which is the "root" of the tree.  A parent can have any number of
children, including none.  The resulting shape looks like a tree, hence the
name.
 
I like objects, so that's how I define my structures.  The first object I
need is a Unit, which is my name for an "Item or Creature".  So into Units
we put information that applies to both: weight, name, etc.  Actually I
implement these not as data but as virtual functions along the lines of
getWeight() and getName() -- this latter method is more "OO", but I could
understand if you used variables instead for the sake of efficiency.  I also
keep a small array of all the possible child nodes -- I use an array because
I keep an arbitrary limit of no more than 20 child nodes, and though a list
would be more efficient it's also complicated.  I then subclass this into
Items and Creatures.  You might think of subclassing items into Weapons,
Armor, and so on, but I didn't find it worth it.  It *is* worth it to
subclass "Creature" into "Player", though.  So you get an object definition
something like this:
 
OBJECT:    Unit
{
# Array of child units
UnitPtr children[MAX_UNITS]
 
# Keep reference to the parent too -- this is technically unnecessary and
requires a bit more care in your
# tree-manipulation functions, but you'll thank me the first time you have a
unit and want to know what
# its parent is.  If parent is NULL then the unit is on the map somewhere.
UnitPtr parent
 
# Some tree functions you should implement
detach()    # Detach node from its parent
destroy()  # Destroy this and all children
attach(UnitPtr newParent) # Attach to another node, detaching if necessary
replace(UnitPtr newUnit) # Put the new unit in this position, and delete
self
 
# Common unit functions
getWeight()          # Object weight
getTotalWeight()  # Weight of object and all its children
getName()
.
}
 
OBJECT:  Creature  EXTENDS  Unit
{
move()      # Move the creature
getHPs()  # Get creature hit points
.
}
 
OBJECT:  Item  EXTENDS  Unit
{
itemType # It's more OO to subclass items, but what the heck
damage              # In the case of weapons
isWielded            # Boolean, if true then the parent (a creature) is
wielding this.  The value is
.                      # meaningless unless the parent is a creature
.
}
 
I won't get into all the cool things you can do with trees: how easy it is
to move nodes around, and recurse or iterate over them, and so on --
instead, I will recommend that you put some time into adding some good tree
manipulation functions, probably build right into the Unit class (but *not*
as virtual methods, as they shouldn't need to be overridden, and you really
want these to be efficient as you'll be using them a lot).  The four
functions I stuck into the Unit object above should be a good start.  Do
make sure if you have a limit on child nodes that methods like "attach" can
fail gracefully, because at some point something in your program is going to
try to exceed that limit (you could of course always test before attaching a
new child, but why bother when you can just put the test in the attach
routine itself?).
 
I will point out what I found most useful about trees in a roguelike game:
that you can deal with only the root node, and it will affect all the child
nodes.  For example, let's say I drop a chest.  That means detaching the
chest from my own inventory hierarchy (so it becomes the root node of its
own tree), and put it on the ground (the map, of course, can hold pointers
to Units -- that's how creatures and items are held on the map!).  The cool
thing: all the child nodes go with it, so the items in the chest are moved
automatically, in constant time!
 
Now how do we return this to the question of monsters?  In my trees, there
are clearly four kinds of relationships: an item can contain an item, an
item can contain a creature, a creature can contain an item, and a creature
can contain a creature.  I interpret each of these differently.  An item
containing an item I think of as physical containment -- like a sword in a
chest, a scroll in a bag, and so on (I suppose I could also see it as a
battery in a flashlight or a bullet in a gun, but there aren't such things
in my game).  An item containing a creature refers to some kind of caging --
a bird in a birdcage or a ghost in a magic ghosttrap, etc.  A creature
containing an item is obvious -- that's the creature's inventory!  And a
creature containing a creature means the contained creature is swallowed (or
would; I don't actually use this anywhere in the game).
 
So what happens if a monster is killed?  Simple: he simply transforms into
(is replaced with) a corpse, which is an item.  Or more specifically, a
*container* item, like a chest or bag.  See?  All the things he is carrying,
by the definitions we're using, become items contained by the corpse.  This
way we avoid the clutter you get in, say, Angband, where the last act of a
powerful unique is apparently to throw his belongings all over the room
(since you don't have stacks of items on the floor in Angband).  Getting
items from the corpse is handled just like getting them from a treasure
chest (and can be quite as dangerous).
 
So now we've handled data structures, but how do we decide what monsters
actually carry?  There are three relationships a monster can have with an
item, and for each of them I have a flag.  First, is it possible for the
monster to carry it?  This usually involves having hands, though I suppose
telekinesis works.  Second, where applicable, is it possible for a monster
to use it?  Helmets require appropriately-shaped heads, scrolls require the
ability to read, etc.  Third, is there a chance that the monster will start
out with it?
 
I implement these first two as flags, and the third as a pair of numbers:
the average number of items the creature has (i.e. "from 0 to 6"), and the
dungeon level equivalent of the items (i.e. a kobold only gets the kind of
items you find on level 1).  The items are generated randomly when the
monster is created, plus a few rules are applied to preserve sanity (no
creature carries more than one armor or more than two weapons; only unique
creatures can start out with artifacts, etc.)  Et voila!  I also keep a flag
to let some monsters carry only one item, and can't fight while carrying --
this is great for animals that can only carry things in their mouths.
 
Of course, mosters should be able to acquire objects, and perhaps steal them
as well (hello Green Glutton Ghosts or the Nymphs of Nethack).  That is easy
enough to manage, and also lets monsters get items way out of their depth
("The kobold hits!  Snicker-snack!").  Again, sanity should be applied --
monsters should have no better idea of what an item is than the player would
(depending on how you handle identification), they should not be able to
touch items inimical to themselves (evil monsters should not touch holy
weapons, goblins are not likely to go around swinging Orcrist), and so on.
 
Care must be taken that game-balance is not hurt.  The biggest danger is
when small creatures have powerful items.  It's very cool when our small
kobold has a big weapon, but if you can stand a few meters away and magic
missile him to death, then you have a free major item.  And in most
roguelikes a really good artifact would increase the power of a low-level
character many times over.  Luckily, a well-balanced and realistic monsters
definition file will handle most of that.  Normally the little guys won't
get the big weapons, and if they occasionally do that's just interesting,
and good (or disasterous) luck for the player -- much like Wormtongue
throwing the Palantir at Gandalf without knowing what it was.  The other
thing is that the tough guys are going to be a *lot* tougher in this system
(which by my book is a good thing).  Imagine an Angband Nazgul if he was
also guaranteed to be carrying a few "good" or "excellent" items on him.
 
The rest you can think of yourself: like destroying the other creature's
items and so on.  Heck, if a fire-breathing dragon can burn up all my
scrolls, I want to be able to destroy his scrolls with a wand of fire.  I
would also point out that the more things a monster carries, the more fun it
is to play a thief.  On the flip side, you could make a really good-aligned
character like a paladin very strong, but unable on moral grounds to remove
items from corpses.
 
= 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
                      XXXXX
                      XXXXX
                      XXXXX
                      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
                      XXXXX
                      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
                        XXX 
                      XXXXX
                      |XXX|
                      ||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-------
########--------
########--------
########--------
########--------
########--------
########--------
########--------
 
(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:
--------########
--------########
--------########
--------########
########----####
########----####
########----####
########----####
----####--------
----####--------
----####--------
----####--------
############----
############----
############----
############----
 
 
Step 3:
------########--
------########--
--##----########
--##----########
########----####
########----####
######--------##
######--------##
----####--------
----####--------
----##----------
----##----------
##########------
##########------
##--########----
##--########----
 
 
Step 4:
-----########---
------########--
-##-----########
--##----#--#####
########----####
########-----###
######--------##
#-####--------#-
----####--------
---####---------
---###----------
-#--#--#--------
##########-----#
#########-#-----
##-#########----
#----######-----
 
 
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
 
= More Continuous Content - Joseph Swing [JSwing@wport.com]. =
 
One feature of RL games is the random placement of monsters and
objects.  While this is good in general, it leads to setups that are
highly improbable at best, and ludicrous at worst.  You know what I'm
talking about.  A barrack of soldiers with one exit leading to a room
containing half a dozen giant spiders.  Orcs frolicing in one room while
a lone elf wanders next door.  Wargs who ignore the juicy smell of the
nearby ratling.  And so forth.
 
A good AI helps, but if the initial placement of the monsters makes it
unlikely the would encounter each other by their default behavior, the
problem isn't fixed.  The community has done a fantastic job developing
dungeons that are physically continuous, but whose content is not. 
 
First of all, we need some additional data for our generic monsters.
Something which indicates which monsters tend to be next to which
monsters.  Call it a Theme.  For a Goblin Lair theme it might look like:
 
1    Goblin King and 3 advisors (1-3 hobgoblins) (unique, mandatory)
2    Goblin guards (1-6)
2    Hobgoblin guards (1-2)
3    Goblin Wolfriders  (1-3)
3    Goblin Shopkeeper (unique)
3    1-3 Goblins and 1-2 Goblin thieves
4    1-2 Goblins and a Crate
4    1-2 Goblin Guards
4    Goblin pig farm - 1 goblin and 3 pigs
4    Empty Room
5    Empty Room
6    Empty Room - random monster possible
7    Empty Room -random monster or stairs allowed
 
First, as you;re building your level, check if there's a theme.  Not all
levels should have one.  If your level has a theme then start at the top
of the list. 
 
In this case, the first room that you plunk down should have a Goblin
King (#1) in it.  When you draw your doors/hallways, draw them leaving
from this room, and carry with it the number on the left.   Moving to
the next room, move down the list (75% chance) or back up the list
(25%).  For the example above, there are two possibilities, either some
Goblin or Hobgoblin guards.  Add these to the next room.  Draw your
doors/halls from there and continue. 
 
You may even choose to add some entries to the hallways themselves, if
they're large enough.  The Goblin King might have a few guards in the
outside hall, but it would be difficult to have a pig farm in a
hallway.  If you wanted to use this option, the simple solution is
staggering your entries so that odd ones were in rooms and even ones
were the hallways between.
 
The nice thing is that you end up with a small goblin community, with a
few empty rooms between them and any wandering monsters.  The Goblin
King sits at the middle, furthest from the stairs where the hero will
enter, which is nice.
 
How to implement?  If you're carving your dungeon this is easy.
Starting with an empty dungeon level, you maintain a separate list of
doorways:
1) Start with a dummy doorway with a content value of 1
2) From the doorway, try and add a room filling with content value from
the doorway; if successful, add both the room and doorway to the map.
3) Add doorways from the room, migrating the content (1->2, etc)
4) Step through your list of doorways and go back to step 2;  You're
done when you;re out of doorways
 
If you're using the grid to plunk down your rooms you either need to
wait until you draw the hallways (and draw them carefully), or use a
flood fill algorithm.
 
If you don't always use fixed rooms (like Crawl) I suppose you could
also flood fill with each entry having a certain radius before it
transitions to the next one.  It's trickier.
 
Other thoughts: 
Not all levels should have a theme.  Some themes should be smaller than
others, maybe only a few connected rooms, with the rest of the level
being more random. 
To set up the themes you could make them more abstract.  Make the sample
above generic to humanoids (xxx lair) and fill in with the details fro
the appropriate level at run time (Orc Lair, Goblin liar, etc).  Or you
could make a large Monster Map connecting the likely monsters/groups.
One whole edge of the map should be 'random monster'.
I recommend that no more than about 1/3 to 1/2 of your dungeon be filled
with this kind of theme, to keep the replay value.
If you include stairs with doors as transition points, it's possible to
spread the theme in 3d, and no longer required to keep the stairs so far
from the center (just treat it like you would a door).
Along with the monsters, make the objects more continuous too.  The
Goblin Guards might have an extra sword lying around, but the peasants
aren't going to have 50gold for very long.  The empty rooms near the
Lair might thave signs of the local occupants - grafitti in the goblin
tongue, for example.
 
= 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

Latest revision as of 09:06, 4 October 2008

Attention! The reason that these articles were not transferred to RogueBasin and are in danger of being lost for good is because the admins could not secure the author's permission for being transferred from the old site to the new one. IF YOU ARE AN AUTHOR: Please let me know on this page that you give your permission. If you do that, I can pull the articles from the archive pages and integrate them into the wiki.

List of authors who have given permission: 

  * Steve Segreto (Permission Granted) N.B. My article is extremely dated by now and probably useless to most everybody

List of authors who have not given permission (alphabetical order by first name): 

  * Adam Szczepaniak
  * Andrew Collins
  * Brian Bucklew
  * Brian Robinson
  * Christopher J Martens
  * Damian Bentley
  * Dana Larose
  * Darren Hebden
  * Erik_Inge_Bols???_knan_mo.himolde.no
  * Erno Tuomainen
  * Esa Ilari Vuokko
  * Gero Kunter
  * Gwidon S. Naskrent
  * Isaac Kuo
  * Jakub Debski
  * James Burton
  * Jim Babcock
  * Joseph Swing
  * Josh Tippets
  * Judy Wray
  * Jurriaan Kalkman
  * Kenneth Power
  * Kornel Anubis Kisielewicz
  * Matthias E. Giwer
  * Michael Blackney
  * Michael Heinich
  * Mike Anderson
  * Mixi Lauronen
  * Peter Farabaugh
  * R.Alan Monroe
  * Radomir 'The Sheep' Dopieralski
  * Rick Carson
  * Ross Morgan-Linial
  * Sean Middleditch
  * Simon McGregor
  * Steve Segreto
  * Stu George
  * Thomas Gilray
  * Unknown ( Direct Screen Output.txt )

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

Cannot Find: 

  * Roguelike Step by Step Guide.txt
  * Recursive randomized world-map generation Phillip C. Culliton [pcullit@hotmail.com].txt

TODO: 

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

Found Articles: 

  * User:Duerig/Archive0
  * User:Duerig/Archive1
  * User:Duerig/Archive2
  * User:Duerig/Archive3
  * User:Duerig/Archive4
  * User:Duerig/Archive5
  * User:Duerig/Archive6
  * User:Duerig/Archive7
  * User:Duerig/Archive8
  * User:Duerig/Archive9
Retrieved from "http://roguebasin.com/index.php?title=User:Duerig&oldid=14166"