User:Duerig

From RogueBasin
(Difference between revisions)
Jump to: navigation, search
(Finished census of old roguelikedevelopment articles. Found the ones I could. Noted the others)
(Found "How to finish a roguelike")
Line 1: Line 1:
 
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:
 +
  * User Interface in Roguelikes - Jim Babcock [jimmy_b@earthlink.net].txt Found a russian translation: http://www.rlgclub.ru/pmwiki.php?n=Main.ArticlesDevUserInterface
 +
  * Roguelike Step by Step Guide.txt
 +
  * Mostly Turn-based Multiplayer Timing - Isaac Kuo [mechdan@yahoo.com].txt Found a russian translation: http://www.rlgclub.ru/pmwiki.php?n=Main.ArticlesDevTurnBasedMultiplayer
 +
  * Lake and Oasis Generator - Adam Szczepaniak [adamshc@wp.pl].txt
 +
  * Fill-area-with-rooms and Maze - algorithms - Josh VertexNortmal Tippetts [vertexnormal@email.com].txt Found russian translation: http://www.rlgclub.ru/pmwiki.php?n=Main.ArticlesDevMazeGen
 +
  * Recursive randomized world-map generation Phillip C. Culliton [pcullit@hotmail.com].txt
 +
  * 3D Representation for Roguelike Worlds - Jimmy Babcock [jimmy_b@earthlink.net].txt
 +
  * Random Dungeon Algo in QBasic - Andrew Collins [andrewcollins@hotmail.com].txt
 +
  * Nest of Ants - Jakub Debski [jakub@mks.com.pl].txt
 +
  * Passable Cave Building Algorithm - Josh Tippets [vertexnormal@email.com].txt
 +
 +
TODO:
 +
  * Add a link to blah.tar.gz
 +
  * add a link to name.zip for Random Name Generation Using Regular Expressions
 +
 +
= Representing Magick Spells - Sean Middleditch [sean.middleditch@iname.com].txt =
 +
 +
This article describes the basics of representing and using Magick Spells in roguelikes.
 +
The general techniques are very similar to those used in my article on Object
 +
representation.
 +
 +
For starts, we need a class to hold the information for a specific spell.
 +
 +
class Spell {
 +
public:
 +
 +
OK.  Now, let's give the spell a name.
 +
 +
char *Name;
 +
 +
There.  Now, every magick spell costs Mana Points (well, if you're using a magick system
 +
similar to most others).  So we need to define the spell's cost in MP.
 +
 +
int MPCost;
 +
 +
Also, every spell has a level: how difficult a spell it is.  Only more powerful casters can
 +
use more powerful spells.
 +
 +
int Level;
 +
 +
There.  Now all we need to know is what in Gehenna the spell does.  We'll make a
 +
sub-class called Effect to store this information.
 +
 +
class Effect: {
 +
friend Spell;
 +
 +
OK, so what does a specific spell do?  We'll make a simple int to describe what a specific
 +
Effect describes.
 +
 +
int Type;
 +
 +
So what does Type mean?  We'll use some #define's to specify.
 +
 +
#define HEAL 0
 +
#define SCORCH 1
 +
#define TICKLE 2
 +
#define CREATE_OBJ 3
 +
 +
You can of course add as many as you want.  Now, we know what an Effect does, but
 +
that's not enough.  For example, for a HEAL Effect, how much HP does it heal?  We
 +
could base everything of level (making a rigid and uniform magick system, which may
 +
be what you want: predictability), or we could give each Effect a set of arguments to
 +
define in more detial what it does.  We'll do this through the use of 5 int's.
 +
 +
int Args[5];
 +
 +
What do the fields of Args mean?  That's based on what Type is equal to.  For an Effect
 +
with Type HEAL, we might say that:
 +
 +
Args[0] is Number of Dice
 +
Args[1] is Sides per Die
 +
Args[3] is Roll Mod
 +
 +
So an Effect of type HEAL with Args[0] = 2, Args[1] = 6, Args[3] = 2 would heal 2d6+2
 +
HP.  Pretty simple, eh?
 +
 +
Anyways, we can close of the Effect class.  We want each Spell to have 5 Effect's (so
 +
every spell can have lots of flexibility).
 +
 +
} Effects[5];
 +
 +
We can now close of the Spell class.
 +
 +
};
 +
 +
So that's all there is to a basic magick class.
 +
 +
Casting the spell is just as simple.  Make a function called Cast or whatever (I used an
 +
object method inside the Spell class, since I'm a C++ OOP freak).  The function would
 +
take as arguments the spell to cast, the target, etc.
 +
 +
void Cast ( Spell *SpellToCast, int TX, int TY );
 +
 +
Then we go with a big, evil, switch statement based on effect.  This actually works
 +
VERY well.  The flexibility is astounding...
 +
 +
Of course, how each spell takes effect is based on how you've programmed the rest
 +
of your roguelike.  Because of the OO nature of WotR, I found it very easy to create
 +
simple object Methods for spell effects.
 +
 +
For the HEAL Spell Effect Type, you might to do something as simple as loop through
 +
all the Characters (NPC's and Players) in the target loc (defined by TX and TY), and
 +
heal them based on the arguments listed above... 2d6+2, or whatever.
 +
 +
Anyways, this is just the basics.  The advanced stuff all depends on your magick
 +
system and how you programmed the rest of the game.
 +
 +
The complete source for the Spell class is:
 +
 +
#define HEAL 0
 +
#define SCORCH 1
 +
#define TICKLE 2
 +
#define CREATE_OBJ 3
 +
 +
class Spell {
 +
public:
 +
char *Name;
 +
 +
int MPCost;
 +
int Level;
 +
 +
class Effect: {
 +
friend Spell;
 +
 +
int Type;
 +
 +
int Args[5];
 +
} Effects[5];
 +
};
 +
 +
Any questions, comments, threats, etc., e-mail me at
 +
sean.middleditch@iname.com
 +
Well, I don't really want any threats.
 +
 +
The End
 +
 +
 +
= RL Dev Code 0.6 - Kornel _ Anubis_ Kisielewicz [kisiel@fulbrightweb.org].txt =
 +
 +
 +
          RL Developer Code
 +
          Version 0.6.0
 +
          Designed by Kornel \"Anubis\" Kisielewicz
 +
          (kisiel@fulbrightweb.org)
 +
 +
Hey, I noticed that both Angband and NetHack users have their own
 +
GeekCode. Why not us? ;). This is the first draft, and it\'s realy
 +
RLDev specific. I think that a Roguelike Dev Code will be especialy
 +
useful, because it may make us more aware of the others ideas. I\'m
 +
open to all new ideas, or corrections. In all project specific
 +
questions answer about your current project. A sample of the code is
 +
on the bottom of the document.
 +
 +
I encourage to at least post your code once, so someone can collect
 +
them and post somewhere :).
 +
 +
---------------------------------------------
 +
1. General info about the developers methods
 +
---------------------------------------------
 +
 +
\"L\": Language used to program your roguelike project.
 +
 +
L:C    C
 +
L:C++  C++
 +
L:VC++  Visual C++
 +
L:Java  Java
 +
L:FP    FreePascal
 +
L:TP    Turbo Pascal
 +
L:DP    Delphi (Pascal)
 +
L:Pyt  Python
 +
?L      I still didn\'t decide
 +
!L      I\'m a designer
 +
[more]
 +
 +
--------------------------------------------------
 +
 +
\"E\": Experience in programing.
 +
 +
E+++  I\'m a professional programmer
 +
E++  I program as a part time job
 +
E+    I program quite well, as a hobby
 +
E-    I\'ve read a few books and made some programs
 +
E--  I\'ve made a few simple programs
 +
E---  I\'m learning while I write a roguelike
 +
 +
!E    I\'m just a designer ;)
 +
?E    What do I need programming for?
 +
 +
--------------------------------------------------
 +
 +
\"T\": Time invested in rl-development. Choose the most true one :).
 +
 +
T+++  Every minute of my spare time!
 +
T++  Most of my free time
 +
T+    Regulary
 +
T-    From time to time
 +
T--  As a recreation
 +
T---  Rarely
 +
 +
!T    I don\'t write yet!
 +
 +
--------------------------------------------------
 +
 +
\"R\": Rewrites. A rewrite is writing your code from scratch, using only
 +
old libraries, and fragments of the old code.
 +
 +
R+++  more than 5
 +
R++  3-4 rewrites
 +
R+    1-2 rewrites
 +
R-    not yet
 +
R--  I\'ve just started
 +
R---  I do not program yet
 +
 +
?R    What are rewrites?
 +
!R    My game doesn\'t need rewrites, cause I write error-free!
 +
 +
--------------------------------------------------
 +
 +
\"P\": Porting to other systems
 +
 +
P+++  My game will be ported to most known platforms
 +
P++    Linux and DOS/Win
 +
P+    I try to keep the code portable.
 +
P-    Why the hell? I write only for Linux/DOS (you may recompile it
 +
though)
 +
P--    DOS/WIN only
 +
P---  Windows only!
 +
 +
!P    I use Java (or something similar)
 +
 +
--------------------------------------------------
 +
 +
\"D\": Importance of design before programming
 +
 +
D+++  I had a detailed DesignDoc before I started programming
 +
D++  I had many notes and information before I started coding
 +
D+    I keep my designdoc ahead of the project, but update it regulary
 +
D-    I had a few notes before I started coding
 +
D--  I had a general image of what I\'m trying to do
 +
 +
!D  Who the hell needs a DesignDoc? I make everything on the fly!
 +
?D  What\'s a DesignDoc?
 +
 +
--------------------------------------------------
 +
 +
\"G\": The generic engine, that is, how generic your game will be.
 +
 +
G+++  You will be able to make a hard-sci-fi game out of my engine, by
 +
just changing the info-files!
 +
G++  My engine is very generic -- you will be able to make a
 +
different game by changing the info files
 +
G+    I have info files for maps, monsters, items and dungeon
 +
generators
 +
G-    I have a few general info files
 +
G--  I keep everything in the code
 +
 +
!G    Why the hell generic engine? I wan\'t to make a GAME.
 +
 +
--------------------------------------------------
 +
 +
\"F\": Favourite Roguelike
 +
 +
F:ToME
 +
F:ADoM
 +
F:V      Vanilla Angband
 +
F:*band  *bands in general
 +
F:Rogue  Yeah :).
 +
F:Moria
 +
F:NHack  NetHack
 +
F:Hack
 +
F:GH    Gearhead
 +
F:DC    DeadCold
 +
[more]
 +
 +
--------------------------------------------------
 +
 +
\"RL\": Your roguelike definition
 +
 +
RL+++  A roguelike MUST be ASCII, MUST be a dungeon crawl, and MUST be
 +
based on a system similar to AD&D, and MUST be permadeath.
 +
RL++  A roguelike has to be ASCII, has to be random, and have
 +
experience levels, and permadeath.
 +
RL+    A roguelike has to be ASCII or use tiles, must have dungeons,
 +
and focus on killing things for experience. It has to be permadeath
 +
too.
 +
RL-    A roguelike may have graphics but has to be rather dungeon
 +
themed permadeath game.
 +
RL--  A roguelike is a game that focuses on randomness, and features
 +
permadeath.
 +
RL---  A roguelike is a game inspired by other roguelike games.
 +
 +
!RL    This is completely unimportant
 +
?RL    What is a roguelike actually?
 +
 +
--------------------------------------------------
 +
 +
\"RLA\": Roguelike community activity
 +
 +
RLA+++ I\'ve created a popular game, or host one of the main roguelike
 +
sites on the web.
 +
RLA++  I\'ve created a roguelike dedicated webpage (focusing not only
 +
on my game)
 +
RLA+  I\'m a FAQ maintainer, or wrote a roguelike article, or created
 +
a roguelike document
 +
RLA-  I play roguelikes and post on a few roguelike newsgroups
 +
RLA--  I post on one roguelike newsgroup
 +
 +
!RLA  Who is that guy?
 +
 +
 +
 +
--------------------------------------------------
 +
2. Project specific questions
 +
--------------------------------------------------
 +
 +
\"W\": World of the game, the genre
 +
 +
W:F    Fantasy
 +
W:DF  DarkFantasy
 +
W:AF  Alternative Fantasy
 +
W:SF  Science Fiction
 +
W:HSF  Hard Science-Fiction
 +
W:MH  Mecha
 +
W:M    Modern
 +
W:CP  CyberPunk
 +
W:G    Generic engine (give eventual default genre in bracets)
 +
 +
--------------------------------------------------
 +
 +
\"Q\": Quests in your project
 +
 +
Q+++  The plot is the master! You will have random interesting quests
 +
in my game.
 +
Q++  I will add many pre-written quests.
 +
Q+    I will add a few quest for flavor, or even ToME-like random
 +
quests.
 +
Q-    Maybe a few quests for flavor
 +
Q--  Kill Sauron. Kill Morgoth.
 +
Q---  No quests -- just Hack\'n\'slash.
 +
 +
!Q    Who the hell needs quests?
 +
?Q    What is a quest?
 +
 +
--------------------------------------------------
 +
 +
\"AI\": Approach to AI in your project
 +
 +
AI+++ AI is the key! The creatures will behave diablo inteligently and
 +
talk to you with Bot-generated messages. They will use military
 +
tactics, recognize dangers, and create traps.
 +
AI++  The NPCs will behave quite reasonable, will flee, band together,
 +
pickup and use items.
 +
AI+  The creatures will use items like wands, staves and the like.
 +
AI-  The creatures will be able to pickup and equip items.
 +
AI--  No monster-inventory -- just Hack\'n\'Slash
 +
AI--- Kill player. Kill player.
 +
 +
--------------------------------------------------
 +
 +
\"GFX\": Approach to graphics
 +
 +
GFX+++  The game will be graphical with nice graphics
 +
GFX++  The hame will have tiled graphics
 +
GFX+    Some popular freeware tiles
 +
GFX-    Somewhere in the future I plan to add graphics
 +
GFX--  I\'d like graphics, but I\'m a poor artist
 +
 +
!GFX    Pure ASCII rulez!
 +
 +
--------------------------------------------------
 +
 +
\"SFX\": Approach to sound
 +
 +
SFX+++  Digitalized Speech and Music is my aim
 +
SFX++  I will add many wave files and maybe some music
 +
SFX+    Just a few Sound-Effects
 +
SFX-    Maybe in the future
 +
SFX--  I\'d like sound, but I\'m a poor at that
 +
 +
!SFX    A roguelike with sound? Buhahahaha...
 +
 +
--------------------------------------------------
 +
 +
\"RN\": Approach to randomness in your project
 +
 +
RN++++ The whole world will be random, random quests, random dialogs,
 +
random plot
 +
RN+++  Same as above, but the plot will be fixed
 +
RN++  The world will be fixed, but there will be random quests,
 +
dungeons and items and monsters
 +
RN+    Random dungeons+items+monster placement
 +
RN-    Just the dungeons and monster placement
 +
RN--  I plan to make everything fixed
 +
 +
--------------------------------------------------
 +
 +
\"PO\": Popularity of current project
 +
 +
PO+++  I have fan-sites of my playable roguelike (reserved for ToME,
 +
NetHack, ADoM, Angband and the like :)
 +
PO++  I have a playable version on the web that can be enjoyed
 +
PO+    I have a playable version on the web that can be looked at
 +
PO-    I have a designer version on the web (dungeon+items+npcs and
 +
the like)
 +
PO--  I have a few design programs (map-view, dungeon generator)
 +
PO---  I haven\'t published anything
 +
 +
!PO    I didn\'t do anything yet!
 +
 +
--------------------------------------------------
 +
 +
\"Hp\": Hitpoint treatment in the roguelike
 +
 +
Hp+++  A 1-st level character has a few hitpoints, a 50th level
 +
character has a few  hundred...
 +
Hp++  I keep the hitpoints rather lower.
 +
Hp+    The player rarely recieves hit-points, I don\'t use a level
 +
system.
 +
Hp-    Fully skillbased
 +
Hp--  Fully skillbased and advancement doesn\'t make you realy
 +
powerfull
 +
 +
!Hp    I don\'t use hitpoints!
 +
 +
--------------------------------------------------
 +
 +
\"Re\": Realism in the roguelike
 +
 +
Re+++  You can die because of disease, rusty weapon wounds, or the
 +
after-effects of an out-dated portion of speed
 +
Re++  Each fight is dangerous
 +
Re+    I\'d rather not let the player kill hordes of monsters
 +
Re-    I like to keep things real as in NetHack
 +
Re--  I like to keep things real as in Angband
 +
Re---  Who needs realism? It\'s the hack\'n\'slash that counts!
 +
 +
--------------------------------------------------
 +
 +
\"S\": Seriousness of the world
 +
 +
S+++ THE GAME. You think it\'s funny? You\'re talking to me?
 +
S++  The game has to be serious. I want to make an atmosphere...
 +
S+  (ADoM) From time to time a funny in-game situation is fun
 +
S-    I like to keep the world rather not gloomy
 +
S--  (ZAngband) Lets keep it easy, sometimes a Barney, or Bull Gates
 +
is fun to kill
 +
S--- (NetHack) Why the hell? Let\'s have nuclear scientists, tourists,
 +
photo-cameras and sinks in a dark dungeon
 +
 +
--------------------------------------------------
 +
 +
regards, and I\'m waiting for your codes and opinions :),
 +
--
 +
Kornel \"Anubis\" Kisielewicz
 +
RLDev Code v.0.6
 +
    L:FP E+ T+ R+++ P+ D++ G++ RL-- RLA++ F:ADoM
 +
    GenRogue 0.16 V8 ( http://genrogue.felis7.civ.pl/ )
 +
    W:DF Q+++ AI++ !GFX !SFX RN+++ PO--- Hp-- Re+++ S+++
 +
 +
= Roguelike_Skeleton_Blah_Documentation_Erik_Inge_Bols???_knan_mo.himolde.no_.txt =
 +
 +
------------------------------------------------------------
 +
NB. If you wish to get hold of Bzip2, please pop along to...
 +
http://www.muraroa.demon.co.uk/
 +
------------------------------------------------------------
 +
 +
Okay. Basically, what works well as of the current version is map
 +
generation, line of sight (everything not in LOS is greyed out) and config
 +
file for key setup. The player, item and inventory structs and functions
 +
have been started. Spells, monsters and combat are just stubs.
 +
 +
- Map generation is by far the most complex part of this. The GenerateRoom
 +
routine (in map-internal.c) creates weird cave-looking rooms by a
 +
conceptually simple method:
 +
 +
//pseudocode
 +
while (room < target_room_size and squares_left)
 +
  pick_random_square_from_stack_and_delete_from_stack
 +
  add_surrounding_squares_to_stack
 +
 +
(actually, I use one stack and an array of pointers to places in that
 +
stack, but the above is the underlying principle)
 +
 +
- config.c implements a simple parser for configuration files, that
 +
probably can be extended to other uses than key configuration.
 +
 +
- The Player and Creature structs have identical upper parts, so that
 +
one can use most routines for both by typecasting (Creature)player ...
 +
 +
- Almost everything in the game is in a linked list or contains one or
 +
more linked lists. See lists.c and lists.h .
 +
 +
- One of the last things I did to this source was rewriting many routines
 +
to use a "tagitems" calling convention, that is:
 +
 +
  createBlah (TAG_UGLINESS, 500, TAG_MONTY_PYTHON_FACTOR, 2.1);
 +
  // (identifier, value) pairs, instead of fixed parameters that will
 +
  // change dozens of times during developement
 +
 +
- creature.c allocates the correct amount of memory for a creature, but
 +
does nothing more as of yet.
 +
 +
- pl_item.c and item.c is in its infancy. It has a demo item defined, and
 +
allocates it to the player, and successfully displays it in the player's
 +
inventory. Fragile. But item.h is quite well-developed, and ought to give
 +
anyone ideas...
 +
 +
- lists.c contains your basic single-linked lists code + the NextTagItem
 +
code.
 +
 +
- magic.c, help.c, combat.c, timer.c are just stubs.
 +
 +
- output.c / output.h / ncurses.c  encapsulates most of the
 +
ncurses-specific stuff for easy porting.
 +
 +
- map.c ... Map_Scanfor was designed to scan for any interesting parameter
 +
inside maps, but are currently not used for much besides finding a good
 +
place for a corridor. map.c contains all routines that should be visible
 +
outside map generation. GenerateCorridor currently uses a hit-and-miss
 +
approach (copy map to temp_map -> run generatecorridor -> if grind to a
 +
halt, try again -> if not copy temp_map to map) and can be improved much,
 +
I suppose.
 +
 +
- types.h defines own UBYTE, BYTE, ULONG, LONG etc. types, also for easy
 +
porting.
 +
 +
- I'm currently undecided on what's the best approach: Defining "id" in
 +
all object structures or defining it in the "node" structure. It must be
 +
defined in any case, so we can find a specific object that we don't have a
 +
pointer to by some FindObject routine (to avoid passing a million pointers
 +
around). (started, see FindWindow in output.c)
 +
 +
- writing colored strings to the screen is currently accomplished by
 +
calling WriteStr as usual, with strings of the format "<White>Bob
 +
<Yellow>the Big" ... WriteStr does not do %s and such expansion, so
 +
sprintf() ing a string before passing it to WriteStr is a good thing. Look
 +
to the bottom of player.c for an example.
 +
 +
= Random Name Generation Using Regular Expressions - Brian Robinson [bcr19374@pegasus.cc.ucf.edu]. =
 +
 +
Rationale
 +
 +
One of the things that makes roguelike games interesting is the
 +
use of unique items and beings.  Having Ringil by your side in Angband is
 +
much more fun than having a sword or even a sword +1.  And its much more
 +
satisfying to get rid of Wormtongue than another "seedy looking human."
 +
In the case of Angband, many of the unique names were derived from the
 +
works of J. R. Tolkien and are used to evoke the same kind of atmosphere
 +
used in his books.  Tolkien provides a rich background for a game, and
 +
plenty of names.  However, what do you do if you want to create your own
 +
game world from scratch?  You could write a few novels and use the
 +
characters and items from them, or instead you could try to use a random
 +
name generator.
 +
A random name generator is a program or part of a program that
 +
can produce names randomly.  The names can be used for anything, from
 +
naming individual beings like monsters and shopkeepers, to naming
 +
artifacts, to naming towns and regions.  However, some tweaking may be
 +
neccasary for different purposes.  For instance, Brian might be a good
 +
name for an orc, and a decent name for a city, but the amulet of Brian
 +
just doesn't sound that great.  One characteristic that a good name
 +
generator should have is flexibility.  It should be able to produce names
 +
of different forms with ease.
 +
 +
Regular Expressions
 +
 +
One way of accomplishing this is to use regular expressions.  If
 +
you've taken a discrete structures class or are a *nix guru, you probably
 +
already know what these are.  For those that do not, I will provide a
 +
brief explanation.  A regular expression is a string, or a sequential
 +
series of letters and symbols, that describes the form a word may take,
 +
or in technical terms, a language.  One special letter used in
 +
regular expressions is called the null symbol, or a blank.  It is usually
 +
denoted by a greek lambda, but I will use a 0 instead.  Each letter and
 +
each grouping of letters within a regular expression is also a regular
 +
expression.
 +
Some regular expressions have only one interpretation; for
 +
instance, the regular expression "bab" can only represent "bab".
 +
However, we can use a number of operators to give regular expressions
 +
more options.  The first operator we will look at is the "or" operator,
 +
commonly written as |.  Or basically means that of the two expressions on
 +
either side of it, only one will be selected.  So, if my regular
 +
expression is "b|a", there are two valid words in this language, "b", and
 +
"a".  I can also use parantheses just as in math to group letters, so
 +
"(b|a)b" has two valid words, "bb" and "ab". 
 +
There are two other operators in classic regular lanugages.  One
 +
is the "and" operator, but it is implicit in the form I am using here.
 +
Basically, whenever an expression is placed next to another expression,
 +
they are anded, which means that they occur together in the order they
 +
were first written.  The other is *, but rather than using * (which can
 +
generate infinitely long words), we will look at the use of numbers as
 +
operators.  Consider the regular expression "a3".  This is analogous to a
 +
to the third power in standard math, and the result of this regular
 +
expression is "aaa". 
 +
One useful technique we can use with regular expressions is
 +
substitution.  Substitution basically maps a single letter to a regular
 +
expression.  So, if I make a substitution of the form "D=(a|b)" and then
 +
write "Db" it would be the same as if I had written "(a|b)b".  This is
 +
particularly applicable to random name generation.  Consider the
 +
substitution "V=(a|e|i|o|u)".  Now whenever we use a "V" in our regular
 +
expression what it really means is to insert a vowel.  Similarly, we can
 +
define the consonants as "C=(b|c|d|f|g|h|j|k|l|m|n|p|q|r|s|t|v|w|x|y|z)".
 +
 +
Actually Making Some Names!
 +
 +
Now we can do something interesting.  Lets define a new regular
 +
expression, "CVC".  This is a very simple thing to type, and yet we can
 +
now generate words such as "bob", "sig", "mop", "non", etc.  There are
 +
very many combinations here!  Lets try another: "C(V2)C".  Here we use the
 +
numerical operator.  Substituting the V,  we expand this as
 +
"C((a|e|i|o|u)2)C", so we must select our vowel first, then place it 2
 +
times, rather than placing 2 different vowels.  This regular expression
 +
will create names like "baab", "look", "hiig", etc.  Lets look at one more
 +
before moving on: "(C|0)VCV".  This regular expression can create names
 +
like "moli" and well as "ago" because of the "C|0" part.  Using the null
 +
along with an or operator can be a powerful tool and give you many
 +
options.
 +
Now that you see how to create some basic names, lets take it a
 +
little further.  You may have noticed that some of the output names I
 +
listed above seem unrealistic; they don't sound like real names.  How can
 +
we improve this?  Well, substitution is again our friend.  I'm going to
 +
define two new substitutions, P for prefix and S for suffix.  The idea
 +
comes from looking at names.  Take a few, like "Brian", "Scott", "Steve",
 +
"Frank", "Casandra", and "Kristen".  These names all have letter
 +
combinations in the beginning or end that we are used to seeing, like
 +
"br" in "Brian" or "nk" in "Frank".  What we do is take these prefixes
 +
and suffixes and map them into a substitution.  So we get
 +
"P=(br|sc|st|fr|kr)" and "S=(tt|nk|dra|sten)".
 +
Now lets play with our new toys.  Remember how the names from
 +
"CVC" were not very impressive?  Well, lets see what we come up with when
 +
we use "(C|P)V(C|S)": "lott", "brik", "stink", "wodra", "juk", "kosten".
 +
With the exception of "stink", these are some pretty good names, and the
 +
regular expression for generating them was pretty simple.  To eliminate
 +
names like "stink", we can use a filter which eliminate a set of words we
 +
don't want to appear.  I cover the implementation of such a filter below.
 +
 +
Implementation
 +
 +
In my implementation, as I mentioned, I treat the concatenation
 +
operator as explicit.  This simplifies things in the code, but makes it
 +
just a little more complex for the person creating the regular
 +
expressions.  Basically, you need to use some more parentheses than you
 +
might expect.  Consider the example above of "C(V2)C".  You might expect
 +
to be able to get the same effect without the parentheses.  But due to the
 +
string implementation, without the parentheses odd things can happen, such
 +
as both the consonant and the vowel being duplicated.
 +
Now, with that caveat, lets proceed.  I have a Java class that
 +
takes a regular expression as an argument to its constructor.  Every time
 +
you want a name in that format, you can call the getName() method, and a
 +
random name of that type will be generated.  Most of the work in the class
 +
takes place in a private method called parse() which is called by
 +
getName().  I will analyse this line by line below so you can understand
 +
what is happening.
 +
 +
--
 +
      public String parse(String s)
 +
      {
 +
        int index;
 +
        char current;
 +
        StringBuffer b;
 +
        Vector leaves;
 +
     
 +
        leaves = new Vector();
 +
        b = new StringBuffer();
 +
        index = 0;
 +
--
 +
 +
This code sets up the variables used throughout the method and
 +
initializes them.  Index keeps track of where we are in the regular
 +
expression string s.  Current is a temp variable to let us examine each
 +
character seperately.  B is a buffer used for temporary string storage.
 +
Leaves is a Vector that will contain all the possible outcomes of the or's
 +
in this expression.  I call it leave because it is like leaves of a tree.
 +
The expression "a|b|c" could be represented as:
 +
 +
                                  *
 +
                                /|\
 +
                                / | \
 +
                              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];
 +
  }