Vectors and graphics general ?'s

[sblass92]

I was just wondering in general the limitations of having moving-game objects stored inside a vector. I was experimenting with general physics where each ball/particle is a class that contains directions and magnitudes of velocity and position. Increasing the number of particles means increasing the iterations of the for loop that updates their position. Is there a better way to organize multiple objects than a vector?

Another question on the efficiency of bitmap drawings: I'm not very advanced in graphics, I've been double-buffering the screen re-draws so far, and clearing the buffer before each draw. To maintain the background I store it as a bitmap in the game and redraw the bitmap to the buffer before drawing the 'moving' parts. Is there a better way to keep a background, and have moving parts re-drawn? What about objects that have the potential to move, but currently aren't? This method means they'll have to be redrawn regardless of movement. General improvement suggestions?

Thanks!

Edit: I use Dev-C++, and the Allegro library

[jwenting]

The best data structure to use depends on how you're going to use it.
Some have fast insertion but slow retrieval, others may have slow insert but fast retrieval.
Then again, retrieval speed will be different depending on whether you're doing sequential or random acccess of elements.

[sblass92]

I initially chose the vector because i'd be able to cycle through every particle and update it, order of the particles wasn't relevant b/c it had to go through all of them, and any additional ones could just be inserted at the end. deleting elements would take longer b/c it would have to re-copy the data, right? is there a breaking point (with x items) where sequential access is faster with one structure or another, or will one structure always be the best at something regardless of number of elements or size of elements?

[jwenting]

Sounds like what you really want is a single linked list.
That's fast for insert and iteration, slow for delete.

[emilo35]

Sounds like what you really want is a single linked list.
That's fast for insert and iteration, slow for delete.

Well, why not a double-linked list then? Requires just a little more memory, but that shouldn't be a problem in the long run. This way deletion is just as fast as insertion.

As for the main question of this thread, I have the same problems. Although I don't have a solid answer to your question, my reasoning goes like this;

- If all your moving objects fit into the screen at all times, storing everything in a vector and iterating over the entire vector is a good solution, since you still have to look at every object in order to find out where to draw them

- If objects leave the screen you don't want to draw them, and therefore you want to skip iterating over them to save time. My theoretical solution to this is to store the objects in a search tree structure, where the keys are which X- and Y-block of the level the object is in. Now, based on the coordinates of your camera, you should be able to find the sub-tree containing the blocks that are currently visible on the screen, and iterate over the elements there. Whenever an object leaves a block, you have to reinsert it into the tree.

I haven't tried this out yet, but with large quantities of objects scattered over a large area, like a space-flying game, this method may be faster. Some optimization has to be done, like determining the height/width of every block.

Best of luck to you!
Emil Olofsson

[jwenting]

double linked list is slower for insert and delete and uses more memory.
It's only really preferable over a single linked list if you desire iteration in both directions.

[mrnutty]

double linked list is slower for insert and delete and uses more memory.
It's only really preferable over a single linked list if you desire iteration in both directions.

Double Linked list has O(1) insertion and deletion, while
a single linked list, has O(n) insertions and deletions.
A double linked list does not use that much more memory than a single linked list, in a small scale size list. If the memory used by a double linked list is a problem, then you shouldn't be even using a list.

A double list is usually more preferable over single linked list, but there are special cases as always.

[jwenting]

you're talking about random inserts and deletes, I'm talking about inserts and deletes only at the end of the list.
That's faster for single linked list as there's less to do (if you keep a pointer to the last element of course so you don't have to traverse the entire list to get to the last element) :)

[emilo35]

Yeah, I figured since it is a game we're talking about here, you never know which object you may wish to remove :)

Emil Olofsson

[jwenting]

he was talking about iterating over the structure and "clearing the buffer", so I assumed a simple loop iteration and bulk delete from the data structure, therefore no random access.

[sblass92]

Thanks for your help guys!
@Emil, I really like that idea of that search tree, and it seems like it could also be adapted to searching for objects with 0 acceleration and then taking those out of the calculation loop.

And for that, a linked list would definitely be preferred. I guess I discounted a list for cycling out of habit of using arrays, but when it comes down to it:

currentLink = currentLink ->nextLink;
vs.
currentItem = (addressStart + element_i*sizeOfItem);

Thanks again