Linked List for items???

Printable View

08-07-2011
voidpain()

Linked List for items???

I am currently working on a project that works very much like a text adventure. Each room in the "world" is a structure defined as follows:

Code:

typedef struct Area { char *name; //name of the area char *desc; //description of the area int exit[4]; //exits the area can make } Area;

Each room will also have items that can be picked up and moved to other rooms. My questions is this--should I store these items in linked lists, wherein each room has its own linked list, and the user has a personal linked list that acts as his/her "inventory"? If I do things this way, will I need to change anything in the structure areas?
08-07-2011
quzah

You should probably make each room keep track of what item is in it. You could also make each item track what room it is in, or who has it. You might also consider making functions such as "move to room" and "move to player", that take an item and move it from wherever it is to a room or to a player. You might even make a list of every item (as a singular big list of everything in existence).

Code:

int do_get( ITEM *item, PLAYER *player ) { if( item->room == player->room ) { moveitemfromroom( item ); moveitemtoplayer( item, player ); return 0; } return -1; }

Or something to that effect.

Quzah.
08-07-2011
CommonTater

Quote:

Originally Posted by voidpain()

I am currently working on a project that works very much like a text adventure. Each room in the "world" is a structure defined as follows:

Code:

typedef struct Area { char *name; //name of the area char *desc; //description of the area int exit[4]; //exits the area can make } Area;

Each room will also have items that can be picked up and moved to other rooms. My questions is this--should I store these items in linked lists, wherein each room has its own linked list, and the user has a personal linked list that acts as his/her "inventory"? If I do things this way, will I need to change anything in the structure areas?

Ok... here is an execllent chance for you to learn a programmer's four steps...
Step 1, where you appear to be now is that of analyzing a given task or problem until you understand it well enough to describe it in writing. So sit down and play the game in your mind and/or on paper until you understand exactly what it needs... then you can move to step 2, planning the various code elements you will need to make it work... Finally when you have a "game plan" (pun intended) you can move to steps 3 and 4... writing and testing your code.

Yes linked lists can be used, but you might also consider arrays... Generally where you have a known number of elements (rooms, bagage, enemies, etc.) an array of structs will be far more efficient than a linked list. It's only when you don't know how many elements that you are left with little choice but to use linked lists... So, in the process of analysing your task, you need to figure that out.

Another consideration is the content of the stucts themselves... this will be dictated by the needs of your game, which until fully understood, can't be decided.
08-07-2011
laserlight
Quote:

Originally Posted by CommonTater

Yes linked lists can be used, but you might also consider arrays... Generally where you have a known number of elements (rooms, bagage, enemies, etc.) an array of structs will be far more efficient than a linked list. It's only when you don't know how many elements that you are left with little choice but to use linked lists... So, in the process of analysing your task, you need to figure that out.

I second CommonTater's point that you need to choose your data structures wisely. That said, I do not think that "is the number of elements known?" should be the primary consideration when choosing between an array and a linked list. While arrays may be of fixed size, by using dynamic memory allocation you can have dynamically sized arrays.

What I would consider are the typical access and modification of this list of items:
- Will you frequently insert into the middle of the list, say immediately after some other item? If so, a linked list would be good because with a pointer to a node, adding a node right after that takes constant time. But if you are only going to add to the end of the list, an array would be just as good as a linked list in which you keep track of the tail.
- Do you need random access? That is, besides accessing the items in sequence, you expect that you will frequently need to access some item in the middle of the list. If so, an array would be better than a linked list.
- Do you need to keep track of the items from another data structure? If so, a linked list may be better because with a dynamic array, when you need to resize the dynamic array, pointers to the items in the array may be invalidated. Alternatively, you could use a dynamic array of pointers to items, but this would make your code more complex.
08-07-2011
quzah

Arrays are generally terrible for this sort of thing. Why? Watch:

Code:

[ ] [3] [ ] [ ] | [0]-[1]-[2] [ ] | [ ] [ ] [4]-[5]

We only really need 6 rooms. But if we want an array, we have to have 12. Sure, an array would work if you needed 100 rooms, and had a perfect 10x10 every-spot-used grid (such as you might if you were doing a maze), because then the benefit of using an array is actually there. You can use X/Y indexing to move the directions you want.

But what if I want 100 rooms, and I want to have a hall 50 rooms long, with another half a dozen branches ending in rooms five to ten rooms deep? Well then an array is terrible, because now we have to have 500 rooms in an array, and we're not using most of them.

There's a reason none of the MUDs out there use arrays for their areas. (Though it's not uncommon for there to be an array in the room structure denoting the exits. So yes, you do need to think carefully about what works best where. A linked list for exits would probably not be very useful - though if you let people create exits attached to whatever they want, rather than compass directions, you may after all!

But I agree with what both of them are saying: Think it through (so that you can come to the obvious conclusion. ;) )

Quzah.
08-08-2011
voidpain()

Very helpful, thank you all!
08-08-2011
TheBigH

Quote:

Originally Posted by quzah

Arrays are generally terrible for this sort of thing. Why? Watch:

Code:

[ ] [3] [ ] [ ] | [0]-[1]-[2] [ ] | [ ] [ ] [4]-[5]

We only really need 6 rooms. But if we want an array, we have to have 12.

Sure, but if the array was more like

Code:

[X] [3] [X] [X] | [0]-[1]-[2] [X] | [X] [X] [4]-[5]

where X is a sentinel value that means "You can't go that way" then 11 of the 12 spots will be useful. Implementing this as a linked list means you have ten valid direction pointers (the paths you can take, in both directions) and thirteen invalid direction pointers (all the paths you can't take, like west from 0 or north from 2), assuming I've counted right. I don't think this is much of an improvement.
08-08-2011
quzah

Quote:

Originally Posted by TheBigH

Sure, but if the array was more like

Code:

[X] [3] [X] [X] | [0]-[1]-[2] [X] | [X] [X] [4]-[5]

where X is a sentinel value that means "You can't go that way" then 11 of the 12 spots will be useful.

You'd still have to add another 2 to each dimension to do what you want, because you'd have to have "don't go here" east of 5, south of 5, north of 3, and west of 0. You could end up with a huge amount of wasted space, considering each 'room' tends to be more than just a char saying you are there or not (for the type of game he's describing; a MUD in effect).

Quote:

Originally Posted by TheBigH

Implementing this as a linked list means you have ten valid direction pointers (the paths you can take, in both directions) and thirteen invalid direction pointers (all the paths you can't take, like west from 0 or north from 2), assuming I've counted right. I don't think this is much of an improvement.

You are confusing "ways to go" with "rooms."

Code:

struct room_data { ROOM_DATA *next; EXIT_DATA *exit[ DIRS ]; CREATURE_DATA *creatures; OBJECT_DATA *objects; char *name; char *description; ... room flags and all sorts of other goodies ... };

The point is, an array for all your rooms, while it could save you X pointer per room, is also going to cost you a ton of memory if you have anything other than tightly clustered rooms. And adding one more room to the north (or any direction) when at a boundary is going to be enormous.

Now "ways to go" could be rooms, but that's not really what he is describing. A room or area has more than just exits (it doesn't have to, but he's doing it that way from the sound of things).

Quzah.