Printable View
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.
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?
check here:
linked list vs array
try profile your code:
http://www.codeproject.com/KB/cpp/profiler.aspx
http://stackoverflow.com/questions/6...file-your-code
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 ?
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.
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:Anything else like that that you can think of would help.
- How many items will typically be in the container?
- Do you need to iterate over them in sorted order or otherwise sort the items?
- Do you ever add or remove items in the middle or at the beginning, or do you only add/remove items at the end?
- Is the order of the items important?
- Do you ever add items after your apps initialisation phase?
- Do you ever use the container for looking up a particular item, or do you always go through the whole lot?
- How often do you do these things in relation to one another: Iteration, lookup, sorting, insertion, removal?
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 tabstop
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 foxman
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 cyberfish
1) How many items will typically be in the container?Quote:
Originally Posted by iMalc
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.
Quote:
Originally Posted by m3rk
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.Quote:
Originally Posted by m3rk
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.
Consider a more intelligent approach. Only check the "HP <= 0" when the HP changes, instead of constantly checking each iteration. Something like:
Not that a single "<=" check will kill your fps, but the idea can be used in more critical locations.Code:void AddHP(int Amount)
{
CurrentHP += Amount; //Amount can be negative
if(CurrentHP <= 0) KillCreature();
}
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.Quote:
Originally Posted by m3rk
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.
Ah yes, I forgot about that. In that case I agree, a dynamic array would be the best choice.Quote:
Originally Posted by iMalc
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.)Quote:
Originally Posted by m3rk
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.