User:Duerig/Archive6
Redefinable Keyboard Bindings - Stu George
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).
>From 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