Jump to content
  • Advertisement
Sign in to follow this  
Tarviathun

Object Management

This topic is 4973 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

As many of you know, I'm working on a 2D RTS engine in C++. I'm not using any specific API yet, as I'm coding it to be API independant via interface classes. Anyways, I come with a question that most likely has been asked before. My question is simple. What's the best way to manage dynamic objects? A little background first: My Object system is completely internalized and modular. The method by which dynamic objects move, is by way of an event system which handles itself. The F_Event functions are friends of the classes that they are meant to handle(such as an F_Event_Movement has an isPossible() that is a friend of F_Actor which can move). This allows for restrictions of the types of events that can be fed to specific classes. For instance, I cannot place an F_Event_Movement into a non-moving F_Object. Doing so would cause an error during compiling. What I need to know, is how do I organize the static and dynamic objects in my world? I can store all of them in a list, iterate through them and process all of their event queues. However, this is very inefficient for finding out where a specific unit is on the world map. On the other hand, I could store all the units in a world-sized matrix and iterate through the matrix tile-by-tile executing the events when I find a unit in the world. This is ineffiecent on two reasons a) I'm going through more loops than units and b) I might call a unit's EventQueue request several times(if a unit is larger than a tile). The method that I'm currently leaning towards, is a hybrid of the two: Have a matrix of lists(for multiple units on one tile) that hold pointers to objects in a list of all the objects in the world. That way, I get the best of both worlds: speed in iterating through them and speed in finding their locations. Additionally, if I use a list to store all of the units, I can easily add and remove units from the list with very little overhead. What do you guys think?

Share this post


Link to post
Share on other sites
Advertisement
I'm still messing around with map objects myself right now, but let me tell you what I've done so far.


First, I have an abstract class called MapObject. All the different objects inherit from this class. At this point, I have PlayerSprite, NPCSprite, StaticObject, and DynamicObject as my inheriting classes. (the difference between static and dynamic is that dynamic is composed of more than one frame).


I have a list of MapObject pointers that I have in my map class, allowing a map to have as many or as few objects as I'd like. When I update the state of the game, the first thing I do is call a sort function on that list, and I sort it by the y-coordinate that the objects are located at. The reason for this is that I want to draw my objects from top to bottom, so that objects can partially or fully be drawn over one another.


So when I'm drawing my objects, I start with the head of the list and I look at the y-coordinate, x-coordinate, object height, and object width to determine if any part of the object should be visible on the screen. I iterate through the entire list each time I draw a frame to find the objects that need to be drawn.



And that's as far as I've gotten. I have the infrastructure for the code there and I'm getting ready to implement this system in a few days. It's probably not the best object management system ever, but I've given it some thought and I think it will work out ok. I'm up for discussing a better methology or alternatives to this system if anyone has one. [smile]

Share this post


Link to post
Share on other sites
I wouldn't suggest sorting every frame. That's very VERY costly performance-wise. Try a presorted method, such as the matrix or a BTree.

Share this post


Link to post
Share on other sites
I haven't used this on a wide scale yet but my game objects belong to multiple lists at the same time. For example:

struct object
{
// for the big list that ALL items belong to
object *next_obj;
object *prev_obj;

// a list of objects this object contains
object *contents;
// a reference to the object that may contain it is usually helpful
object *container;

// the list parts we use for objects that are contained
object *obj_next_content;
object *obj_prev_content;
};

// a global instance of a list of objects
object *object_list = NULL;

// create a new object
object *new_object( ... some initializers if you want )
{
object *new_obj = new object;

// do the initialization etc.
// ...

// add it to the big list of objects
// should probably sort it right away by its location
// but this is a quick example
if ( object_list )
object_list->prev_obj = new_obj;

new_obj->next_obj = object_list;
object_list = new_object;

return new_obj;
}

// insert an object into another object
void object_to_object( object *container, object *item )
{
// sorting doesn't really matter for item contents
// unless you really need it

if ( container->contents )
container->contents->obj_prev_content = item;

item->obj_next_content = container->contents;
container->contents = item;

item->container = container;
}

// remove an object from a container
void object_from_object( object *container, object *item )
{
if ( container->contents == item )
{
container->contents = item->obj_next_content;
}

if ( item->obj_prev_content )
item->obj_prev_content->obj_next_content = item->obj_next_content;

if ( item->obj_next_content )
item->obj_next_content->obj_prev_content = item->obj_prev_content;

item->obj_next_content = NULL;
item->obj_prev_content = NULL;
}

// free an item from the world
void free_object( object *obj_free )
{
// does it belong to a container?
// if so remove it
if ( obj_free->container )
object_from_object( obj_free->container, obj_free );

// now remove it from he big list
if ( obj_free == object_list )
{
object_list = obj_free->next_obj;
}

if ( obj_free->prev_obj )
obj_free->prev_obj->next_obj = obj_free->obj_next;

if ( obj_free->next_obj )
obj_free->next_obj->prev_obj = obj_free->obj_prev;

delete obj_free;
obj_free = NULL;
}


obviously the STL comes in handy and wrapping this up into an object class is preferable but as this is more of a concept than actual useable code I think this shows what I am doing a little better.

Characters and items alike stem from a common base class whos objects belong to a large sorted render list. This is helpful because it is quite easy to pop things out of the list and push them back into it without caring what it actually is. Upon further reflection though, I have been pondernig having things contain render objects instead of being one although I am not sure of any useful performance gain.

Oh well, hopefully that helps out.

Share this post


Link to post
Share on other sites
Quote:
Original post by Tarviathun
I wouldn't suggest sorting every frame. That's very VERY costly performance-wise. Try a presorted method, such as the matrix or a BTree.



Hmm. I don't really agree with you. I'm not sure what the O notation for list.sort() is but for the sake of argument let's assume it's n*log(n). Also remember I'm using a list of pointers to objects, not the objects themselves. Let's say I have an average of 64 objects on a map. Then that would be O(64 * log64)) = 384, which isn't too gigantic. Besides, the time to draw the frame would be the real bottleneck I imagine. :p


Using a pre-sorted method would not work, because my objects (sprites for example) change their position and thus need to be re-sorted.


Like I said I'm sure my method is not the optimum one, but it's what I've come up with and it will work. If there are any better solutions out there I am eager to hear them. [smile]

Share this post


Link to post
Share on other sites
Quote:
Quote:
Original post by Tarviathun
I wouldn't suggest sorting every frame. That's very VERY costly performance-wise. Try a presorted method, such as the matrix or a BTree.

Hmm. I don't really agree with you. I'm not sure what the O notation for list.sort() is but for the sake of argument let's assume it's n*log(n). Also remember I'm using a list of pointers to objects, not the objects themselves. Let's say I have an average of 64 objects on a map. Then that would be O(64 * log64)) = 384, which isn't too gigantic. Besides, the time to draw the frame would be the real bottleneck I imagine. :p

Maybe I am arguing over wording here but sorting every FRAME is a waste of time especially if not all of the objects move every frame. Instead have the objects pop themselves from the list when they move and reinsert themselves based on their new position. This is really easy if you have a doubly linked list and perform a binary search from it's last location.

Share this post


Link to post
Share on other sites
This I would agree would be a better method. Having your list sorted on initialization, and then re-inserting objects as needed in the proper places. Maybe every x frames re-sorting the list to remove any errors.

That aside, the way I render my objects is have the object that needs to be rendered add an event to it's stack(changed from queue so that render call is always last) adding itself to the vector of lists(oriented towards depth. eg tiles are at index 0, ground objects at 1, aerial at 2, etc). So far, that's the method I've got on paper, nothing coded yet.

I'm still tackling how I'm going to organize my objects. Should I have a global list of F_Objects? Should I subdivide them into something else? The reason why I hestitate to implement your method evillive, is that this is going to be an RTS with(theoretically) hundreds of units on the screen. I need something that's good for managing large numbers of objects. Same thing for your method, Roots. I have to be very performance aware.

A thought that occured to me, would be implementing a list of all the world objects, and then have a list of pointers for active and non-active objects(which ones need to be updated on a frame-by-frame basis). Finally, have the object manager hold the tile matrix which defines movement, where objects can place themselves on tiles easily. This allows for a simple location lookup(the tile matrix) and priority in processing. Does this sound like a good method?

Share this post


Link to post
Share on other sites
Hmm, yeah I think that would probably work better actually. I could even set a flag between frames to indicate that a sprite or whatever has moved to a new tile/location and then make sure I only pop/insert those objects which have changed position. Thanks for the idea! [grin]


Quote:
Original post by Tarviathun
That aside, the way I render my objects is have the object that needs to be rendered add an event to it's stack(changed from queue so that render call is always last) adding itself to the vector of lists(oriented towards depth. eg tiles are at index 0, ground objects at 1, aerial at 2, etc). So far, that's the method I've got on paper, nothing coded yet.


I'm a little confused what you mean here. I understand the data structures, but you are you saying you're only adding events to the object's stack if that object is going to be rendered in the next frame drawn? You need to update all your objects whether they are drawn on the next frame or not, otherwise sprites and the like won't move around unless they are in the current frame, which would look weird. Maybe I'm misunderstanding you though.


Quote:
Original post by Tarviathun
I'm still tackling how I'm going to organize my objects. Should I have a global list of F_Objects? Should I subdivide them into something else? The reason why I hestitate to implement your method evillive, is that this is going to be an RTS with(theoretically) hundreds of units on the screen. I need something that's good for managing large numbers of objects. Same thing for your method, Roots. I have to be very performance aware.


Hmmm, well I'm not really sure of a better way to organize your objects. If I did, I would probably be doing that instead of the method I'm working on right now. Personally though, I stay away from global anything. The global namespace is a sacred entity, not to be adulterated with a bunch of global variables. =D


Quote:
Original post by Tarviathun
A thought that occured to me, would be implementing a list of all the world objects, and then have a list of pointers for active and non-active objects(which ones need to be updated on a frame-by-frame basis). Finally, have the object manager hold the tile matrix which defines movement, where objects can place themselves on tiles easily. This allows for a simple location lookup(the tile matrix) and priority in processing. Does this sound like a good method?


Again the whole "don't update an object if it's not on the screen" has to be taken with a grain of salt. I don't know the details of your game, but the only way I can think of implementing this type of "don't update what you don't see" is to keep a timer associated with each object, indicating the last time it was updated. Then when you are updating your on-screen objects, you look at that variable and compare it to the time of the current update, and based on that you update the object a certain number of times so it gives the "illusion" that it has been updating itself off-screen.

However, this has a critical fault in that an object that is off-screen can *NEVER* walk onto your screen by itself, you have to walk onto the object. And if you update the object X times, maybe the object has moved and now is in a different location, so you end up not drawing it after all, even though technically you should have seen it. Yeah, I really think it's a BAD idea to try and get by with only messing around with objects that are on-screen only.



Since your main problem seems to be having a large number of objects, I suggest you spend some time trying to think of ways in which you can reduce that number. For example, let's say you have a turrent which shoots a barrage of 5 missles out to a target. Instead of labeling each individual missle as an individual object, group them together into a "meta-object" so you only have to update a single object rather than 5.

Share this post


Link to post
Share on other sites
Since I'm in a long-winded mood ;-)

I thought I might briefly go over the "object-system" used in Morning's Wrath.

-Objects
worlds and such are broken down into a hiearchy

->Map :the map structure
-->Tile :the tile structure
--->Base :pointer to a ground structure (optionally null)
--->Overlays :pointers to ground structures (optionally empty)
--->Item :pointer to a sprite object (optionally null)
--->Character :pointer to a sprite object(optionally null)
--->UnderSprites :pointers to sprite objects(optionally empty)
--->OverSprites :pointers to sprite objects(optionally empty)
--->Structure :pointers to structure object(optionally null)

the three classifications of objects that can exist on a tile are,

Sprite - heavy,named,managed,animating,moving,(optionally subclassed)
Ground - lightweight,TileSet Pointer and Localized TileSet Cell
Structure - lightweight,TileSet Pointer, Localized TileSet Cell, Area (walls)
Displacement


-The Setup

It should be noted that MW has mutal exclusion for characters and structures on a single tile, this was done so that characters and structures would not have to be sorted, greatly improving performance.

The different storage slots on a tile, are used to define draw order,
e.g. grounds are drawn first, items always under characters, structures over all, etc.

this system, while it removes the need for such things as pixel perfect collision detection, complicates things such as motion, since a character cannot exist anywhere but in the center of a tile, while at rest, so it makes moving from tile to tile an 'atomic' type action, even thought it is done smoothly.

-Rendering


based on the camera position the 'looking-at' tile is determined, and then an
'action area' is computed from that center tile.

all tiles in the action area are then rect-tested against the screen

lights within range are also collected, and light values computed for each tile within the view

ground and tile overlays are drawn

then, all items, characters, structures, etc are rendered using the LORM rendering pattern taking into account object area displacement, then all are rendered.

hope that gives some insight lol, or not =)

Share this post


Link to post
Share on other sites
Roots:

I get what you're saying. I think what I'm getting at, are objects that are information data only, that don't change. For instance, a spawn point for the player is not going to change on a frame by frame basis, so it wouldn't need checked for change. A soldier unit, however, would need to be. His sprite would need to be updated, if he's moving his path needs to be updated, you get the idea. The difference between the two, say, is that the soldier would need to know where a tree is because it affects things such as movement and targetting, but the tree doesn't need to be checked for change. So, I get into the problem of figuring out where I need to put the tree and how I eleminate that overhead of checking that tree for change, because it's still in the object system.

Which is where the active/in-active dichotomy comes in. Basically, the objects that don't need to be updated are needed because their location affects dynamic objects' behavior. The location would be handled by the matrix, it'd be a quick lookup, and the overhead of checking those static objects would be eleminated by seperating it from those that do need to be updated. However, the problem remains of how do I store everything? To which the simplest answer would be in a single list that holds all objects in the world. The memory footprint could be decreased by using pointers and not copying anything, but organization-wise, the more things you add on the closer to hell my life gets.

A clarification on the confusing wording about how I render my objects, is that when they're updated, they put an event that adds themselves the renderer. This is handled last, because I don't want to render an object at (x,y) when in fact it's at (x+50, y+50). This is where the stack comes in. I don't know how many events I'm going to have per object, and I want the rendering event to be last. So, if I used a queue, I'd have to figure out when the object was done with everything, and then add the render event. However, with a stack, I don't need to worry about it because it's first in, last out. The depth of the objects is sorted by where it tells the renderer to add it, in the z-layer. The z-layer I was thinking of having sorted by a vector who indices start with ground and move upwards. Personally, I don't worry about if I render objects from left-to-right or top-to-bottom, because as long as they get rendered, everything's ok. They know their location and that's all the renderer needs to put them on the screen.

EDI:

I pretty much have the same system down on paper for rendering and setup. I just need to find out how they all interact, hehe. My approach to minimize the system hit, would be to organize all the objects in a manner where it's easy to find them. eg, have a matrix that holds their location, active vs non-active lists. I can render them once I know where they are and what they're doing by adding them to the renderer's queue, but I can't think of a decent way to make hundreds of units interact in a way that's not ridiculously inefficient.

BTW, what does rect-tested mean and what's your action area?

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!