
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
This text is written specially for Darren Hebden's Roguelike News developers section. Visit Darren's great pages at
""
---------------------------------------------------------------------------- (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:
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:
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:
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