Sign in to follow this  
godmodder

Datastructures in C++ for games

Recommended Posts

Hello, I've been programming games and normal applications in C++ for quite some time now and I was wondering what would be the best way to represent certain datastructures specific to games? I'm talking, in particular, of datastructures that hold vertices, indices, room data etc... Most of the online articles and C++ books I've read say I should always use STL types like std::vector in preference to classic arrays. But it seems a bit overkill and weird (and maybe slow) to use such methods for an application in which every frame counts. What's your opinion on this matter? Jeroen

Share this post


Link to post
Share on other sites
Well in all honesty that depends on what your useing say for a 3d game instead of useing vectors you can just use .. Say if you were useing Direct 3D .. a matrix to store a rooms data and just transform that into the display matrix now i don't know alot about Direct 3D but as far as im aware fo thats a good way to go if you can understand it ;p..

It may help other pepole trying to answer your question if you say what your trying to acomplish and what language and what lib's you are useing

Regards jouei.

Share this post


Link to post
Share on other sites
Quote:
Original post by godmodder
What's your opinion on this matter?

Seems a bit half-baked. In what way do you think std::vector is overkill for a particular situation? In what way do you think it's weird for a particular situation? In what way do you think it's slow for a particular situation?

Share this post


Link to post
Share on other sites
Quote:
In what way do you think std::vector is overkill for a particular situation? In what way do you think it's weird for a particular situation? In what way do you think it's slow for a particular situation?


Well for example, all the API functions accept the vertex buffer as an array. The vertex buffer will not change size frequently (not in my app anyway). I mean, why use a vector or any other container for it? Why not just dump it all in a big array? All the sources I've read from suggest I should always favor the STL containers above classic arrays, but it just seems more of a hassle for these simple things.

Jeroen

Share this post


Link to post
Share on other sites
The basic reason for using a vector over manually managing an array is that using a vector makes it easier to avoid things like memory leaks, double deletion and other similar kinds of problems.

Share this post


Link to post
Share on other sites
a std::vector is, at it's root, a big array (all elements are guaranteed to be contiguous in memory). so you can use it happy-dappy in the api calls and get all the benefits of STL protections

-me

Share this post


Link to post
Share on other sites
If I wrapped the array around in a RAII class, wouldn't that essentially have the same effect?

Now that I think of it, another problem is multidimensional arrays. Say for example I have a room structure which contains several tiles. The room has a width, height and depth, so a multidimensional array seems very intuitive here. How would I go about and achieve the same easy method with a std::vector and why would I even want to do that?

Edit: Palidine, I did not know that. I guess that removes one of the restrictions. However, are you SURE they are always contiguous in memory?

Jeroen

Share this post


Link to post
Share on other sites
Contiguous storage in a vector is guaranteed in section 23.2.4 paragraph 1 of ISO/IEC 14882:2003.

Share this post


Link to post
Share on other sites
Quote:
If I wrapped the array around in a RAII class, wouldn't that essentially have the same effect?

Yeah, so why reinvent the wheel?

Quote:
Now that I think of it, another problem is multidimensional arrays. Say for example I have a room structure which contains several tiles. The room has a width, height and depth, so a multidimensional array seems very intuitive here. How would I go about and achieve the same easy method with a std::vector


std::vector< std::vector< int> > theRoom;
theRoom[x][y] = blah;

And if you don't like the template notation, just typedef it:

typedef std::vector< std::vector< int> > Room;
Room theRoom;
theRoom[x][y] = blah;

Quote:
and why would I even want to do that?

As mentioned before, because it is safer than using a dynamic array built from a raw pointer.

Quote:
Edit: Palidine, I did not know that. I guess that removes one of the restrictions. However, are you SURE they are always contiguous in memory?

According to the standard:
Quote:
"The elements of a vector are stored contiguously, meaning that if v is a vector<T, Allocator> where T is some type other than bool, then it obeys the identity &v[n] == &v[0] + n for all 0 <= n < v.size()."


In other words, yes.

Share this post


Link to post
Share on other sites
Quote:
Original post by godmodder
If I wrapped the array around in a RAII class, wouldn't that essentially have the same effect?


More or less, but you'd have to write it yourself, and you'd lose the benefit of the existing research done into std::vector's implementation. In particular, the way std::vectors resize is clever but not especially intuitive, and there is also generally some tricky stuff done with placement new to avoid needless initialization of unused memory space.

Quote:
Now that I think of it, another problem is multidimensional arrays. Say for example I have a room structure which contains several tiles. The room has a width, height and depth, so a multidimensional array seems very intuitive here. How would I go about and achieve the same easy method with a std::vector and why would I even want to do that?


You wouldn't (unless you're a masochist); you'd use boost::multi_array, which provides that kind of element access into a std::vector-like memory allocation. You'd want it because you could defer specifying the array dimensions to runtime, and also resize (and even "reshape") the array.

Share this post


Link to post
Share on other sites
Quote:
Original post by CodeMunkie
std::vector< std::vector< int> > theRoom;
theRoom[x][y] = blah;


Nesting vectors loses the contiguous-memory guarantee (between "rows"), compounds the potential for wasting space (a vector that doubles in size with each resizing might average 6N + 12 bytes of used space for N integers; a vector of vectors would then cost 9N^2 + 18N + 12 bytes to store N^2 integers) and loses the guarantee of rectangularity (each "row" can be resized independantly, so you have to add logic to keep the lengths in sync, and you are throwing away flexibility after explicitly asking for it). Just use boost::multi_array.

Share this post


Link to post
Share on other sites
Quote:
Original post by Zahlman
Quote:
Original post by CodeMunkie
std::vector< std::vector< int> > theRoom;
theRoom[x][y] = blah;


Nesting vectors loses the contiguous-memory guarantee (between "rows"), compounds the potential for wasting space (a vector that doubles in size with each resizing might average 6N + 12 bytes of used space for N integers; a vector of vectors would then cost 9N^2 + 18N + 12 bytes to store N^2 integers) and loses the guarantee of rectangularity (each "row" can be resized independantly, so you have to add logic to keep the lengths in sync, and you are throwing away flexibility after explicitly asking for it). Just use boost::multi_array.


Agreed, I just wanted to show that it was possible to use std::vector in this way. But multi_array is a much better solution.

Share this post


Link to post
Share on other sites
Ok, so the boost library really seems the way to go. I must admit I haven't got any experience with it, but everybody keeps saying it's really good so I'm willing to give it a try. I'm going to use the multi_array for the multidimensional data. Now another question: in my app, there is a "level" class that consists out of several rooms with lot's of data. The rooms contain quite a bit of data, so I really can't create them on the stack or I would get an overflow very soon. So I must create these objects on the heap. My idea was to use a vector of pointers to the rooms. Since I'm going to use the boost library anyway, I will also use smart pointers for each of these rooms. Is this a good approach?

Now that I think of it, this would totally free me from having to do any manual new and delete's. Being mostly a C guy, this admittedly feels a little weird. Is there any situation where you still have to use new and delete explicitely or do I always have to use smart pointers?

Jeroen

Share this post


Link to post
Share on other sites
Quote:
Original post by godmodder
Ok, so the boost library really seems the way to go. I must admit I haven't got any experience with it, but everybody keeps saying it's really good so I'm willing to give it a try. I'm going to use the multi_array for the multidimensional data. Now another question: in my app, there is a "level" class that consists out of several rooms with lot's of data. The rooms contain quite a bit of data, so I really can't create them on the stack or I would get an overflow very soon. So I must create these objects on the heap. My idea was to use a vector of pointers to the rooms. Since I'm going to use the boost library anyway, I will also use smart pointers for each of these rooms. Is this a good approach?


The vector already puts its contents onto the heap. (It has to make a dynamic allocation in order for resizing to work.) Just make a vector of Rooms, for normal cases.

The two main exceptions are: (a) Rooms are polymorphic somehow, and (b) Rooms can be shared between Levels. In both of these cases, you need some indirection (i.e. smart pointers) because in (a), the derived classes can't "fit" into a vector of base class instances, and in (b), if you gave each level a copy, and you changed one, its copy would not be updated, so you'd have a nightmare of trying to keep things in sync, while also wasting huge amounts of memory.

Quote:
Now that I think of it, this would totally free me from having to do any manual new and delete's. Being mostly a C guy, this admittedly feels a little weird. Is there any situation where you still have to use new and delete explicitely or do I always have to use smart pointers?


You never really have to do anything in particular. ;) But modern, proper C++ usually involves writing 'new' very rarely, and 'delete' even more rarely. (The reason there is an imbalance is because you sometimes need to do the dynamic instantiation yourself for an object whose "ownership" will be "transferred" to a smart pointer; it does the delete, but it can't do the new, because it doesn't know what parameters to pass to the constructor.)

As for feeling weird... most modern programming practices will feel weird to people who are most accustomed to C. But, you know, Occam's razor suggests that it's not "everyone else" who's weird, it's you. ;) When you stop seeing explicit memory management as a tool (exactly what kind of flexibility are you gaining, in practice, anyway?), and start seeing it as the burden that it is, you will be enlightened.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this