Archived

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

Monder

Organising Game data

Recommended Posts

Every game I''ve made just has a simple array, vector or linked list that holds pointers to different object classes which are then looped through every frame and then draw( ) and update( ) are called or a draw and update message is then sent to the object. All objects are indexed by their posistion in the list/vector/array How does everybody else do it?

Share this post


Link to post
Share on other sites
quote:
Original post by Monder
Every game I''ve made just has a simple array, vector or linked list that holds pointers to different object classes which are then looped through every frame and then draw( ) and update( ) are called or a draw and update message is then sent to the object. All objects are indexed by their posistion in the list/vector/array

How does everybody else do it?


Exact same way (linked list). Although I also have a 2d array representing the map which, for every tile, has a list of pointers to all game objects that are on that tile.

That''s just to make sure everything gets drawn in the right order (2d game).

Share this post


Link to post
Share on other sites
Yeah I''m considering using some kind of tree based stucture with messages being sent down from the root node. So for example the game would send a draw command to the root node and this would filter down into all the other nodes

Share this post


Link to post
Share on other sites
I''ve been considering using an AVL binary tree to hold the info for the objects in my game that need to be tested for collision. I figure if I add objects to the tree and keep them sorted by their x coordinate, I can treat collision as a kind of binary search. The only problems are that I''d have to create a new tree every time I update the objects so as to represent their new x coordinates, and I''d also have to find some efficient way of containing objects that have the same x coordinate.

What do you guys think? Is it worth it, or is there a better way of doing what I''m describing? (this is for a 2d game)

Share this post


Link to post
Share on other sites
In the game Widelands, which works similar to Settlers 2, we''ve got a 2D array representing the map. Every "tile" of the map has a linked list of objects that are on it. Additionally, every object has a unique id (serial number) for cross-object references. A global hash is used to lookup objects by serial number.

We never loop through all objects. When drawing the map, we simply visit all tiles that are currently visible and draw the objects on them.
Since the world in Widelands is discrete, there''s no need to update an object''s movement every frame. Instead, there''s a global priority queue of events that will call callback functions. Objects can register events such as "reached the next position" etc. While an object is moving from one field to the next nothing is actually done per frame. The on-screen position of the object is simply interpolated between the start and end point.

cu,
Prefect

Share this post


Link to post
Share on other sites
The list method works as long as the # of objects is small, but sooner or later you need some other method of organizing data for fast access. I don''t recommend the AVL tree that someone mentioned, because building it everytime something moves would destroy performance. I suggest some kind of partitioning like a quadtree so you can easily cull objects that arn''t on the screen. Also, you might want to keep an "active" list of objects that need to be updated even when they are off the screen. If you want to get fancy, you could try two lists for updating, one list updates the usual way, and the other does a cut down version that is faster for objects that aren''t on the screen. Basically, just play around with it and do performance tests. Start simple, and add complexity only if it needs it. It doesn''t make sense to spend time on doubling performance when you already get 300fps.

Share this post


Link to post
Share on other sites
quote:
Original post by Pseudo
building it everytime something moves would destroy performance...
I suggest some kind of partitioning like a quadtree so you can easily cull objects that arn''t on the screen.



This makes perfect sense if all or most of the objects in the tree don''t move. But if you have a quadtree of mostly moving objects wouldn''t you still have to rebuild the tree when they all move anyway?

Share this post


Link to post
Share on other sites