Thread: Linked List for items???

  1. #1
    Registered User
    Join Date
    Aug 2011
    Posts
    20

    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?

  2. #2
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    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.
    Hope is the first step on the road to disappointment.

  3. #3
    Banned
    Join Date
    Aug 2010
    Location
    Ontario Canada
    Posts
    9,547
    Quote Originally Posted by voidpain() View Post
    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.
    Last edited by CommonTater; 08-07-2011 at 09:55 PM.

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    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.
    Last edited by laserlight; 08-07-2011 at 10:11 PM.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #5
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    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.
    Last edited by quzah; 08-07-2011 at 11:02 PM. Reason: shuffling sentences around
    Hope is the first step on the road to disappointment.

  6. #6
    Registered User
    Join Date
    Aug 2011
    Posts
    20
    Very helpful, thank you all!

  7. #7
    Registered User TheBigH's Avatar
    Join Date
    May 2010
    Location
    Melbourne, Australia
    Posts
    426
    Quote Originally Posted by quzah View Post
    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.
    Code:
    while(!asleep) {
       sheep++;
    }

  8. #8
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Quote Originally Posted by TheBigH View Post
    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 View Post
    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.
    Hope is the first step on the road to disappointment.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. how to reverse items in linked list?
    By ilikeapplepie in forum C Programming
    Replies: 8
    Last Post: 04-09-2011, 11:15 PM
  2. Delete All Items In A Linked List
    By Khellendros in forum C++ Programming
    Replies: 6
    Last Post: 02-09-2009, 01:22 AM
  3. Sorting items in a std::list
    By alkis_y3k in forum C++ Programming
    Replies: 7
    Last Post: 01-19-2003, 07:45 AM
  4. modifying items in a linked list?
    By aspand in forum C Programming
    Replies: 3
    Last Post: 06-14-2002, 01:37 PM
  5. Replies: 5
    Last Post: 11-20-2001, 12:48 PM

Tags for this Thread