There''s been lots of talk on the STL recently, and it''s got me thinking... I am about to implement map functions in my game, and I''m gonna make linked lists for the enemies and powerups and stuff. I have two questions about that. 1) I have made a linked list before, and I would love to use the STL to deal with it this time around, but is it really fast enough? Or should I integrate it into the structs for the enemies and powerups? I''m kind of worried about using the STL, because I wouldn''t think it would be fast enough for a main loop thing, would it? 2) Should I even bother with linked lists? In the game, I am going to know how many enemies and powerups there are in the level, and new ones are never going to be created until I load a new level, so would it be worth it to make a linked list or should I just use dynamically allocated arrays? I know that would waste memory, but is the memory a good sacrifice for the speed of using arrays? Thanks ----------------------------- "And I write and I write and I don't believe it's gonna change today" - From Yellow Ledbetter by Pearl Jam http://www.crosswinds.net/~uselessknowledge

Your second question concerning memory for speed is really dependant upon the target audience you are trying to reach and their average system size, and the size of the tradeoff. How many nodes are you talking about? If the array has thousands of nodes then it might be better to linked list it with possible a b-tree index on it. If the array is rather small then use arrays. Is your game already constraining memory in other areas for the target audience? If so use linked lists or optimize other areas of your code. There are many answers and the best thing I can tell you is to try it and see. From there you will be able to make a more informed decision.

As for STL, I have not used it because I can code linked lists in my sleep. I found the bit class to be confusing and have pretty much dismissed it from use in my game. I have been told that the algorithms for traversal and searching are general purpose algorithms which may or may not mean it is slow for your purpose. My rule of thumb has been that for large lists, use something more specific in purpose and implement your own. For small things you will probably not realize a speed difference for the progamming time you put into it. My last thought on the whole STL thing is that if your lists are going to use a tun of memory then STL doesn''t provide a way to manage the heap memory under NT and is not suitable. Please correct me if I am wrong here because this is the main reason why I am not going to STL.

Kressilac

I have used STL before but only for very generic(textbook) linked_lists, queues, etc... Like kressilac said, the algorithms are very general, so if there is any kind of special processing you do, or if your data set is large, it''s usually beneficial to roll your own. As for your specific case, if your amount of items is fixed for each level and there are not a ton of them, I would prob. use a dynamic array allocated at the level load time. HTH

Joe

Some of us are wondering what STL is, could you explain?

STL is the Standard Template Library, a set of C++ classes that ship with most compilers. STL was created in an attempt to ship C++ with a set of standard data storage (and other) algorithms. The advantage of STL is that it is already written - and known to work, so you avoid many of the "hey, I need a linked list quickly for this little piece of data" problems that can easily lead to memory leaks, etc. The disadvantage, as mentioned above, is that its very general - and by definition not optimized for an individual''s specific needs. STL is great for writing business apps, I''m not sure about it for high-performance games - especially not for linked lists and similar, which are really pretty easy to code properly anyway.

The other disadvantage of STL is that it supplies a crutch that can stop people from learning the efficient/correct way of doing things; using prewritten linked lists, for example, tends to reduce one''s knowledge of how a linked list works!

> if your lists are going to use a tun of memory then STL
> doesn''t provide a way to manage the heap memory under NT
> and is not suitable.

Not true. In general, there are "reserve" commands that you can use to reserve space for large amounts of items.

I agree with what Bracket''s point - it''s good to know how to do it "by hand" before you start to use STL... and IMO some of the STL classes are a bit weak (string, for instance)... but in general, STL is the way to go.

If you don''t know what STL is, fear not, I''ve got a new article 1/2way done that explains it.



Mason McCuskey
Spin Studios - home of Quaternion, 2000 GDC Indie Games Fest Finalist!
www.spin-studios.com