User:Duerig

From RogueBasin
(Difference between revisions)
Jump to: navigation, search
(Checked AI, Randomiser)
(Half way through checking map. Map is all that is left)
Line 5: Line 5:
 
   * User Interface in Roguelikes - Jim Babcock [jimmy_b@earthlink.net].txt Found a russian translation: http://www.rlgclub.ru/pmwiki.php?n=Main.ArticlesDevUserInterface
 
   * User Interface in Roguelikes - Jim Babcock [jimmy_b@earthlink.net].txt Found a russian translation: http://www.rlgclub.ru/pmwiki.php?n=Main.ArticlesDevUserInterface
 
   * Roguelike Step by Step Guide.txt
 
   * Roguelike Step by Step Guide.txt
 +
  * Mostly Turn-based Multiplayer Timing - Isaac Kuo [mechdan@yahoo.com].txt Found a russian translation: http://www.rlgclub.ru/pmwiki.php?n=Main.ArticlesDevTurnBasedMultiplayer
 +
  * Lake and Oasis Generator - Adam Szczepaniak [adamshc@wp.pl].txt
 +
  * Fill-area-with-rooms and Maze - algorithms - Josh VertexNortmal Tippetts [vertexnormal@email.com].txt Found russian translation: http://www.rlgclub.ru/pmwiki.php?n=Main.ArticlesDevMazeGen
 +
  * Recursive randomized world-map generation Phillip C. Culliton [pcullit@hotmail.com].txt
 +
  * 3D Representation for Roguelike Worlds - Jimmy Babcock [jimmy_b@earthlink.net].txt
  
 
TODO:
 
TODO:
Line 1,328: Line 1,333:
 
If you combine the methods as described here, it shouldn't be a problem to  
 
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!
 
come up with as many exciting names as your roguelike game will ever ask for!
 +
 +
= Time Tracking - Gwidon S. Naskrent [naskrent@skrzynka.pl].txt =
 +
 +
When creating a roguelike, more often than not you are presented with
 +
the challenging task of devising an interesting world in which the
 +
game takes place. And, naturally, most beings in most worlds, even if
 +
they are immortal, need to keep the flow of time for personal,
 +
governmental (taxes) and religious (feasts) purposes. This article
 +
deals with issues commonly encountered upon adding a time dimension to
 +
your game.
 +
 +
Most assuredly, you are not bound to design your time according to the
 +
traditional sense, with seconds, minutes and hours. But for the
 +
simplicity of the discussion, we will assume that you operate in a
 +
framework that consists of time units that everyone knows - seconds
 +
that make minutes, minutes that make hours, hours that make days and
 +
days that make years. We'll also assume that typical Earth standards
 +
are in force, with the exception that a year is always 365 days
 +
(not 365.24624 as in reality).
 +
 +
After determining how are your time units structured, it is important
 +
to decide what within the game will you use to represent it. The
 +
simplest approach is to assign a different variable to each of the
 +
various units; a signed char (byte) to seconds, minutes and hours, and
 +
an unsigned int to days. This simple solution has, however, a
 +
significant drawback: you waste storage space. It's certainly not a
 +
big waste, but helps to forget about memory issues and develop bad
 +
programming habits.
 +
 +
Therefore, a more efficient way to approach our problem will be the
 +
introduction of *scalar time*. Scalar time is an uniform figure; it
 +
represents the amount of basic time units - in our case seconds - that
 +
have elapsed from a specific point in time. This point can be purely
 +
arbitrary, but should be antecedent to the start of your adventure, so
 +
as to avoid 'negative time', if possible. The variable type for scalar
 +
time should be a 32-bit int (it is a good idea to make it a signed
 +
int, to avoid problems with negative time). 32 bits are, surprisingly
 +
enough, sufficient to cover a period exceeding 68 Earth years,
 +
probably more than the longest lifetime of a typical adventurer in
 +
danger-ridden dungeons. If you still think it's not enough, you can
 +
make the variable unsigned and double the available period. You can
 +
even increase the variable length to 64 bits, and it will cover (gasp)
 +
some 292 trillion years. Now THAT should be enough even if your game
 +
starts at Big Bang...
 +
 +
 +
Basic Timekeeping
 +
 +
We'll start the coding part by defining some basic quantities:
 +
 +
#define MINUTE 60
 +
#define HOUR (60 * MINUTE)
 +
#define DAY (24 * HOUR)
 +
#define YEAR (365 * DAY)
 +
 +
These will be helpful in adding or substracting larger amounts of time
 +
to/from our scalar clock.
 +
 +
Next, we must write a function that will do for us the dirty work of
 +
calculating actual time representation. Programmers call that
 +
'breaking down' of the scalar value. Assuming the time units are
 +
always of equal length, we can achieve the task very easily without
 +
resorting to floating point arithmetics.
 +
 +
Here's a function I used in GSNband (slightly changed)
 +
 +
int break_scalar_time (int what)
 +
{
 +
switch (what)
 +
{
 +
case SEC:
 +
    return (sc_time % MINUTE);
 +
case MINUTE:
 +
    return ((sc_time / MINUTE) % 60);
 +
case HOUR:
 +
    return ((sc_time / HOUR) % 24);
 +
case DAY:
 +
    return ((sc_time / DAY) % 365);
 +
case YEAR:
 +
    return (sc_time / YEAR);
 +
default:
 +
return (0);
 +
}
 +
}    
 +
 +
(sc_time is my 32-bit time variable; SEC, MINUTE etc. are #defined modes
 +
the function is called with; they may be any value you want).
 +
 +
In short, to calculate the remainder corresponding to any unit, we first
 +
divide the scalar time by the amount of base units correspoding to that
 +
unit (note that in the first case sc_time is equivalent to sc_time / 1),
 +
and then take the modulus of it and the amount of units it takes to fill
 +
the next higher unit. The last case does not include the modulus, since
 +
there is no higher unit that a year, and we immediately know how many
 +
years have passed on our clock.
 +
 +
This is a rather unoptimised function that will not work well in a
 +
compiling environement that generates lots of extra code for each
 +
function call. It that case, it is better to rewrite the function header
 +
using pointers, like this:
 +
 +
int break_scalar_time (int *sec, int *min, int *hour, int *day, int *year)
 +
 +
And then call it after having initialized the variables:
 +
 +
int sec, min, hour, day, year;
 +
break_scalar_time (&sec, &min, &hour, &day, &year);
 +
 +
Yet another solution would be a structure to keep the information
 +
returned, or even better an union (since all the fields are of equal
 +
length).
 +
 +
 +
Months and Weeks
 +
 +
The next thing you want is a calendar. Unless, of course, the inhabitants
 +
of your world customarily refer to the likes of 'day 164 of the year'.
 +
For a calendar, you'll need months and perhaps weeks (if each months
 +
contains an equal number of weeks).
 +
 +
If you wanted to emulate the Gregorian calendar (without a leap day),
 +
your best bet would be to make two arrays like this:
 +
 +
char *month_names[12] =
 +
{
 +
  "January", "February" ...
 +
}
 +
 +
int month_table[12] = /* No. of first day of each month in a year (0-364) */
 +
 +
  0, 31, 59 ...
 +
};
 +
 +
(we're counting from 0 to be in common with the values break_scalar_time()
 +
returns)
 +
 +
And then we can calculate the month and day of month like this (with the result
 +
in out_str):
 +
 +
int day, month, i, j;
 +
int year_day = break_scalar_time(DAY);
 +
char *p;
 +
char *out_str;
 +
 +
for (i=0; i <= 12; i++)
 +
{
 +
if (year_day >= month_table[i])
 +
  {
 +
      month = i;
 +
      day = year_day - month_table[i] + 1;
 +
     
 +
      /* Take account of annoying English */
 +
      p = "th";
 +
      j = day % 10;
 +
      if ((day / 10) == 1) /* nothing */;
 +
      else if (j == 1) p = "st";
 +
      else if (j == 2) p = "nd";
 +
      else if (j == 3) p = "rd";
 +
 +
      (void)sprintf (out_str, "%d%s day of %s", day, p, month_names[i]);
 +
    }
 +
}
 +
 +
 +
What To Do With Time?
 +
 +
After we've written our timekeeping routines, we must consider how
 +
much time will elapse while the player is doing something, IOW, how
 +
fast will the game time progress. If you game employs large wilderness
 +
areas, you will probably want to hasten time flow while the player is
 +
there. OTOH, in a dungeon settings time should pass more slowly.
 +
 +
First, define the area of the basic grid of your dungeon, if you
 +
haven't already. For example, in Angband this is 10 feet (somewhat
 +
over three metres). How fast can you expect the player to cover a
 +
distance of ten feet, moving at a somewhat cautious pace? What about
 +
combat - how long does a blow take? (I based time elapsed between blows
 +
on dexterity and weapon weight.) Do monsters act in a separate time
 +
piece or does time not move while they have a turn? How fast do you use
 +
magical items? Change levels? Eat something? (think about weight/volume)
 +
Etc. etc. Providing for all actions the player may undertake is vital
 +
if you want the time flow to correspond, at least vaguely, to what
 +
you've been doing.
 +
 +
 +
Some other ideas employing the concept of (recurring) time:
 +
 +
- Shops that are open 7/11 or on certain weekdays
 +
- NPCs that can be had only at specific hours (otherwise they sleep,
 +
  work, wander away etc.)
 +
- Quests given may be restricted to a deadline
 +
- Artifacts that activate a set number of times per day (or, if that's
 +
  too sparse, per hour). Same goes for recharging time.
 +
- Your character may have to spend a few hours, or even days, to learn
 +
  new spells at a guild.
 +
- Article prices fluctuate over time (probably in a random way, unless
 +
  you have an economy model handy. :)
 +
- Delayed magical effects, like a retarded fireball or a time
 +
  bomb/grenade (the concept of delayed function calls probably merits
 +
  its own article)
 +
 +
Not to mention time travel...
 +
 +
Any questions, corrections or notes? Mail naskrent@artemida.amu.edu.pl
 +
 +
------
 +
This article is (c) 2000 by Gwidon S. Naskrent. Any further copying,
 +
publication or revisal is subject to the explicit permission of the
 +
author, except when the copying or revisal occurs in the context of your
 +
viewing this page in a web browser.
 +
------
 +
 +
= Sureal Time - Damian Bentley [Damian.Bentley@dsto.defence.gov.au]. =
 +
 +
COPYRIGHT AND LICENSE
 +
The Sureal Time algorithm is a part of Interhack. Interhack is copyright (c) 1996-
 +
1999 by Damian Bentley. Please contact bendchon@mehta.anu.edu.au for a copy
 +
of the license. Basically feel free to copy and pass this document on - Sureal Time is
 +
something that anyone making a roguelike game can use.
 +
 +
 +
INTRODUCTION
 +
This document describes the Sureal Time algorithm. What is it, and why was it
 +
developed? There is a group of games available today referred to as roguelike games. They
 +
consist of a set of levels (in most cases, dungeons), with a player running around killing
 +
monsters, performing tasks, and in general having a good time. In many cases they are text
 +
based, and almost all are single player.
 +
With single player roguelike games, movement is usually turn based. In other
 +
words, the player makes a move, and then all the monsters make their moves. In the
 +
development of a multi player version of a roguelike game this becomes a problem as will
 +
be discussed later.
 +
One solution to this problem is described here. Sureal Time is the combination of
 +
real time movement and turn based movement. It was developed by many people who have
 +
worked on Interhack, with each change or idea adding to the advantages of the algorithm.
 +
Feedback on Sureal Time is appreciated, including ways in which to improve this
 +
document, or questions that have not been answered by this document.
 +
 +
 +
THE PROBLEM
 +
As it turns out, the problem is quite simple. But first we shall start with current
 +
methods in single player roguelike games.
 +
With a single player making moves, it is quite easy to create a simple loop where
 +
the player makes a move until the die, quit or save. Then everything else that happens in the
 +
game happens. That is: monsters move, checks will be made to make sure the player is
 +
alive, and so on. Given that some roguelike games require some thought at some stages (oh
 +
heck I am almost dead, what can I do), this is good because a player can stop and think for
 +
as long as they want before making a move.
 +
However when there are several players, problems crop up. If two players are in
 +
the same room, what happens to movement? Does one player make a move, then the other
 +
player? Can both players move at any time they want? If a player has a fast connection, do
 +
they move faster? What happens to players that have intrinsic speed? All these problems
 +
need to be solved in a way that is fair to players.
 +
In addition to the problem described above, there are other aspects to be looked at.
 +
For instance, what happens when a player looses a connection, and how do monsters now
 +
attack players? One of the most important parts of the Sureal Time algorithm is in handling
 +
events when a players keyboard action lags behind. What does a player do if a move is
 +
forced in Sureal Time?
 +
So the problem is this: When there are two or more players in close proximity to
 +
each other, how should movement occur?
 +
 +
 +
POSSIBLE SOLUTIONS
 +
The first and most obvious solution to the problem is to use real time. Each player
 +
has a certain amount of time to make a move before all the monsters and other events
 +
occur. It does not matter if the player has a fast or slow connection. It does not matter home
 +
many players are in the game. All players are placed on the same level of game play.
 +
Real time has one major drawback: A player can not stop and think about what
 +
move to make next. If a player wishes to spend a minute looking through their inventory to
 +
see what they can drop, they are still under the influence of the real time - they could be
 +
attacked at any point in time.
 +
Another alternative is fully turn-based movement. If there are three players A, B
 +
and C, player A makes a move, then player B, and finally player C. This repeats over and
 +
over again. This allows players to stop and think about their next move. There is one very
 +
obvious problem with this solution. If player B stops and looks through their inventory,
 +
player C and player A, are kept waiting for possibly long periods of time.
 +
Both real time and turn-based movement have their advantages. Real time allows
 +
the game to flow on no matter what is happening. Turn based allows players to stop and
 +
think about how the next move should be made. So why not combine both of these
 +
solutions to form what shall be called Sureal Time. Essentially Sureal Time is like adding a
 +
real-time time limit onto turn based movement.
 +
 +
 +
SUREAL TIME
 +
So now for the gory details of how to actually make Sureal Time work. First we
 +
need to look at players that are grouped, and isolated players. If a player is on a level with
 +
no other players, there is no need to use anything other than turn-based movement. The
 +
simple turn based movement is sufficient to cover this case, as it allows a player to play at
 +
their own pace.
 +
If there are two players on a level, it is more likely that they will need some sort of
 +
movement control. When and where does this take place? If one player is on one side of the
 +
level, and the other player is on the other side of the level, they are not going to interact
 +
with each other much. So even though two players are on the same level, they may not need
 +
to have movement control.
 +
When is movement control needed? As two players get closer and closer, their
 +
actions are going to start to effect each other. A player that zaps a wand or casts a spell
 +
might effect the other player. So if we determine the largest area of affect for most events a
 +
player can cause, a boundary is formed. If this boundary is 16 units, when a player is within
 +
16 units to another player, both players now have some form of movement control. When
 +
two players are further apart than this, they live in their own little turn-based world.
 +
Now lets consider three players: A, B and C. If player A is within 16 units of
 +
player B, and player B is within 16 units of player C, but player A and player C are outside
 +
the 16 unit range, what happens? Simply all three players come under the same movement
 +
control. This is a simple case.
 +
Next, consider four players: A, B, C and D. What if player A and player B are
 +
together, and player C and player D are together. However these two groups of players are
 +
not within the same 16 units. It would not be fair to place all four players in the same
 +
movement control, so two different "forms" of movement control are used.
 +
Now we can bring this al together into a simple set of two rules:
 +
 +
Rule 1) A player that is outside a radius of 16 units of all other players on the same level is
 +
placed in a turn based movement.
 +
Rule 2) Players or groups of players that are within 16 units of another player or group of
 +
players are placed in the same group. These groups are "controlled movement" groups.
 +
 +
The next aspect of Sureal Time is what happens to players that have movement
 +
control? First of all, if no players in the controlled group move, nothing happens. This
 +
means that players could talk to each other to determine what should happen next. Players
 +
would be able to check their inventory for a particular item.
 +
 +
Rule 3) When groups are in controlled movement, if no players move, then no turns are
 +
made in the game.
 +
 +
When a player makes a move, what determines how and when other players
 +
move? The first part in answer to this question is related to the speed of the connection a
 +
player has. A player with a fast connection would be able to make moves faster. A player
 +
with a slow connection would make fewer moves. In addition to this aspect, players can
 +
sometimes be "faster" in the game: intrinsic speed.
 +
When several players are connected to a machine, the speed of a connection can be
 +
obtained. Obviously the slowest connection is the best one to select for the speed of a group
 +
of players, because it makes all movement fair on all players. If a player has an intrinsic
 +
speed, all other players' base connection speed is modified to reflect this.
 +
 +
Rule 4) All players have a base connection speed. In a group of players, the slowest
 +
connection speed is selected as the timeout basis for movement.
 +
Rule 5) The base connection speed is only ever increased.
 +
Rule 6) A player with an intrinsic of speed modifies the base connection speed of all other
 +
players in a group.
 +
 +
So what happens if a player does not move at all, and another player close to them
 +
moves? In this case the player that does not move has a certain amount of time to move
 +
after the other player has moved. Once this time has ended, they will be forced to move.
 +
This introduces a whole new problem, as to what moves are made when a player is forced
 +
to move.
 +
The moves that are forced by the computer are usually "intelligent". For example,
 +
a player that is in combat will remain in combat unless they are badly injured or in need of
 +
food badly. These rules are expanded in detail later. Once a player that is being forced to
 +
move, and has made more than thirty moves, they are automatically saved.
 +
In addition there is also the problem of a player that has lost their connection and
 +
then enters into Sureal Time. If it is know that a player has lost their connection they are
 +
automatically saved. Otherwise the player makes forced moves until they have exceeded
 +
the thirty moves limit, and are saved by default.
 +
 +
Rule 7) After a player in a group makes a move, all other players must move within a
 +
certain time.
 +
Rule 8) Players that do no move within the time limit are forced to move, with the
 +
computer making an intelligent move, such as attacking the last attacked monster (see
 +
forced move rules).
 +
Rule 9) If a player is forced to move more than 30 times in a row, they are automatically
 +
saved.
 +
Rule 10) If a player looses their connection, they are automatically saved.
 +
Rule 11) A player can enter into Sureal Time even if they are not moving.
 +
 +
In some cases a lag in the connection between the client and server could cause a
 +
players key-press to arrive at the server after a forced move has occurred. If the key-press
 +
arrives within a certain amount of time after the forced move, it is ignored. This ignore time
 +
can be set by the player.
 +
 +
Rule 12) After a forced move, all key-presses from the player forced to move will be
 +
ignored for an amount of time specified by the user.
 +
 +
Additionally there is also a reaction time involved. This is considered a "fair" time
 +
by which most players will see another player move, think of an appropriate move, and
 +
make the move. This reaction time makes a player being forced to move slower than a
 +
player moving by its self. Due to this slower speed, a player being forced to move has a
 +
tally for forced moves to be made. All moves on this tally will be made unless the player
 +
being forced to move presses a key to move.
 +
 +
Rule 13) A reaction time will be added to the time before a player is forced to move. The
 +
reaction time should allow for a player to see a move, think of a move, and make it.
 +
Rule 14) For every move that forces a move on another player, the player that is forced to
 +
move will have a tally kept. This tally will be reduced every time the player is forced to
 +
move. When it reaches zero no more forced moves will be made.
 +
Rule 15) A player that makes a move will reduce their forced move tally to zero.
 +
 +
That appears to be most of the main parts of Sureal Time. There are some
 +
additional problems that do begin to appear. For instance, what happens with monsters no
 +
there is more than one player? As said earlier, monster AI has to be much better than
 +
before, and able to cope with the problem where they might have three of four players
 +
attacking them at once.
 +
The solution is fairly simple. Every monster is "attached" to the monster that is
 +
closest to them. In the case where two players are of equal distance, one of those players is
 +
selected at random. Some people consider this to be unfair for the monster: If two players
 +
are close (but not next to) a monster, both could attack it. However if you consider both
 +
these players would more than likely be in Sureal Time, the monster would receive at least
 +
as many moves as a forced move player would.
 +
As two or more players get closer to a monster, it will become "unfair" for the monster.
 +
Monster may need to be harder to kill, or attack in a group. This aspect of the game design
 +
is left to the designer to decide. A combination of more monsters, monsters that attack in a
 +
group, and smarter monsters is recommended.
 +
 +
Rule 16) Every monster is attached to the player they are closest to.
 +
Rule 17) When the player a monster is attached to makes a move, the monster makes a
 +
move.
 +
 +
These 17 rules are a fairly good summery of Sureal Time. In addition to these
 +
rules, an appendix at the end includes a set of rules recommended for forced moves. It
 +
seems fairly simple, however putting these rules into practice is tricky, as will be seen in
 +
the example source code.
 +
 +
 +
 +
EXAMPLE SOURCE CODE
 +
Before providing sources that implement Sureal Time, there are a few things to
 +
say. To start with, this code only shows how the movement aspect of Sureal Time works.
 +
Aspects such as the monster movement are left out. In addition, rule 12 of Sureal Time (key
 +
presses ignored for a certain time) has not been delt with. This is viewed as a small addition
 +
to the source code - something has to be left out to challenge people.
 +
Writing Sureal Time code is not something to be undertaken lightly. The original
 +
version of the source code was written in Java, and did not use millisecond timers. The
 +
second version was in c/c++ and had a few bugs, and found a few problems in the original
 +
implementation. What is provided here is the third version of Sureal Time. All up
 +
development took about 20 hours.
 +
Most of the source code is documented, however the algorithm basically follows
 +
along the following lines:
 +
 +
1. Continue looping until input is received (from the keyboard). Simulates incoming data
 +
from players. (This looping should be based on a sleep loop. The next event to occur is set
 +
as the length of time to sleep. If no events are selected, sleep continuously until an input is
 +
received).
 +
2. If the key-press is 'Q' quite the program.
 +
3. If the key-press is for a player, store the keypress (the player is no longer forced to
 +
move).
 +
4. If the sleep time has ended, check for forced moves. If there are forced moves, make
 +
them.
 +
5. If the sleep time has ended, make moves, and update the details of players. If other
 +
players are on the timer that a player has just moved on, set the forced move timer for each
 +
player.
 +
 +
The first file is the Sureal Time header file "sureal.h". Cut and paste this to a file.
 +
The second file is "sureal.c" containing the main source for the algorithm. Again cut and
 +
paste into a file. Compile this code with your preferred compiler: "cc -o sureal sureal.c"
 +
Once this has been done, run the program with "sureal". When running, press 'Q'
 +
and enter to quit. In the configuration below, press '2' then enter. This simulates a move by
 +
player 2. There are three players in this example: 0, 1 and 2. 0 and 1 are on the same timer.
 +
If you enter '0', player 1 will eventually be forced to move. To see more of what is
 +
happening, recompile the source code: "cc -DDEBUG -o sureal sureal.c".
 +
 +
Now for a few quick hints and tips on how to modify the source code. First of all,
 +
in most cases you should only need to modify the header file "sureal.h". NPLAYERS is the
 +
number of players in the "game". If you increase this, do not forget to add another element
 +
to the array of players created just below the NPLAYERS define. For each player created,
 +
the first number is the id / timer the player is on. The last two numbers are the
 +
seconds:milliseconds for the players timeout.
 +
LEADWAY is what has been called in this document the "reaction time". The
 +
greater this value, the longer period of time the player has to respond to a move made by
 +
another player. A side effect of this is if a player is forced to move, it will take longer
 +
before the forced move is made if LEADWAY is increased. MAXFORCED specifies the
 +
number of moves before a player would be forced to quit. In the code below this has been
 +
set to 10 so as to speed the results up.
 +
The CSureal class is where all the important timers and numbers are kept track of.
 +
Refer to the comments in the header file as to what each of these variables are. For most of
 +
the rest of the source code in "sureal.c" please refer to the comments. It looks complicated
 +
mainly because of the need for milli second timing.
 +
The only thing to really take note of in the actual source code is the select() call
 +
from the main function. This call has been used for two purposes. Firstly it allows
 +
millisecond timing. Secondly, it can be combined with a socket setup such that connections
 +
and data from the outside world are received here. Essentially by pressing a key the user is
 +
simulating incoming data from a player.
 +
My final comment is this: Do not just look at the sources. Try it out to see how it
 +
works. Most likely some of you will have trouble of some sort. Please contact
 +
bendchon@mehta.anu.edu.au and report any problems or bugs so this document
 +
can be kept up to date and others have fewer problems.
 +
 +
-------------------------------------------------------------
 +
#ifndef _sureal_h_
 +
#define _sureal_h_
 +
 +
#include <sys/time.h>
 +
#include <unistd.h>
 +
 +
// Redefine a few of the timer functions
 +
#ifdef timerisset
 +
#undef timerisset
 +
#endif
 +
#ifdef timercmp
 +
#undef timercmp
 +
#endif
 +
#ifdef timerclear
 +
#undef timerclear
 +
#endif
 +
 +
#define timerisset(tvp)\
 +
((tvp).tv_sec || (tvp).tv_usec)
 +
#define timercmp(tvp, uvp, cmp)\
 +
((tvp).tv_sec cmp (uvp).tv_sec ||\
 +
(tvp).tv_sec == (uvp).tv_sec &&\
 +
(tvp).tv_usec cmp (uvp).tv_usec)
 +
#define timerclear(tvp)\
 +
((tvp)->tv_sec = (tvp)->tv_usec = 0)
 +
 +
// Add a few timer functions
 +
#define timershow(tvp)\
 +
(tvp).tv_sec << "-" << (tvp).tv_usec
 +
#define timeradd(tvp, uvp)\
 +
{(tvp)->tv_sec += (uvp).tv_sec;\
 +
(tvp)->tv_usec += (uvp).tv_usec;\
 +
if ((tvp)->tv_usec > 1000000) {\
 +
    (tvp)->tv_usec -= 1000000;\
 +
    ((tvp)->tv_sec)++; }; }
 +
#define timersub(tvp, uvp)\
 +
{(tvp)->tv_sec -= (uvp).tv_sec;\
 +
(tvp)->tv_usec -= (uvp).tv_usec;\
 +
if ((tvp)->tv_usec < 0) {\
 +
    (tvp)->tv_usec += 1000000;\
 +
    ((tvp)->tv_sec)--; }; }
 +
 +
typedef struct timeval Timeval;
 +
 +
class CSureal {
 +
public:
 +
    int key;            // == 0 when no key has been pressed
 +
    int STTimer;        // Timer player is associated with
 +
    Timeval STTimeout;  // Timeout value (connection speed)
 +
    Timeval STNext;    // When the next move can be made
 +
    Timeval STForced;  // When the player is forced to move
 +
    int STForcedRemain; // Forced moves yet to be made
 +
    int STnForced;      // Number of contiguous forced moves
 +
    CSureal(int a, Timeval b) {
 +
        key = 0; STTimer = a; STTimeout = b;
 +
        STnForced = 0; STForcedRemain = 0;
 +
        timerclear(&STNext); timerclear(&STForced); };
 +
    CSureal(int a, long b, long c) {
 +
        key = 0; STTimer = a;
 +
        STTimeout.tv_sec = b; STTimeout.tv_usec = c;
 +
        timerclear(&STNext); timerclear(&STForced);
 +
        STnForced = 0; STForcedRemain = 0; };
 +
};
 +
 +
// This is just a list of sureal time class for simulation
 +
#define NPLAYERS 3
 +
CSureal list[NPLAYERS] = {
 +
    CSureal(1, 2, 0),
 +
    CSureal(1, 3, 0),
 +
    CSureal(2, 4, 0)
 +
};
 +
 +
Timeval LEADWAY = {0, 500000};
 +
#define MAXFORCED 10
 +
 +
// These are the functions for use in sureal time
 +
Timeval * sleepTime();
 +
void keyPressed(int, int);
 +
void forcedMoves();
 +
void makeMoves();
 +
 +
#endif
 +
 +
 +
-------------------------------------------------------------
 +
#include <sys/types.h>
 +
#include <sys/time.h>
 +
#include <iostream.h>
 +
#include <unistd.h>
 +
#include <stdlib.h>
 +
#include <time.h>
 +
 +
#include "sureal.h"
 +
 +
int main() {
 +
    srand(time(NULL));
 +
    while (1) {
 +
        // Sleep until the next action happens
 +
#ifdef DEBUG
 +
        cout << "Sleeping\n";
 +
#endif
 +
        fd_set rfds; FD_ZERO(&rfds); FD_SET(0, &rfds);
 +
        int retval;
 +
        retval = select(1, &rfds, NULL, NULL, sleepTime());
 +
#ifdef DEBUG
 +
        cout << "Awake\n";
 +
#endif
 +
 +
        // Deal with any key presses
 +
        if (retval > 0) {
 +
            int c;
 +
            do {
 +
                c = cin.get();
 +
                if (c == 'Q') return 0;
 +
                if (c >= '0' && c <= ('0'+NPLAYERS-1))
 +
                    keyPressed(c-'0',65);
 +
            } while (c != 10);
 +
        }
 +
 +
        // Check for forced moves
 +
        forcedMoves();
 +
 +
        // Make other moves
 +
        makeMoves();
 +
    }
 +
    return 0;
 +
}
 +
 +
// sleepTime returns minimum time until next expected action
 +
// it returns NULL when no action is expected
 +
Timeval st;
 +
Timeval * sleepTime() {
 +
    Timeval zt; timerclear(&zt);
 +
    Timeval ct; gettimeofday(&ct, NULL);
 +
    int stSet = 0;
 +
    timerclear(&st);
 +
 +
    for (register int i = 0; i < NPLAYERS; i++) {
 +
        if (timercmp(list[i].STNext, ct, >) &&
 +
          (timercmp(list[i].STNext, st, <) || stSet == 0)) {
 +
          st = list[i].STNext;
 +
          stSet = 1;
 +
        }
 +
        if (timercmp(list[i].STForced, ct, >) &&
 +
          (timercmp(list[i].STForced, st, <)
 +
            || stSet == 0)) {
 +
          st = list[i].STForced;
 +
          stSet = 1;
 +
        }
 +
    }
 +
 +
    timersub(&st, ct);
 +
#ifdef DEBUG
 +
    cout << "Sleeping for " << timershow(st) << endl;
 +
#endif
 +
    if (timercmp(st, zt, <))
 +
        return NULL;
 +
    return &st;
 +
}
 +
 +
// Player p has pressed key
 +
void keyPressed(int p, int k) {
 +
    // if player already pressed a key, ignore this key press
 +
    if (list[p].key != 0) return;
 +
    // The player is no longer forced to move
 +
    timerclear(&(list[p].STForced));
 +
    // Store the keypress
 +
    list[p].key = k;
 +
    // Reset the contiguous count of forced moves
 +
    list[p].STnForced = 0;
 +
    // Reset the remaining forced moves to be made
 +
    list[p].STForcedRemain = 0;
 +
    Timeval ct; gettimeofday(&ct, NULL);
 +
    cout << "Player " << p << " pressed key "
 +
        << timershow(ct) << endl;
 +
}
 +
 +
// Force a player to move
 +
void forcedMoves() {
 +
    Timeval ct; gettimeofday(&ct, NULL);
 +
    Timeval zt; timerclear(&zt);
 +
    for (register int i = 0; i < NPLAYERS; i++)
 +
        if (timercmp(list[i].STForced, ct, <) &&
 +
            timercmp(list[i].STForced, zt, !=)) {
 +
            // The player is no longer forced to make a move
 +
            timerclear(&(list[i].STForced));
 +
            // Player can move after their timeout finishes
 +
            timerclear(&(list[i].STNext));
 +
            timeradd(&(list[i].STNext), ct);
 +
            if (list[i].STTimer != i)
 +
                timeradd(&(list[i].STNext),
 +
(list[list[i].STTimer].STTimeout))
 +
            else
 +
                for (register j = 0; j < NPLAYERS; j++)
 +
                    if (j != i && list[j].STTimer == i) {
 +
                        timeradd(&(list[i].STNext),
 +
(list[list[i].STTimer].STTimeout))
 +
                        break;
 +
                    }
 +
 +
            // Add one to count of contiguous forced moves
 +
            // If player more than MAXFORCED moves, they quit
 +
            if (list[i].STnForced++ > MAXFORCED)
 +
                cout << "Player " << I
 +
                    << " now forced to quit\n";
 +
 +
            // Make sure no other forced moves to be made
 +
            cout << "Player " << i << " forced at  "
 +
                << timershow(ct) << endl;
 +
            list[i].STForcedRemain--;
 +
            if (list[i].STForcedRemain < 0)
 +
                list[i].STForcedRemain = 0;
 +
            if (list[i].STForcedRemain > 0) {
 +
                Timeval ft; gettimeofday(&ft, NULL);
 +
                timeradd(&ft,
 +
list[list[i].STTimer].STTimeout);
 +
                timeradd(&ft, LEADWAY);
 +
                list[i].STForced = ft;
 +
#ifdef DEBUG
 +
                cout << "Setting forced timer again for "
 +
                    << I << " to " << timershow(ft) << endl;
 +
#endif
 +
            }
 +
        }
 +
}
 +
 +
// Make moves if player has pressed key and timeout finished
 +
void makeMoves() {
 +
    Timeval ct; gettimeofday(&ct, NULL);
 +
    Timeval zt; timerclear(&zt);
 +
    for (register int i = 0; i < NPLAYERS; i++)
 +
        if (list[i].key != 0
 +
            && timercmp(list[i].STNext, ct, <=)) {
 +
            // The player is no longer forced to make a move
 +
            timerclear(&(list[i].STForced));
 +
            // Player can move after their timeout finishes
 +
            timerclear(&(list[i].STNext));
 +
            timeradd(&(list[i].STNext), ct);
 +
            if (list[i].STTimer != i)
 +
                timeradd(&(list[i].STNext),
 +
(list[list[i].STTimer].STTimeout))
 +
            else
 +
                for (register j = 0; j < NPLAYERS; j++)
 +
                    if (j != i && list[j].STTimer == i) {
 +
                        timeradd(&(list[i].STNext),
 +
(list[list[i].STTimer].STTimeout))
 +
                        break;
 +
                    }
 +
            cout << "Player " << i << " moved at    "
 +
                << timershow(ct) << endl;
 +
            list[i].key = 0;
 +
 +
            // If other players on our timer, force them to
 +
            // move in the near future
 +
            for (register int j = 0; j < NPLAYERS; j++)
 +
                if (j != I &&
 +
                    list[j].STTimer == list[i].STTimer &&
 +
                    list[j].key == 0 &&
 +
                    timercmp(list[j].STNext, ct, <)) {
 +
                        if (list[j].STForcedRemain < 1) {
 +
                            Timeval ft; gettimeofday(&ft,
 +
NULL);
 +
                            timeradd(&ft,
 +
list[list[j].STTimer].STTimeout);
 +
                            timeradd(&ft, LEADWAY);
 +
                            list[j].STForced = ft;
 +
                        }
 +
                        list[j].STForcedRemain++;
 +
#ifdef DEBUG
 +
                        cout << "Setting forced timer for "
 +
                            << j << " to "
 +
                            << timershow(ft) << endl;
 +
                        cout << "\tForced count: "
 +
                            << list[j].STForcedRemain
 +
                            << endl;
 +
#endif
 +
                    }
 +
        }
 +
}
 +
 +
 +
APPENDIX A - SUREAL TIME RULES
 +
The following are all of the Sureal Time rules without any explanations:
 +
 +
Rule 1) A player that is outside a radius of 16 units of all other players on the same level is
 +
placed in a turn based movement.
 +
Rule 2) Players or groups of players that are within 16 units of another player or group of
 +
players are placed in the same group. These groups are "controlled movement" groups.
 +
Rule 3) When groups are in controlled movement, if no players move, then no turns are
 +
made in the game.
 +
Rule 4) All players have a base connection speed. In a group of players, the slowest
 +
connection speed is selected as the timeout basis for movement.
 +
Rule 5) The base connection speed is only ever increased.
 +
Rule 6) A player with an intrinsic of speed modifies the base connection speed of all other
 +
players in a group.
 +
Rule 7) After a player in a group makes a move, all other players must move within a
 +
certain time.
 +
Rule 8) Players that do no move within the time limit are forced to move, with the
 +
computer making an intelligent move, such as attacking the last attacked monster (see
 +
forced move rules).
 +
Rule 9) If a player is forced to move more than 30 times in a row, they are automatically
 +
saved.
 +
Rule 10) If a player looses their connection, they are automatically saved.
 +
Rule 11) A player can enter into Sureal Time even if they are not moving.
 +
Rule 12) After a forced move, all key-presses from the player forced to move will be
 +
ignored for an amount of time specified by the user.
 +
Rule 13) A reaction time will be added to the time before a player is forced to move. The
 +
reaction time should allow for a player to see a move, think of a move, and make it.
 +
Rule 14) For every move that forces a move on another player, the player that is forced to
 +
move will have a tally kept. This tally will be reduced every time the player is forced to
 +
move. When it reaches zero no more forced moves will be made.
 +
Rule 15) A player that makes a move will reduce their forced move tally to zero.
 +
Rule 16) Every monster is attached to the player they are closest to.
 +
Rule 17) When the player a monster is attached to makes a move, the monster makes a
 +
move.
 +
 +
 +
APPENDIX B - FORCED MOVEMENT RULES
 +
The following are a relatively "intelligent" set of rules to follow when a player is
 +
forced to move. It is more than likely that other rules may need to be included. I would like
 +
to hear comments on this section:
 +
 +
Rule 1) When no other rules apply, a player repeats their last action. A player that was
 +
moving, continues to move, a player that was attacking, continues to attack.
 +
Rule 2) It is not safe for a player to attack or move if they are hungry, or lacking hit points.
 +
Rule 3) A player is lacking hit points if they have less than 10% or their total.
 +
Rule 3) If a player is confused, stunned, or blind, they wait unless the opportunity exists to
 +
attack safely.
 +
Rule 4) A player that is not in attack mode, and is hungry eats.
 +
Rule 5) A player that is almost fainting eats.
 +
Rule 6) If a moving player comes to a door they open it (open, lock pick, keys, kick).
 +
Rule 7) If a moving player comes to a dead end, they search for 15 units of time until
 +
something changes. If nothing changes, they player resumes in the opposite direction.
 +
Rule 8) If something changes while searching the player continues in that direction.
 +
Rule 9) A player that can not move left, goes forward. A player that can not move forward,
 +
moves right. A player than can not move right turns around and goes back the way they
 +
came.
 +
Rule 10) If a moving player enters a room, they will seek out the best items from any
 +
objects.
 +
Rule 11) A moving player will try to remain in Sureal Time, following other players.
 +
Rule 12) If a player sees a monster it will attack at long distance first (throwing weapons,
 +
potions, zapping known wands).
 +
Rule 13) While in close attack, monsters will use weapons, spells, wands etc. The method
 +
of attack selected is that which is considered best for the situation. In most cases weapon
 +
based attack should be selected as the best method. However a wizard with 10% failure rate
 +
on magic missile may opt to use that spell.
 +
Rule 14) Players forced to move will not use objects being carried unless for offensive or
 +
defensive purposes. If an object is unknown, it will not be used.
 +
 +
= Monsters Who Carry - James Burton [burton@cs.stanford.edu]. =
 +
 +
In _Civilization and its Discontents_, Sigmund Freud describes Man as a kind
 +
of "cybernetic god" -- by ourselves we are weak, vulnerable, and impotent,
 +
but with our machines we can move mountains, build or destroy worlds, and
 +
make Roguelike games in our spare time.  This is a vitally important
 +
observation in Roguelikes, where the power of a character can be summed up
 +
in two things: a) Their own statistics, and b) what they're carrying.  A
 +
mighty wizard with Raal's Tome of Destruction is a lot more powerful than
 +
one without, as is a plevel 50 warrior with Ringil and Speed Boots a lot
 +
more frightening than a plevel 50 warrior with chainmail and a whip.
 +
 +
And so it should be with monsters, and is in some (NetHack) games.  That
 +
gnome is easy bait -- until he fires up his lightsaber.
 +
 +
You should *strongly* consider allowing monsters both to carry and _use_
 +
objects, and to drop them afterwards.  For one, it provides a lot more
 +
variety.  Second, it adds realism, in that it makes creatures with *hands*
 +
much more intimidating.  In Roguelike World, a sabre-tooth tiger is more
 +
dangerous than a small kobold because it is faster and stronger.  In the
 +
Real World (or at least the version that has small kobolds in it), our
 +
kobold is the deadlier because he could carry *and use* something much
 +
nastier than sabre-teeth.  Third, it adds variety.  Having hundreds of
 +
monsters is cool.  But if you let them hold an item (and a good item system
 +
will have thousands of different items, by combining different traits
 +
together, as in the "Whip of Freezing" and so on), then you have hundreds of
 +
thousands of combinations.  Let them hold multiple items, and pick new items
 +
up, and the variety is astronomical -- and has a real impact on gameplay.
 +
 +
Now for some coding ideas.  In my own game (not yet released), I have
 +
decided that creatures should have the same ability to wear/wield/carry
 +
items as the player -- unless it is biologically or mentally unable to (more
 +
on this below).  Why is it that in so many games the player is a walking
 +
blacksmith's shop, but the creatures seem to have no material needs except
 +
bags full of gold?  Since I also leave open the ability to hold one item
 +
inside another item, and even put creatures into items (like tigers into
 +
cages), I find a *tree* structure to be most efficient.
 +
 +
Everyone learns (or should learn) all about making trees in their first
 +
computer course, and all about the optimising of trees in their first theory
 +
course, so I won't go too deep into the data structure (look on the Internet
 +
if you need it).  For this article, I am defining a tree as a collection of
 +
objects such that each object has exactly one "parent" object, except for
 +
one object which is the "root" of the tree.  A parent can have any number of
 +
children, including none.  The resulting shape looks like a tree, hence the
 +
name.
 +
 +
I like objects, so that's how I define my structures.  The first object I
 +
need is a Unit, which is my name for an "Item or Creature".  So into Units
 +
we put information that applies to both: weight, name, etc.  Actually I
 +
implement these not as data but as virtual functions along the lines of
 +
getWeight() and getName() -- this latter method is more "OO", but I could
 +
understand if you used variables instead for the sake of efficiency.  I also
 +
keep a small array of all the possible child nodes -- I use an array because
 +
I keep an arbitrary limit of no more than 20 child nodes, and though a list
 +
would be more efficient it's also complicated.  I then subclass this into
 +
Items and Creatures.  You might think of subclassing items into Weapons,
 +
Armor, and so on, but I didn't find it worth it.  It *is* worth it to
 +
subclass "Creature" into "Player", though.  So you get an object definition
 +
something like this:
 +
 +
OBJECT:    Unit
 +
{
 +
# Array of child units
 +
UnitPtr children[MAX_UNITS]
 +
 +
# Keep reference to the parent too -- this is technically unnecessary and
 +
requires a bit more care in your
 +
# tree-manipulation functions, but you'll thank me the first time you have a
 +
unit and want to know what
 +
# its parent is.  If parent is NULL then the unit is on the map somewhere.
 +
UnitPtr parent
 +
 +
# Some tree functions you should implement
 +
detach()    # Detach node from its parent
 +
destroy()  # Destroy this and all children
 +
attach(UnitPtr newParent) # Attach to another node, detaching if necessary
 +
replace(UnitPtr newUnit) # Put the new unit in this position, and delete
 +
self
 +
 +
# Common unit functions
 +
getWeight()          # Object weight
 +
getTotalWeight()  # Weight of object and all its children
 +
getName()
 +
.
 +
}
 +
 +
OBJECT:  Creature  EXTENDS  Unit
 +
{
 +
move()      # Move the creature
 +
getHPs()  # Get creature hit points
 +
.
 +
}
 +
 +
OBJECT:  Item  EXTENDS  Unit
 +
{
 +
itemType # It's more OO to subclass items, but what the heck
 +
damage              # In the case of weapons
 +
isWielded            # Boolean, if true then the parent (a creature) is
 +
wielding this.  The value is
 +
.                      # meaningless unless the parent is a creature
 +
.
 +
}
 +
 +
I won't get into all the cool things you can do with trees: how easy it is
 +
to move nodes around, and recurse or iterate over them, and so on --
 +
instead, I will recommend that you put some time into adding some good tree
 +
manipulation functions, probably build right into the Unit class (but *not*
 +
as virtual methods, as they shouldn't need to be overridden, and you really
 +
want these to be efficient as you'll be using them a lot).  The four
 +
functions I stuck into the Unit object above should be a good start.  Do
 +
make sure if you have a limit on child nodes that methods like "attach" can
 +
fail gracefully, because at some point something in your program is going to
 +
try to exceed that limit (you could of course always test before attaching a
 +
new child, but why bother when you can just put the test in the attach
 +
routine itself?).
 +
 +
I will point out what I found most useful about trees in a roguelike game:
 +
that you can deal with only the root node, and it will affect all the child
 +
nodes.  For example, let's say I drop a chest.  That means detaching the
 +
chest from my own inventory hierarchy (so it becomes the root node of its
 +
own tree), and put it on the ground (the map, of course, can hold pointers
 +
to Units -- that's how creatures and items are held on the map!).  The cool
 +
thing: all the child nodes go with it, so the items in the chest are moved
 +
automatically, in constant time!
 +
 +
Now how do we return this to the question of monsters?  In my trees, there
 +
are clearly four kinds of relationships: an item can contain an item, an
 +
item can contain a creature, a creature can contain an item, and a creature
 +
can contain a creature.  I interpret each of these differently.  An item
 +
containing an item I think of as physical containment -- like a sword in a
 +
chest, a scroll in a bag, and so on (I suppose I could also see it as a
 +
battery in a flashlight or a bullet in a gun, but there aren't such things
 +
in my game).  An item containing a creature refers to some kind of caging --
 +
a bird in a birdcage or a ghost in a magic ghosttrap, etc.  A creature
 +
containing an item is obvious -- that's the creature's inventory!  And a
 +
creature containing a creature means the contained creature is swallowed (or
 +
would; I don't actually use this anywhere in the game).
 +
 +
So what happens if a monster is killed?  Simple: he simply transforms into
 +
(is replaced with) a corpse, which is an item.  Or more specifically, a
 +
*container* item, like a chest or bag.  See?  All the things he is carrying,
 +
by the definitions we're using, become items contained by the corpse.  This
 +
way we avoid the clutter you get in, say, Angband, where the last act of a
 +
powerful unique is apparently to throw his belongings all over the room
 +
(since you don't have stacks of items on the floor in Angband).  Getting
 +
items from the corpse is handled just like getting them from a treasure
 +
chest (and can be quite as dangerous).
 +
 +
So now we've handled data structures, but how do we decide what monsters
 +
actually carry?  There are three relationships a monster can have with an
 +
item, and for each of them I have a flag.  First, is it possible for the
 +
monster to carry it?  This usually involves having hands, though I suppose
 +
telekinesis works.  Second, where applicable, is it possible for a monster
 +
to use it?  Helmets require appropriately-shaped heads, scrolls require the
 +
ability to read, etc.  Third, is there a chance that the monster will start
 +
out with it?
 +
 +
I implement these first two as flags, and the third as a pair of numbers:
 +
the average number of items the creature has (i.e. "from 0 to 6"), and the
 +
dungeon level equivalent of the items (i.e. a kobold only gets the kind of
 +
items you find on level 1).  The items are generated randomly when the
 +
monster is created, plus a few rules are applied to preserve sanity (no
 +
creature carries more than one armor or more than two weapons; only unique
 +
creatures can start out with artifacts, etc.)  Et voila!  I also keep a flag
 +
to let some monsters carry only one item, and can't fight while carrying --
 +
this is great for animals that can only carry things in their mouths.
 +
 +
Of course, mosters should be able to acquire objects, and perhaps steal them
 +
as well (hello Green Glutton Ghosts or the Nymphs of Nethack).  That is easy
 +
enough to manage, and also lets monsters get items way out of their depth
 +
("The kobold hits!  Snicker-snack!").  Again, sanity should be applied --
 +
monsters should have no better idea of what an item is than the player would
 +
(depending on how you handle identification), they should not be able to
 +
touch items inimical to themselves (evil monsters should not touch holy
 +
weapons, goblins are not likely to go around swinging Orcrist), and so on.
 +
 +
Care must be taken that game-balance is not hurt.  The biggest danger is
 +
when small creatures have powerful items.  It's very cool when our small
 +
kobold has a big weapon, but if you can stand a few meters away and magic
 +
missile him to death, then you have a free major item.  And in most
 +
roguelikes a really good artifact would increase the power of a low-level
 +
character many times over.  Luckily, a well-balanced and realistic monsters
 +
definition file will handle most of that.  Normally the little guys won't
 +
get the big weapons, and if they occasionally do that's just interesting,
 +
and good (or disasterous) luck for the player -- much like Wormtongue
 +
throwing the Palantir at Gandalf without knowing what it was.  The other
 +
thing is that the tough guys are going to be a *lot* tougher in this system
 +
(which by my book is a good thing).  Imagine an Angband Nazgul if he was
 +
also guaranteed to be carrying a few "good" or "excellent" items on him.
 +
 +
The rest you can think of yourself: like destroying the other creature's
 +
items and so on.  Heck, if a fire-breathing dragon can burn up all my
 +
scrolls, I want to be able to destroy his scrolls with a wand of fire.  I
 +
would also point out that the more things a monster carries, the more fun it
 +
is to play a thief.  On the flip side, you could make a really good-aligned
 +
character like a paladin very strong, but unable on moral grounds to remove
 +
items from corpses.
 +
 +
= Direct Screen Output.txt =
 +
 +
Direct screen output
 +
 +
1. Introduction
 +
Here are instruction how to write to screen without involving BIOS or your
 +
system. I did this in my RL project. This may prove dangerous though. This
 +
information is true when and only when computer is in color text mode. If you
 +
plan to use it in other modes (graphics for example) strange things may attack
 +
your viewport(vacuum worms?). Memory location is varying depending on which
 +
mode is set in given time. I will give some Pascal code bits to help understand
 +
this method. Please forgive me my mediocre english.
 +
 +
2. Location
 +
The memory adresses (in hex) B800:0000 to B800:FFFF (be warned that in
 +
monochrome mode it would be B000:0000 to B000:FFFF) is belonging to graphics
 +
card. First byte indicates an ASCII characted being stored. Next one describes
 +
it's attributes (color, background color and blinking).
 +
 +
Second bit may need some detailed explanations:
 +
 +
Bits  7  6  5  4  3  2  1  0
 +
    [ ][      ][          ]
 +
      ^    ^            ^
 +
blink-/  background color |
 +
                      textcolor
 +
 +
It means that one may use colors 0-15 for text and 0-7 for background. Blinking
 +
may be used for seen invisible monsters for example. So how we declare our
 +
array?
 +
 +
3. Declaration
 +
In Pascal it could look like this: (I used 80x50 color text mode in example)
 +
 +
Const MinY = 1; {defined constants}
 +
      MaxY = 50;
 +
      MinX = 1;
 +
      MaxX = 80;
 +
 +
Var TheScreen : Array[MinY..MaxY, MinX..MaxX] of Record
 +
                                          Symbol : Char;
 +
                                          Attrib : Byte
 +
                                          End; Absolute $B800:$0000;
 +
 +
Note that Y coordinate preceeds X. Ever wondered why BASIC statement locate
 +
asks for Y as first parameter? Now this is an answer. But this has minor
 +
drawback. It uses entire screen! In most cases you would want to save some
 +
lines for message area. To do this adjust MinY, MaxY and add MaxX*2 bytes to
 +
start position in memory. To add space add the bottom simply decrease MaxY.
 +
 +
4. Example
 +
We want to display a white blinking G on black background at (57, 22). In
 +
pascal we make these assignments:
 +
 +
TheScreen[22, 57].Symbol := 'G';
 +
TheScreen[22, 57].Attrib := 15+0*16+128;
 +
 +
Displaying letter Z at (X, Y) in color A on a background color of B without
 +
blinking:
 +
TheScreen[Y, X].Symbol := 'Z';
 +
TheScreen[Y, X].Attrib := A+B*16+0;
 +
 +
Yes, this 0 is unnecessary but i wanted to point that no blinking was used.
 +
Note that you may display even control characters. Rogue used char 1 of ASCII.
 +
I've seen no other rouguelike that had the same image for player. In my opinion
 +
@ is much uglier.
 +
 +
5. Conclusion
 +
This is faster than anything else I've seen before (tested on 386DX gives great
 +
results!). Let the processor speed be used for other features. Undetected
 +
ingerence of other programs might force you to add screen redraw key to your
 +
roguelike (as is in ADOM). Code was not tested by any compiler, so it may
 +
contain errors. If this is the case - sorry. Hope this helps anyone.
 +
 +
NOTE: writing to screen this way will NOT move cursor. It also saves time :)
 +
but you may move it manually or even disable.
 +
 +
Micha??? Bieli???ski
 +
 +
= Compressing Savefiles - Ross Morgan-Linial [rmorgan@fhcrc.org].txt =
 +
 +
(or, It's a Big World Out There)
 +
 +
It's fairly easy to write a simple algorithm for reading and writing
 +
savefiles. Just dump all your data structures in a fixed order, and
 +
then read them in later (although, if your data structures have
 +
pointers, it's a bit more complicated - but that deserves another
 +
article). However, the problem with this simple algorithm is that the
 +
savefiles can be _big_. If you plan to save 100 levels, each 20x80
 +
tiles, and each tile takes 10 bytes, that's 1.6 megabytes right
 +
there... and that's just for the maps.
 +
 +
 +
A Solution: Run-Length Encoding
 +
 +
Fortunately, there is a very simple algorithm that can achieve enormous
 +
compression on the average map. That algorithm is called run-length
 +
encoding. The basic idea is simple. Most of the tiles in your dungeon
 +
will be walls or floors, and these walls and floors will tend to be
 +
grouped together in blocks. Instead of writing one byte to indicate
 +
the type of each tile in your dungeon, you use two bytes to indicate
 +
the type of a sequence of tiles. The first byte indicates how many
 +
consecutive tiles (in a left-to-right, top-to-bottom traverse of the
 +
map) are the type indicated by the second byte. Therefore, the basic
 +
algorithm to compress your dungeon is simple:
 +
 +
Algorithm 1: Compressing a dungeon, take 1
 +
  For each tile in the dungeon, in some order
 +
      If that tile is the same as the last tile and the tile count is < 255
 +
        Increment the tile count
 +
      Otherwise
 +
        Output the tile count and the type of the last tile
 +
        Set the tile count to 1
 +
  Output the tile count and the type of the last tile
 +
 +
The algorithm to decompress it is even simpler:
 +
 +
Algorithm 2: Decompressing a dungeon, take 1
 +
  Until you reach the end of the dungeon
 +
      Read a run count
 +
      Read a tile
 +
      For a number of tiles equal to the run count
 +
        Set that tile to the tile you read
 +
 +
 +
Fixing the Problems
 +
 +
If you try the preceding algorithms, you'll find that they work well,
 +
but there is some room for improvement. Some data in each tile can be
 +
compressed more effectively than with RLE, and some data just isn't
 +
amenable to RLE encoding and tends to break the coding into a
 +
succession of one-tile entries.
 +
 +
Most games keep the data about in a monster's or object's location in
 +
two places: in the data structure representing the monster or object,
 +
and in the data structure representing the map. Because the
 +
information about the monsters and objects on the map has to be saved
 +
anyway, we can completely omit the monster and object information from
 +
the map portion of the savefile. When we read in the savefile, we will
 +
reconstruct the data about monsters and objects on the map from the
 +
data about the monsters and objects themselves. This will save two
 +
two-byte or four-byte fields, and allow the RLE algorithm to compress
 +
the map more effectively.
 +
 +
Some data fields usually have a constant value, or a value that can be
 +
easily computed from other values in the tile structure. We can save
 +
space, and make the RLE more effective, by omitting these values and
 +
only saving the exceptional values in the savefile. The easiest way to
 +
do this is emit a string of X-Y-value groups into the savefile,
 +
followed by a sentinel element:
 +
 +
Algorithm 3: Saving sparse data
 +
  For each tile in the dungeon, in some order
 +
      Compute the expected value of the data
 +
      If the value is not the expected value
 +
        Emit the X and Y coordinates of the current tile
 +
        Emit the actual value of the data
 +
  Emit a sentinel value larger than any possible real X
 +
 +
Algorithm 4: Reading sparse data
 +
  For each tile in the dungeon, in some order
 +
      Set the value of the data to the expected value
 +
  Repeat until the sentinel is read
 +
      Read the X coordinate
 +
      If the X coordinate is the sentinel, stop
 +
      Read the Y coordinate
 +
      Read the real value
 +
      Set the data at the indicated tile to the real value read
 +
 +
An alternative, if exceptional values are more common, is to emit a
 +
bit-packed array (bit map) indicating which tiles have unusual values,
 +
followed by the values in order.
 +
 +
One final trick, which might reduce the size of savefiles, is to
 +
run-length encode the various fields of the map data separately. If
 +
the fields don't tend to have the same runs, this significantly
 +
reduces the size of the RLE data. On the other hand, it might not. The
 +
only way to find out is to try it and see.
 +
 +
= Stacktraces in gcc-compiled programs in Win32 and Linux-executables - Jurriaan Kalkman [thunder7@xs4all.nl].txt =
 +
 +
========================================================================
 +
Copyright (c)  2000 Jurriaan Kalkman
 +
Permission is granted to copy, distribute and/or modify this document
 +
under the terms of the GNU Free Documentation License, Version 1.1
 +
or any later version published by the Free Software Foundation;
 +
with no Invariant Sections, with no Front-Cover Texts, and with no
 +
Back-Cover Texts.  A copy of the license is available on the Internet
 +
at http://www.gnu.org or is available on demand from the author.
 +
========================================================================
 +
 +
So you've made this great rogue-like, and it seems to crash now and
 +
again. Perhaps you're not as great a coder as you thought :-). Or,
 +
you develop it under GNU/Linux, and most other people run it under
 +
Windows, and it crashes.
 +
 +
If it crashes and you have the debugger GDB handy, you can type 'bt'
 +
to get a nice stack-trace, so you can see what routines called the
 +
one that caused the crash. This is often very useful information.
 +
Consider the situation where you have a routine that changes some part
 +
of the dungeon (lighting a square for example) and you find out that once
 +
in a while it is called with an x-coordinate of 0, and this causes a
 +
crash. It would be very useful to know from where this routine is called,
 +
particularly if it is called from 60 places or so and you cannot check
 +
them all.
 +
 +
There is a solution for that, if you use gcc. It works under any compiler
 +
that is gcc-based, but requires signals to be available. These environ-
 +
ments include any unix-system I know of, DOS (DJGPP) and win32
 +
(cygwin32). OS/2 has a gcc-compiler, but it doesn't support signals, I've
 +
been told.
 +
 +
1 Introduction
 +
2 Signal handlers
 +
3 What is on the stack
 +
4 When to stop
 +
5 Coding it
 +
  5.1 The windows 'get-an-address-off-the-stack macro'
 +
  5.2 The GNU/Linux 'get-an-address-off-the-stack macro'
 +
  5.2 The decoding routine for the addresses on the stack
 +
  5.3 The signal handler
 +
  5.4 Compilation
 +
6 Sample output
 +
 +
1 Introduction
 +
--------------
 +
Gcc has certain builtin functions known as __builtin_frame_address
 +
and __builtin_return_address.
 +
 +
These functions allow you to determine which functions were calling
 +
the crashing function.
 +
 +
All examples and files are taken from Angband/64, which can be found
 +
at http://www.xs4all.nl/~thunder7. Added to this article are bits
 +
and pieces of files in the source-archive. If you want to know more,
 +
read the whole source. Compile it, experiment with it, then go code
 +
your own.
 +
 +
The beauty of this solution is that you can let your program read it's
 +
own executable-file, and use the debug-information that is in there to
 +
display what was going on at the moment of the crash. This in contrast
 +
with my earlier attempt at this, where you needed an extra file, gene-
 +
rated at compile time, to translate addresses into function names.
 +
 +
2 Signal handlers
 +
-----------------
 +
First of all, you need a signal-handler for signals like
 +
 +
SIGFPE (floating point error)
 +
SIGKILL (^c or something like it)
 +
SIGSEGV (pointer gone wild)
 +
etc.
 +
 +
3 What is on the stack
 +
----------------------
 +
Then you need to find out what are the addresses on the stack.
 +
This looks simple:
 +
 +
__builtin_return_address(0) is the current address (say function C)
 +
__builtin_return_address(1) is the address in function B which called C
 +
__builtin_return_address(2) is the address in function A which called B
 +
 +
these functions return 32 bits addresses. (except if you're on Alpha :-) )
 +
 +
4 When to stop
 +
--------------
 +
now the problem is when to stop, or, how deep is the stack?
 +
 +
In GNU/Linux and DOS, this is simple: as soon as __builtin_return_address
 +
returns 0, the end is reached.
 +
 +
In win32 (or at least the cygwin32 cross-compiler I use here), this is
 +
more of a problem, I've found out that there is no 0 at the end, it
 +
simply crashes. So I've used the second builtin function there, called
 +
__builtin_frame_address, and with trial and error found out that it seems
 +
to work quite well if you make sure you only follow
 +
__builtin_return_address as long as the upper 2 bytes from
 +
__builtin_return_address match the upper 2 bytes from
 +
__builtin_frame_address. This means you stay in the same frame. Now I'm
 +
no expert, and I cannot explain why this is so. It works for me, YMMV.
 +
 +
5 Coding it
 +
-----------
 +
 +
Grabbing these addresses should not be done with subroutines, because
 +
that would introduce another frame on the stack :-). So there are some
 +
huge macro-definitions needed.
 +
 +
Then we borrow (a lot of) code from the addr2line program in the GNU
 +
binutils suite. The addr2line program prints out the name of the source-
 +
file, the exact linenumber and the name of the function, when you supply
 +
the name of the executable and the address. Both are known, so we are
 +
in business.
 +
 +
I suggest first reading the source for the addr2line program. It's only
 +
about 350 lines, and is really easy to understand. Then you'll be able to
 +
see that all I added in files.c is just a simplification: I've deleted
 +
the argument/option parsing, I've deleted the logic that let addr2line
 +
handle files in a non-standard object-format, I've copied together some
 +
procedures, and now there is just something like 85 lines left.
 +
 +
5.1 The windows 'get-an-address-off-the-stack macro'
 +
----------------------------------------------------
 +
 +
#ifdef WINDOWS
 +
#define handle_stack_address(X) \
 +
  if (baseframe == 0L) \
 +
  { \
 +
      baseframe=(unsigned long)__builtin_frame_address(0); \
 +
      baseframe=((baseframe & 0xffff0000L) >> 16); \
 +
      dlog(DEBUGSAVE,"files.c: handle_signal_abort: baseframe now %08lx\n",
 +
\
 +
          baseframe); \
 +
  } \
 +
  if (continue_stack_trace && \
 +
      ((((unsigned long)__builtin_frame_address((X)) & 0xffff0000L)>&gt16)
 +
== baseframe) && \
 +
      ((X) < MAX_STACK_ADDR)) \
 +
  { \
 +
      stack_addr[(X)]= (unsigned long)__builtin_return_address((X)); \
 +
      dlog(DEBUGSAVE,"files.c: handle_signal_abort: stack %d %08lx frame %d
 +
%08lx\n", \
 +
                      (X), __builtin_return_address((X)), (X),
 +
__builtin_frame_address((X))); \
 +
  } \
 +
  else if (continue_stack_trace) \
 +
  { \
 +
      continue_stack_trace = FALSE; \
 +
  }
 +
#endif
 +
 +
note that we use baseframe to check if we stay in the same frame. This
 +
is based upon experimentation at my side.
 +
 +
5.2 The GNU/Linux 'get-an-address-off-the-stack macro'
 +
------------------------------------------------------
 +
 +
#define handle_stack_address(X) \
 +
  if (continue_stack_trace && ((unsigned long)__builtin_frame_address((X))
 +
!= 0L) && ((X) < MAX_STACK_ADDR)) \
 +
  { \
 +
      stack_addr[(X)]= (unsigned long)__builtin_return_address((X)); \
 +
      dlog(DEBUGSAVE,"files.c: handle_signal_abort: stack %d %08lx frame %d
 +
%08lx\n", \
 +
                      (X), __builtin_return_address((X)), (X),
 +
__builtin_frame_address((X))); \
 +
  } \
 +
  else if (continue_stack_trace) \
 +
  { \
 +
      continue_stack_trace = FALSE; \
 +
  }
 +
#endif
 +
 +
5.2 The decoding routine for the addresses on the stack
 +
-------------------------------------------------------
 +
 +
/* this is a adapted version of addr2line */
 +
/* addr2line.c -- convert addresses to line number and function name
 +
  Copyright 1997, 98, 99, 2000 Free Software Foundation, Inc.
 +
  Contributed by Ulrich Lauther &ltUlrich.Lauther@zfe.siemens.de>
 +
 +
  This file is part of GNU Binutils.
 +
 +
  This program is free software; you can redistribute it and/or modify
 +
  it under the terms of the GNU General Public License as published by
 +
  the Free Software Foundation; either version 2, or (at your option)
 +
  any later version.
 +
 +
  This program is distributed in the hope that it will be useful,
 +
  but WITHOUT ANY WARRANTY; without even the implied warranty of
 +
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 +
  GNU General Public License for more details.
 +
 +
  You should have received a copy of the GNU General Public License
 +
  along with this program; if not, write to the Free Software
 +
  Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */
 +
 +
/* Look for an address in a section.  This is called via
 +
bfd_map_over_sections.  */
 +
static void find_address_in_section (bfd *abfd, asection *section, PTR
 +
data)
 +
{
 +
  bfd_vma vma;
 +
  bfd_size_type size;
 +
 +
  if (dump_found) return;
 +
 +
  if ((bfd_get_section_flags (abfd, section) & SEC_ALLOC) == 0)
 +
  {
 +
    return;
 +
  }
 +
 +
  vma = bfd_get_section_vma (abfd, section);
 +
  if (dump_pc < vma)
 +
  {
 +
    return;
 +
  }
 +
 +
  size = bfd_get_section_size_before_reloc (section);
 +
  if (dump_pc >= vma + size)
 +
  {
 +
    return;
 +
  }
 +
 +
  dump_found = bfd_find_nearest_line (abfd, section, dump_syms, dump_pc -
 +
vma,
 +
&dump_filename, &functionname,
 +
&dump_line);
 +
}
 +
 +
/* Read hexadecimal addresses from stdin, translate into
 +
  file_name:line_number and optionally function name.  */
 +
/* changed, it takes a single address as argument */
 +
static void translate_address (bfd *abfd, int address,
 +
                              char *function_name, char *source_name, int
 +
*source_line)
 +
{
 +
  char addr_hex[100];
 +
  sprintf(addr_hex,"%x", address);
 +
 +
  dump_pc = bfd_scan_vma (addr_hex, NULL, 16);
 +
 +
  dump_found = false;
 +
  bfd_map_over_sections (abfd, find_address_in_section, (PTR) NULL);
 +
 +
  if (! dump_found)
 +
  {
 +
      strcpy(function_name, "??");
 +
      strcpy(source_name, "??");
 +
      *source_line = 0;
 +
  }
 +
  else
 +
  {
 +
      if (functionname == NULL || *functionname == '\0')
 +
      {
 +
        strcpy(function_name, "??");
 +
        if (dump_filename == NULL)
 +
        {
 +
            strcpy(source_name, "??");
 +
        }
 +
        else
 +
        {
 +
            strcpy(source_name, dump_filename);
 +
        }
 +
        *source_line = dump_line;
 +
      }
 +
      else
 +
      {
 +
        strcpy(function_name, functionname);
 +
        if (dump_filename == NULL)
 +
        {
 +
            strcpy(source_name, "??");
 +
        }
 +
        else
 +
        {
 +
            strcpy(source_name, dump_filename);
 +
        }
 +
        *source_line = dump_line;
 +
      }
 +
 +
      /* fflush() is essential for using this command as a server
 +
        child process that reads addresses from a pipe and responds
 +
        with line number information, processing one address at a
 +
        time.  */
 +
  }
 +
  fflush (stdout);
 +
}
 +
 +
void dump_stack(void)
 +
{
 +
  s16b i;
 +
  static unsigned long stack_addr[MAX_STACK_ADDR];
 +
  bfd *abfd;
 +
  char **matching;
 +
  long storage;
 +
  long symcount;
 +
 +
  bfd_init();
 +
 +
  /* clean the stack addresses if necessary */
 +
  for (i=0; i < MAX_STACK_ADDR; i++)
 +
  {
 +
      stack_addr[i] = (unsigned long)0;
 +
  }
 +
 +
  handle_stack_address(0);  handle_stack_address(1);
 +
handle_stack_address(2);  handle_stack_address(3);
 +
  handle_stack_address(4);  handle_stack_address(5);
 +
handle_stack_address(6);  handle_stack_address(7);
 +
  handle_stack_address(8);  handle_stack_address(9);
 +
handle_stack_address(10); handle_stack_address(11);
 +
  handle_stack_address(12); handle_stack_address(13);
 +
handle_stack_address(14); handle_stack_address(15);
 +
  handle_stack_address(16); handle_stack_address(17);
 +
handle_stack_address(18); handle_stack_address(19);
 +
  handle_stack_address(20); handle_stack_address(21);
 +
handle_stack_address(22); handle_stack_address(23);
 +
  handle_stack_address(24); handle_stack_address(25);
 +
handle_stack_address(26); handle_stack_address(27);
 +
  handle_stack_address(28); handle_stack_address(29);
 +
handle_stack_address(30); handle_stack_address(31);
 +
  handle_stack_address(32); handle_stack_address(33);
 +
handle_stack_address(34); handle_stack_address(35);
 +
  handle_stack_address(36); handle_stack_address(37);
 +
handle_stack_address(38); handle_stack_address(38);
 +
 +
  /* dump stack frame */
 +
  i = MAX_STACK_ADDR-1;
 +
  while ( (i >=0) && (stack_addr[i] == 0)) i--;
 +
 +
  if (i < 0)
 +
  {
 +
      dlog(DEBUGALWAYS,"files.c: dump_stack: unable to get any addresses
 +
off the stack.\n");
 +
      return;
 +
  }
 +
  abfd = bfd_openr (argv0, NULL);
 +
 +
  if (abfd == NULL)
 +
  {
 +
      cptr errmsg = bfd_errmsg( bfd_get_error() );
 +
      dlog(DEBUGALWAYS,"files.c: dump_stack: abfd == NULL; bfd error =
 +
%s\n", errmsg);
 +
      return;
 +
  }
 +
 +
  if (bfd_check_format (abfd, bfd_archive))
 +
  {
 +
      cptr errmsg = bfd_errmsg( bfd_get_error() );
 +
      dlog(DEBUGALWAYS,"files.c: dump_stack: bfd_check_format return-value
 +
!= 0; bfd error = %s\n", errmsg);
 +
      return;
 +
  }
 +
 +
  if (! bfd_check_format_matches (abfd, bfd_object, &matching))
 +
  {
 +
      cptr errmsg = bfd_errmsg( bfd_get_error() );
 +
      dlog(DEBUGALWAYS,"files.c: dump_stack: format doesn't match; bfd
 +
error = %s\n", errmsg);
 +
      return;
 +
  }
 +
 +
  if ((bfd_get_file_flags (abfd) & HAS_SYMS) == 0)
 +
      return;
 +
 +
  storage = bfd_get_symtab_upper_bound (abfd);
 +
  if (storage < 0)
 +
  {
 +
      cptr errmsg = bfd_errmsg( bfd_get_error() );
 +
      dlog(DEBUGALWAYS,"files.c: dump_stack: storage < 0; bfd error =
 +
%s\n", errmsg);
 +
      return;
 +
  }
 +
 +
  dump_syms = (asymbol **) xmalloc (storage);
 +
 +
  symcount = bfd_canonicalize_symtab (abfd, dump_syms);
 +
  if (symcount < 0)
 +
  {
 +
      cptr errmsg = bfd_errmsg( bfd_get_error() );
 +
      dlog(DEBUGALWAYS,"files.c: dump_stack: symcount < 0; bfd error =
 +
%s\n", errmsg);
 +
      return;
 +
  }
 +
 +
  for (; i>=0 ; i--)
 +
  {
 +
      {
 +
        char function_name[2048];
 +
        char source_name[2048];
 +
        int source_line;
 +
       
 +
        translate_address (abfd, stack_addr[i], function_name,
 +
source_name, &source_line);
 +
        dlog(DEBUGALWAYS,"files.c: stack_dump: stack frame %2d address
 +
%08lx = %s (%s %d) \n",
 +
                          i, stack_addr[i], function_name, source_name,
 +
source_line);
 +
      }
 +
  }
 +
 +
/* and cleaning up afterwards */
 +
  if (dump_syms != NULL)
 +
  {
 +
      free (dump_syms);
 +
      dump_syms = NULL;
 +
  }
 +
 +
  bfd_close (abfd);
 +
}
 +
 +
5.3 The signal handler
 +
----------------------
 +
 +
Now define some signal handlers like this:
 +
 +
#ifdef SIGFPE
 +
    (void)signal(SIGFPE, handle_signal_abort);
 +
#endif
 +
 +
#ifdef SIGILL
 +
    (void)signal(SIGILL, handle_signal_abort);
 +
#endif
 +
 +
#ifdef SIG
 +
TRAP
 +
    (void)signal(SIGTRAP, handle_signal_abort);
 +
#endif
 +
 +
#ifdef SIGIOT
 +
    (void)signal(SIGIOT, handle_signal_abort);
 +
#endif
 +
 +
#ifdef SIGKILL
 +
    (void)signal(SIGKILL, handle_signal_abort);
 +
#endif
 +
 +
and define a function handle_signal_abort like:
 +
 +
static void handle_signal_abort(int sig)
 +
{
 +
  bool                save_ok = FALSE;
 +
 +
  FILE                *fff = NULL;
 +
  char                filename[1024];
 +
  s16b                i;
 +
  bool                dump_ok = FALSE;
 +
 +
  /* Clear the bottom lines */
 +
  Term_erase(0, 20, 80);
 +
  Term_erase(0, 21, 80);
 +
  Term_erase(0, 22, 80);
 +
 +
  /* Give a warning */
 +
  Term_putstr(1, 20, -1, TERM_RED, "You suddenly see a gruesome SOFTWARE
 +
BUG leap for your throat!");
 +
  Term_xtra(TERM_XTRA_NOISE, 0);
 +
 +
  /* Access the help file */
 +
  strcpy(filename, ANGBAND_DIR_USER);
 +
  strcat(filename, "crash.txt");
 +
 +
#if defined(MACINTOSH) && !defined(applec)
 +
  /* Global -- "text file" */
 +
  _ftype = 'TEXT';
 +
#endif
 +
 +
  /* Drop priv's */
 +
  safe_setuid_drop();
 +
 +
  /* Open the non-existing file */
 +
  fff = my_fopen(filename, "w");
 +
 +
  /* Grab priv's */
 +
  safe_setuid_grab();
 +
 +
  /* Invalid file */
 +
  if (fff)
 +
  {
 +
      fprintf(fff,"Your game has just crashed. Please forward the
 +
following\n");
 +
      fprintf(fff,"information to the maintainer (email to
 +
thunder7@xs4all.nl)\n\n");
 +
      fprintf(fff,"\nAlso, please add any information you feel is
 +
relevant:\n");
 +
      fprintf(fff,"especially, what were you doing at the time this
 +
happened?\n\n");
 +
      fprintf(fff,"Angband/64 beta %d release %d (%d.%d.%d)\n\n",
 +
                  VERSION_BETA, VERSION_RELEASE, VERSION_MAJOR,
 +
VERSION_MINOR, VERSION_PATCH);
 +
      fprintf(fff,"STACK TRACE:\n\n");
 +
 +
      dump_stack();
 +
 +
      fprintf(fff,"\nCONFIGURATION:\n\n");
 +
      fprintf(fff, "debuglevel 0x%08lx\n", debuglevel);
 +
 +
#ifdef ALLOW_COMPRESSION
 +
      fprintf(fff,"compression support compiled in\n");
 +
#endif
 +
 +
and so on. An emergency-save routine is also nice to have here!
 +
At the end, make sure your program ends with something like exit(1).
 +
 +
5.4 Compilation
 +
---------------
 +
You'll need to make sure bfd.h can be found when compiling, and
 +
link with -lbfd -liberty. I won't deny that the last two can be
 +
a bit of a bother. They come out of the binutils-suite, which can
 +
be found on any gnu-repository. They are, however, *not* included in
 +
binary distributions of binutils, you'll have to build your own from
 +
source. On GNU/Linux building binutils is straightforward
 +
(./configure; make; make install) but I had to go to some lengths to get
 +
those libraries for go32 and cygwin32. Ah well, sensible people use
 +
GNU/Linux anyway.
 +
 +
6 Sample output
 +
----------------
 +
 +
Your game has just crashed. Please forward the following
 +
information to the maintainer (email to thunder7@xs4all.nl)
 +
 +
Also, please add any information you feel is relevant:
 +
especially, what were you doing at the time this happened?
 +
 +
Angband/64 beta 5 release 5 (2.7.10)
 +
 +
STACK TRACE:
 +
 +
stack frame 10 address 0804abb1 = _start (?? 0)
 +
stack frame  9 address 401fb213 = ?? (?? 0)
 +
stack frame  8 address 08117a69 = main
 +
(/home/jurriaan/games/myang/src/main.c 640)
 +
stack frame  7 address 0810b4b7 = play_game
 +
(/home/jurriaan/games/myang/src/dungeon.c 2084)
 +
stack frame  6 address 0810a355 = handle_dungeon
 +
(/home/jurriaan/games/myang/src/dungeon.c 1386)
 +
stack frame  5 address 08109ee7 = process_player
 +
(/home/jurriaan/games/myang/src/dungeon.c 1116)
 +
stack frame  4 address 08109545 = process_command
 +
(/home/jurriaan/games/myang/src/dungeon.c 717)
 +
stack frame  3 address 080f8565 = do_cmd_wizard
 +
(/home/jurriaan/games/myang/src/wizard2.c 3264)
 +
stack frame  2 address 080f72fb = wiz_create_crash
 +
(/home/jurriaan/games/myang/src/wizard2.c 2411)
 +
stack frame  1 address 402019b8 = ?? (?? 0)
 +
stack frame  0 address 080b1b10 = handle_signal_abort
 +
(/home/jurriaan/games/myang/src/files.c 4302)
 +
 +
CONFIGURATION:
 +
 +
debuglevel 0x80000040
 +
compression support compiled in
 +
using other RNG
 +
monster flow support compiled in
 +
 +
DISPLAY MODULES:
 +
 +
main-xaw compiled in
 +
main-x11 compiled in
 +
main-gcu compiled in
 +
 +
OPTIONS SET:
 +
 +
Quick messages
 +
Display coordinates on screen
 +
Print experience needed to advance
 +
Auto open doors when colliding
 +
Pick things up by default
 +
&ltetc. Angband/64 has a *lot* of options.>
 +
========================================================================
 +
 +
= Redefinable Keyboard Bindings - Stuart George [dfiber@mega-tokyo.com]. =
 +
 +
Your friend is a diehard rogue player, the VI keyboard mapping
 +
is second nature to her.
 +
 +
You have just finished your whizzbang roguelike game, only it doesnt
 +
support the VI mapping as you detest it with a passion!
 +
 +
If you dont want to alienate some players, you need to keep them
 +
happy. You need redefinable keyboard bindings.
 +
 +
This requires a two-tier representation of the key. An internal
 +
(to your game) representation and an external (eg: ncurses, dos, etc)
 +
representation.
 +
 +
In my roguelike I maintained an enumeration of valid keys.
 +
 +
enum InternalKeyBindings
 +
{
 +
ik_NullKey=0,
 +
 +
ik_KeyDown,
 +
ik_KeyLeft,
 +
ik_KeyRight,
 +
ik_KeyUp,
 +
 +
ik_MAX_KEYS
 +
};
 +
 +
 +
external key values are then mapped to the internal key values.
 +
 +
#define _ALIAS_COUNT 2
 +
unsigned long lngKeyBinding[ik_MAX_KEYS][_ALIAS_COUNT];
 +
 +
The _ALIAS_COUNT in the array definition shows that we can store
 +
up to two different key values per internal binding, for example,
 +
Open Door and Bash Door, say 'o' and 'b', could be an alias for the same
 +
key.
 +
 +
For this to work properly we must translate our keypresses from external
 +
to internal.
 +
 +
For something like NCurses,
 +
 +
unsigned long ncurses_GetKey()
 +
{
 +
return getch();
 +
}
 +
 +
unsigned long TranslateKey()
 +
{
 +
unsigned long lngKey;
 +
unsigned long lngReturnKey;
 +
unsigned long lngLoopCount;
 +
unsigned long lngAliasCount;
 +
 +
lngKey=ncurses_GetKey();
 +
lngReturnKey=ik_NullKey;
 +
 +
for(lngLoopCount=1; lngLoopCount<ik_MAX_KEYS; lngLoopCount++)
 +
{
 +
for(lngAliasCount=1; lngAliasCount<_ALIAS_COUNT;
 +
 +
lngAliasCount++)
 +
{
 +
 +
 +
if(lngKeyBinding[lngLoopCount][lngAliasCount]=lngKey)
 +
{
 +
lngReturnKey=lngLoopCount;
 +
/* break out of the loop faster/nicer */
 +
lngAliasCount=_ALIAS_COUNT;
 +
lngLoopCount=ik_MAX_KEYS;
 +
}
 +
}
 +
}
 +
 +
return lngReturnKey;
 +
}
 +
 +
 +
Now we have our translation working, we can assign keys for our
 +
VI key fans and our VI key haters!
 +
 +
void BindKeys(void)
 +
{
 +
/* binds VI only */
 +
lngKeyBidning[ik_KeyUp][0]='i';
 +
lngKeyBinding[ik_KeyUp][1]=0;
 +
lngKeyBidning[ik_KeyDown][0]='k';
 +
lngKeyBinding[ik_KeyDown][1]=0;
 +
lngKeyBidning[ik_KeyLeft][0]='j';
 +
lngKeyBinding[ik_KeyLeft][1]=0;
 +
lngKeyBidning[ik_KeyRight][0]='l';
 +
lngKeyBinding[ik_KeyRight][1]=0;
 +
 +
/* the uppercase KEY_* are NCurses constants */
 +
/* binds non VI arrows + number movement */
 +
lngKeyBidning[ik_KeyUp][0]=KEY_UP;
 +
lngKeyBinding[ik_KeyUp][1]='8';
 +
lngKeyBidning[ik_KeyDown][0]=KEY_DOWN;
 +
lngKeyBinding[ik_KeyDown][1]='2';
 +
lngKeyBidning[ik_KeyLeft][0]=KEY_LEFT;
 +
lngKeyBinding[ik_KeyLeft][1]='4';
 +
lngKeyBidning[ik_KeyRight][0]=KEY_RIGHT;
 +
lngKeyBinding[ik_KeyRight][1]='6';
 +
 +
/* binds both VI and non VI together */
 +
lngKeyBidning[ik_KeyUp][0]='i';
 +
lngKeyBinding[ik_KeyUp][1]=KEY_UP;
 +
lngKeyBidning[ik_KeyDown][0]='k';
 +
lngKeyBinding[ik_KeyDown][1]=KEY_DOWN;
 +
lngKeyBidning[ik_KeyLeft][0]='j';
 +
lngKeyBinding[ik_KeyLeft][1]=KEY_LEFT;
 +
lngKeyBidning[ik_KeyRight][0]='l';
 +
lngKeyBinding[ik_KeyRight][1]=KEY_RIGHT;
 +
}
 +
 +
Now you just have to remember to work with internal keys instead
 +
of external.
 +
 +
if(keypress==ik_KeyDown) instead of a hardcoded keyboard scancode
 +
or a hardcoded NCurses constant.
 +
 +
There are other things you can add to this, such as checking for
 +
a key that is bound two or more times.
 +
 +
Ultimatly the next step is to have all your key bindings in a config
 +
file that your roguelike reads in on startup, that way the user can
 +
bind whatever keys they like however they like them.
 +
 +
For my roguelike I allowed the player to bind NCurses constants into
 +
the config file (KEY_UP, etc) isntead of making them hunt down
 +
obscure scancodes for keyup \0\P etc.
 +
 +
Adding Meta key / CTRL / ALT key support is also another issue worth
 +
considering.
 +
 +
(*nb* the above code was written off the top of my head at work,
 +
but should be pretty much correct. Enough to get you started anyway)
 +
 +
= How to write a roguelike gameengine - Esa Ilari Vuokko [eivuokko@mbnet.fi].txt =
 +
 +
      Some ideas that could be useful ?
 +
      As shared by Esa Ilari Vuokko.
 +
Comments and bugfixes ;) to eivuokko@mbnet.fi
 +
 +
 +
 +
      I've played roguelike games for 7 years now. First I hacked Moria,
 +
  which I got from friend (no modem or net connection :(). Then I got
 +
  Omega which I still play (newer version, thought ;). At that time I
 +
  got rid of Basic I was programming with and got Turbo Pascal. Well,
 +
  I tried to do some pathetic games myself but they were just dead
 +
  as they were real mode programs. Then (not earlier) I got nethack
 +
  which I didn't like at that time. I hated djgpp (it's not bad, it's
 +
  ugly in msdos) so I was bounded to real mode. Then I got Linux and
 +
  installed it few times with no success (one time I installed it on
 +
  broken hd, guess did it work, no - it just paniced suddenly ;). And
 +
  I played ADOM, a lot. And then little Nethack and Omega.
 +
 +
 +
      Because Linux I got all so mighty gcc and make. After playing for a
 +
  while with graphics stuff (in linux and in win) and in winenv doing
 +
  some accounting program (with delphi, thought I quitted after it
 +
  started compiling wrong - I mean(debugged) it) I got an idea. In an
 +
  accounting program we move money from one account to another (I'm sorry
 +
  I know finnish terminology better than english). Well those accounts
 +
  must be linked list because : they must be easy to create, modify and
 +
  delete. Nothing new - a linked list. Of course all objects in rg should
 +
  be in linked lists. But the what if even attributes were linked lists ?
 +
  So that we had a linked list which can store data (some 16 bytes is enough)
 +
  and a name (string) and children list.
 +
 +
 +
      Listing attributes, skills, and everything that describes object with
 +
  such presentation would be quite flexible. But if one does such game,
 +
  and many people contribute to it ? It can go way off road as everybody
 +
  add something new. A bloated memory use, and unneeded complexity are
 +
  real threats. As normally, say ADOM, player char needs more memory
 +
  (more variables) than npc. But in this approach we give npc only those
 +
  skills and attributes it needs and we are still able to use same routines
 +
  on both, player and npc.
 +
 +
 +
      Of course above system can be optimized. I've defined it like this :
 +
  Okey, I've got a bit more complex.
 +
        class List {
 +
          private:
 +
                List *child,*next,*parent;
 +
                int id;
 +
                int data[4];
 +
                Link(List *);
 +
                Unlink(List *);
 +
                Query(int,int,int,int,int);
 +
          public:
 +
                int *Data();
 +
                char *Name();
 +
                int *Data(char *);
 +
                List *Name(char *);
 +
                int *Data(int,int,int,int,int);
 +
                List *Name(int,int,int,int,int);
 +
                Item *Index(int);
 +
                int Index(Item *);
 +
                int Count();
 +
                List *Add();
 +
                List *Remove();
 +
        } ;
 +
 +
      Quite clear, I think. Id can be converted (by another class) to char.
 +
  Almost all ints are for quick query. I use dot as delimiter between child
 +
  and parent and I don't have plurals.  "skill.weapon.blade.short".
 +
 +
      Then I wanted an engine that doesn't need special cases. It would be
 +
  (sorry for saying this) stupid to do special levels, which have special
 +
  if of switch statement in level code. How could one have such a really
 +
  flexible system ? Well I read Thomas Biskup's ideas of JADE. I don't know
 +
  whetever he meant the same as I with the mentioning everything to be
 +
  event based. So what I'm chasing here is that every object should have
 +
  message handler list, which would handle requests to do something.
 +
 +
    Say we have a character A. A has handler list of next functions
 +
  (stacked):
 +
      creature_shield_deflector,
 +
      creature_ro_poison_res,
 +
      creature_basic_poison,
 +
      player_non_ai,
 +
      basic_creature_handler.
 +
 +
  First a monster(mage) B would shoot an firebolt to A. Firebolt code would
 +
  send a message to A that some fire damage is  coming. First this message
 +
  would reach first handler in list, creature_shield_deflector. That would
 +
  say "no,no fire damage" and that would be it, no damage to creature. Then
 +
  B would throw a acidbolt. Well this time deflector would say nothing as
 +
  wouldn't other before basic_creature_handler. That would make some damage
 +
  to creature and spare some to inventory too (and send approciate messages
 +
  to items). Then would engine send TIMEUPDATE to creature, which would be
 +
  handled first by creature_basic_poison. Well it seems this creature has
 +
  poisoning and handler would notice that it just ending. First it sends to
 +
  creature A (self) damage message of poison, which would end to
 +
  creature_ro_poison_res, and no damage. Then it would return
 +
  UNLINK_AND_CONTINUE so that it would be removed from list and message
 +
  (TIMEUPDATE) would be sent on. Then message would reach basic_handler which
 +
  would add some speed to energy (ADOM) or add a timepulse (nethack,angband).
 +
  If it would be creature's turn to move, it would send message ACTION to
 +
  itself (creature A). That would be caught by player_non_ai which would wait
 +
  for keypress and then do whatever is defined and player wishes to do.
 +
 +
      Because paragraph above seems a bit unclear ;) I'll do an easier
 +
  table here :
 +
      1 creature_shield_deflector,
 +
      2 creature_ro_poison_res,
 +
      3 creature_basic_poison,
 +
      4 player_non_ai,
 +
      5 basic_creature_handler.
 +
 +
  Messages :
 +
    Fire damage
 +
      1 - take message (do nothing) return KEEP_AND_STOP -> that's it.
 +
    Acid damage
 +
      1 - no action, return KEEP_AND_CONTINUE
 +
      2 - no action, return KEEP_AND_CONTINUE
 +
      3 - no action, return KEEP_AND_CONTINUE
 +
      4 - no action, return KEEP_AND_CONTINUE
 +
      5 - Share damage to creature and inventory, send damage message to
 +
          inventory. Return KEEP_AND_STOP.
 +
    TIMEUPDATE
 +
      1 - no action, return KEEP_AND_CONTINUE
 +
      2 - no action, return KEEP_AND_CONTINUE
 +
      3 - Check if it's poison time. If it is send poison damage to self:
 +
              Poison damage
 +
                1 - no action, return KEEP_AND_CONTINUE
 +
2 - Take message (do nothing) and return KEEP_AND_STOP.
 +
  If poison is diluted enough return UNLINK_AND_CONTINUE
 +
  else return KEEP_AND_CONTINUE
 +
      4 - no action return KEEP_AND_CONTINUE
 +
      5 - Check whetever it's time to move or not (some way to count time
 +
          compared to time). If it is send ACTION to self.
 +
              ACTION
 +
                1 - no action, return KEEP_AND_CONTINUE
 +
                2 - no action, return KEEP_AND_CONTINUE
 +
                3 - no action, return KEEP_AND_CONTINUE
 +
                4 - Normal player's turn in roguelike games.
 +
  return KEEP_AND_STOP.
 +
 +
      KEEP_AND_CONTINUE, UNLINK_AND_STOP etc mean whatever function which
 +
  handles handler lists should keep sending message on in list and if
 +
  handler should be removed from list.
 +
 +
 +
      Yes, I know, this is really heavy way to do things. But if we can count
 +
  on fast 486, it is REALLY flexible. I think that with handlers lists and
 +
  description lists we can mimic any game we want or make just about anything
 +
  we want (well world conquest is a _bit_ hard maybe, but as rg game anything)
 +
 +
      I'm sorry if there's too many errors in my english. I didn't mean to
 +
  be offensive either but I needed to make my point clear (if it can be
 +
  done at all). If someone has implemented this allready, good, sorry to
 +
  say that I were to late.
 +
 +
      I'm sorry if there is something that have been published before and
 +
  I don't want to claim that I've been first to thing this kind of things
 +
  but I haven't seen anything like this before (I haven't read too much).
 +
  Anyway Copyright 2000 Esa Ilari Vuokko. I don't (of course) take any
 +
  responsibility of anything you do or don't do with this text. It can be
 +
  freely copied and published electronically as long as it isn't modified.
 +
 +
= Heap Space Conservation - Steve Segreto [ssegreto@titan.com]. =
 +
 +
Or How to have LOTS of monsters and LOTS of treasure in your Roguelike.
 +
 +
    Here are some tips for conserving precious heap space, so that you
 +
will be able to populate each of your dungeon levels with as many
 +
monsters and items as you want! This is a good alternative to having to
 +
write a protected mode program, and while it may be a little too slow
 +
for some 386s, the algorithms can be tuned as needed. The basic concept
 +
is that you will only store in RAM as little as you possibly need to
 +
know about all the monsters and items. All the rest of the stuff
 +
(specific information about a monster or item) you store on the
 +
player's hard drive. The speed versus memory usage trade-off is obvious.
 +
You will use a lot less RAM by only storing the indices into the disk
 +
files in a linked list in memory, but your game will be slightly slower
 +
because you must frequently return to the hard drive and read/write
 +
information from it (this is VERY slow compared to reading/writing from
 +
RAM).
 +
 +
Anyway, here is some sample code for storing indices for monsters and
 +
items using ANSI C and assuming that each of your dungeon levels is 80
 +
cells by 25 cells, for a total of 2000 square cells  (this may be
 +
smaller or larger than what you want for your roguelike). My ANSI C is
 +
pretty rusty (I prefer Pascal) so please be aware that this code does
 +
contain syntax errors.
 +
 +
/////////////////////////////////////////////////////////////////////////////////
 +
 +
// BEGIN CODE FRAGMENT
 +
/////////////////////////////////////////////////////////////////////////////////
 +
 +
    #define MAX_ROWS 25
 +
    #define MAX_COLS  80
 +
    typedef unsigned int word;  // 16-bit quantity
 +
    typedef unsigned char byte; // 8-bit quantity
 +
    typedef enum NodeTypes = { MONSTER, ITEMS }; // Different sorts of
 +
data files you will have
 +
 +
 +
/////////////////////////////////////////////////////////////////////////////////
 +
 +
    //  A singly linked list of indices.
 +
 +
/////////////////////////////////////////////////////////////////////////////////
 +
 +
    typedef struct index_list_node;
 +
    typedef index_list_node *index_list_node_ptr;
 +
    struct
 +
    {
 +
        word                      index;
 +
        NodeTypes            node_type;
 +
        index_list_node_ptr link;
 +
    } index_list_node; // Size = 7 bytes
 +
    // Related list functions are new_list(), free_list(),
 +
insert_before(), insert_after(), is_empty(), is_full()
 +
    //  advance_list(), reset_list(), read_list_from_disk(),
 +
write_list_to_disk()
 +
 +
 +
/////////////////////////////////////////////////////////////////////////////////
 +
 +
    //  Records to hold monsters and items on diskette.
 +
 +
/////////////////////////////////////////////////////////////////////////////////
 +
 +
    typedef struct
 +
    {
 +
          byte row, col, depth;
 +
          char symbol; // Whatever data you will have to represent a
 +
monster: name, hit points, AC, etc.
 +
    }monster_record;
 +
 +
    typedef struct
 +
    {
 +
          byte row, col, depth;
 +
          char symbol; // Whatever data you will have to represent an
 +
item: weight, damage, etc.
 +
    }item_record;
 +
 +
 +
/////////////////////////////////////////////////////////////////////////////////
 +
 +
    // Global array of index_list_nodes for each square of the dungeon.
 +
    // Initiallly this array will be MAX_ROWS * MAX_COLS * sizeof
 +
(index_list_node) bytes large
 +
    // 80 * 25 * 7 = 14,000 bytes plus 7 bytes for every monster/item
 +
added.
 +
    // Assuming about 150 monsters and 200 items per level, this gives
 +
you 14,000 + (7 * 350)=16,450 bytes
 +
 +
/////////////////////////////////////////////////////////////////////////////////
 +
 +
    index_list_node object_array[MAX_ROWS][MAX_COLS];
 +
 +
 +
/////////////////////////////////////////////////////////////////////////////////
 +
 +
    // Because the above list will only contain INDICES into permanent
 +
disk files, deleting elements from the list
 +
    // such as when an item is picked up or a monster slain, will be
 +
extremely slow (because the entire level file
 +
    // on disk will have to be re-written minus one single record). To
 +
alleviate this, simply keep a second linked
 +
    // index list of all the indices which need to be deleted from the
 +
permanent disk file when the player leaves this
 +
    // dungeon level (these indices have already been deleted from the
 +
object_array linked lists.) Remember to
 +
    // insert indices into this list EVERY time a monster is killed or
 +
an item is picked up (you might want to
 +
    // have a function delete_monster(which_row, which_col, what_index)
 +
which removes the specified node
 +
    // from the object_array[] linked list and also inserts it into the
 +
deleted_list [Do you see why you need to
 +
    // pass in what_index? That's right, so you can go to the
 +
appropriate (what_row, what_col) element in object_array
 +
    // and traverse that linked list until currPtr->index == what_index,
 +
then you can delete this node and insert the
 +
    // what_index into the deleted_list!] ).
 +
 +
/////////////////////////////////////////////////////////////////////////////////
 +
 +
    index_list_node deleted_list;
 +
 +
 +
/////////////////////////////////////////////////////////////////////////////////
 +
 +
    // You will also have two disk files per dungeon level, one for
 +
MONSTERS and one for ITEMS.
 +
    // You must devise a naming scheme for each (LEVEL01.MON and
 +
LEVEL01.ITM for example)
 +
    // LEVEL01.MON is a random-access file of monster_records and
 +
LEVEL01.ITM is a random-
 +
    // access file of item_records, one record per monster on that level
 +
and one record per item on the
 +
    // level. Note that these disk files may be quite large
 +
(sizeof(monster_record) * num_records bytes).
 +
 +
/////////////////////////////////////////////////////////////////////////////////
 +
 +
 +
/////////////////////////////////////////////////////////////////////////////////
 +
 +
    // stock_depth()
 +
    // Call this function at the start of the game or whenever the level
 +
needs to be completely re-stocked:
 +
 +
/////////////////////////////////////////////////////////////////////////////////
 +
 +
    void stock_depth ()
 +
    {
 +
        // 1. Open the appropriate monster level file (LEVEL01.MON for
 +
example)
 +
        // 2. Read each monster_record one at a time into a local
 +
variable, m
 +
        // 3. Based on the m's (row, col, depth) triple, use the
 +
appropriate element of the global object_array[].
 +
        //    For example, if m.row = 10 and m.col = 10 then
 +
object_array[10][10] would have a singly linked list
 +
        //    of index_list_nodes.
 +
        // 4. Insert the index into the linked list (use insert_after()
 +
from the basic list routines above).
 +
        // 5. Do the same thing for the item level file.
 +
        item_record i;
 +
        monster_record m;
 +
        FILE *infile;
 +
        word index = 0;
 +
 +
        // Add all the monsters to our array of linked lists.
 +
        infile = fopen ("LEVEL01.MON") // This line is not syntactically
 +
correct
 +
        while (!eof(infile))
 +
        {
 +
            fread (infile, m); // Wrong also!
 +
            insert_after (object_array[m.row][m.col], index, MONSTER);
 +
// The index is the record number and the linked list is
 +
 +
// at (m.row, m.col)
 +
            index++;  // Move on to the next record
 +
        }
 +
 +
        // If there are not enough monsters on this level, ADD monsters
 +
until there are enough.
 +
 +
        // Add all the items to our array of linked lists.
 +
        index = 0;
 +
        infile = fopen ("LEVEL01.ITM") // This line is not syntactically
 +
correct
 +
        while (!eof(infile))
 +
        {
 +
            fread (infile, m); // Wrong also!
 +
            insert_after (object_array[i.row][i.col], index, ITEM); //
 +
The index is the record number and the linked list is
 +
 +
// at (m.row, m.col)
 +
            index++;  // Move on to the next record
 +
        }
 +
    }
 +
 +
 +
/////////////////////////////////////////////////////////////////////////////////
 +
 +
    // change_depth()
 +
    // Call this function every time the player changes dungeon levels,
 +
including at the end of the game:
 +
 +
/////////////////////////////////////////////////////////////////////////////////
 +
 +
    void change_depth ()
 +
    {
 +
        // 1. Open the current monster level file (LEVEL01.MON for
 +
example)
 +
        // 2. Open a temporary file
 +
        // 3. Read each record one at a time into a local variable, m.
 +
        // 4. If this record number (index) is NOT in the deleted_list
 +
(see above) then write this
 +
        //    record to the temp file (otherwise DON'T write the record
 +
to the temp file).
 +
        // 5. Close and delete the monster level file.
 +
        // 6. Rename the temp file to the same name as the monster level
 +
file.
 +
        // 7. Now the temp file contains all the records except those
 +
which have been deleted (dead monsters).
 +
        // 8. Do the same with the item level file.
 +
        // 9. Call free_list() to destroy the linked index list.
 +
        // 10. Based on the new depth, call stock_depth() with the new
 +
depth number to load/build the new index_list.
 +
    }
 +
 +
 +
/////////////////////////////////////////////////////////////////////////////////
 +
 +
    // square_has_monster()
 +
    // Simply scan the linked list at object_array[which_row][which_col]
 +
and return TRUE as soon as one of
 +
    // the nodes has a node_type of MONSTER.
 +
    // You can devise a similar function for square_has_item().
 +
 +
/////////////////////////////////////////////////////////////////////////////////
 +
 +
    boolean square_has_monster (byte which_row, byte which_col)
 +
    {
 +
        // List at this square is empty (square has neither monster nor
 +
items)
 +
        if (object_array[which_row][which_col] == NULL) return (FALSE);
 +
 +
        index_list_node currPtr = object_array[which_row][which_col];
 +
        while (currPtr != NULL)
 +
        {
 +
            if (currPtr->node_type == MONSTER) return (TRUE);
 +
 +
            // Move down the list
 +
            currPtr = currPtr->link;
 +
        }
 +
        return (FALSE);
 +
    }
 +
 +
/////////////////////////////////////////////////////////////////////////////////
 +
 +
// END CODE FRAGMENT
 +
/////////////////////////////////////////////////////////////////////////////////
 +
 +
= Handing Out Experience - Rick Carson.txt =
 +
 +
Roguelikes are part of a family of games in which the participant builds
 +
something over time.  Relatives are of course roleplaying games and other
 +
storytelling games.  Distant relatives are games such as Civilization.
 +
 +
Since players often fail to achieve the primary goal (e.g. retrieve the
 +
artifact of lint removal which will cleanse the bellybuttons of everyone
 +
in the universe thereby ending world hunger) the secondary rewards (or payoffs
 +
(or utility for all you economists out there in RL land)) become very important.
 +
Too much advancement too quickly (kill a kobold - get to 35th level) devalues
 +
the payoff, whereas too slow an advancement (kill everything in the whole
 +
game and maybe get halfway to level 2) means that they never even get to
 +
feel rewarded.
 +
 +
Of course experience might be handed out for a range of activities, not
 +
just killing things.  such a list is certainly not limited to: solving quests;
 +
receiving damage; causing damage; casting spells; using skills; getting
 +
treasure; idle gossip; donations to the (un)worthy cause of your choice;
 +
doing nothing or resting; healing; travelling, mapping, making other players
 +
laugh....
 +
 +
So lets consider the case of a fairly generic dungeon bashing roguelike.
 +
The dungeon has sixteen levels, a predetermined number of monsters per
 +
level, and unique monsters.  There are no 'random' monsters.  We'll call
 +
our theoretical roguelike Jiavlo and code it in Java.  (Stop me if I infringe
 +
any copyrights ;-) 
 +
 +
Experience is only handed out when we generate a monster killing event.
 +
 +
Our first realization is that in this scenario there are a fixed number
 +
of monsters, and that this means that there is an upper limit for how much
 +
experience the player will ever get.
 +
 +
We need to decide how many levels we want the players to be able to gain.
 +
So what constitutes a good number of levels that could be gained?  Most
 +
of the audience will have at least a passing familiarity with the D&D game
 +
family, in which you start at level one, and progress is technically unlimited,
 +
but which is less meaningful once you get into double digits.  And certainly
 +
once you get into the low twenties you are in danger of being accussed (unjustly
 +
of course) of being a 'power gamer'.  So most of the target audience is
 +
going to be happy with a top level of around 15 to 30.  Twenty is a nice
 +
round number in that range which should give a decent payoff in terms of
 +
achievement.
 +
 +
Note that the point is not to mirror any particular published system for
 +
which one runs the risk of being sued and losing the shirt off ones back,
 +
but rather to recognise and take advantage of this subconscious assumption
 +
that most people are going to make, ie that getting to level 20 is a superhuman
 +
feat and that getting to level 12 (say) is pretty spectacular.
 +
 +
The other thing to do is to make the experience scale exponential (this
 +
means that each level requires more experience to get to than the level
 +
before it).  Mathematically there is no reason for this, but people will
 +
expect it, and because of their expectation they will not feel as much of
 +
a payoff if they get the same amount of experience for killing a dragon
 +
as a kobold.  Because of this, I recommend using a spreadsheet to play around
 +
with the numbers till you some that you like.  Hopefully you won't need
 +
a spreadsheet to follow this article though!
 +
 +
It is useful to consider the linear case here though, because it forms a
 +
basis from which you can build the exponential formula, and if you do so
 +
you will be much more likely to get a well balanced game.  But before we
 +
look at the linear model, lets examine the constant model.  This is even
 +
worse in terms of payoffs, but much simpler again to balance properly.
 +
 +
For every monster you kill you get 1 xp.
 +
There are 50 monsters per level.  (Times 16 levels is 800 xp)
 +
We can now say something like, for every 40 xp you have, you go up a level.
 +
(800 divided by 20).
 +
Note that you start at level 1, so you would get to level 20 after killing
 +
760 creatures, ie you max out your levels shortly before you kill the UberLintDaemon
 +
which drops the game ending artifact, so that you have time to enjoy maxing
 +
out on levels before the game ends.
 +
 +
If the monsters on deeper levels get harder to kill, then logically players
 +
would try to clear a level before progressing to the next in order to get
 +
the 'easiest' xp first (minimise risk, maximise payoff).
 +
 +
Note that we are requiring them to kill 40 monsters in order to advance
 +
to second level.  This is far too harsh, and for many first time players
 +
this will take too long for them to get hooked.  Ten is a much more reasonable
 +
number.  And we want them to be able to get to say level 5 or 6 fairly quickly
 +
before it becomes hard slog.  So lets break it down, lets say that by the
 +
end of dungeon level 15 they are level 20, and they gain a level per level
 +
they clear back till say the player is level 10.  That means that we then
 +
need to plot the xp from 0 (at level 1) to 250 (which they have after clearing
 +
5 levels at level 10).  We could go back and rewrite our assumptions, and
 +
have them start at level 0, and then have them gain a level every 25 points.
 +
That makes it nice and easy for us in terms of maths.
 +
 +
The effect this has on the game though, is to make the clearing of each
 +
level a hard thing at first, and then get easier halfway through each level.
 +
This is actually not too bad in terms of payoffs, because the player begins
 +
to notice that the monsters are easier to clear after going up the level.
 +
 +
So lets modify how players go up levels.  Here is the table (level, xp required):
 +
1 0
 +
2 5
 +
3 15
 +
4 30
 +
5 50
 +
6 75
 +
7 105
 +
8 140
 +
9 180
 +
10 225
 +
(and 50 per level after that). 
 +
 +
So at the end of clearing level 1 (50xp), they are fifth level, clearing
 +
level 2 puts them at sixth level verging on seventh, etc.  This uses a clear
 +
progression, in order to go up a level, you need as much extra xp as the
 +
last time you went up a level, plus five, until you get to needing 50 a
 +
level where it tops out).
 +
 +
Despite the plain maths behind this, I would be tempted to fiddle with it
 +
even more, because fifth level after clearing only one level of monsters
 +
seems 'too much'.
 +
 +
But lets take this 'constant' model, and see what happens when we make it
 +
'linear'.
 +
We assume that all the monsters on level x of the dungeon are 'level x monsters'
 +
and we give x points for killing them.  The maximum amount of experience
 +
in the game is now: 6800.  The maths for working this out is starting to
 +
get more complicated, but the formula is: (((n squared) plus n) divided
 +
by 2) times the number of monsters per level).  Where n is the number of
 +
levels, and the number of monsters per level is still 50.
 +
 +
Obviously we cannot now just multiply the cost of going up levels by 8.5
 +
(6800 divided by 800) because that would mean we would need 85 xp to get
 +
to second level, which means clearing all of level 1, and a third of level
 +
2.  All of a sudden things look a lot harder!  One way of solving this,
 +
is to try to match monsters killed to levels gained, assuming that all the
 +
low level monsters are killed first.  This is easier than it sounds for
 +
levels 10 through 20, because we already know that we want the player to
 +
advance at the mid point of the level.  And this is not too hard to work
 +
out (especially with a spreadsheet).
 +
 +
&gtFrom 10th level and up (level, xp required):
 +
10 900
 +
11 1225
 +
12 1600
 +
13 2025
 +
14 2500
 +
15 3025
 +
16 3600
 +
17 4225
 +
18 4900
 +
19 5625
 +
20 6400
 +
 +
(The formula for this is: (((n squared) plus n) / divided by 2) plus (25
 +
times (n plus 1))  where n = level required minus 5.  The minus five is
 +
because we have five more experience levels than the last level of the dungeon
 +
that we cleared)
 +
 +
Now if we want to keep the same progression, that is, getting to level five
 +
after clearing the first level of the dungeon (yuck!) we leave that bit
 +
of the table alone, and figure out a progression from 5th level to 10th
 +
level.  Or, we can choose another formula to govern low level advancement,
 +
such as: (n times n) plus (14 times n) minus 1, where n is the current
 +
level which yields:
 +
1 0
 +
2 14
 +
3 45
 +
4 95
 +
5 166
 +
6 260
 +
7 379
 +
8 525
 +
9 700
 +
 +
Which is a much nicer fit to the lower levels of the dungeon and how fast
 +
they should advance.  Unfortunately I've just noticed that it bears a striking
 +
similiarity to the xp curve in Crawl.  What a shame :-)
 +
 +
But of course noone wants to get 12 xp for killing a Dragon, so we need
 +
to think about how much xp we want to hand out for killing a monster of
 +
each level.  I suggested at the start of the article that making it exponential
 +
is probably more in fitting with the players expectations.  Lets say that
 +
on level one you get 1 xp per monster killed, and on level 16 you get 10,
 +
000 xp per monster (so level 16 has half a million xp of monsters on it
 +
- suitably impressive amount :-)
 +
 +
A 'basic' formula for this would be: (n to the power of ((n minus 1) divided
 +
by (15 divided by 4)))
 +
 +
Which gives these results:
 +
1 1
 +
2 1.847849797
 +
3 3.414548874
 +
4 6.309573445
 +
5 11.65914401
 +
6 21.5443469
 +
7 39.81071706
 +
8 73.56422545
 +
9 135.9356391
 +
10 251.1886432
 +
11 464.1588834
 +
12 857.6958986
 +
13 1584.893192
 +
14 2928.644565
 +
15 5411.695265
 +
16 10000
 +
 +
 +
You then need to figure out how many xp are needed for each level (use a
 +
spreadsheet!), and split the difference between levels, and then somehow
 +
figure out a formula for advancing.  I came up with (2 to the power of n)
 +
plus (n cubed) minus (25 times n).  Which is ok, but given more time we
 +
could come up with something better.  In particular, I'd reduce the base
 +
number of the power to something in the range of 1.97 to 1.99 so as to get
 +
closer to the 'ideal' value for that last level (you would get to 20th level
 +
with three creatures remaining given the formula above).
 +
 +
Some things to think about: do the rewards actually match the difficulty.
 +
For instance if a level 12 monster isn't really much harder to kill than
 +
a level 8 monster, why hand out ten times as much xp for killing it?
 +
 +
In fact, the difficulty of balancing even a limited scenario as outlined
 +
above means that you are far better off having a 'complicated' function
 +
for handing out experience, than aiming for some mathematically pure function.
 +
 +
An example: Offense * Defense is a very good measure of combat capability
 +
(ignoring the effects of swarming, assume that the character can always
 +
retreat such that they only fight one monster at a time).  Offense is the
 +
average damage they do (ie chance to hit times average damage times number
 +
of attacks) and defense is how much damage they can take on average (ie
 +
chance to avoid damage times hit points).
 +
 +
Example 1: a rat which does 1-2 points of damage, has a 1 in 3 chance of
 +
hitting, has no chance of dodging and 2 hitpoints would be worth 1 xp. 
 +
((1.5 times (1 divided by 3)) times 2)
 +
Example 2: a balrog which does 10-20 points of damage, has a 100% chance
 +
of hitting, gets three attacks a round, avoids (dodges/deflects/counterspells/whatever)
 +
50% of attacks and has 100 hit points would be worth (15 times 3) times
 +
((100 divided by 50)  times 100) or 9000 xp.  Actually, that might not be
 +
enough :-)
 +
 +
You can increase the spread by raising the amount of xp from the above formula
 +
by some power greater than 1, try 1.1 or 1.2.  9,000 to the power of 1.2
 +
is 55,602 which should keep the players happy.  Whereas 1 to the power of
 +
anything is still 1.
 +
 +
Other factors to consider are the dungeon level the character has gotten
 +
to, what resistances the monster has, whether the monster has ranged attacks
 +
(these are really nasty in roguelikes, you may wish to reward the players
 +
accordingly) and whether it drops items that help the player (which are
 +
a reward in themselves in that they improve the character) when it dies.
 +
Of course killing an Elder Dragon and having the experience it gives you
 +
reduced by 10% because it dropped a +1 dagger, would suck.
 +
 +
In terms of experience to go up levels, something to avoid is requiring
 +
as mush xp to go from 1 to 2 as from 2 to 3.  This can happen when you use
 +
an exponential curve that doubles for a while.  Just as a wild totally random
 +
example, take a fighter that needs 2000xp to get to level 2, and 4000xp
 +
to get to level 3, and 8000 xp to get to level 4 etc.  Now think about this,
 +
in order to get to level 2, the fighter had to gain only 2000xp, but this
 +
is also the amount they need to gain in order to get to the next level,
 +
but now they have an extra levels worth of hitpoints, better chances to
 +
hit etc, which means that it is easier to get from 2 to 3 than it was to
 +
go from 1 to 2.  And the game shouldn't get easier as they go up levels.
 +
 +
cheers,
 +
 +
Rick
 +
 +
= Allocating Experience and Character Advancement - Matthias E. Giwer [mgiwer@ij.net]. =
 +
 +
First, a brief bit about my experience in this area:
 +
 +
I've been an active player of "pencil and paper" role playing
 +
games since 1987, encompassing more than thirty (truthfully, I've
 +
forgotten all the games I've played) different systems, as well as a
 +
number of "tactical" games such as BattleTech, Warhammer, etc.
 +
 +
I've spent (wasted :) hundreds of hours in roguelikes such as
 +
Larn, Moria, Nethack, (A-Z)ngband, ADOM, etc.  I attempted to develop
 +
my own on several occasions, the most recent attempt being Saga, a Perl
 +
roguelike.
 +
 +
I do not claim to be the worlds most serious gamer, nor the
 +
worlds best software engineer, but I do feel I have enough experience
 +
on this subject to be able to offer some useful information.
 +
 +
 +
Now, on to the meat:
 +
 +
How you implement character advancement will depend heavily on
 +
your choice of game mechanics. For example, is it a level based system
 +
where a 10th level being will be ten times more capable than a 1st
 +
level being? a hundred?  Or is it entirely skills based, where
 +
facility with a particular weapon or ability is to be developed
 +
independently of any other capability?
 +
 +
The majority of current roguelikes seems to be dominated by
 +
levels and level/skills hybrids.  This is fine, though while I
 +
personally advocate an entirely skills-based approach, it is truly a
 +
matter of taste.
 +
 +
The base idea is that individual actions performed by the
 +
characters will return (on success, failure or both) some measure of
 +
"experience", either generic or towards the skill governed by the
 +
action. In order to develop a mental yardstick, I usually try to get
 +
a firm idea of what a brand new, baseline character is capable of. In
 +
most roguelikes today, that would be a human fighter.
 +
 +
Next, try to imagine what this character would be capable of, if
 +
his abilities were taken to their absolute limits, without regard to
 +
items and equipment that may boost her capabilities. This should give
 +
you a continuum of capability that will let you look at, and gauge,
 +
difficulty of things like quests, unique creatures, and so on.
 +
 +
It also usually helps me to think of creatures that this
 +
character may face as based on this brand new beginning fighter.  In
 +
other words, a Grey Kobold is about half the power of a beginning
 +
fighter, but an Elite Orc Guardsman is six times more powerful than
 +
the baseline.
 +
 +
Yes, there is a LOT of tweaking and experimentation involved to
 +
get it right. Also, many abilities can make combat orders of magnitude
 +
simpler (teleportation, ranged attacks, etc) so this has to be taken
 +
into account when trying to judge anything other than a raw fighter
 +
type.  Again, there is no perfect measure, experimentation is the key
 +
to balance here.
 +
 +
If you wish to model the real world, most performance type
 +
skills (dancing, martial arts, typing, etc) are developed in terms of
 +
plateaus that may take months or years to break through, usually on a
 +
sliding scale of time.  The first plateau might take only a few weeks
 +
to reach, but the next may take a few months, etc. Roguelikes (and
 +
many traditional RPG's) model this with each "level" requiring
 +
progressively larger amounts of experience points to reach.
 +
 +
However, because most games give out larger amounts of
 +
experience for more difficult and more powerful creatures, the result
 +
is that most characters end up on a hyper-accelerated track, and can
 +
reach quite amazing levels of skill in relatively short amounts of
 +
game time. Now, as a fantasy game goes, that is perfectly acceptable,
 +
but it does make it more difficult to judge when a player is ready to
 +
face the "Deep dwelling Thing from Beyond". Then again, people don't
 +
play roguelikes because they are easy. ;)
 +
 +
I would have no issue with this, if it was a one-time event. 
 +
For example, the first time you wipe out a Grey Ooze, get the full
 +
experience value for it.  For each one after, only bestow a standard
 +
action credit that doesn't change, for all actions of that type. New
 +
things, and new challenges help you grow a lot, practice helps you a
 +
little (which is why you have to keep at it).
 +
 +
An extension of this idea is experience for, say, casting
 +
spells. You get full experience value the first time you cast a new
 +
spell, but only a small "cast spell" value each time thereafter. The
 +
idea works for any ability that is action based, rather than intrinsic
 +
or "always-on".
 +
 +
For added realism (ha :), it may be worth investigating a
 +
"decay" function for skills and abilities that go unused for long
 +
periods of time, with the time before decay increasing the higher the
 +
level of skill.
 +
 +
 +
Like the design of any game system, this article is two parts
 +
experience and one part prejudice. I hope that, at least, mentioning
 +
these issues will prompt roguelike designers to devote more thought
 +
game mechanics issues, and to question some accepted standards.
 +
 +
I do apologize if you were looking for code examples, but the entire
 +
issue of character development is so tightly bound to the specific
 +
system and other game mechanics to make even pseudo code examples
 +
just about worthless.
 +
 +
Feel free to write me with questions, comments, etc.  Please keep the
 +
flames constructive, thanks! :)
 +
 +
-Matthias E. Giwer
 +
mgiwer@ij.net
 +
 +
= Creating A Player - Brian Bucklew [bbucklew@inteletek.com]. =
 +
 +
Section 1 : The Definition
 +
 +
[Note : I will be using C++ Class definitions]
 +
 +
        So, let's pretend we have a nice endless dungeon filled with
 +
vile demonic beasts, heaps of gold, and piles of flaming swords of instant
 +
monster to magic item transmutation. Mabey we even have an engine to make
 +
the ubiquitous '@' saunter around in this great dungeon.
 +
        Now, what we really need is some way to make that little '@' into
 +
a daring adventurer, with Herculean strength and an intelligence to
 +
rival Hawking (or perhaps the lack of the same...).
 +
        First off, we need to have some basic statistics and attributes.
 +
perhaps we need a Name, a Race, and a Class... We also need some numbers
 +
to represent the Hero's strength, and intelligence as well as his other
 +
important attributes.
 +
        Now, in any RL, a player's Statistics are going to go up and
 +
down during the course of play, whether it's from going up a level or
 +
getting hit by a Lecherous Walking Carrot Of Charisma Sapping. So we should
 +
really represent each score by two numbers, a current score and a base score:
 +
 +
class Stat
 +
{
 +
        public:
 +
        int    Base;
 +
        int    Current;
 +
}
 +
 +
        All of our calculations done in the game should be based off of the
 +
current score, but the base score will allow us to revert to the Player's
 +
origional score or hit-point total after a magical-effect or damage wares
 +
off.
 +
 +
        Having the basic stat class, let's go ahead and derive a class to
 +
contain a basic RL character:
 +
 +
class Player
 +
{
 +
        public:
 +
        char    Name[256];      // A String to hold the player's name
 +
        int    Race;          // let's say, 0=Human 1=Elf 2=Frog...
 +
        int    Class;          // hmm... 0=Fighter 1=Mage 2=Tourist...   
 +
 +
        Stat    Str;            // How Strong
 +
        Stat    Int;            // How Smart
 +
        Stat    Dex;            // How Fast
 +
        Stat    Hlt;            // How Healthy
 +
        Stat    Cha;            // How Well-Liked
 +
 +
        Stat    HP;            // How much damage you can take
 +
        Stat    AR;            // Your armor-rating
 +
        Stat    SP;            // Spell-points... How many kobold you can toast
 +
};
 +
 +
        That should be a good starting point for developing a unique character
 +
representation for your RL...
 +
 +
Section 2 : The Creation
 +
 +
        The actual creation of the character is accomplished by somehow
 +
assigning a score to each of the stats... There are two main ways
 +
to accomplish this; Random Rolling and Point Distribution.
 +
        Random Rolling would display all of the statistics, and allow
 +
the player to hit a key to "Roll" (or randomly assign numbers, say between
 +
1 and 100) to each main statistic. The player would then continue rolling
 +
until they have a set of numbers that is agreeable to them.
 +
        Point Distribution would give the player's a number of points, say
 +
100, and allow them to distribute those points to their attributes in any
 +
way they wish; Thus allowing the player to design a character that they want
 +
to play.
 +
       
 +
Usually, the player's chosen race affects the statistics in some way.
 +
For instance if our player picked:
 +
 +
A Human - No change; Humans should be pretty standard fare.
 +
An Elf  - +2 Dex, -2 Str; Elfs are quick, but weaker than humans
 +
A Frog  - +2 Int, -2 Cha; Frogs are obviously intelligent, but ugly...
 +
 +
Classes are generally restricted by attributes...       
 +
 +
Fighters - No basics; Everyone can pick up a stick and hit something...
 +
Mage    - At least a 12 Int; A Mage has to read, at least...
 +
Tourist  - At least a 12 Dex; You have to move fast, only 36 days left of
 +
                              vacation...
 +
 +
The player might be given some basic equipment based on his class, and
 +
that's about it... That '@' has everything it needs to thump some Kobolds!
 +
                               
 +
The Author:
 +
Brian Bucklew, 18
 +
bbucklew@inteletek.com
 +
Current RL Project : Dungeon or "This game needs a new name"... :)
 +
Projected Beta Release : Early 98
 +
 +
= Pretty Pictures - Darren Hebden [rogue@skoardy.demon.co.uk].txt =
 +
 +
Some thoughts on Graphics in Roguelike Games.
 +
by Darren Hebden [rogue@skoardy.demon.co.uk]
 +
 +
 +
Traditionally, if you suggested graphics to a roguelike-
 +
stalwart, you would have found yourself out on your ear for speaking
 +
such heresy. Many would argue that being text-based is a defining
 +
feature of the roguelike genre. Others want more and look upon
 +
graphics as a natural progression.
 +
 +
Many people (purveyors of quality knee-jerk reactions and 'The
 +
end is Nigh' flavoured rantings) warn of the old-style being phased
 +
out or graphic-based roguelikes lacking the same depth of text-based.
 +
Personally, I like to believe that both can exist quite happily and
 +
that the addition of graphics in roguelike games is a bonus, not a
 +
replacement. It is a new feature and it's use within the roguelikes
 +
is still being explored.
 +
 +
This document talks a little about the uses of graphics in
 +
roguelikes, the different styles and some graphic techniques. Not
 +
being an expert on all systems (or the one I own, come to that), I'll
 +
try to make my article non-machine-specific. If you know a little
 +
about the packages you own, you should be able understand my texts.
 +
 +
                              ----//----     
 +
 +
# Why Graphics.
 +
 +
PROS.
 +
1) It's a "draw".
 +
The visual style attracts the eye to games that many of the
 +
uneducated heathens (sorry, I mean -- people who haven't encountered
 +
roguelike games before) would ignore and pass over because of their
 +
archaic text-editor style appearance.
 +
 +
2) It's expected.
 +
Unfortunately, the expectations of todays game player have been
 +
adversely influenced by big budget, multi-cd, flashy productions. I
 +
don't exactly find this a pleasant situation but ignoring it or
 +
"taking a stand" won't help you or your game.
 +
 +
3) So what's a 'Furgikan-bug'?
 +
Although a great deal of people are up on Tolkien lore and AD&D
 +
monster theory 101, but an unknown creature shown as a 'F' character
 +
on-screen may leave several of your players scratching their heads. A
 +
well-drawn image, however, is instantly recognisable and gives a
 +
better impression of the creatures appearance.
 +
 +
CONS.
 +
1) Graphics kill the imagination.
 +
The original roguelike style counts on the players imagination
 +
to transform a simple red 'D' into the terrifying bulk of Fire Dragon
 +
flesh. No matter how detailed your graphics are, they may not be able
 +
to live up to the visions swirling around an over-active imagination.
 +
 +
2) Bigger programs.
 +
The storage of large amounts of graphics data all adds to the
 +
overall archive size for your game. It's very difficult to produce a
 +
competent roguelike game with a small selection of graphics without
 +
compromising the colour-depth or tile size. Whichever way you even
 +
things out, graphics mean an increased game footprint.
 +
 +
3) Bad graphics drag a game down.
 +
Good graphics can really add to the atmosphere of a game but in
 +
the same way, a bad set of graphics can seriously hamper a game which
 +
is technically competent and full of depth. Will you be able to supply
 +
good graphics for your game or would the game be better served staying
 +
with a text only display? Don't treat graphics like the current
 +
band-wagon to climb aboard.
 +
 +
                              ----//----     
 +
 +
# Graphic Styles.
 +
 +
Although all through this document I speak of older roguelikes
 +
being text based, simple texts characters _are_ a form of graphics. A
 +
'g' from a gremlin may be missing a few limbs and that mad glint in
 +
his eye but people soon become lost within the game world and accept
 +
that a horde of crazed 'g's bearing down on a weakened adventurer is
 +
not a good sign.
 +
 +
There are several different styles that you can use when representing
 +
your dungeon on-screen.
 +
 +
1) Flat Tiles.
 +
The most typical use of graphics in roguelikes is a one-for-one
 +
replacement of the ascii-characters themselves. A wall character is
 +
replaced with a brick pattern, a water character by a lump of blue.
 +
 +
A little work is needed re-assigning what is displayed or how
 +
they are arranged on screen but often, this method restricts the
 +
artist in getting the best from the tile size and colour depth
 +
available. Due to the forced nature of the way the tiles may be
 +
arranged, the artist could be unable to introduce some details that
 +
would improve the overall look.
 +
 +
This style doesn't _have_ to suffer from badly arranged tiles if
 +
the artist uses the way the tiles are placed to his benefit and the
 +
programmer is willing to make slight alterations to get the best out
 +
of the tiles provided. The perfect solution is to be programmer and
 +
artist :-)
 +
 +
Badly drawn example... XXXXX
 +
                      XXXXX
 +
                      XXXXX
 +
                      XXXXX
 +
                      XXXXX
 +
 +
 +
2) Pseudo-3D Flat Tiles.
 +
The next style is very similar to the first but instead of flat
 +
patterns for tiles, the impression of depth is given by drawing front
 +
edges on lower half of the tile for the walls. It's a cheap trick but
 +
is quite effective. The illusion is only spoiled by the fact that the
 +
player cannot walk behind the tiles as they occupy the same space as a
 +
normal wall tile. A little 'walk-behind' effect can be gained if the
 +
tiles are overlapped. It okay but you also begin to lose a little of
 +
the floorspace of the tile above.
 +
 +
All in all, a popular choice and for tiles that need a little
 +
more work when it comes to designing them to fit together. It means
 +
more graphics but generally, it's worth it.
 +
 +
Badly drawn example... XXXXX
 +
                      XXXXX
 +
                      XXXXX
 +
                      |||||
 +
                      |||||
 +
 +
 +
3) Isometric Tiles.
 +
These tiles create the impression that the level is viewed from
 +
an angle of 45 degrees to the left/right. As they go, this style gives
 +
a very good illusion of depth (apart from the total lack of
 +
perspective, ofcourse).
 +
 +
A problem with this style is that these tiles really need to
 +
overlap. I've tried some experiments with not overlapping them and
 +
they looked very bizarre. The overlap causes a bit of lost floorspace
 +
of the tiles drawn above the walls but this can be reduced by having
 +
shorter walls.
 +
 +
As with the overlapping from the previous style, don't go over the top
 +
with the shortened walls though or you'll have levels looking like a
 +
stunted hedge-maze.
 +
 +
A solution would be to make any wall that overlaps a floorspace
 +
semi-transparent. This effect can be achieved by either some rather
 +
clever palette mixing tricks on the programmers side of things (which
 +
is rather a bit of overkill for a roguelike) or by a chess-board style
 +
hashing of the pixels over the overlapped area -- one pixel of the
 +
wall, one of the floor, etc. It is a bit of a cop-out but quite
 +
effective.
 +
 +
Badly drawn example...  X
 +
                        XXX 
 +
                      XXXXX
 +
                      |XXX|
 +
                      ||X||
 +
                        |||
 +
                        |
 +
 +
 +
4) Tunnel Vision (or That-Style-From-Dungeon-Master).
 +
The player is presented with a full perspective view of a
 +
corridor/tunnel of the dungeon. Items in the distance are smaller and
 +
tunnels lead off from the original at right angles. Movement is
 +
generally made in steps and switching the direction viewed usually
 +
snaps round ninety degrees.
 +
 +
This style allows for more detail on the wall/floor tiles as the
 +
tiles closest to the player are quite large on screen. I've yet to
 +
see this used in a roguelike game although it has been suggested
 +
quite a few times. Other games have used this style and in some
 +
ways, you could argue that Dungeon Master, Eye of the Beholder, etc.
 +
are in essence roguelike.
 +
 +
One reason for it not being implemented is that the player can
 +
only see in one direction at a time. Usual roguelikes have forces
 +
coming at the player from all sides. This may put several players off
 +
due to the confusing nature of this 'realistic' feature. Other
 +
windows containing the left/right/back views may help this situation.
 +
 +
Badly drawn example...  .........
 +
                        |.......|
 +
                        ||.....||
 +
                        |||  |||
 +
                        |||  |||
 +
                        ||.....||
 +
                        |.......|
 +
                        .........
 +
 +
 +
5) 3D Texture Mapped.
 +
The last style I'm going to cover is texture mapping. So far
 +
(without making a massive leap with the definition of the genre), no
 +
roguelike game has ever used texture mapped 3D graphics. I'm sure if
 +
you visualise a game like Quake, or whatever the current splurge of
 +
the month is, you'll realise what I'm getting at here.
 +
 +
One problem with texture mapping is that to get a good
 +
definition on the walls, floors, etc. the textures need to be of a
 +
fair size otherwise, close inspection of a wall reveals a horrible
 +
level of pixelisation. 3D accelerator cards (and a certain console)
 +
can provide techniques to smooth the textures but now we're getting
 +
into silly-land. Roguelike game with texture-mapped polygons needing a
 +
3D accelerator card? Hmm. One day maybe...? ;-)
 +
 +
Anyway, it's really up to you as to what looks right and at what
 +
point it stops looking like a wall pattern and more like a bunch of
 +
large square pixels. Working towards high quality textures means
 +
bigger textures and even more space taken up by the graphics.
 +
 +
Obviously, programming such a view for just a roguelike game
 +
is no small fear either when compared to the original text-mode (or
 +
even the other styles mentioned in this document). How you present
 +
your 3D environment is up to you. Possible options are the fully
 +
submersing environments of Quake/Mario64. Or you could go for an
 +
isometric display such as Bullfrog's Dungeon Keeper.
 +
 +
Badly drawn example...  Yeah, right.
 +
 +
                              ----//----     
 +
 +
# Issues
 +
 +
Some problems you might want to take into consideration when working
 +
on your graphics...
 +
 +
# Colour Depth.
 +
 +
Colour depth is essentially how many colours you're allowed to
 +
create your wondrous and vivid roguelike graphics. Basically there is
 +
two camps. The programmers want the less number of colours possible
 +
and the artists generally want the most. The exception to the
 +
programmers is when the programmer in question doesn't care how much
 +
space the game takes or already has the code to handle higher colour
 +
depths. The exception with artist is when you find an artist who knows
 +
they can get the same effect with less colours.
 +
 +
A set of tiles that only use a palette of 16 colours but have
 +
been stored as in a graphic format that utilises 65,000 colours uses
 +
up more memory than exactly the same tile set in a format that only
 +
allows for only 16 colours needed. If your tiles only take up a small
 +
range of colours, that 16bit (or 24bit) mode could be a waste of time.
 +
And if you can get beautiful tiles with 16 colours, programmers will
 +
love you. :)
 +
 +
Again, it's a balance. Try some test tiles first. If you've got
 +
a list of the tiles needed, experiment with some fairly mis-matched
 +
sets and see how they stand up to the lower colour depths. If you're
 +
not happy with how they are working out, move up to the next depth.
 +
Remember though, an artist may have to compromise the graphics he/she
 +
creates to work within limits. Do the best you can with the tools
 +
available and the boundaries you are set.
 +
 +
 +
# Tile Size & Screen Size.
 +
 +
In a perfect world, all players would have limitless hard-drive
 +
space, screen-resolutions that stretch into the ten-thousands and
 +
download the several hundred meg your game takes up in a second.
 +
Problem is, it  doesn't work like that. Once again, file-size is
 +
affected by the choice you make over tile sizes. Deciding to expand
 +
your tiles from 16x16 pixels to 32x32 pixels will increase the file
 +
space each tiles takes up by 4. If the programming has decided they
 +
want tiles for each of the five-hundred different flavours of gnome
 +
they've implemented, we're talking of a big increase.
 +
 +
Can you do everything you want with 16x16? Can you get all the
 +
detail you need and is the detail really necessary? In some cases, a
 +
good artist can 'imply' detail in a very small space. Do you really
 +
need to see the texture on the knight's chain mail or would a light
 +
grey mesh give the same impression?
 +
 +
Another point to take into consideration is the screen size. A
 +
small screen size and a large tile size could cause trouble and
 +
restrict the amount of 'dungeon' you can see at one time. Small tiles
 +
on a huge screen could mean the player has trouble making out the
 +
tiles and misses out important details. Again - balance.
 +
 +
See what the programmer wants. How many tiles do they want
 +
onscreen. Make sure that they understand how big that would allow you
 +
to make the tiles. A sample screen knocked up in five minutes is
 +
usually a good visual aid for both you and the programmer. Does it
 +
look right?
 +
 +
If there is a lot of other information needed onscreen, the
 +
amount of screen left over to the level window may be cut down. Make
 +
sure you take all of that into consideration.
 +
 +
 +
# Resizing or Reducing Colours.
 +
 +
Okay. You've created all your tiles. Five hundred gnomes of all
 +
shapes, sizes and colours. All in 64x64 pixel, 24bit colour tiles. The
 +
programmer gets in touch and tells you that they can't use them. They
 +
need 16x16, 16 colour. Bugger...
 +
 +
Well, you've got three choices - call it a day, move to Tibet
 +
and take up the serene life of a monk or restart from scratch or start
 +
reducing tile size and colour depth. In the extreme case stated above,
 +
the reduction is going to pretty much murder your graphics and perhaps
 +
restarting is the only way to go. In other situations, when you only
 +
need to reduce the colour depth or just resize, you might just get
 +
away with it.
 +
 +
One thing to remember when reducing colours, it always helps to
 +
choose a good utility/art package. The best way to test this is to use
 +
it with other graphics first. Choose a picture (maybe a scan of some
 +
sort) with a fair spread of colours and detail. Reduce the colours. If
 +
you're coming down from 24bit to 16bit, chances are you won't notice
 +
the reduction but down to anything less and the package has to create
 +
it's own palette of used colours.
 +
 +
Most often, it's a best-fit and most-used kind of technique.
 +
Some packages offer different methods for reduction and some use a
 +
dithering algorithms to fool the eye. Sometimes it even works.
 +
Remember though, you may be reducing the colours of some fairly small
 +
tiles and when they begin to repeat in the game, the pattern these
 +
dithered tiles create may become very noticeable. The key to reduction
 +
is getting a good palette. Again, this depends on the tool you use.
 +
 +
One thing I have noticed is once your package has reduce the
 +
colours, it tends to organise the colours in the palette in a manner
 +
which I find a little 'random'. Personally, I like my colours divided
 +
up into nice hue sets but after reduction, most packages generate
 +
light-to-dark range or that bizarre mac-style organisation that I
 +
dislike so much :) It's a little gripe but remember that if you're
 +
drawing more tiles after the reduction, finding the exact colour
 +
you're after may become a pain in the ass.
 +
 +
Resizing is another matter. Most resizing does cause your tiles
 +
to lose all their detail and essentially makes touching-up afterwards
 +
a must. Some packages anti-alias or blur the tiles to cover the loss
 +
of detail. This is all very nice within the tile but you've got tiles
 +
with areas that are supposed to be transparent (for overlaying onto
 +
floor tiles, etc.) then the program tends to blur the edges of the
 +
shapes and destroy the clean edge you need. A good package will allow
 +
you turn this off.
 +
 +
 +
# 1001 Monsters.
 +
 +
Not just monsters but potions, swords, shields, helmets,
 +
scrolls, spell-books, traps, walls, floor, stairs, food... well, you
 +
get the idea. When you think of all the tiles you may be called on to
 +
draw, you start begin longing for those simple ascii-characters. When
 +
drawing your tiles, it's always a good start to have some sort of idea
 +
of how many monsters, etc. will be required. If you need several
 +
different types of mold (green mold, yellow mold, red mold, blah-blah-
 +
blah), you would probably be able to get away with the same graphic
 +
but with changes to the colour. It saves time and allows you
 +
concentrate on making the basic mold design stand out from your other
 +
creatures.
 +
 +
It is also useful to find a theme within creatures. If you need
 +
several ranks of orc, maybe changing their size and armour might help.
 +
If you have a set of monsters that have a specific trait (nether
 +
beasts, lava beasts), it'll help player recognition if you style those
 +
creatures similarly.
 +
 +
 +
# 3D packages.
 +
 +
All styles can enjoy the benefits that using a 3D package can
 +
give. For the 2D bitmap tiles, building your objects and monsters with
 +
a 3D package means that size or colour depth isn't really an issue any
 +
more. The object you create can be rendered from any angle, at any
 +
size and with varying amounts of colour (if the package you're using
 +
is any good in the first place). And because the output is from the 3D
 +
package itself, outputting a smaller render will generally give a
 +
better result than trying to reduce the size of the tile with another
 +
graphics utility.
 +
 +
Ofcourse, the amount of work required initially is massively
 +
increased as you need to model all the objects you wish to show. The
 +
benefit comes from the flexibility afterwards. For the user wishing to
 +
create modeled creatures for a Quake-style roguelike, a 3D package is
 +
essential. I'm sure there are people out there who can quite happily
 +
create some very good models with a pencil and graph paper but with
 +
so many cheap and shareware modelers on the market, save yourself the
 +
bother.
 +
 +
 +
# Size matters?
 +
 +
Okay, first you're asked to draw a mouse and then you're asked
 +
for a poison breathing dragon. Do your work in scale? Draw a mouse
 +
that takes up a tile then draw a dragon that fills half the screen?
 +
'Course not. If you're drawing a dragon that takes up a tile but a
 +
mouse in scale would be hard pushed to fill a pixel. It takes some
 +
getting used to be it's usually a good idea to throw scale out of the
 +
window. Just pretend that mouse is really, really, really close. :)
 +
 +
 +
# Conclusion.
 +
 +
As you've probably gathered by now, how you go about creating
 +
your graphics depends largely on the games needs. If you have been set
 +
limits either by the programmer or the hardware you're aiming for,
 +
always experiment to get the best you can from the tools you have
 +
available. If you're given an open-ended project with no definite
 +
requirements, planning will save you a lot of work in the long run.
 +
Decide which colour depth and tile size is best for the game and stick
 +
with it.
 +
 +
Whatever style you choose, its all a question of whether your
 +
roguelike needs these graphics. Do they honestly add something to the
 +
game? Ignore those who automatically scream 'no!' or have built up
 +
some kind of barrier to considering the option. Graphics are just
 +
another feature to add to your game. Like everything you add, whether
 +
it works or not is up to you.
 +
 +
= Object Representation - Sean Middleditch [sean.middleditch@iname.com]. =
 +
 +
Representing objects in a roguelike.  A difficult thing to do, in fact.  When
 +
I started War of the Runes, I wasn't sure exactly how to go about doing it.
 +
Would everything be hard coded into the game?  Would objects be malleable?
 +
What kinds of different objects need to be represented?
 +
 +
Well, for starts, I knew I didn't want anything to be hard coded.  One thing
 +
about War of the Runes is that EVERYTHING would need to be able to be changed.
 +
So objects need to be stored in external files, with all descriptions of the
 +
object need to be stored; from description, to behavior, to properties.  And
 +
this also means all objects needed to be malleable. the state of an object can
 +
change at any time through any number of ways.  And what kinds of objects were
 +
there?  There's weapons and armor, food and drink, doors, chests, bags, rings,
 +
books, anything that can exist in a real world.
 +
 +
So what is the best way to represent objects in a roguelike?  Well, first we
 +
need to start with an object class:
 +
 +
class Object {
 +
public:
 +
 +
What kind of data do we need for objects?  For starts, we need to know what
 +
the object is.  We can do this with a name and a description;
 +
 +
char *Name, *Desc;
 +
 +
That's fairly self-explanatory.  Information about where the object is would
 +
be useful, too:
 +
 +
int X, Y;
 +
 +
There are lots of different objects in the roguelike universe.  Armor,
 +
weapons, books, rings, potions, lawn-chairs, etc.  Each object can only be
 +
of one type.
 +
 +
int ObjType;
 +
 +
This field will be set to a value we define with #define's.
 +
 +
#OBJ_WEAPON 1
 +
#OBJ_ARMOR 2
 +
#OBJ_POTION 3
 +
 +
You get the idea.  Every different type of object in the game would need a
 +
separate number.  This will help in a LOT of areas.  For example, characters
 +
can only equip items of type 2 (armor).
 +
 +
Since I'm sure some of you may be a bit confused (I know I'm not the best of
 +
teachers) why don't we start defining an example item before we continue?  A
 +
longsword.
 +
 +
We'd set the Name field to point to "long sword".  Simple enough.  The Desc
 +
field would be "a long, sharp, metal stick".  Well, you may want to use
 +
something other than that.
 +
 +
The X,Y coordinates can be set to whatever... let's say 2,10.
 +
 +
What about the object type?  1 (OBJ_WEAPON) of course!
 +
 +
Now what?  What does a longsword do?  The game knows it's a weapon, but the
 +
game needs more information than that.
 +
 +
Let's make a class to define what an object does.
 +
 +
class ObjArg {
 +
public:
 +
 +
Each ObjArg will define one aspect of an object.  We'll need a way to store
 +
what each ObjArg defines.
 +
 +
int ArgType;
 +
 +
We'll give this meaning through the use of more defines.
 +
 +
#define OARG_ATTACK 1
 +
#define OARG_DEFEND 2
 +
#define OARG_HEAL 3
 +
 +
Now we know what an ObjArg defines.  Now we need to store the actual
 +
definition.  We'll do this by storing an array of 5 integers.
 +
 +
int Args[5];
 +
 +
And that's all there is to the ObjArg class.  The meaning of the Args
 +
array's field will depend on the value of ArgType.
 +
 +
Now, we want every object to be pretty versatile, so we'll make it so
 +
every object has 5 of the ObjArg classes.
 +
 +
} Defines[5];
 +
 +
And that's all we need for a basic Object class
 +
 +
};
 +
 +
So how does the ObjArg class work?  Well, for our longsword, we'll need
 +
only one.  It's ArgType will be set OARG_WEAPON.  Now what about the
 +
Args array?  Let's say for ArgType 1 (weapon), the first field of Args
 +
is the number of damage dice, the second field is sides per die, the
 +
third field is damage modifier, and the fourth field is the modifier
 +
to the character's skill.  The fifth field will be unused.
 +
 +
So, if we wanted long sword's to cause 1 to 8 damage, with no
 +
additional modifiers to damage or attack skill.  So...
 +
 +
Args[0] = 1
 +
Args[1] = 8
 +
Args[2] = 0
 +
Args[3] = 0
 +
 +
Now if the character equips the long sword and attacks, we'll first
 +
check to see what kind of object is in the character's hand.  We see
 +
the ObjType field is set to 1 (weapon).  OK, so he/she can attack with
 +
that object.  Now we'll look through the Defines array until we find an
 +
ObjArg entry whose ArgType is set to 1 (attack).  The game see that
 +
Defines[0].ArgType = 2, so we'll use that ObjArg to look up the weapon's
 +
statistics.  The game checks Defines[0].Args[3] = 0, so there's no skill
 +
modifier.  The game does whatever combat system and determines the
 +
character hit.  It check the damage (Args fields 0, 1, 2) and sees that
 +
the long sword does 1d8+0 damage.  The game rolls the damage, hurts the
 +
target, etc.
 +
 +
Well, that's all you need for simple objects.  Although, you could do a
 +
LOT more, using the sample code I've given here as a base.  For example,
 +
some ObjArgs are in effect whenever an item is equipped (the long sword's
 +
attack field, or armor's defend field).  Some objects, like potions,
 +
don't effect unless a character uses the object (or in the case of objects
 +
with ObjType = 3, the character quaffs the potion).  Only then will their
 +
ObjArg fields (like healing, in the case of a potion of healing) take
 +
effect.  So you might want to store how many times an object can be used,
 +
and how many times it has been used.
 +
 +
The complete code for the Object class is:
 +
 +
#define OBJ_WEAPON 1
 +
#define OBJ_ARMOR 2
 +
#define OBJ_POTION 3
 +
 +
#define OARG_ATTACK 1
 +
#define OARG_DEFEND 2
 +
#define OARG_HEAL 3
 +
 +
class Object {
 +
public:
 +
 +
char *Name, *Desc;
 +
 +
int X, Y;
 +
 +
int ObjType;
 +
 +
class ObjArg {
 +
public:
 +
 +
int ArgType;
 +
 +
int Args[5];
 +
} Defines[5];
 +
};
 +
 +
If you have any questions, feel free to e-mail me at
 +
sean.middleditch@iname.com
 +
 +
The End
 +
 +
= Inventory Abstraction - Kenneth Power [uncle_wiggly@bigfoot.com]. =
 +
 +
An Inventory tracks Items in Storage. Items are anything you deem
 +
trackable: gloves, clubs, food, coins, flowers. Storage is anything
 +
defined as able to hold items: chests, sacks, hands, buildings.
 +
 +
A basic Inventory does not care about extraneous fluff, such as
 +
container limitations. Keeping inventory implementation basic enables
 +
code reuse as discussed later.
 +
 +
Throughout this paper, psuedo code is used to model examples. The
 +
examples use the following sample item definition:
 +
 +
  define Item:
 +
      variable Name
 +
 +
 +
Tracking items
 +
There are two basic ways to track items. First is with a simple list,
 +
rather like writing a list of groceries. Lists usually are FIFO (First
 +
in First out) or LIFO (Last in First out). Other ways may exist. Indeed
 +
in some languages, there are very exotic forms of lists. A trouble with
 +
lists is the retrieval of information from the middle of the list. The
 +
list is examined from either end until the information is located.
 +
 +
Our example simple list:
 +
 +
  list define Inventory
 +
 +
Second is through a more complex scheme wherein more than the item is
 +
tracked. Also tracked is information about the item. This is so items
 +
may be grouped. Grouping has its pro's and con's like anything else.
 +
Use of grouping, for example, allows easier display of items (in my own
 +
opinion of course). In a way, grouping is a more esoteric list form,
 +
using such things as dictionaries, maps and other terms.
 +
 +
In this example, the items are tracked by their name.  Example:
 +
 +
  list define Inventory:
 +
      list define itemNames
 +
      keyedList define qtys
 +
 +
 +
Add items
 +
What use is an Inventory if you are not able to add items to it? Thus,
 +
the first function we define is the add() function.
 +
 +
In basic form, add() only wants to place the passed item to the list:
 +
 +
  List define Inventory:
 +
      define add(item):
 +
        insert item
 +
 +
With the complex form, add() is more detailed. Questions are raised:
 +
is the item already in inventory - this might affect or tracking
 +
feature-? Did I/you make an adjustment to the tracking feature if
 +
necessary? Note how this is done in the example:
 +
 +
list define Inventory:
 +
  list define itemNames
 +
      keyedList define qtys
 +
      define add(item):
 +
        if item is in me.itemNames      #do I exist?
 +
            then me.qtys.key(item.name) = +1
 +
        if item is not in me.itemNames  #I don't exist
 +
            then me.qtys.key.add(item.name)
 +
            me.itemNames.add(item.name)
 +
            me.qtys.key(item.name) = +1
 +
 +
 +
Remove items
 +
The remove() function is really the opposite of add(). Find the item
 +
passed and remove it from the list. Let's examin it with our two
 +
pseudo codes.
 +
 +
Of course, this example doesn't take into consideration language
 +
dependent behavior (C - did you fix your pointers?). Thus the
 +
abstraction is the same for add():
 +
 +
  List define Inventory:
 +
      define remove(item):
 +
        delete item
 +
 +
Here, as in the complex add() function, more work needs accomplished.
 +
We not only find the item, but we make certain our tracking feature
 +
is adjusted accordingly.
 +
 +
  list define Inventory:
 +
      list define itemNames
 +
      keyedList define qtys
 +
      define remove(item):
 +
      if item is in me.itemNames
 +
        then me.qtys.key(item.name) = -1
 +
        if me.qtys.key(item.name) == 0
 +
            then me.qtys.delete(item.name)
 +
      if item is not in me.itemNames
 +
        then error
 +
 +
At the completion, our example would show the proper quantity for the
 +
item. Plus, if we have no more item in inventory, no quantity or
 +
listing will exist.
 +
 +
 +
Display items (opt.)
 +
This is listed as optional, because you may not code Inventory display
 +
as part of your Inventory. It may be in your UI code. However, during
 +
testing, having a simple Inventory Display feature is very useful.
 +
 +
Like always, the simplest way is the list method. Merely iterate the
 +
list, printing each item:
 +
 +
  List define Inventory:
 +
      define display():
 +
        For each item in Inventory:
 +
            print item.name
 +
 +
Because of our tracking feature, we need print item and qty. Otherwise
 +
uncertainty will exist. The only added feature of the complex over
 +
simple is the header printed "Item        Qty".
 +
 +
  List define Inventory:
 +
      define display():
 +
        print "Item    Qty"
 +
        for each item in me.itemNames:
 +
            print item, me.qtys.key(item.name)
 +
 +
 +
Possible benefits
 +
For developers using OO style languages (C++, SmallTalk, Java, etc),
 +
having a simple Inventory Object lets you easily include it in other
 +
areas of the game. Containers (combinations of Items and Inventory),
 +
Buildings (Structure and Inventory), and more can be made. Of course
 +
non-OO languages(C, Pascal, Basic) can use Inventory as functions in
 +
other parts of the game. The point is: once you define what a basic
 +
inventory will be in your game, find how to use it in more areas.
 +
 +
An Example
 +
Here is an example inventory, using the Python language. I find Python
 +
to be a grat language for prototyping. It is easy to spot errors, fix
 +
them, etc. Then you may easily recode in any other language.
 +
 +
The Item Object -
 +
class Item:
 +
  def __init__(self, name): #object constructor
 +
      self.name = name
 +
The Inventory Object -
 +
class Inventory:
 +
  def __init__(self):
 +
      self. NameList = [] #a list of item names
 +
      self.qtys = {} #a dictionary of item quantities
 +
      self.contents = [] #a list of actual items
 +
  def add(self, itemList = []):
 +
      for item in itemList:
 +
        #Check item is self
 +
        if item is self:
 +
            print 'Cannot store', item,' in itself!'
 +
        if item in self.contents:
 +
            print 'You already have this item!'
 +
        else:
 +
            #Check if item is in nameList
 +
            if item.name in self.NameList:
 +
              #merely insert
 +
              self.qtys[item.name] = self.qtys[item.name] + 1
 +
            #otherwise add to nameList
 +
            else:
 +
              self.qtys[item.name] = 1
 +
              self.nameList.append(item.name)
 +
            self.contents.append(item)
 +
  def remove(self, item):
 +
      #does item exist?
 +
      If item not in self.contents:
 +
        print item.name, 'is not in your inventory'
 +
      else:
 +
        self.qtys[item.name] = self.qtys[item.name] - 1
 +
        if self.qtys[item.name] == 0:
 +
            del self.qtys[item.name]
 +
            self.NameList.remove(item.name)
 +
        self.contents.remove(item)
 +
  def display(self):
 +
      #let's show everything!
 +
      Print "Item\tQty"
 +
      for item in self.NameList:
 +
        print item,"\t", self.qtys[item]
 +
 +
 +
More Info
 +
For information about Python, visit: http://www.python.org
 +
Please send all comments, queries, and error notifications to the author.
 +
Written by: Ken Power email: uncle_wiggly@bigfoot.com
 +
Version: 1.0 Date: Oct. 25, 1999
 +
 +
= Creating Inventories - Erno Tuomainen [ernomat@evitech.fi]. =
 +
 +
----------------------------------------------------------------------------
 +
            CREATING INVENTORIES - WHAT TOOLS ARE AVAILABLE
 +
                        (C) 1997 Erno Tuomainen
 +
                          ernomat@evitech.fi
 +
                        16th of November 1997
 +
----------------------------------------------------------------------------
 +
 +
I know that many of you wonder about this problem. Atleast I did so when
 +
starting my Roguelike project (Legend of Saladir). In this article I
 +
intend to give you some tools for making those inventories, it's not
 +
intended to be a complete tutorial for making player inventories, maybe
 +
later I can offer you some more routines/ideas related to this subject.
 +
 +
I assume that the reader of this article is not a total beginner (hey,
 +
you are starting to make your own game! :) and has a basic knowledge of
 +
C-language along with knowledge of pointers.  And please, forgive me my
 +
bad english!
 +
 +
Without any more hassle, lets begin defining a basic item structure for
 +
all examples in this article. This is just an example, the item defined
 +
is not really useful in real development :)
 +
 +
  typedef struct ITEMTYPE
 +
  {
 +
      int itemtype;
 +
      int weight;
 +
      unsigned int attributes;
 +
  } Titem;
 +
 +
So this is just a data structure which contains all the information
 +
needed for a particular item. Every item in the game has a similar
 +
(exactly!) structure.
 +
 +
There are basically two methods of creating the inventory list for
 +
player/monster.
 +
 +
1. Fixed size array
 +
-------------------
 +
 +
You allocate an array of for example 100 items. Obviously this has one
 +
big disadvantage, you can't carry more than 100 items if the programmer
 +
doesn't change the code and secondly this array always takes
 +
100*sizeof(Titem) bytes of memory even if you were carrying just one
 +
item.
 +
 +
Player-information structure would look like this:
 +
 +
  typedef struct PLAYERTYPE
 +
  {
 +
      char name[100];  /* normal player information fields */
 +
      int age;
 +
 +
      Titem inv[100];  /* inventory array containing 100 items (See Titem definition) */
 +
  } Player;
 +
 +
So this is a structure which keeps all information about our player. You
 +
will have similar structures for your monsters/NPC's too, they might be
 +
a bit different but you can use the same methods for your monsters too.
 +
 +
So the size is constant. The good point is that additions and deletions
 +
to this list are easy, you can index it directly. However, you can't
 +
easily insert/delete items to/from the middle of the list. It requires
 +
rebuilding the array from the point where you are inserting. This is
 +
slow.
 +
 +
Another good point is that when you are going to save this structure,
 +
you just store this whole block into the file.
 +
 +
This kind of approach has it's own good uses, but I have a better method
 +
for the purpose we are talking about.
 +
 +
2. Dynamic memory allocation with linked lists
 +
----------------------------------------------
 +
 +
So what is this? Ok, you can guess from the name. Each time you need a
 +
new item added to the inventory you allocate space for it and link it to
 +
the inventory you already have for your player/monster.
 +
 +
This is a bit more complicated but it's not too hard when you go and
 +
think about it! When adding to the middle of the list, all you need to
 +
do is to go to the right place and move some pointers.
 +
 +
Now, keeping the above player structure mostly the same, but modifying
 +
only the inventory part we will get:
 +
 +
  typedef struct PLAYERTYPE
 +
  {
 +
      char name[100];  /* normal player information fields */
 +
      int age;
 +
 +
      InvList *inv;  /* pointer to the start of inventory list */
 +
  } Player;
 +
 +
What is the third field "InvList *" in the structure, I hear you ask.
 +
 +
"InvList" is also a structure, it defines ONE node for the inventory
 +
list. Node is one segment of the dynamic linked list. Look at this
 +
picture:
 +
 +
  +-------+      +-------+--+
 +
  | start |----->| node 1| >---\    +-------+------+
 +
  +-------+      +-------+--+  \-->| node 2| NULL |
 +
                                    +-------+------+
 +
 +
This example resembles a linked list with TWO nodes, the first block
 +
named 'start' contains a pointer to the node 1, telling that the first
 +
node of the list is there. And again, you see that in 'node 1' there is
 +
a extra field which contains a pointer to the NEXT node or 0 (NULL) if
 +
the list ends there.
 +
 +
So the above "Player" structure contains just a POINTER to the players
 +
inventory list. It's a memory address holding the first node of the list
 +
if any (or NULL if inventory is empty!)
 +
 +
At this point, compare this method to the array method I showed you
 +
earlier. If items are stored in array they will be stored in sequential
 +
order in memory ( 1-2-3-4-5-6-..) as one big block next to each other.
 +
In the case of linked lists, the list consists of nodes, which can be
 +
all around in the memory, the order of the list is preserved with the
 +
pointers linking each node to another. This list is  called as "one way
 +
linked-list" or "single linked list" meaning that you can traverse only
 +
to one direction along the list. There is also a list which contains a
 +
"previous" and "next" link. This is a "dual linked" or "two way linked"
 +
list. But I won't speak about it this time.
 +
 +
Now we have structures for the ITEM and the PLAYER. We must define the
 +
structure for InvList defining a one node of the list.
 +
 +
  typedef struct node
 +
  {
 +
      Titem item;
 +
      struct node *next;
 +
  } InvList;
 +
 +
  or like this:
 +
 +
  /* define a pointer to the list node */
 +
  /* so we can use "Ipointer" instead of "struct node *" */
 +
  typedef struct node *Ipointer;
 +
 +
  typedef struct node
 +
  {
 +
      Titem item;
 +
      Ipointer next;
 +
  } InvList;
 +
 +
I will use the first method.
 +
 +
The first field in the struct is the actual item stored in this node,
 +
and the "next" field contains an address to the NEXT node if there is
 +
such a node. (NULL telling that list is terminated here)
 +
 +
So basically this is a very simple idea, it requires a bit more work to
 +
maintain this kind of inventory, but it offers some advantage which are
 +
really good for Roguelike games. You can use this kind of list in many
 +
places. For example, I use it in these situations:
 +
 +
  List of monsters in the level
 +
  List of items in the level
 +
  List of items carried by the player
 +
  List of items carried by monsters
 +
 +
So in my game, only limitation in the above situations is the amount of
 +
memory available. There can be for example 1000 items in a level.
 +
 +
This practise can be used in MANY other situations, in other programs
 +
too. It's all depends in your imagination and how you can make this
 +
thing useful in certain situations.
 +
 +
I must point however that this "linked list" method will make you some
 +
problems later on. Think about savegames. You must create a routine
 +
which saves each node from the list and when loading you must build the
 +
list again. Not a big deal, but it brings you again a bit more work to
 +
do :)
 +
 +
Now that we have the idea coverered, let's start writing some code for
 +
the list.
 +
 +
----------------------------------------------------------------------------
 +
              WHAT FUNCTIONS DOES THIS KIND OF LIST NEED
 +
----------------------------------------------------------------------------
 +
 +
First off, you need to initialize this list, you'll need node addition,
 +
node deletion and the routine for deleting the whole list. Let's create
 +
the actual code for these functions.
 +
 +
1) Initialization of the list
 +
 +
  void initialize_list(Player *player)
 +
  {
 +
      player->inv=NULL;
 +
  }
 +
 +
This routine takes a pointer to the player structure and initializes the
 +
list pointer to NULL, telling that list does not exists yet. (so player
 +
has no items in inventory!)
 +
 +
Please note that you should not call this routine if you have items
 +
stored in the list. You will destroy the pointer to your list, thus you
 +
will have allocated memory which can't be freed because you lost the
 +
pointer.
 +
 +
2) Node addition
 +
 +
This routine adds a node to the list. I use the method where the last
 +
added node will be put to the BEGINNING of the list (thus to the field
 +
Player->inv) and this new node will point to the to the previous value
 +
of Player->inv. Like this:
 +
 +
  int add_node(Player *player, Titem newitem)
 +
  {
 +
      InvList *newnode;
 +
      /* allocate memory for the new node */
 +
      newnode=(InvList *)malloc(sizeof(InvList));
 +
 +
      /* if newnode == 0 then the memory is out or something is messed up */
 +
      if(!newnode)
 +
        return 0;
 +
 +
      /* now place the new data item to the item-field in space we allocated */
 +
      /* remember, "newnode->item" is similar to "newitem", both are defined */
 +
      /* by "Titem" */
 +
      newnode->item=newitem;
 +
 +
      /* if player inventory does not yet exists */
 +
      if(player->inv==NULL) {
 +
        newnode->next=0;
 +
        player->inv=newnode;
 +
      }
 +
      else {
 +
        /* point the "next" field of "newnode" to the old player->inv */
 +
        newnode->next=player->inv;
 +
        /* point the player->inv field to the node we just created */
 +
        player->inv=newnode;
 +
      }
 +
      return 1;
 +
  }
 +
 +
The function returns 0 if the addition failed, otherwise 1.
 +
 +
3) Node deletion
 +
 +
This routine really depends on the fact how you want to delete the item
 +
from the list. I will create a routine which removes item with an index.
 +
For example, you might want to delete the fifth item from the list.
 +
 +
Here is an example, it's not the optimal routine, should be easy to
 +
understand
 +
 +
int delete_node(Player *player, int index)
 +
{
 +
  InvList *node, *tmp;
 +
  int count;
 +
 +
  /* again check first if the inventory exists */
 +
  if(!player->inv)
 +
      return 0;
 +
 +
  node=player->inv;
 +
 +
  /* if you are trying to delete the first node */
 +
  if(index==0) {
 +
      player->inv=node->next;
 +
      free(node);
 +
 +
      /* we are done so return with success */
 +
      return 1;
 +
  }
 +
 +
  count=0;
 +
  while(node) {
 +
      /* remember the previous node */
 +
      tmp=node;
 +
      node=node->next;
 +
 +
      /* increase the item count in list */
 +
      count++;
 +
      if(count==index) break;
 +
  }
 +
 +
  /* if trying to delete item over list boundaries */
 +
  if(monesko>count) return 0;
 +
 +
  tmp->next=node->next;
 +
  free(node);
 +
  return 1;
 +
}
 +
 +
4) Freeing the whole list at once
 +
 +
Here is a useful routine for freeing the whole list at once. Notice how
 +
I traverse on the list.
 +
 +
  void free_list(Player *player)
 +
  {
 +
      InvList *tmp, *freethis;
 +
 +
      /* put the start of inventory to temporary variable */
 +
      tmp=player->inv;
 +
 +
      /* do until we reach NULL */
 +
      while(tmp) {
 +
        freethis=tmp;
 +
 +
        /* assign "tmp" with the next node, if there isn't a next node
 +
            "tmp" will contain NULL */
 +
        tmp=tmp->next;
 +
        /* free the current node */
 +
        free(freethis);
 +
      }
 +
      player->inv=NULL;
 +
  }
 +
 +
The similar approach can be used for example when displaying the
 +
contents of the list.
 +
 +
----------------------------------------------------------------------------
 +
                            SOMETHING EXTRA
 +
----------------------------------------------------------------------------
 +
 +
 +
Linked list is just one of the advanced data types (often called as
 +
Abstract Data Types, ADT), there are many other types of ADTs which can
 +
be useful in game programming. For example, Queue and Stack. Each of
 +
them have many uses, and again many ways to implement them. Some
 +
explanations.
 +
 +
Stack
 +
-----
 +
 +
Stack is a special case of a list. New items inserted to the stack will
 +
always go to the end of the list and when you take something out it will
 +
be taken from the end. So this type of list is called LAST IN FIRST OUT
 +
(LIFO). Stack has many uses.
 +
 +
  +-+----+
 +
  |3|data| top/end of the stack (last added item)
 +
  +-+----+
 +
  |2|data|
 +
  +-+----+
 +
  |1|data|
 +
  +-+----+
 +
  |0|data| start of the stack
 +
  +-+----+
 +
 +
So items will "pile up" in the stack. You'll get the most recent item
 +
when you get something from the stack.
 +
 +
One example from computer world. We want to check if a string is a
 +
palindrome: (string read forwards equals string read backwards)
 +
 +
  create 3 empty character stacks
 +
 +
  state1:
 +
  for each_char_in_string do
 +
      put_into_stack1(current char from string)
 +
      put_into_stack2(current char from string)
 +
      count=count+1
 +
  end_do
 +
 +
  state2:
 +
  while stack_2_has_something do
 +
      put_into_stack3(take_from_stack2())
 +
  end_do
 +
 +
  state3:
 +
  while stack_1_has_something do
 +
      if take_from_stack1() equals take_from_stack3()
 +
        palindrome=true,
 +
      else
 +
        palindrome=false
 +
  end do
 +
 +
for example for word "automatic" it would go like this:
 +
 +
  after state1
 +
  stack 1 contains: automatic
 +
  stack 2 contains: automatic
 +
  after state2
 +
  stack 1 contains: automatic
 +
  stack 3 contains: citamotua
 +
  in state3 we take from both stacks and compare them:
 +
  ? a==c ?
 +
  ? u==i ?
 +
  and so on...
 +
 +
Queue
 +
-----
 +
 +
Again, queue is a special case of a list. Items placed into the queue
 +
will go to the end and items taken from the queue will be taken from the
 +
start.
 +
 +
      first                              last
 +
      +------+------+------+------+------+------+        +------+
 +
  <--| data | data | data | data | data | data | <-- add | new  |
 +
      +------+------+------+------+------+------+        +------+
 +
 +
Good example taken from the Real Life(tm) could be a BANK QUEUE. You
 +
come to the bank and the desk you go has a long long and long queue
 +
(it's friday and the bank is going to close soon :), you will have to go
 +
to the end of the queue. When the bank clerk can, he/she takes a next
 +
customer from the first position of the queue.
 +
 +
The end?
 +
--------
 +
This ends this part of the lesson. I've tried to provide you a method
 +
for creating dynamic inventories along with some knowledge of other
 +
advanced data types. It's up to you to decide how you make use of them.
 +
 +
I thank you for reading this, and apologise for any errors in C-examples
 +
I provided, there might be some since this text was written on a fly
 +
without any aid of C-compiler :)
 +
 +
If you have any questions, ideas for my game, or want to report a bug in
 +
my examples, please feel free to contact me via email.
 +
 +
  ernomat@evitech.fi
 +
 +
Also go see the homepage of my Roguelike project:
 +
 +
  The Legend of Saladir
 +
  http://www.evitech.fi/~ernomat/saladir/main.html
 +
 +
This text is written specially for Darren Hebden's Roguelike News
 +
developers section. Visit Darren's great pages at
 +
 +
        "http://www2.krisalis.co.uk/wwwdheb/index.html"
 +
 +
----------------------------------------------------------------------------
 +
(C) 1997 by Erno Tuomainen                      Sunday 16th of November 1997
 +
----------------------------------------------------------------------------
 +
            Do not modify or publish without my approval.
 +
 +
= Equipment Wear and Tear - Michael Heinich [mheinich@yahoo.com]. =
 +
 +
  Every piece of equipment should have a durability. One example of this
 +
system is demonstrated in a popular series of commercial hack and slash games
 +
with some Rogue-Like tendencies. Another example can be found in ADOM. Both
 +
of these implementations could be improved upon.
 +
 +
  In the commercial games, durability played a very important if limited role.
 +
If an item's durability reached 0, it was broke beyond repair. This was
 +
normally kept as a ratio of current:maximum durability. The game allowed a
 +
character class a repair skill to partially repair an item. The drawback was
 +
that the maximum durability was reduced. Or a member of the town was able to
 +
provide this service. Found items had a lower then maximum durability and
 +
equipment that was used, lost durability during the course of weilding or
 +
wearing them. Durability also effected the value of the item in question. An
 +
item in great shape was worth more then the same item in bad repair. While
 +
the measurement system was easy to understand and to manage, it could still
 +
be improved upon.
 +
 +
  One area is in the item's use. The equipement was either broke or not. A
 +
better method would be to reduce the effectivness of the item in question.
 +
Using a sword for example, as it becomes worn out, the sword may cause less
 +
damage because it has become dull with use. Or the sword may have an ever
 +
increasing change where it may break during an attack as it's durability
 +
decreases. An armor example would be that the protection a chain mail shirt
 +
provides may be reduced as it's durability worsens.
 +
 +
  ADOM does take some of these factors into consideration, but it can be
 +
confusing to figure out the multitude of stats offered (some would say that
 +
this is one of it's strengths)and it lacks adequate skills or town services
 +
for the repairing of items. Usually it is usually better to replace an item
 +
then to repair it.
 +
 +
Here are some more ideas thrown out more or less at random that build on this
 +
concept. The use of durability can also open other possibilities for object
 +
descriptives and use. For example, a sword that is undamaged and is like
 +
brand new may have a desciption before identification of Shiny and Sharp, as
 +
the sword becomes used, the description may change to dull and nicked.
 +
Durability provides an interesting twist to potions or items made of glass.
 +
Potions may be in delicate containers. In Angband, potions sometimes break
 +
when they are subject to heat or cold attacks. But what if a potion is dropped
 +
or thrown. They should spill, spreading their contents over the floor, wall or
 +
monster. This could cause interesting effects if the Potion was healing or Acid.
 +
A Crystal Ball may not last too long under a heavy attack by giants or earth
 +
hounds. Just how sturdy is a Lantern full of Oil anyway? Why hasn't one of
 +
these broke after an attack, spilling flaming oil all over the user. Or throwing
 +
the lantern, to have it's flaming contents spill over the monster. This is much
 +
preffered to the Flask of Oil attack in Angband. Since it assumes that you have
 +
lit the Flask first somehow.
 +
 +
The code to add statistics for wear and tear should not be to hard to add to your
 +
Roguelike. Specially if you are using an Object Oriented programming language.
 +
You can just add an extra two lines to the Class for starters.
 +
 +
int CurrentWear, NoWear; // Measure how much wear and tear
 +
int Durability; // How durable is this item
 +
 +
In your object definition for a sword you would add the value for NoWear an the
 +
value for Durability. During the Object creation you would assign the value of
 +
NoWear to CurrentWear.
 +
 +
CurrentWear = NoWear; // set CurrentWear value to NoWear
 +
 +
Then when ever the item is used or after a certin number of uses, you would
 +
subtract from the value.
 +
 +
if (NumOfUses == 10) {
 +
CurrentWear--;
 +
if (possiblebreak(Sword.CurrentWear)) Sword.Status = BROKE;
 +
NumOfUses=0;
 +
}
 +
 +
I hope these meanderings showed you a new diminsion for your Game. The code examples
 +
were way oversimplified but will hopefully point you in the right direction.
 +
 +
Happy Coding!
 +
 +
= Fractal Landscapes - Mike Anderson [mike@mikera.net]. =
 +
 +
30th October 1999
 +
 +
There's something special about fractals. Maybe it's the way that
 +
infinitely complex shapes appear out of the simplest mathematical
 +
formulae.....
 +
 +
Certainly beautiful, but why would you want to use them in your game?
 +
The answer, quite simply, is that they are perfect for generating
 +
realistic-looking landscapes. For example, real coastlines frequently
 +
exhibit fractal-like properties and fractal heightfields are often a
 +
good first approximation to the contours of mountainous terrain.
 +
 +
Here I'm going to present a basic fractal algorithm that was
 +
originally designed for generating random islands, seas and coastlines.
 +
With a few minor alterations, it could easily be adapted to producing
 +
all kinds of natural landscape patterns. My algorithm is vaguely based
 +
on the familiar "plasma" type of fractal heightfield, but modified to
 +
work with tiled maps.
 +
 +
I've included the source for a simple Java coastline generator applet
 +
at the end of this article. If you are impatient and want to see the
 +
thing working right away, just go to:
 +
 +
  http://www.mikera.net/code/coastline.html
 +
 +
 +
The Fractal Algorithm
 +
=====================
 +
 +
One of the distinctive properties of fractal images is self-similarity.
 +
That is, a zoomed in version will look similar to the whole image. This
 +
algorithm achieves this effect by starting with a coarse map, and then
 +
enhancing it by applying increasing levels of random detail.
 +
 +
Let's say that you are considering a square area of your map with the
 +
corners labelled a, b, c and d :
 +
 +
a * b
 +
 +
* * *
 +
 +
c * d
 +
 +
Each map square can have a different colour. I used green for land and
 +
blue for sea in the example applet.
 +
 +
The algorithm will then determine the map colours for the intermediate
 +
points marked "*". It does this by randomly choosing a colour from one
 +
of the adjacent corner squares. The "*" in the centre could take the
 +
colour of either a, b, c or d.
 +
 +
Thus a possible final result might be:
 +
 +
a a b
 +
 +
c b d
 +
 +
c c d
 +
 +
 +
We have now defined smaller squares on the map. The algorithm can then
 +
be applied iteratively on a smaller scale. This process continues until
 +
the desired level of detail is achieved.
 +
 +
a*a*b
 +
*****
 +
c*b*d
 +
*****
 +
c*c*d
 +
 +
Note that for convenience, it is helpful to have a map size that is a
 +
power of two so that it can be repeatedly subdivided.
 +
 +
 +
Example
 +
=======
 +
 +
Below shows the iterations for a 16*16 grid.
 +
 +
For viewing convenience, the larger tiles have been completely filled
 +
with the colour from the top-left corner, though this is not needed for
 +
the algorithm to work.
 +
 +
In addition, the map is considered to be toroidal, i.e. the points on
 +
the left edge are considered to be adjacent to those on the right edge,
 +
and similarly for top and bottom.
 +
 +
 +
Step 1:
 +
a-------b#######
 +
--------########
 +
--------########
 +
--------########
 +
--------########
 +
--------########
 +
--------########
 +
--------########
 +
c#######d-------
 +
########--------
 +
########--------
 +
########--------
 +
########--------
 +
########--------
 +
########--------
 +
########--------
 +
 +
(a, b, c and d mark the points that are coloured at the start. This
 +
can be done randomly, or they can be pre-set to create land masses)
 +
 +
 +
Step 2:
 +
--------########
 +
--------########
 +
--------########
 +
--------########
 +
########----####
 +
########----####
 +
########----####
 +
########----####
 +
----####--------
 +
----####--------
 +
----####--------
 +
----####--------
 +
############----
 +
############----
 +
############----
 +
############----
 +
 +
 +
Step 3:
 +
------########--
 +
------########--
 +
--##----########
 +
--##----########
 +
########----####
 +
########----####
 +
######--------##
 +
######--------##
 +
----####--------
 +
----####--------
 +
----##----------
 +
----##----------
 +
##########------
 +
##########------
 +
##--########----
 +
##--########----
 +
 +
 +
Step 4:
 +
-----########---
 +
------########--
 +
-##-----########
 +
--##----#--#####
 +
########----####
 +
########-----###
 +
######--------##
 +
#-####--------#-
 +
----####--------
 +
---####---------
 +
---###----------
 +
-#--#--#--------
 +
##########-----#
 +
#########-#-----
 +
##-#########----
 +
#----######-----
 +
 +
 +
Et voila - one random continent ready to be populated with thriving
 +
cities, dangerous mountain ranges and deep forests.
 +
 +
 +
The Code
 +
========
 +
 +
Here's a quick Java implementation of the fractal coastline algorithm.
 +
It generates a new landscape each time the applet is repainted.
 +
 +
The makeFractal(step) method does all the actual work. This method
 +
calls itself to handle finer detail levels.
 +
 +
 +
========= CoastApp.java ==========
 +
package kult.quest;
 +
 +
import java.awt.*;
 +
import java.applet.*;
 +
import java.awt.event.*;
 +
 +
public class CoastApp extends Applet {
 +
 +
  // map size: must be a power of 2
 +
  public static final int size=128;
 +
 +
  // allocate map storage
 +
  public int[] map= new int[size*size];
 +
 +
  public void paint(Graphics g) {
 +
    super.paint(g);
 +
 +
    // initial pattern (0=sea, 1=land)
 +
    setCell(0,0,0);
 +
    setCell(size/2,0,0);
 +
    setCell(0,size/2,0);
 +
    setCell(size/2,size/2,1);
 +
 +
    makeFractal(size/4);
 +
 +
    // draw the map
 +
    for (int y=0; y<size; y++) for (int x=0; x<size; x++) {
 +
      g.setColor( (getCell(x,y)==0) ? Color.blue : Color.green );
 +
      g.fillRect(x*2,y*2,2,2);
 +
    }
 +
  }
 +
 +
  public void setCell(int x, int y, int c) {
 +
    map[x+size*y]=c;
 +
  }
 +
 +
  public int getCell(int x, int y) {
 +
    return map[x+size*y];
 +
  }
 +
 +
  // this routine builds the landscape....
 +
  //  step = detail square width
 +
  public void makeFractal(int step) {
 +
  for (int y=0; y<size; y+=step) {
 +
    for (int x=0; x<size; x+=step) {
 +
      // The inner loop calculates (cx,cy)
 +
      // this is the point from which to copy map colour
 +
 +
      // add random offsets
 +
      int cx=x+ ((Math.random()<0.5) ? 0 : step);
 +
      int cy=y+ ((Math.random()<0.5) ? 0 : step);
 +
 +
      // truncate to nearest multiple of step*2
 +
      // since step*2 is the previous detail level calculated
 +
      cx=(cx/(step*2))*step*2;
 +
      cy=(cy/(step*2))*step*2;
 +
 +
      // wrap around to reference world as torus
 +
      // also guarantees getCell() and setCell() are within bounds
 +
      cx=cx%size;
 +
      cy=cy%size;
 +
 +
      // copy from (cx,cy) to (x,y)
 +
      setCell(x,y,getCell(cx,cy));
 +
    }
 +
  }
 +
 +
    // recursively calculate finer detail levels
 +
    if (step>1) makeFractal(step/2);
 +
  }
 +
 +
  // applet initialisation
 +
  public void init() {
 +
    super.init();
 +
 +
    // repaint on mouse clicks
 +
    addMouseListener(new MouseAdapter()
 +
      public void mouseClicked( MouseEvent e ) {
 +
        repaint();
 +
      }
 +
    });
 +
  }
 +
 +
  // main function allows applet to run as an application
 +
  public static void main(String[] args) {
 +
 +
    // create a frame
 +
    Frame f = new Frame("Fractal Coastlines");
 +
    f.addWindowListener(new WindowAdapter() {
 +
      public void windowClosing(WindowEvent e) {
 +
        System.exit(0);
 +
      }
 +
    });
 +
 +
    // set up frame and add applet
 +
    f.setSize(300,300);
 +
    f.setLayout(new BorderLayout());
 +
    CoastApp q=new CoastApp();
 +
    q.init();
 +
    f.add(q);
 +
 +
    // go live....
 +
    f.show();
 +
  }
 +
}
 +
 +
 +
 +
Conclusion
 +
==========
 +
 +
Well, I hope I've given you a quick way to get some good-looking
 +
fractal landscapes. It is easy to extend this by adding different land
 +
types (forests, deserts etc). You could also enhance the method to
 +
include a height map by taking averages of adjacent points and adding
 +
random offsets.
 +
 +
In fact, I've implemented a fractal algorithm to generate the World
 +
Maps for Tyrant, my very own roguelike. You can see it in action at:
 +
 +
  http://www.mikera.net/tyrant/
 +
 +
This uses essentially the same method as the one described above,
 +
except that it uses a little bit of coding magic to make the landscapes
 +
look more realistic and textured. While it's still far from perfect, it
 +
does at least show there's scope for a lot of imaginative use of this
 +
technique.
 +
 +
Happy Coding.
 +
 +
Mike.
 +
 +
 +
Any questions or comments:
 +
  mike@mikera.net
 +
 +
= Terrain Generator - Mixi Lauronen [mplauron@paju.oulu.fi].txt =
 +
 +
I have experimented with the following algorithm:
 +
 +
1) Decide the range of land height values (I think 0-255 is conveninent)
 +
 +
2) Initialize the land area with a value of 0. (Arbitrarily, you can
 +
initialize it with the average of the height minimum and maximum)
 +
 +
3) Randomly set a rectangle of random size with a random value of (0-255)
 +
on the map, adding the value to every coordinate inside the rectangle's
 +
area. Arbitrarily the value can be anything between (-x to x). If the
 +
result is less than the minimum height or more than maximum height,
 +
readjust the value.
 +
 +
4) Repeat as many times as needed.
 +
 +
5) Apply a smoothing routine to every coordinate, thus simulating the
 +
effect of erosion. I use a simple method of setting the value of a land
 +
block to the average of (block+southern block+northern block+eastern
 +
block+western block).
 +
 +
6) Set the water level. Anything under that will be water.
 +
 +
Haven't implemented a river algorithm yet. Otherwise it seems to work
 +
fine, although it is a little bit slow (especially the smoothing routine).
 +
Of course the building blocks could be circles, ovals or single pixels,
 +
too.
 +
 +
= Metaballs Dungeon.txt =
 +
 +
The Metaballs Dungeon
 +
----------------------
 +
The idea of the metaballs dungeon is to generate two dimensional
 +
meatballs to construct a cave-like dungeon that looks natural and rough
 +
but still constructed by... goblin hands!
 +
If anyone here has ever worked with a 3d raytracer you may know what i
 +
am talking about. Basically the idea is that in many 3-D raytracing
 +
applications you can place these metaballs in your scene. Each meta
 +
ball has x,y,z coordinate variables and a t--threshhold. If you have
 +
one metaball then the edge of the ball is mearly a distance away from
 +
the center equal to the threshhold. In case you havent already guessed
 +
this, we are thinking about doing this in 2d (x,y,t). So lets look at
 +
how that would look.
 +
 +
                        ####
 +
                      #....#
 +
                      #......#
 +
                      #......#
 +
                      #......#
 +
                      #....#
 +
                        ####
 +
        (a better looking circle then above)
 +
 +
Now this is because we only have one ball. If we place another right
 +
next too the first, then in our 2-D scenerio we will say that for every
 +
square we look to see if there is a ball or are balls nearby. Nearby is
 +
defigned like this
 +
 +
If the square in question's distance to a ball's center is less then
 +
the ball's threshhold then that ball is "nearby".
 +
 +
Now if we have a vector of balls (x,y,t) that have contructed (I will
 +
explain later) then we want to find out what our betaballs dungeon
 +
looks like. We would do the following.
 +
 +
(slow version, could be optimized!! a lot!)
 +
For every square on our grid, we compile a list of the "nearby" balls.
 +
We then add the threshhold of every nearby ball to a temporary integer
 +
and then subtract the distance to every ball from this integer. If this
 +
number is positive then we have a floor tile. if not we have a wall
 +
tile. Its that simple. This algorthim could be optimized and the math
 +
is probably a little off. There are algorithms you can find through a
 +
google search that will probably be better/faster and offer you much
 +
more control. My simple example does work and has been tested on
 +
QBasic. I will probably implement this for some levels in my upcomming
 +
game CHAZM!
 +
 +
A sample might look like this. A nice smooth melted merge between
 +
balls. You could also experiment with using ellipes and rounded
 +
rectangles. There are algorithms for those out their too.
 +
                      ################
 +
                      #########....###
 +
                      ##....##......##
 +
                      #.............##
 +
                      #.............##
 +
                      #......##.....##
 +
                      ##....####...###
 +
                      ################
 +
          (This was handdrawn as a representation only...)
 +
If you cant visualize what this would look like with many rooms/balls
 +
then take a look here:
 +
 +
http://foresightsagas.com/software/chazm/metaballs_cave_example.htm
 +
 +
Laying out the Rooms
 +
---------------------
 +
You could lay out the rooms in any way you want but personally i would
 +
advocate for a recursive flow.
 +
 +
call branch 2-4 times on randome angles at the center...
 +
 +
void branch(x,y,a){
 +
  do{
 +
    a += randombetweenr(-.2 radians, +.2radiant);
 +
    step x and y forward 8-12 squares forward in the direction of angle
 +
a
 +
    then add room at location
 +
    if (randombetween(0,6) == 2) branch(x,y,a);
 +
    if (randombetween(0,6) == 3) return;
 +
  }
 +
}
 +
 +
thus you get a branching and twisting maze of caverns that go out quite
 +
far. You could also add other end conditions like hitting the edge of
 +
the screen or getting a cirtain distance from the original center....
 +
If you have any questions you can ask me about this recursion.
 +
 +
I think this would work out great as a caves level. Any thoughts or
 +
questions: email me at comments (AT) foresightsagas .com
 +
 +
Thanks. And have fun making your RL.
 +
 +
By Thomas Gilray
 +
foresightsagas.com
 +
 +
= More Continuous Content - Joseph Swing [JSwing@wport.com]. =
 +
 +
One feature of RL games is the random placement of monsters and
 +
objects.  While this is good in general, it leads to setups that are
 +
highly improbable at best, and ludicrous at worst.  You know what I'm
 +
talking about.  A barrack of soldiers with one exit leading to a room
 +
containing half a dozen giant spiders.  Orcs frolicing in one room while
 +
a lone elf wanders next door.  Wargs who ignore the juicy smell of the
 +
nearby ratling.  And so forth.
 +
 +
A good AI helps, but if the initial placement of the monsters makes it
 +
unlikely the would encounter each other by their default behavior, the
 +
problem isn't fixed.  The community has done a fantastic job developing
 +
dungeons that are physically continuous, but whose content is not. 
 +
 +
First of all, we need some additional data for our generic monsters.
 +
Something which indicates which monsters tend to be next to which
 +
monsters.  Call it a Theme.  For a Goblin Lair theme it might look like:
 +
 +
1    Goblin King and 3 advisors (1-3 hobgoblins) (unique, mandatory)
 +
2    Goblin guards (1-6)
 +
2    Hobgoblin guards (1-2)
 +
3    Goblin Wolfriders  (1-3)
 +
3    Goblin Shopkeeper (unique)
 +
3    1-3 Goblins and 1-2 Goblin thieves
 +
4    1-2 Goblins and a Crate
 +
4    1-2 Goblin Guards
 +
4    Goblin pig farm - 1 goblin and 3 pigs
 +
4    Empty Room
 +
5    Empty Room
 +
6    Empty Room - random monster possible
 +
7    Empty Room -random monster or stairs allowed
 +
 +
First, as you;re building your level, check if there's a theme.  Not all
 +
levels should have one.  If your level has a theme then start at the top
 +
of the list. 
 +
 +
In this case, the first room that you plunk down should have a Goblin
 +
King (#1) in it.  When you draw your doors/hallways, draw them leaving
 +
from this room, and carry with it the number on the left.    Moving to
 +
the next room, move down the list (75% chance) or back up the list
 +
(25%).  For the example above, there are two possibilities, either some
 +
Goblin or Hobgoblin guards.  Add these to the next room.  Draw your
 +
doors/halls from there and continue. 
 +
 +
You may even choose to add some entries to the hallways themselves, if
 +
they're large enough.  The Goblin King might have a few guards in the
 +
outside hall, but it would be difficult to have a pig farm in a
 +
hallway.  If you wanted to use this option, the simple solution is
 +
staggering your entries so that odd ones were in rooms and even ones
 +
were the hallways between.
 +
 +
The nice thing is that you end up with a small goblin community, with a
 +
few empty rooms between them and any wandering monsters.  The Goblin
 +
King sits at the middle, furthest from the stairs where the hero will
 +
enter, which is nice.
 +
 +
How to implement?  If you're carving your dungeon this is easy.
 +
Starting with an empty dungeon level, you maintain a separate list of
 +
doorways:
 +
1) Start with a dummy doorway with a content value of 1
 +
2) From the doorway, try and add a room filling with content value from
 +
the doorway; if successful, add both the room and doorway to the map.
 +
3) Add doorways from the room, migrating the content (1->2, etc)
 +
4) Step through your list of doorways and go back to step 2;  You're
 +
done when you;re out of doorways
 +
 +
If you're using the grid to plunk down your rooms you either need to
 +
wait until you draw the hallways (and draw them carefully), or use a
 +
flood fill algorithm.
 +
 +
If you don't always use fixed rooms (like Crawl) I suppose you could
 +
also flood fill with each entry having a certain radius before it
 +
transitions to the next one.  It's trickier.
 +
 +
Other thoughts: 
 +
Not all levels should have a theme.  Some themes should be smaller than
 +
others, maybe only a few connected rooms, with the rest of the level
 +
being more random. 
 +
To set up the themes you could make them more abstract.  Make the sample
 +
above generic to humanoids (xxx lair) and fill in with the details fro
 +
the appropriate level at run time (Orc Lair, Goblin liar, etc).  Or you
 +
could make a large Monster Map connecting the likely monsters/groups.
 +
One whole edge of the map should be 'random monster'.
 +
I recommend that no more than about 1/3 to 1/2 of your dungeon be filled
 +
with this kind of theme, to keep the replay value.
 +
If you include stairs with doors as transition points, it's possible to
 +
spread the theme in 3d, and no longer required to keep the stairs so far
 +
from the center (just treat it like you would a door).
 +
Along with the monsters, make the objects more continuous too.  The
 +
Goblin Guards might have an extra sword lying around, but the peasants
 +
aren't going to have 50gold for very long.  The empty rooms near the
 +
Lair might thave signs of the local occupants - grafitti in the goblin
 +
tongue, for example.
 +
 +
= Creating A Dungeon - Brian Bucklew [bbucklew@inteletek.com]. =
 +
 +
Section 1 : Creating A Map
 +
 +
        When creating a rogue-like game (RL from this point on), there
 +
are several points you have to address. One of the first problems you
 +
are likely to encounter is the problem of generating a suitable dungeon
 +
level. Actually, not only do you need a level, you need a pretty much
 +
infinite supply of random levels all filled to the brim with monsters,
 +
treasure, traps and other various unsundries.
 +
        Our first goal will be to actually create the maze, empty. Later
 +
we can integrate code that stocks our dungeon, but for now our main goal
 +
will be to just get a pretty fair complex of passages and rooms.
 +
        As with an programming problem there are many solutions, each
 +
that generates a perfectly acceptable dungeon. The first method we will
 +
discuss is a recursive one.
 +
 +
Creating A Map : A Recursive Method
 +
 +
        This algorithm will be based around taking a solid chunk of rock,
 +
let's say 256x256 and carving a dungeon out of it using rooms and passages.
 +
We'll try to stay as simplistic as possible at the beginning, though this
 +
algorithm can be expanded to generate many different dungeon types from
 +
caves to castles, with fairly minor changes to the basic code.
 +
 +
        So we begin with a 256x256 array of blocks, each filled with stone.
 +
For our basic dungeon generation we will also need two functions:
 +
 +
MakeRoom(), which generates a random room and then calls:
 +
MakeHall(), which generates a hall of random length.
 +
 +
We will call MakeRoom() which will generate a randomly sized room, which
 +
will then call MakeHall() a randomly determined number of times out into
 +
the dungeon from the walls of the room. MakeHall() will generate a hall of
 +
a random length. At the hall's end, the hall will either 1:End 2:Call MakeHall()
 +
a random number of times in random directions or 3:Call MakeRoom(). Later
 +
we can improve the algorithm my making a hall stop if it hits another hall
 +
or room, or coding rooms so that they won't overlap, but for now this will
 +
suffice.
 +
 +
lets say, using pseudocode we have:
 +
 +
... StartX and StartY will be integers defining the seed location
 +
... of each room and hall
 +
 +
... Direction will be an integer defining the direction the
 +
... room or hall is facing
 +
 +
... RecurseDepth will be used to terminate the recursion at a specific
 +
... depth
 +
 +
 +
First we will define MakeRoom.
 +
 +
void MakeRoom( StartX, StartY, Direction, RecurseDepth )
 +
{
 +
        integer X1,Y1,X2,Y2; // These variables will be used to define
 +
                            // the extents of the room
 +
 +
        // limit the recursion to some depth
 +
        if( RecurseDepth > MAXRECURSEDEPTH ) return;
 +
 +
        DetermineExtents();
 +
/*      We need to take direction into account when determining the extents
 +
        ... For Example:
 +
        ( '#' = Rock '.' = open space, in standard RL convention )
 +
 +
        ##########
 +
        ##########
 +
        ##########
 +
        #####X.... <--- Hall calls MakeRoom at X going west.
 +
        ##########
 +
        ##########
 +
        ##########
 +
 +
        This is the situation we want to create when determining
 +
        the extents:
 +
        a = x1,y1
 +
        b = x2,y2
 +
        ##########
 +
        ##########
 +
        #a****####
 +
        #****X....
 +
        #****b####
 +
        ##########
 +
        ##########
 +
        This is good...
 +
 +
        If we did not take direction into account, we would most
 +
        likely end up with this:
 +
        a = x1,y1
 +
        b = x2,y2
 +
        ##########
 +
        ##########
 +
        ###a****##
 +
        ###**X....
 +
        ###****b##
 +
        ##########
 +
        ##########
 +
        This is bad...
 +
*/
 +
 +
        CreateTheRoom();
 +
 +
        for( x = x1 to x2 )
 +
        for( y = y1 to y2 )
 +
          Dungeon[x,y] = OpenSpace;
 +
 +
        integer R = Random(0,4); // Actually this is probably some non-linear
 +
                                // random choice, but this will suffice.
 +
                               
 +
        for( x = 0 to R )
 +
        {
 +
                int hx,hy,hd;
 +
 +
                DetermineLocationOfHall();
 +
                // Choose a spot along one of the walls,
 +
                // Then determine the appropriate direction
 +
                // (North,South,East or West) depending
 +
                // on the chosen wall.
 +
 +
                MakeHall( hx,hy,hd, RecurseDepth+1 );
 +
        }
 +
}
 +
 +
Now, MakeHall which is comparatively simple:
 +
 +
void MakeHall( StartX, StartY, Direction, RecurseDepth )
 +
{
 +
        // Limit the recursion...
 +
        if( RecurseDepth > MAXRECURSEDEPTH ) return;
 +
 +
        integer x1,y1;
 +
        x1 = StartX;
 +
        y1 = StartY;
 +
 +
        for( x = 1 to RandomLength )
 +
        {
 +
                if( x1 or y1 is out of bounds ) return;
 +
 +
                Dungeon[x1,y1] = OpenSpace;
 +
 +
                // Note:
 +
                // For ease of stepping in a direction we will define
 +
                // two arrays containing the X & Y deltas of each direction
 +
                x1 += DirectionXDelta[Direction];
 +
                y1 += DirectionYDelta[Direction];
 +
        }
 +
 +
        RandomChoice = Random(1,3);
 +
 +
        if( RandomChoice == 1 ) return;
 +
 +
        if( RandomChoice == 2 )
 +
        for( x = 1 to Random(0,3) )
 +
          MakeHall( x1,y1, RandomDirection, RecurseDepth+1 );
 +
 +
        if( RandomChoice == 3 )
 +
        MakeRoom( x1,y1, Direction, RecurseDepth+1 );
 +
}
 +
                       
 +
That's it... A simple recursive algorithm for carving out a dungeon.
 +
This is by no means an ideal algorthm and requires quite a bit of tweaking
 +
and a few algorithmic improvements to generate a really good dungeon, but this
 +
example serves to illustrate the method.
 +
 +
The Author:
 +
Brian Bucklew, 18
 +
bbucklew@inteletek.com
 +
Current RL Project : Dungeon or "This game needs a new name"... :)
 +
Projected Beta Release : Early 98
 +
 +
= The Building of Towns - Michael Blackney [michaelblackney@hotmail.com]. =
 +
 +
Introduction
 +
  Most roguelikes of reasonable popularity contain towns, though
 +
  not always in the design we are used to seeing them in real life.
 +
  I for one am utterly confused by the first town in ADOM.  How is
 +
  it that this small group of farmers and rations salesmen were not
 +
  wiped out long ago by horrible dorn beasts?  How do they defend
 +
  themselves?  And with the multitude of eager young adventurers at
 +
  their doorstep, why has no one opened a sucker-market?
 +
  In this article I intend on addressing these points, and other
 +
  problems I have encountered with town-creation.  This method
 +
  should, with few adjustments, work equally well with all sizes
 +
  of towns and can be used both as a random-town generator (like in
 +
  Angband) and to help with preset-town design (like in ADOM).
 +
  For code excerpts I have used C++, as I favor it.  I could
 +
  have used Pseudocode for those of you who don't understand C++, but
 +
  then nobody would be happy.
 +
 +
Features
 +
  Most of this article will refer to 'Feature's.  This is a class
 +
  created for the town design stage.  A Feature represents an arbitrary
 +
  feature in your town, be it a house, a forest or a grave.  You may
 +
  even decide for consitency to make the Town a Feature as well.  A Feature
 +
  upon creation often creates other Features which are part of it, such
 +
  as a Castle Feature which creates a Moat, a Guardhouse and a Keep.
 +
  A simple C++ interface for the class Feature could be as follows:
 +
/-*/
 +
  class Feature {
 +
    public:
 +
      // Construction / Destruction
 +
      Feature( Level*l, char x1, char y1, char x2, char y2 )
 +
: onlevel( l ), name( "" ), bounds( x1, y1, x2, y2 ) {
 +
create();
 +
}
 +
      virtual ~Feature( void );
 +
      // public methods
 +
      virtual void create( void ) = 0; // Specialized classes must override
 +
    // this method.
 +
    protected:
 +
      // inheritable data
 +
      String name;
 +
      Rectangle bounds;
 +
      Level *onlevel;
 +
    };
 +
/*-/
 +
  This class would interact with the Level class, which describes a 2d
 +
  array of LevelElements where each LevelElement represents one game
 +
  square.  The create() method would then alter the Level accordingly,
 +
  adding walls, floor space, trees or whatever.
 +
 +
Natural Terrain
 +
  All towns (which I intend on covering here) are situated in the
 +
  'real' world that you have created, and as such all have surrounding
 +
  terrain.  In fact many of the decisions to be made regarding the
 +
  features found in your town will be affected by the terrain in and
 +
  around the town.
 +
  We all know that when people decide to establish a town, the terrain
 +
  is already there.  For this reason, we should create the surrounding
 +
  terrain first.
 +
  One way of implementing this is to make a series of specialized
 +
  Features each dealing with a different type of terrain.  Classes such
 +
  as Clearing, Swamp, Coast and Hills are all examples of this.  These
 +
  classes can then create the streams, forests and so forth.
 +
 +
TEST RUN::
 +
  The following is an example of terrain creation.
 +
  We begin with a blank 15x5 level like so:
 +
 +
xxxxxxxxxxxxxxx
 +
xxxxxxxxxxxxxxx  x  unallocated LevelElement
 +
xxxxxxxxxxxxxxx
 +
xxxxxxxxxxxxxxx
 +
xxxxxxxxxxxxxxx
 +
 +
  We then decide (using our special number generator) to create a
 +
  grass field.  The GrassField class calls its version of create() which
 +
  at first will do nothing more than filling the level with grass squares,
 +
  like so:
 +
 +
...............
 +
...............  .  grass
 +
...............
 +
...............
 +
...............
 +
 +
  create() then has some decisions to make, such as how sparse vegetation
 +
  is and how frequently streams occur.  Our GrassField decides to have a
 +
  SmallStream and a few scattered trees.  Soon out GrassField looks like
 +
  this:
 +
 +
...............
 +
.T....T..=...T.  .  grass
 +
.........===...  T  tree
 +
..T....==......  =  water (now part of SmallStream)
 +
.....==.....T..
 +
 +
  The actual generation of your terrain is up to you.  You can make this
 +
  as simple or complicated as you wish.
 +
  Now that we have a Level filled with adequate terrain, it is time to
 +
  establish a settlement.
 +
 +
Your Town
 +
  In order to make a sensible Town, it must be created and inhabited
 +
  by your residents, with all of the benefits and drawbacks this brings.
 +
  eg. If you wish to have thieves in your world, it makes sense to either
 +
  have a thieving skill (such as ADOM's Pickpocketing) or to have houses
 +
  where our friend the Aimless Merchant keeps all of his most valued
 +
  posessions.  Otherwise our poor friend the thief would be out of a job.
 +
  In order to know what types of features to create, we really should
 +
  know the types of people who will be interacting with them.
 +
  To get the ball rolling, I have created a small list of likely residents
 +
  in a fantasy world.  In doing this, it becomes more clear what sorts of
 +
  features I will expect to find in towns.
 +
 +
Professions (in no particular order)
 +
    - Warriors        - Mages          - Scholars
 +
    - Smiths          - Guides          - Alchemists
 +
    - Rogues          - Bards          - Merchants
 +
    - Assassins        - Paladins        - Monks
 +
    - Priests          - Runesmiths      - Thieves
 +
    - Druids          - Rangers        - Farmers
 +
    - Men-at-Arms      - Knights        - Guards (and police)
 +
    - Traders          - Pirates        - Masons
 +
    - Healers          - and so on...
 +
 +
  Try to make the list smallish to begin with to speed things up a little,
 +
  you can always return to this point if you think of more later.
 +
 +
Profession-Related Features
 +
  For each possible profession in your rich and complex world, you
 +
  will require a place for them to 'hang out'.  Examine your profession
 +
  list and see what you can come up with.  For this I have separated
 +
  my profession list into three categories: Class, Guild and Religion-
 +
  based, though this is not really necessary.
 +
 +
  Class-based features
 +
  - Taverns (for Bards and drunkards [warriors, rogues]),
 +
  - Houses (for people to live in and thieves to steal from),
 +
  - Library (for Scholars and Mages),
 +
  - Hospital (for Healers),
 +
  - xxxxsmiths (for Smiths),
 +
  - Shops (for Merchants),
 +
  - Ports (for Traders, Pirates, Rogues, &c.),
 +
  - Farms (for Farmers),
 +
  - Alpharmacy? (for Alchemists).
 +
 +
  Guilds
 +
  - Barracks (for Men-at-Arms),
 +
  - Thieves Guild,
 +
  - Assassins Guild,
 +
  - Runemasters Guild,
 +
  - Gatehouse (for Guards),
 +
  - School of Magic (for Mages),
 +
  - Palaces, Castles, &c. (for Guards, Knights).
 +
 +
  Religions
 +
  - Assorted Temples and Churches.  These should have variance to
 +
    shew the alignments of your gods, eg.
 +
    - Monastery,
 +
    - Nunnery,
 +
    - Cathedral,
 +
    - Stone Circle (for Druids).
 +
 +
  Other
 +
  - Inn,
 +
  - Stables,
 +
  - Asylum?,
 +
  - Town Square.
 +
 +
  Now that we have a nice beginner's list of features for every fantasy
 +
  denizen, we can flesh it out by adding some nice small details.  Many
 +
  other types of features are required for efficient town life.  These
 +
  quite frequently have to do with keeping the residents alive, or
 +
  disposing with the dead.  Small additions such as wells and fountains
 +
  can add much richness to a settlement; as can graveyards, statues,
 +
  gibbets (and all other forms of public humiliation and execution), and
 +
  so forth.
 +
 +
 +
Town Themes
 +
  Before taking the above information directly to coding, one key issue
 +
  must be addressed: that of town themes.  In life, towns are frequently
 +
  created for specific needs, be it a need for metals thereby necessitating
 +
  a minetown or merely a need for clean water and safe refuge.
 +
  If you wish to have more than one town in your game, it will be quite
 +
  integral to their design to give them themes.  The best example of why
 +
  town themes are important is to think briefly of what your towns would
 +
  look like without them.  Imagine ten towns, all of roughly the same size,
 +
  all with mines, all with markets, all with churches, all with guilds.
 +
  These towns look artificial and can be much worse to play in than towns
 +
  built completely randomly merely because of the cookie-cutter look they
 +
  will have.
 +
  I will assume here that if you do wish to have more than one town, you
 +
  have a way of modelling the landscapes surrounding them, like the realm
 +
  maps of ADOM, Omega, &c.  This is not required, though as themed towns
 +
  can add a lot of flavour even to games like Vanillangband with only one
 +
  town.
 +
  It may be handy to make note of the types of terrain your denomination
 +
  of humanoids may inhabit, and why they would be there.
 +
    eg.  Human - Mainly near water, forests.  Have Castles on hills, Ports
 +
  near running water, only small towns in mountains.
 +
Dwarf - Mainly on hills.  Have Mines in mountains.
 +
&c.
 +
 +
  Doing so will help the software in setting the theme for a town.
 +
  Upon the decision to settle a specific area, the designer should examine
 +
  the surrounding areas to see what a town here could add to life elsewhere.
 +
  Is it a port for merchant ships? an oasis for passing travellers? a mine-
 +
  town to supply precious metals to neighbors?  You will acquire a rough
 +
  idea of how large a town will grow to be, given the amount the town
 +
  is needed at its location and the theme of town created.  eg. If a town
 +
  theme TouristTown is decided upon for an area with only a small
 +
  surrounding population and no hot tourist spots (no dungeons, &c.) then
 +
  the town will be quite small.  Whereas if a MineTown is decided upon and
 +
  the mine is a necessary backbone for the arms and armour of a whole race,
 +
  I would bet that it would be defended quite well, no matter how close
 +
  they were to the enemy borders.
 +
  Town themes also generally restrict the types of Features occuring in
 +
  them.  It would be nothing short of disastrous to have your
 +
  WitheredHouse near the StoneCircle filled with Cultists, only to have
 +
  the evil random number generator put HappyJoesFriendlyInn between
 +
  them.
 +
  After the decision of what Theme to use has been made by the software
 +
  for the town, it should then access a list of what features will be
 +
  available for this theme.  You can do this any way you wish. For
 +
  article continuity I will use a similar sort of list as Joseph Swing
 +
  [JSwing@wport.com] used in his article on Continuous Content in dungeons,
 +
  though I have adapted it to make use of my system of Features creating
 +
  sub-Features.
 +
  A sample list of a Human MineTown:
 +
 +
  Human MineTown
 +
  .1 MineShaft ( exactly 1 )
 +
  .2 Port ( if running water is available, maximum of 1 )
 +
    .1 Market
 +
  .3 Keep ( exactly 1 )
 +
  .3 Tower
 +
  .3 Castle ( if town is large, maximum of 1 )
 +
    .1 City Walls ( exactly 1 )
 +
    .2 Keep ( exactly 1 )
 +
    .3 Gatehouse
 +
    .3 Barracks
 +
    .4 Tower
 +
    .5 Tower
 +
    .6 Tower
 +
  .4 Temple ( or other religious site )
 +
  .5 Tavern
 +
  .5 Inn
 +
    .1 Tavern
 +
  .5 Shop
 +
  .6 Shop
 +
  .6 xxxsmith
 +
  .6 Town Square
 +
  .7 Farm
 +
  .7 Farm
 +
  .7 House
 +
  .8 House
 +
  .9 House
 +
 +
  The actual order of adding Features to your town is up to
 +
  you. I suggest that you first create the important parts, such as
 +
  mines, ports, and any other parts which depend on a certain type of
 +
  terrain for positioning.  This is to ensure that you don't place
 +
  another Feature where it will obscure access to the required terrain.
 +
  You may wish to add (for added complexity) a system which records
 +
  certain values for each town: foodAccess, shelter, defence, trade,
 +
  and so on.  This will allow you to avoid adding redundant features,
 +
  such as excessive shelter per resident, and more food than your
 +
  residents can eat, trade or store.
 +
 +
Townspeople (t)
 +
  Now that you have a reasonable idea of how you can design the towns,
 +
  you now have the option of adding towns-people.  I say option, because it
 +
  would be nice to have a version which doesn't create 'regular' inhabitants
 +
  so you could adapt it to create ghost-towns, overrun towns, and more.
 +
  This could easily be done by creating the class Town, then the derived
 +
  classes PopulatedTown, GhostTown, &c.  Then all that these specialized
 +
  versions need do is add the residents (possibly also knocking a few walls
 +
  down for that 'derelict' look).  This is also a nice way to create over-
 +
  run towns, such as the Human town taken over by Goblin Berserkers (or
 +
  vice-versa).
 +
  I will not go into the depths of creature behaviour here, though I
 +
  will say that if you are going to this much trouble to make realistic
 +
  towns, you really should think about adding at least a little depth
 +
  and complexity to your creatures.
 +
  You may also wish to consider racial tensions (if any) when creating
 +
  your towns.  It is a fairly common fantasy convention that Dwarves
 +
  don't really like anyone.  This could be taken into account when creating
 +
  your towns, lowering the probability of other races living in a mainly
 +
  Dwarvern town.  In the system I have developed, I take a creature's
 +
  religious alignment to be much more important than their actual alignment.
 +
  This allows creatures of all nationalities to befriend each other should
 +
  they follow the same god: but creatures of opposed gods will certainly
 +
  not tolerate living in the same town as each other.
 +
 +
Creation
 +
  TEST RUN::
 +
Below is a demonstration of the previous methods in action, of the steps
 +
  an implementation of this might undergo.
 +
  - Map.  We begin with a map, created by some other means, showing our
 +
  lovely countryside, as below.  Take note that this is a 'Realm Map',
 +
  such as in ADOM.
 +
 +
..^^....==...      #  Dungeon (or tower, ghost town, etc.)
 +
^~^~.^~..=...      .  Clearing
 +
^#~......==~~      T  Forest
 +
.....TT...===      =  River
 +
......TT..~^^      ~  Hills
 +
.T.........~.      ^  Mountains
 +
 +
  - Choose an area.  How you do this is up to you: you can use the RNG,
 +
  or (my personal preference) you can have a Race(Human) class make the
 +
  decision on where they would likely settle.  If you use this method
 +
  you must choose at this point what race will be living here. We will
 +
  create a Human city for this example. Here, the X marks the spot where
 +
  we have decided to build.
 +
 +
..^^....==...
 +
^~^~.^~..=...
 +
^#~......==~~      X  Proposed town site
 +
.....TT...===
 +
......TT..X^^
 +
.T.........~.
 +
 +
  - Pick a Theme.  Examining the terrain around the designated area,
 +
  we see that on four sides there are plains, on two sides there are
 +
  rivers, and on one side each there are mountains and hills.  Given
 +
  also that this site has high access (from the river) and is on
 +
  hilly terrain, the designer decides to create a large city, which
 +
  will contain mines, a castle for defense from the denizens of the
 +
  dungeon '#' (and because, as was written above, Humans usually build
 +
  their Castles on hills), and a port for trade.  We also decide now
 +
  whether to create a populated town or not: for this example we will
 +
  not make a population - this is really another topic, and dependant
 +
  on how your creature system works.
 +
 +
  - Now we create the town, terrain first.  I will use (to save space
 +
  here) a quarter-screen sized map, 40x12.  You may not wish to use
 +
  elevation in your RL, but I have added here hills, marked with ':'.
 +
  These have a few special rules: combat bonuses for creatures on
 +
  elevated areas when in combat with those on normal ground; improved
 +
  LOS and missile range.  Our terrain generator has created a HillyArea,
 +
  which has then created a River, some Hills and a few scattered trees.
 +
 +
...............====............=======..
 +
................========================  .  ground
 +
..T................=============...:.===  :  hill
 +
......................:::T::......:::...  T  trees
 +
...T...::.....:.......:::::......::::..:  =  water
 +
....:::::....::......:T..:T:........::::
 +
.....::....::::...........:.........::::
 +
...::::...:::.::::.............::....:.:
 +
..........::...::.......:::............:
 +
......::.T......:.......:::.....TT....::
 +
...........T.............::..........:::
 +
.................................:::::::
 +
 +
  - The Town.  We have the list of Features above, and by now you have
 +
  likely added to the list some of your own favourites.  Now choose
 +
  the first Feature from the list ( MineShaft ) and add it somewhere
 +
  sensible (near hills).  We can then continue in the fashion described
 +
  by Mr Swing ( 75% chance of choosing the next item, 25% chance of
 +
  choosing the previous ), creating a Port and so on.
 +
 +
...............====............=======..
 +
................========================  a  Mine
 +
..T................=#===#=======...:.===  b  Port
 +
....................#b::#T::......:::...
 +
...T...::.....:.....#+###::......::::..:
 +
....:::::....::......:T..:T:........::::
 +
.....::....::::...........:.........::::
 +
...::::...:::.::::.............::....:.:
 +
..........::...::.......:::......##+###:
 +
......::.T......:.......:::.....T#a..>#:
 +
...........T.............::......######:
 +
.................................:::::::
 +
 +
    After a few more recursions, the town will hav begun to take shape.
 +
  The map below shows what the town might look like after having created
 +
  a castle.  Note that the castle walls do not fully include the Mine.
 +
  This was due to the mine being close to the border of the map.
 +
  Obviously there will be situations such as this, so your code might
 +
  need a little tweaking.  Given the small scale of the map used, I will
 +
  end the demonstration here, though on a larger map there would be
 +
  sufficient room for adding the rest of the features on the list.
 +
    The up staircases on the map below connect with to the second floor
 +
  (where any guards would be) and the down staircases in the Mine and
 +
  Keep can connect with Mines and Dungeons respectively.  There are
 +
  enough articles on how to make these last two items: you shouldn't
 +
  need my help.
 +
 +
  Ground Floor
 +
...............====............=======..
 +
................========================
 +
..T........#+####..=#===#=======...:.===  a  Gatehouses
 +
......####.#a.#.#####.::####......:::...  b  Towers
 +
...T..#<b####+#....c#+###:<#.....::::..:  c  City walls
 +
....::#::+...::.........#:b#........::::  d  Keep
 +
.....:##+#####:.........#+###..######:::
 +
...::::#.#<..+::::g.......+a+..+<+.a#:.:
 +
.......#.#>.f#.::.......#+#########+###:  e  space (on a larger map
 +
......:#.#####.:........#:b#....T#...>#:            you would add
 +
.......#.......##########:<#.....######:            shops, houses,
 +
.......#########........####.....:::::::            an inn, and such.)
 +
 +
  Upstairs
 +
 +
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
 +
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx  x  Either unallocated
 +
xxxxxxxxxxx######xxx#####xxxxxxxxxxxxxxx      tiles or 'air' tiles.
 +
xxxxxx######....#####...####xxxxxxxxxxxx
 +
xxxxxx#>................/.>#xxxxxxxxxxxx
 +
xxxxxx#..################..#xxxxxxxxxxxx
 +
xxxxxx########xxxxxxxxxx#..##########xxx
 +
xxxxxx#>..#xxxxxxxxxxxxx#.......>...#xxx
 +
xxxxxx#...#xxxxxxxxxxxxx#..#######..###x
 +
xxxxxx#####xxxxxxxxxxxxx#..#xxxxx#....#x
 +
xxxxxxxxxxxxxxxxxxxxxxxx#.>#xxxxx######x
 +
xxxxxxxxxxxxxxxxxxxxxxxx####xxxxxxxxxxxx
 +
 +
  That's it.  After creating your town, you have only the task
 +
  of giving it some inhabitants of reasonable wit.  I hope that I
 +
  have inspired a little something in some of you.  Please feel
 +
  free to send me comments to me [michaelblackney@hotmail.com].
 +
 +
/-*/
 +
 +
= Recursive Level Generation - Radomir 'The Sheep' Dopieralski [sheep@venus.wmid.amu.edu.pl] =
 +
 +
Introduction.
 +
-------------
 +
This article contains some of my thoughts about level generation in roguelike
 +
games. It's inspired with an algorithm used in Alphaman to generate buildings,
 +
some articles red on Roguelike News and, that's a little odd, Bison and Yacc
 +
input files format. The ideas may seem a little complicated and hard to
 +
implement, but I hope the article proves useful in some way.
 +
 +
 +
Overview.
 +
---------
 +
The idea is to describe the level in form similar to BNF (Backus-Naur Form),
 +
used usually for describing context-free grammars.
 +
 +
 +
It's natural for humans to describe large and complicated objects in terms of
 +
more simple ones. So we can describe a level.
 +
For example:
 +
 +
a level is either: a maze, a dungeon, a cave, a castle, etc...
 +
 +
 +
a maze is a set of connected corridors and crossroads.
 +
 +
 +
a corridor is a vertical or horizontal line of floor tiles, surrounded
 +
by walls on each side, opened at at least one end.
 +
 +
 +
a crossroad is a single floor tile with walls around, opened in at least two directions.
 +
 +
 +
a dungeon is a set of rooms, crossroads and corridors.
 +
 +
 +
a room is either: a vault, a minor vault, an ordinary room.
 +
etc...
 +
 +
 +
There are some rules not covered here. For example, we'd like to ensure each
 +
place of the level is reachable. It's not very easy to do, so we won't try to
 +
describe any level type, like in the example above. We'll try to only describe
 +
(and then generate) some special level type, constructed by dividing rooms.
 +
 +
 +
Alphaman's buildings.
 +
---------------------
 +
We will use an algorithm similar to this used in Alphaman. I'll first describe
 +
the original algorithm. It is quite simple:
 +
 +
 +
1. Start with a large, empty room.
 +
XXXXXXXXXXXXXXXXX
 +
X...............X
 +
X...............X
 +
X...............X
 +
X...............X
 +
X...............X
 +
X...............X
 +
X...............X
 +
X...............X
 +
X...............X
 +
X...............X
 +
X...............X
 +
X...............X
 +
X...............X
 +
XXXXXXXXXXXXXXXXX
 +
 +
 +
2. Pick an acxis (horizontal or vertical) and a point within the room (far from walls).
 +
Let's suppose we have picked horizontal axis and point marked with '1'.
 +
XXXXXXXXXXXXXXXXX
 +
X...............X
 +
X...............X
 +
X...............X
 +
X...............X
 +
X...............X
 +
X...............X
 +
X...............X
 +
X......1........X
 +
X...............X
 +
X...............X
 +
X...............X
 +
X...............X
 +
X...............X
 +
XXXXXXXXXXXXXXXXX
 +
 +
3. Make a wall in selected axis, crossing the chosen point, ending at the
 +
room's walls and with door in point '1'.
 +
XXXXXXXXXXXXXXXXX
 +
X...............X
 +
X...............X
 +
X...............X
 +
X...............X
 +
X...............X
 +
X...............X
 +
X...............X
 +
X######+########X
 +
X...............X
 +
X...............X
 +
X...............X
 +
X...............X
 +
X...............X
 +
XXXXXXXXXXXXXXXXX
 +
 +
4. You get two new rooms. Repeat the procedure with those of them, that arte large enough.
 +
XXXXXXXXXXXXXXXXX
 +
X...............X
 +
X...............X
 +
X###########+###X
 +
X...............X
 +
X...............X
 +
X...............X
 +
X...............X
 +
X######+########X
 +
X.........#.....X
 +
X.........+.....X
 +
X.........#.....X
 +
X.........#.....X
 +
X.........#.....X
 +
XXXXXXXXXXXXXXXXX
 +
 +
5. You end up with set of interconnected rooms, with exactly one way between
 +
every two rooms. Something like a tree.
 +
 +
The procedure is simple, but the result is not very nice. It's always a
 +
labirynth of rooms and you usually have to walk a lot to explore it. We'll try
 +
to make the result better.
 +
 +
Adding corridors.
 +
-----------------
 +
We can try to add some corridors, so our level will look more naturally and
 +
there will be more connections between rooms.
 +
So, instead of adding a wall, we'll add two parallel walls, making a corridor.
 +
We also add doorways at the ends of the corridors, so there will be more
 +
connections. The algorithm goes like this:
 +
 +
1. Start with a large, empty room.
 +
XXXXXXXXXXXXXXXXX
 +
X...............X
 +
X...............X
 +
X...............X
 +
X...............X
 +
X...............X
 +
X...............X
 +
X...............X
 +
X...............X
 +
X...............X
 +
X...............X
 +
X...............X
 +
X...............X
 +
X...............X
 +
XXXXXXXXXXXXXXXXX
 +
 +
2. Pick an acxis (horizontal or vertical) and a point within the room (far from walls).
 +
Let's suppose we have picked horizontal axis and point marked with '1'.
 +
XXXXXXXXXXXXXXXXX
 +
X...............X
 +
X...............X
 +
X...............X
 +
X...............X
 +
X...............X
 +
X...............X
 +
X...............X
 +
X......1........X
 +
X...............X
 +
X...............X
 +
X...............X
 +
X...............X
 +
X...............X
 +
XXXXXXXXXXXXXXXXX
 +
 +
3. Make a corridor in selected axis, crossing the chosen point, ending at the
 +
room's walls. If the walls at it's ends are not permanent, make some doorways
 +
there.
 +
XXXXXXXXXXXXXXXXX
 +
X...............X
 +
X...............X
 +
X...............X
 +
X...............X
 +
X...............X
 +
X...............X
 +
X###############X
 +
X......1........X
 +
X###############X
 +
X...............X
 +
X...............X
 +
X...............X
 +
X...............X
 +
XXXXXXXXXXXXXXXXX
 +
 +
4. Make some doors along the corridor's walls. There should be at leas one door
 +
in each wall, so you make sure all the rooms are connected.
 +
XXXXXXXXXXXXXXXXX
 +
X...............X
 +
X...............X
 +
X...............X
 +
X...............X
 +
X...............X
 +
X...............X
 +
X####+######+###X
 +
X......1........X
 +
X###+###########X
 +
X...............X
 +
X...............X
 +
X...............X
 +
X...............X
 +
XXXXXXXXXXXXXXXXX
 +
 +
5. You get two new rooms. Repeat the procedure with those of them, that are large enough.
 +
XXXXXXXXXXXXXXXXX
 +
X...............X
 +
X###+###########X
 +
X...........2...X
 +
X#####+#####+###X
 +
X...............X
 +
X...............X
 +
X####+######+###X
 +
X......1........X
 +
X###+#####.#####X
 +
X........#3#....X
 +
X........#.+....X
 +
X........+.#....X
 +
X........#.#....X
 +
XXXXXXXXXXXXXXXXX
 +
 +
The result doesn't look so bad, especially if the rooms left at the end are big
 +
enough (in the example there isn't much place).
 +
But there is another problem -- how to fill the rooms with appropriate contents
 +
(that is items and monsters)? How to make sure the rooms are connected with
 +
some logic?
 +
 +
Level definitions.
 +
------------------
 +
Here's what we can do. We don't just split in two similar rooms. We will have
 +
to name these rooms and provide some rules how to split them. For example, for
 +
a scientific level in sf roguelike:
 +
 +
a level may: (put some probabilities here)
 +
be a scientific level;
 +
 +
a scientific level must:
 +
be at least SIZE large, but not larger than SIZE;
 +
 +
a scientific level may:
 +
consist of two scientific sections, divided (horizontally or
 +
vertically) with a scientific hall;
 +
 +
a scientific hall may:
 +
be a very wide corridor, with large doors at each end and at least one
 +
door at each side;
 +
there may be some plants or statues;
 +
there may be some scientific guards;
 +
there may be some scientific monsters;
 +
tehre may even be some scientific scientifists;
 +
 +
a scientific section may:
 +
consist of two scientific sections divided (horizontally or vertically)
 +
with a scientific corridor;
 +
 +
a scientific corridor may:
 +
be a wide corridor with open doorways at each end and at least one door
 +
at each side;
 +
 +
a scientific section must:
 +
be at least SIZE large, but not larger than SIZE;
 +
 +
a scientific section may:
 +
consist of two scientific labs divided (horizontally or vertically)
 +
with a scientific corridor;
 +
 +
a scientific lab must:
 +
be at least SIZE large, but not larger than SIZE;
 +
 +
a scientific lab may:
 +
consist of two scientific labs divided with a scientific wall;
 +
 +
a scientific wall may:
 +
be a wall with door in the middle;
 +
 +
a scientific lab may:
 +
be a room with tiled floor;
 +
there may be some scientific artifacts;
 +
there may be some scientific monsters;
 +
there may even be some scientific scientifists;
 +
 +
Building a level.
 +
-----------------
 +
Now, let's see how to produce a random level from such an information.
 +
First, we want to build a level. So we look at the definitions and see that our
 +
level may be a scientific level with such-and-such probability. But there may
 +
be also other level definitions, so we have to choose (randomly) which level
 +
definition to choose. Let's suppose we have chosen the scientific level. We
 +
see that it has to be such-and-such big, so we provide an empty starting room
 +
of given size.
 +
Now we look into the definion and see that we have to split our level in two
 +
with a scientific hall and put a scientific section on each side. So we pick a
 +
point, pick an axis, put aour corridor in the middle and a scientific section
 +
at each side. It would be good to pay attention on the minimal size of each of
 +
the sections while picking a point to split the level. Then, we have to make
 +
our scientific sections. As we look into definitions, we see that we have two
 +
choices. So we pick randomly one of them.
 +
We can either split these sections into smaller ones, or into scientific labs.
 +
At some points, we'll have to do the second thing, because there will be no
 +
place to put a scientific section (which is supposedly larger than a lab). We
 +
continue down the tree of level fetures, until we arrive at the 'atom' ones,
 +
that is the features that doesn't consist of other features, and taht we can
 +
generate using other algorithms.
 +
Sometimes there may be need for the algorithm to 'back up' wrong decissions,
 +
because there is no way it can get to the atoms. This is because of the size
 +
limitations. It's a drawback and I don't know how to make sure it ever
 +
completes the level.
 +
But I believe it can be solved somehow.
 +
 +
Level representation.
 +
---------------------
 +
With this algorithm you can use different level representations. The most
 +
common, simple two-dimensional array will do. But you can also have a linked
 +
list of features, or even a binary tree. If there were no doors at the ends of
 +
the corridors, you could even generete only these parts of the level you need
 +
at the moment, making all the fetures from the root of the tree to the node you
 +
want to know.
 +
 +
--
 +
The Sheep

Revision as of 20:16, 1 May 2008

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

Cannot Find:

  * How to finish your roguelike - Peter Farabaugh [pete@tbe.net].txt Found a russian translation: http://www.rlgclub.ru/pmwiki.php?n=Main.ArticlesDevRlgFinish
  * User Interface in Roguelikes - Jim Babcock [jimmy_b@earthlink.net].txt Found a russian translation: http://www.rlgclub.ru/pmwiki.php?n=Main.ArticlesDevUserInterface
  * Roguelike Step by Step Guide.txt
  * Mostly Turn-based Multiplayer Timing - Isaac Kuo [mechdan@yahoo.com].txt Found a russian translation: http://www.rlgclub.ru/pmwiki.php?n=Main.ArticlesDevTurnBasedMultiplayer
  * Lake and Oasis Generator - Adam Szczepaniak [adamshc@wp.pl].txt
  * Fill-area-with-rooms and Maze - algorithms - Josh VertexNortmal Tippetts [vertexnormal@email.com].txt Found russian translation: http://www.rlgclub.ru/pmwiki.php?n=Main.ArticlesDevMazeGen
  * Recursive randomized world-map generation Phillip C. Culliton [pcullit@hotmail.com].txt
  * 3D Representation for Roguelike Worlds - Jimmy Babcock [jimmy_b@earthlink.net].txt

TODO:

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

Contents