Thread: Best data structure to use.

  1. #1
    Registered User
    Join Date
    Dec 2008
    Location
    California
    Posts
    37

    Best data structure to use.

    I'm currently creating a RPG game but I don't know which data structure is the fastest. Is it arrays or linked list? I'm just storing maybe more than 100 data inside and every frame it checks everything (checks if hp <= 0 and etc) so I really need a fast data structure so that my game will run fast on some old computers. Less cpu power and memory.

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Data structures aren't fast; in fact they don't do anything but sit there. Algorithms may or may not be fast.

    There are going to a couple things to consider, I would guess -- traversing might be quicker with an array, or at worst a tie; where the difference between them would come out would be creating them and manipulating them. Will you know, at the beginning, how many objects you'll need? Will you have to take things out and put things in while the game is playing?

  3. #3

  4. #4
    Chinese pâté foxman's Avatar
    Join Date
    Jul 2007
    Location
    Canada
    Posts
    404
    I would also add that there might (read, certainly) be more important things to consider if your goal is to use the minimum of CPU ressource. Also, don't try to create problems where there's not. Do you really believe that you'll need this kind of "extra performance" to play on old computers ?
    I hate real numbers.

  5. #5
    Registered User
    Join Date
    Dec 2006
    Location
    Canada
    Posts
    3,229
    100 checks per frame is nothing for modern computers (within a few decades).

    Linked lists are better if you need to FREQUENTLY insert or delete elements in the middle.
    Arrays are better if you need random access.

    If you are only going to create a fixed size list and iterate through it every time (no insertion/deletion in the middle, and no random access), both will work.

    However, arrays tend to be faster for that due to locality of reference. They are also more memory-efficient (don't need to store pointers to next element).

    Rule of thumb - arrays (or vectors, since this is C++) should be used until proven otherwise.

  6. #6
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    You're unfortuantely in the position where you don't even know what information you need to provide for anyone to make any kind of informed decision. You need to answer as many of these as possible:
    1. How many items will typically be in the container?
    2. Do you need to iterate over them in sorted order or otherwise sort the items?
    3. Do you ever add or remove items in the middle or at the beginning, or do you only add/remove items at the end?
    4. Is the order of the items important?
    5. Do you ever add items after your apps initialisation phase?
    6. Do you ever use the container for looking up a particular item, or do you always go through the whole lot?
    7. How often do you do these things in relation to one another: Iteration, lookup, sorting, insertion, removal?
    Anything else like that that you can think of would help.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  7. #7
    Registered User
    Join Date
    Dec 2008
    Location
    California
    Posts
    37
    Quote Originally Posted by tabstop View Post
    Data structures aren't fast; in fact they don't do anything but sit there. Algorithms may or may not be fast.

    There are going to a couple things to consider, I would guess -- traversing might be quicker with an array, or at worst a tie; where the difference between them would come out would be creating them and manipulating them. Will you know, at the beginning, how many objects you'll need? Will you have to take things out and put things in while the game is playing?
    What I want to put in there is all the units in the map. For example, there's more than 100 monster in the map and it will check every frame which of the unit's hp is less than 0(if so, remove it) and it will also check if I (the user/player) reach his line of sight(if so, run AI). I'll probably add more in the future.

    Quote Originally Posted by foxman View Post
    I would also add that there might (read, certainly) be more important things to consider if your goal is to use the minimum of CPU ressource. Also, don't try to create problems where there's not. Do you really believe that you'll need this kind of "extra performance" to play on old computers ?
    Your saying that I should ignore this and continue programming without knowing which one is faster? Yes. I need a fast one because I want my game to run fast on a old pentium 1 or even on my old compaq armada. Maybe your the type of programmer who doesn't care about old computers.

    Quote Originally Posted by cyberfish View Post
    100 checks per frame is nothing for modern computers (within a few decades).

    Linked lists are better if you need to FREQUENTLY insert or delete elements in the middle.
    Arrays are better if you need random access.

    If you are only going to create a fixed size list and iterate through it every time (no insertion/deletion in the middle, and no random access), both will work.

    However, arrays tend to be faster for that due to locality of reference. They are also more memory-efficient (don't need to store pointers to next element).

    Rule of thumb - arrays (or vectors, since this is C++) should be used until proven otherwise.
    Yeah I think it will be in fixed size or maybe it will not? (Summon skeletons or what so ever). Is there a big advantage with the fixed size and the one that is not.

    Quote Originally Posted by iMalc View Post
    You're unfortuantely in the position where you don't even know what information you need to provide for anyone to make any kind of informed decision. You need to answer as many of these as possible:
    1. How many items will typically be in the container?
    2. Do you need to iterate over them in sorted order or otherwise sort the items?
    3. Do you ever add or remove items in the middle or at the beginning, or do you only add/remove items at the end?
    4. Is the order of the items important?
    5. Do you ever add items after your apps initialisation phase?
    6. Do you ever use the container for looking up a particular item, or do you always go through the whole lot?
    7. How often do you do these things in relation to one another: Iteration, lookup, sorting, insertion, removal?
    Anything else like that that you can think of would help.
    1) How many items will typically be in the container?
    more than 100. Maybe it will reach 200 or 300.

    2) Do you need to iterate over them in sorted order or otherwise sort the items?
    Nope

    3) Do you ever add or remove items in the middle or at the beginning, or do you only add/remove items at the end?
    Remove it anywhere if the (hp <= 0)

    4) Is the order of the items important?
    No.

    5) Do you ever add items after your apps initialization phase?
    What do you mean apps initialization? After loading all the required files like images, musics, sound effect and the map? If so, yes.

    6) Do you ever use the container for looking up a particular item, or do you always go through the whole lot?
    Always search particular item. Remove it or do some ai.

    7) How often do you do these things in relation to one another: Iteration, lookup, sorting, insertion, removal?
    Iteration,lookup = always
    removal = if something is true
    sorting = I think I don't need to sort it.
    insertion = Spawning a monster? it depends on the spawning time of the monster.

    I'm creating a 2d RPG Diablo like game.

  8. #8
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,412
    Quote Originally Posted by m3rk
    What I want to put in there is all the units in the map. For example, there's more than 100 monster in the map and it will check every frame which of the unit's hp is less than 0(if so, remove it) and it will also check if I (the user/player) reach his line of sight(if so, run AI). I'll probably add more in the future.
    Quote Originally Posted by m3rk
    6) Do you ever use the container for looking up a particular item, or do you always go through the whole lot?
    Always search particular item. Remove it or do some ai.
    The above two paragraphs seem to conflict. In the former, it looks like you intend to iterate over the entire list of monsters and for each monster, either remove it, run its AI routine, or do nothing. In the latter, it looks like you are will always search for a given monster, but it is not clear how you know what monster to search for.

    If you actually mean the former, then a linked list (e.g., using the std::list container) does make sense since you would want fast deletion in the middle and do not need fast searching.
    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

  9. #9
    Confused Magos's Avatar
    Join Date
    Sep 2001
    Location
    Sweden
    Posts
    3,145
    Consider a more intelligent approach. Only check the "HP <= 0" when the HP changes, instead of constantly checking each iteration. Something like:
    Code:
    void AddHP(int Amount)
    {
      CurrentHP += Amount; //Amount can be negative
      if(CurrentHP <= 0) KillCreature();
    }
    Not that a single "<=" check will kill your fps, but the idea can be used in more critical locations.
    MagosX.com

    Give a man a fish and you feed him for a day.
    Teach a man to fish and you feed him for a lifetime.

  10. #10
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,318
    Quote Originally Posted by m3rk View Post
    5) Do you ever add items after your apps initialization phase?
    What do you mean apps initialization? After loading all the required files like images, musics, sound effect and the map? If so, yes.
    That one's a difficult one to ask unfortunately. Rewording, once the 'game' is underway does it ever change. Don't worry I realise the answer is yes. When the answer is no, it leans you towards having a sorted table on which binary searches are performed.

    From your answers, a vector is fastest (which is no surprise), but you'll want to use the "swap with back + pop_back" method to remove items, which will be fine since you've stated the order is unimportant.

    I'm ignoring your statement about lookups though as it seems you were confused. Lookups relate to hunting down one single item, such as looking up a PC name via it's IP Address. You appear to do stuff to all items every time.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  11. #11
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,412
    Quote Originally Posted by iMalc
    From your answers, a vector is fastest (which is no surprise), but you'll want to use the "swap with back + pop_back" method to remove items, which will be fine since you've stated the order is unimportant.
    Ah yes, I forgot about that. In that case I agree, a dynamic array would be the best choice.
    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

  12. #12
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by m3rk View Post
    Your saying that I should ignore this and continue programming without knowing which one is faster? Yes. I need a fast one because I want my game to run fast on a old pentium 1 or even on my old compaq armada. Maybe your the type of programmer who doesn't care about old computers.
    I think he's saying do the math -- assuming 60 frames per second, 100 monsters, say on average ten operations per monster, that's 60,000 operations per second. (Never mind about this -- see edit.)

    It's probably for the best to use the most efficient algorithm that you can, but in this case I don't know that either is going to make a huge difference (unless you are planning to delete monsters a lot).

    Edit: Well, the 8086 was a 5MHz machine, that actually translates to about 10,000 operations per second, my mistake. Still, a Pentium 1, you're looking at over 3 million instructions per second.
    Last edited by tabstop; 01-26-2009 at 01:25 PM.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Include GTK+ just for a data structure?
    By Jesdisciple in forum C Programming
    Replies: 0
    Last Post: 04-12-2009, 07:19 PM
  2. pthread question how would I init this data structure?
    By mr_coffee in forum C Programming
    Replies: 2
    Last Post: 02-23-2009, 12:42 PM
  3. Data structure implementation
    By fkheng in forum C Programming
    Replies: 3
    Last Post: 07-31-2003, 07:44 AM
  4. can't insert data into my B-Tree class structure
    By daluu in forum C++ Programming
    Replies: 0
    Last Post: 12-05-2002, 06:03 PM
  5. Tab Controls - API
    By -KEN- in forum Windows Programming
    Replies: 7
    Last Post: 06-02-2002, 09:44 AM