• Advertisement

Archived

This topic is now archived and is closed to further replies.

Should I store the enemies etc. in lists / arrays? (2D game)

This topic is 5552 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Or where? Is it ok to to create a vector / linked list of say CGameObject. Then derive all the enemies, the player, energy boosts etc. from that CGameObject and place all of them in that list. That way I could do the following thing (Not real code btw ):
CGameObject* poGameObject;
poGameObject = oList.GetNext();
poGameObject->Render();
 
Something like that. Is this a stupid way of doing things? To me it seems like a handy way of drawing all the objects (sprites more specifically) nice and cleanly. Comments are welcome. =) Oh and if I have that list of CGameObject pointers, should I place that list in my CGame class as a private member?
CGame oGame;
oGame.RenderObjects();
 

Share this post


Link to post
Share on other sites
Advertisement
Enemies will often die, and depending on your game, new ones may often be created (especially true for other sprites such as projectiles). Therefore arrays are a bad choice. I have written games using arrays, but that was before I learned of linked lists. Linked lists are a much better alternative.

Note that for permanent sprites, like static objects placed in the level, arrays are best.

~CGameProgrammer( );

Share this post


Link to post
Share on other sites
Yup, that''s probably very true. After all, I don''t know or want to limit the amount of objects/sprites. Thanks for the advice.=)

Btw, what do you mean by static objects?

Share this post


Link to post
Share on other sites
Static objects = objects that you know will be there, objects you know will not change/die/spawn in a random fashion.
Like bakgrounds, terrain etc.

Share this post


Link to post
Share on other sites
That trick is quite valid in OO programming, in fact it involves polymorphism and specialization.

(Note: in VC++ 6.0 it involves changing a setting in the project to activate ''RTTI information'')
As an example, this is how I built a whole GUI system...


  
class GUI{
virtual bool IsOver(int X, int Y)=0; // returns true if given screen coordinates are over the GUI

virtual void MouseEvent(DWORD dwEventType, DWORD dwEventData)=0; // Called when the manager detects mouse events for this GUI

virtual HRESULT Render()=0; // Renders this GUI

virtual HRESULT Update(float fDeltaT)=0; // Updates this GUI (call each frame)

};


Look up virtual classes and pure virtual classes. The trick is that when creating a specialized ''GUI'', one can still use a basic GUI pointer yet use the specialized functions. Making it ''pure virtual'' ensures you don''t accidentally use a simple nonspecialized GUI.


  
class GUIRectangle : public GUI{
GUIRectangle(...){...} // involves coords and color

virtual bool IsOver(int X, int Y){...} //rectangle detection

virtual void MouseEvent(DWORD dwEventType, DWORD dwEventData){...} //depends on implementation

virtual HRESULT Render(){...} //render a quad

virtual HRESULT Update(float fDeltaT){} // depends on implementation

};


Obviously, a circular GUI would be specialized in a different manner than this. But keeping a list of GUI pointers, one can do this (with RTTI active):

GUI *ptr[2];
ptr[0]=new GUIRectangle(...);
ptr[1]=new GUICircle(...)
ptr[0]->Render();
ptr[1]->Render();

That''s the beauty of inheritance and polymorphism. Don''t be afraid to use it!
Oh, question two is about keeping that list of object as a member... Well, I''d advise that you should expect to -vary- that list a lot according to an active ''scene'' (or loaded level, or whatever). So a manager that can easily handle your variety of game objects, load new lists and possibly reorder them according to godknowswhat might be a better thing than a simple ''member list''.

One last tip: LEARN STL! ^n.n^ And use your std::list with pointers rather than whole objects to save on recopy constructors.

=^.^= Leaders and teachers should remember: It is best to offer others what they Need, not what they Want.

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
You''ll want to be careful with linked-lists. Jumping all over memory isn''t good for the cache and very bad if a new page needs to be loaded. Perhaps clever use of a vector would be more in line.

Share this post


Link to post
Share on other sites
Thank you guys. I''m by no means a newbie to OO but I''m very new to game development thus I had to make sure I wasn''t approaching this the wrong way.

Share this post


Link to post
Share on other sites
quote:
Original post by Spacecat
That trick is quite valid in OO programming, in fact it involves polymorphism and specialization.

(Note: in VC++ 6.0 it involves changing a setting in the project to activate ''RTTI information'')

Why does it have to be activated? Never knew this. Oh and where do I activate it?

quote:

Oh, question two is about keeping that list of object as a member... Well, I''d advise that you should expect to -vary- that list a lot according to an active ''scene'' (or loaded level, or whatever). So a manager that can easily handle your variety of game objects, load new lists and possibly reorder them according to godknowswhat might be a better thing than a simple ''member list''.



So you''re saying I should create a manager class which contains the pointer list(s)?

Share this post


Link to post
Share on other sites
Make a typedef, and try both! It''s really not very hard to do. Spontaneously, I would favor a deque over a linked list, because there is going to be much more access than deletion/insertion, but only profiling could tell which one is really faster.

Cédric

Share this post


Link to post
Share on other sites
You might want to check out STL::vector(it might have been said before, didn''t read the whole thread..)


/* Everything IMHO */
-Luctus

Share this post


Link to post
Share on other sites
quote:
Original post by xjussix
quote:
Original post by Spacecat
(Note: in VC++ 6.0 it involves changing a setting in the project to activate 'RTTI information')

Why does it have to be activated? Never knew this. Oh and where do I activate it?

It doesn't have to be activated to use polymorphic classes. RTTI only needs to be activated if you use RTTI stuff (such as dynamic_cast, etc).

[edited by - Dactylos on December 4, 2002 10:33:47 AM]

Share this post


Link to post
Share on other sites
quote:
Original post by Maverick the divider
I think for a small game you should follow one rule:

"Never create and delete objects during a real-time process"




Why not ? You certaintly will not notice any performance problems. Especially not if it is a small game.

Share this post


Link to post
Share on other sites
quote:
Original post by xjussix


CGameObject* poGameObject;
poGameObject = oList.GetNext();
poGameObject->Render();


Something like that. Is this a stupid way of doing things?


I have done something similar a few times and it works great.

Share this post


Link to post
Share on other sites
quote:
Original post by granat
Why not ? You certaintly will not notice any performance problems. Especially not if it is a small game.


and that one depends on how often you do it. use a list for a particle system or say projectiles of a minigun and you shouldnt be surprised if its slow as hell (you would not only create the projectile but also the list element, have constructor and destructor calls etc.).
creating an object means allocating space and probably a constructor call. now if youre also one of the people who dont use the initialization but do a lot of bla=x; in the constructor or do other work that can be quite expensive. same goes for destructor calls and deallocating memory.

using an array is pretty simple especially if you know that there will never be more than x elements. store pointers not objects, add new ones to the end and if you delete one copy the last element to fill the gap. if you use stl vector in addition you dont even have to worry about the size (but should still reserve enough memory in advance).

whenever its reasonable, allocate all the memory you need in advance and free it in the end.

you should see a difference even in a small game (though it wouldnt matter, because both would probably be more than fast enough)

Share this post


Link to post
Share on other sites
quote:
Original post by Trienco
and that one depends on how often you do it. use a list for a particle system or say projectiles of a minigun and you shouldnt be surprised if its slow as hell (you would not only create the projectile but also the list element, have constructor and destructor calls etc.).
creating an object means allocating space and probably a constructor call. now if youre also one of the people who dont use the initialization but do a lot of bla=x; in the constructor or do other work that can be quite expensive. same goes for destructor calls and deallocating memory.

using an array is pretty simple especially if you know that there will never be more than x elements. store pointers not objects, add new ones to the end and if you delete one copy the last element to fill the gap. if you use stl vector in addition you dont even have to worry about the size (but should still reserve enough memory in advance).


Umm, call me thick but I don''t see a problem using a list in this case. I mean, it would be a list of pointers which point to objects already created, so no constructor calls would be made when accessing the pointers. Just like when using an array like you said. Could you clarify a bit so that a thickskulled guy like me would understand.

Share this post


Link to post
Share on other sites
quote:
Original post by Dactylos
[quote]Original post by xjussix
quote:
Original post by Spacecat
(Note: in VC++ 6.0 it involves changing a setting in the project to activate ''RTTI information'')

Why does it have to be activated? Never knew this. Oh and where do I activate it?

It doesn''t have to be activated to use polymorphic classes. RTTI only needs to be activated if you use RTTI stuff (such as dynamic_cast, etc).

[edited by - Dactylos on December 4, 2002 10:33:47 AM]

Right, thank Dactylos for correcting me... In all my polymorphic class usages, the specializations would offer new function members and I''d constantly use dynamic_cast along with my polymorphic objects. Which is why I''ve always needed RTTI...

Anyway, how to activate it in VC++: Right-click on your project, enter the settings, [C/C++] tab, [C++ Language] category, you''ll have a checkbox for ''enable RTTI''.

Share this post


Link to post
Share on other sites
quote:

Umm, call me thick but I don't see a problem using a list in this case. I mean, it would be a list of pointers which point to objects already created, so no constructor calls would be made when accessing the pointers. Just like when using an array like you said. Could you clarify a bit so that a thickskulled guy like me would understand.



Linked lists are generally not very cache friendly. They use structs as nodes to store the pointer to the data and a pointer to the next (and previous in the case of a double linked list).

A naive implementation of a linked list would allocate these nodes whenever an element is added, and deallocate when it's removed. These nodes will be spread all over memory, and thus the processor can't cache blocks of elements.

More efficient implementations (like CList) allocate blocks of these nodes, so there are less allocations needed. When enough elements are removed to empty such a block, it's added to an internal list that keeps track of all unused blocks. This way it can be reused when you add more elements later, thus eventually avoiding any need for allocations (unless your list only becomes bigger and bigger).

These lists are perfectly fine for dynamic usage, where you add and remove (double linked) stuff a lot, but generally go through the list in a 'lineair' fashion to render all elements, or update AI, etc. A vector approach (with underlying array) would be better for stuff that uses a lot of random access.


[edited by - dynaguy on December 5, 2002 3:13:20 PM]

Share this post


Link to post
Share on other sites
usually games have an entity limit which means you can create an array

why arrays are easier to handle and you won t have problems with checking tons of pointers
you just check is it dead or not

Share this post


Link to post
Share on other sites
Basiror is correct, you don''t need linked lists for units, but when it comes to projectiles you are in trouble.

Say that you have an array the size of 255 (eg. csUnit units[255], this will work perfectly. But the problem here is when you deal with projectiles. If every unit fires a projectile or two you could have tons of them. So for projectiles I would reccomend double-linked lists. It makes searching projectiles easier, and as soon as a projectile hits it target or whatever, you just delete it.

Simple as pie.

I used it in my split-screen sample application in FFT (link in signature). Check out the latest code release. The information you''d want is specifically in the units.h/.cpp files.

These classes are of importance:
bProjectile
csProjectileTracker

and the struct L_LIST which is the double linked list itself.
(No I don''t use the STL)

-----------------------------
Final Frontier Trader
quote:
Original post by Dynaguy
Linked lists are generally not very cache friendly. They use structs as nodes to store the pointer to the data and a pointer to the next (and previous in the case of a double linked list).



Cache my ass. You won''t notice the difference. When flipping the primary and seconday buffer you sit there waiting for the monitor to catch up anyway (Unless you are doing some SERIOUS HEAVY CODE to fill up that time).

Share this post


Link to post
Share on other sites
quote:
Original post by granat
Cache my ass. You won''t notice the difference. When flipping the primary and seconday buffer you sit there waiting for the monitor to catch up anyway (Unless you are doing some SERIOUS HEAVY CODE to fill up that time).


hm.. so youre sending your render calls after telling your pc to switch buffers??

you can of course also use the stl vector for projectiles which will expand if you want to add more than fits. though i guess it would be better to have a little more overhead for lists every time than a big overhead whenever your vector reallocates a lot of memory and has to move all the data.

else you could do something like: with a max of 32 players and your fastest gun fires 100 projectiles a second that live for 0.1 second you would have a max of 320 projectiles.
or get the highest ratio with: rate of fire*live of projectile.. or just say 5000 should be enough or play it safe and use lists *ggg*

Share this post


Link to post
Share on other sites
So which is faster, STL Vector or a homemade linked list?

"To err is human, to really mess up requires a computer"

Share this post


Link to post
Share on other sites
quote:
Original post by Lukerd
So which is faster, STL Vector or a homemade linked list?



i should give my favorite answer to ''whats better/faster'' questions and say ''it depends'' *g*

usually i would suspect the vector to be faster. im not sure how much freedom an stl implementation has, but imagine a vector that would increase in size by only 1 if you add more elements than possible. or that you erase elements you dont need anymore. in that case a vector might be even slower, because you spend a lot of time reallocating more memory and moving stuff around.

and of course it depends on how optimized your list is. a simple list would allocate/free nodes all the time. the other approach sounded a bit like something between vector and list. in the end performance would depend on how you use your vector/list/whatever

Share this post


Link to post
Share on other sites

  • Advertisement