Archived

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

Zeraan

Which is better? Array of classes or linked list?

Recommended Posts

In my game, I''m debating whether to use array of classes or linked lists for the asteroids. In the game, they get shot, and breaks apart into smaller asteroids (aka classic asteroids). Which is the best way to do this? The reason why I''m asking this is because I don''t know pointers and lists real well, so I don''t know if they will be useful in this game. Arrays, on the other hand, I know how to use, but its hard to deal with. If you say linked list, can you point me to a tutorial on it, or tell me how to use it?

Share this post


Link to post
Share on other sites
I''m not sure if this is the best idea, but you can use a combination of both.

Since the objects could break down into smaller pieces, you could try using an array of linked list. Each asteroid could be a linked list of classes. You could make the length of each linked list be 3, or 4, depending on how many times the asteroid can be broken down. Now each asteroid has its own space to be broken down into.

I''d explain it a bit more, but I have to run out for a half hour.

Share this post


Link to post
Share on other sites
Well if you dont know pointers and list very well then you might want to use an array, but on the other hand you could do the linked list way to teach yourself how to use them. But personally the way I would do it is something like: CAstroid Astroids[MAX_ASTROIDS]; with MAX_ASTROIDS being at like 50 or something, as I cant see having anymore than that on screen at once and then you would have like:
class CAstroid
{
bool Active; // can you see it on screen yet?
int Type; // eg, big (ones u start with), medium, small...
int x, y; // position
...
etc.
}

CEO Platoon Studios

Share this post


Link to post
Share on other sites
That array of linked lists makes the most sense and I think it will work better because I shoot 1 big asteroid, it breaks into 3 medium asteroids, but still linked to the first big asteroid, then I shoot one of the medium asteroids, and it breaks in some small asteroids, but those are linked to the 1 medium that I shot, and it is linked back to the big asteroid, when I shoot all of the asteroids in that list, that list get deleted, right?

Share this post


Link to post
Share on other sites
You could just use a single linked list. When one breaks up you reduce the size of that asteroid and add N more of the same size to the end of the list.

When asteroid->size=0 (destroyed) take it out of the linked list.

There''s no reason to group asteroids using an Array of linked lists.

Ben


IcarusIndie.com [ The Rabbit Hole | The Labyrinth | DevZone | Gang Wars | The Wall | Hosting | Dot Com ]

Share this post


Link to post
Share on other sites
I just did this not too long ago. What I did was make an array of CAsteroids[MAX] The thing is you don't want too create and destroy a bunch of asteroid objects so create them all at the beginning and just include an isactive variable (bool) in the class definition then you can set asteroids active and in active, init them to different sizes,velocities etc... and then set them to inactive when they get destroyed. When you need a to create some medium asteroids just search the array for !asteroid{i}.isactive(); and use that one. A linked list is way overkill for this.

EDIT: can't use square brackets for array index i.

[edited by - nonnus29 on July 27, 2002 9:29:52 PM]

Share this post


Link to post
Share on other sites
Use Vectors:
take a look at an example program using the vector class:

#include <iostream>
#include <vector>
int main()
{
vector example; //Vector to store integers
example.push_back(3); //Add 3 onto the vector
example.push_back(10); //Add 10 to the end
example.push_back(33); //Add 33 to the end
for(int x=0; x cout< if(!example.empty()) //Checks if empty
example.clear(); //Clears vector
vector another_vector; //Creates another vector to store integers
another_vector.push_back(10); //Adds to end of vector
example.push_back(10); //Same
if(example==another_vector) //To show testing equality
example.push_back(20);
example.switch(1, 2); //Switches elements 1 and 2
for(int y=0; y cout< return 0;
}
Hopefully you know have an idea that vectors are useful and somewhat easier to use than regular arrays. At the very least, they get around having to be resized constantly using new and delete. Furthermore, their immense flexibility - support for any datatype and support for automatic resizing when adding elements - and the other helpful included functions gives the clear advantages to arrays.


X4J

Share this post


Link to post
Share on other sites
I would like to learn about linked lists, so I want to do it with asteroids. Some of you use lists, but didn''t say how to do them. Is it like this?


  
class someClass {
int* nextClass;

...
} First, Last;

someClass Second = new;
First.nextClass = Second;
Second.nextClass = Last;
Last.nextClass = NULL;

//and when you remove a list do you do like this?


First.nextClass = Last;
delete Second;


If that''s not right, can you correct me (syntax, wrong method, etc)?




You know your game is in trouble when your AI says, in a calm, soothing voice, "I''m afraid I can''t let you do that, Dave"

Share this post


Link to post
Share on other sites
Function to create an asteroid pushes one onto the asteroid vector.
Upon being shot, 3 asteroids of smaller size are pushed onto the asteroid vector, and the previous one is erased.
Repeat process.

No fancy frills, just quick, plain, and simple (it works too ). Writing custom linked lists isn''t worth it (unless you''re really interested in coding like that), vectors are good.

------------
aud.vze.com - The Audacious Engine <-- It''s not much, yet. But it''s mine... my own... my preciousssss...
MSN: nmaster42@hotmail.com, AIM: LockePick42, ICQ: 74128155

Share this post


Link to post
Share on other sites
I don''t suggest using a vector here, since deletion is O(n) and you''re likely to be doing a lot of deletions.

With that said, tho, most of us are using processors over one gigahertz. You could create and delete millions of asteroids per second if you wanted to. So use whatever''s easiest for you.



Don''t listen to me. I''ve had too much coffee.

Share this post


Link to post
Share on other sites
Okay, thanks for that vector thing, but I really want to learn linked list, and I think asteroids is the way to do it. I will optimize later after I''ve finished the game, because if I optimize now, I will never finish the game. After I finish the asteroids, I will look up on vector. I never knew that it could be used in situation like this, and I didn''t even know that vector.h existed, only apvector for my AP class.



You know your game is in trouble when your AI says, in a calm, soothing voice, "I''m afraid I can''t let you do that, Dave"

Share this post


Link to post
Share on other sites
Don''t use the vector.h header, just use vector. No extension.

Different data structures vary mostly in how fast they are at performing operations like:
- add or remove an element at the beginning, middle, and end
- access an arbitrary element (in other words accessing the ith element)
They also differ in how much memory they use but unless you''re doing something outrageous it won''t be significant on a typical PC.

So figure out what operations you want to perform on your data and how often you''re going to perform them, then from that decide which data structure is best. If you''re deciding between vectors and lists...
- Lists are fast for adding and removing elements at the beginning, middle, or end. They''re slow for accessing arbitrary elements.
- Vectors are generally fast for adding elements to the end but are slow for adding to the middle or beginning. They''re fast for accessing arbitrary elements.

Share this post


Link to post
Share on other sites
Thanks for giving me that link, I''ll research terror tomorrow when I have time. Thanks!



You know your game is in trouble when your AI says, in a calm, soothing voice, "I''m afraid I can''t let you do that, Dave"

Share this post


Link to post
Share on other sites
sheesh i dont believe what im reading.

for all the people who said linked list:
why the hell would you use a linked list?- do you know how fragmented your memory is going to get. at the most your going to have 60-100 asteriods on screen at any given time(and evan thats streching it. 20 - 30 is more likely) unless your running a 2 meg machine or something your not going to have anything to worry about, just allocate the memory up front and forget about it, itll be alot faster.

Yes Linked Lists and STL vectors sound sexy and impressive, but you have to use the right tools for the right job, an array is the most efficient and approperiate solution. With Linked lists and vectors, not only will you spending extra time coding these exotic data structures your actually going to lower the performance of your app.





Twenty years from now you will be more disappointed by the things you didn''t do than by the ones you did. So throw off the bowlines, Sail away from the safe harbour. Catch the trade winds in your sails. Explore. Dream.
-Mark Twain

Share this post


Link to post
Share on other sites
quote:
Original post by yb legal

for all the people who said linked list:
why the hell would you use a linked list?- do you know how fragmented your memory is going to get. at the most your going to have 60-100 asteriods on screen at any given time(and evan thats streching it. 20 - 30 is more likely) unless your running a 2 meg machine or something your not going to have anything to worry about, just allocate the memory up front and forget about it, itll be alot faster.


You are obviously missing the point here. It is not about memory use - it is about management. He needs a way to iterate through those asteroids.
Also, in this case he will be doing frequent additions and deletions, and as has been pointed out earlier, deletions(and insertions anywhere but at the end) is an expensive operation for an array.
quote:

Yes Linked Lists and STL vectors sound sexy and impressive,


A statement leads me to think that you really dont know anything about them. Consider taking a basic course on datastructures and algorithms(or get a book).
quote:

but you have to use the right tools for the right job, an array is the most efficient and approperiate solution.


For all intents and purposes, an std::vector is equivalent to an array in terms of performance and usage patterns. There is normally no good reason to prefer a raw array over a std::vector. Raw arrays are frowned upon in ''proper'' C++.
quote:

With Linked lists and vectors, not only will you spending extra time coding these exotic data structures


No, you won''t. They are already written for you. #include <list>
quote:

your actually going to lower the performance of your app.


Why?


"I would defend the liberty of concenting adult creationists to practice whatever intellectual perversions they like in the privacy of their own homes; but it is also necessary to protect the young and innocent."
Arthur C Clarke

Share this post


Link to post
Share on other sites
quote:
sheesh i dont believe what im reading.

The irony of that post is hilarious

I would use either std::vector or std::list. Everything is already written, working, and robust, and performance is comparable to anything you can write yourself. If you do use the containers with pointers to memory though, you will still have to manage the memory those pointers point to.

Share this post


Link to post
Share on other sites
quote:
Original post by yb legal
do you know how fragmented your memory is going to get.


Barely fragmented at all. Do you actually know how STL allocators work? Have you ever actually used them? freed list node memory is reclaimed by STL.

Sorry to take a harsh tone, but your comment implies a fair amount of expertise, and its content belies that.



Don''t listen to me. I''ve had too much coffee.

Share this post


Link to post
Share on other sites
After studying your Terror.cpp, Terror.h, and Terrorclass.cpp, I made my own little program for making nodes and displaying them backwards and inputting data for each node. I am now confident enough to implement it into my game. Thanks so much! (Geez, its easy, or at least not as hard as I thought it would be.)



You know your game is in trouble when your AI says, in a calm, soothing voice, "I''m afraid I can''t let you do that, Dave"

Share this post


Link to post
Share on other sites
quote:
Original post by Arild Fines
You are obviously missing the point here. It is not about memory use - it is about management. He needs a way to iterate through those asteroids.


Are you suggesting that its not possible to iterate through an array? if so i would seriously considering getting some background knowledge before you post.

quote:

Also, in this case he will be doing frequent additions and deletions, and as has been pointed out earlier, deletions(and insertions anywhere but at the end) is an expensive operation for an array.



The very fact that one would evan consider adding and deleting ->_asteriods_<- dynamically shows that the given solution is an incorrect one, the fact the you help him to implement this shows your not exactly aware of the implications of such an action and have also misunderstood the goal, maybe you should take your own advice and get a book or something.

quote:

A statement leads me to think that you really dont know anything about them. Consider taking a basic course on datastructures and algorithms(or get a book).



wow great little attack, give yourself a pat on the back i can see alot of thought went into that.


quote:
Original post by Sneftel
Barely fragmented at all. Do you actually know how STL allocators work? Have you ever actually used them? freed list node memory is reclaimed by STL.

Sorry to take a harsh tone, but your comment implies a fair amount of expertise, and its content belies that.




Sorry to take a harsh tone, but your comments implies a fair amount of illiteracy.

If youd bothered to _read_ my post, youd know that was in reference to a linked list, the line was - "why the hell would you use a linked list?- do you know how fragmented your memory is going to get."



Any given asteriod is going to be on screen *appx* 2-5 seconds max, allocating them dynamically just is not worth it for such a small class so frequently.

you people seem to have the idea that because i choose not to use a linked list or STL vector in this situaton that i obviuosly dont know anything about them and bashing them for no good reason. This is false.

Heres the thing, knowing about them is one thing, knowing what situation to use them ,and just as important, knowing when _not_ to use them is where the real skill lies- this concept has obviously flown over many of your heads.

sure use an STL vector- just dont consider adding and deleting dynamically, and if youre not going to do that then you might as well use an array, considering hes already stated that he knows how to use them.

Try looking at the big picture rather than attemptimg to flex your programming muscles with approaches that are overkill, cuz you'll only impress the ignorant.








Twenty years from now you will be more disappointed by the things you didn't do than by the ones you did. So throw off the bowlines, Sail away from the safe harbour. Catch the trade winds in your sails. Explore. Dream.
-Mark Twain

[edited by - yb legal on July 30, 2002 5:19:09 AM]

Share this post


Link to post
Share on other sites
Linked lists work great and they''re perfect for what he needs to do.

"allocating them dynamically just is not worth it for such a small class so frequently."

He wants to learn how to use linked lists. Therefore it really doesn''t matter if it''s not practical for this situation.

He doesn''t need random access and there''s no law requiring you delete an entry in a linked list when it''s not needed. Adding a node to the end of a linked list is quick and easy.

Using a linked lists will allow him to do everything your array can do except he doesn''t have to guess how many asteroids he''s going to have on the screen at once before he compiles.

Lighten up.

Ben


IcarusIndie.com [ The Rabbit Hole | The Labyrinth | DevZone | Gang Wars | The Wall | Hosting | Dot Com ]

Share this post


Link to post
Share on other sites
"I am now confident enough to implement it into my game. Thanks so much! (Geez, its easy, or at least not as hard as I thought it would be.)"

No problem. I thought they were hard when I first used them, too.

Ben


IcarusIndie.com [ The Rabbit Hole | The Labyrinth | DevZone | Gang Wars | The Wall | Hosting | Dot Com ]

Share this post


Link to post
Share on other sites