This article was originally written for Darren Hebden's RLNews
----------------------------------------------------------------------------
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.
|
