oooooooo
o o
o |-o---------|
o | o |
o | o |
o |-o---------|
o o
oooooooo
[Data structure] Best way to store game objects
Author
Hello everyone!
I'm currently writing a map editor and I need and efficient way to store my game objects and meets these criteria:
- Objects can be retrieved by their position on the map
- Objects can be retrieved by a point on the map (objects that intersect the point)
- The objects size on map isn't fixed (this affect the way objects are retrieved by their position/size)
- Object list can be traversed in order for rendering
I started toying with a red black tree which I think would be a good way to handle this however I realized that since the size of my objects isn't fixed, it will cause some problems. For example, I cannot simply start rendering objects at X pixels before the actual view position because an object that is located at 0,0 could cover the whole map. Then I thought that including all four corners of the object in the tree would fix it but the object would disappear if the object intersect with the view but none of the corners do.
You could store pointers to your objects in both a flat sequence (e.g. an array) and in some kind of tree structure.
When putting an object into a tree, if it lies on both sides of the split criteria, then add the pointer to both branches of the tree (i.e. the same pointer to exist in the tree multiple times).
If you want to execute some function on all objects (e.g. update) then you can iterate through the sequence. If you want to extract a visible set of objects (e.g. for rendering), then you can traverse the tree and remove any duplicate results when you're done.
To remove the duplicates you can do a few things:
1) As you traverse the tree, copy pointers of visible objects into an array.
Sort the array.
Then when iterating through the array, ignore any pointers that are the same as the previous array item.
2) As you traverse the tree, copy pointers of visible objects into a set.
Then iterate through the set.
3) An old-school technique used in Quake1's renderer was to simply traverse the tree calling Render on each visible item. To avoid calling render multiple times on the same object, each object recorded the frame-counter whenever it was rendered. If the recorded frame-counter is equal to the current frame-counter, then the call to render was ignored.
When putting an object into a tree, if it lies on both sides of the split criteria, then add the pointer to both branches of the tree (i.e. the same pointer to exist in the tree multiple times).
If you want to execute some function on all objects (e.g. update) then you can iterate through the sequence. If you want to extract a visible set of objects (e.g. for rendering), then you can traverse the tree and remove any duplicate results when you're done.
To remove the duplicates you can do a few things:
1) As you traverse the tree, copy pointers of visible objects into an array.
Sort the array.
Then when iterating through the array, ignore any pointers that are the same as the previous array item.
2) As you traverse the tree, copy pointers of visible objects into a set.
Then iterate through the set.
3) An old-school technique used in Quake1's renderer was to simply traverse the tree calling Render on each visible item. To avoid calling render multiple times on the same object, each object recorded the frame-counter whenever it was rendered. If the recorded frame-counter is equal to the current frame-counter, then the call to render was ignored.
Author
Sorry I took so long to reply, my job kept me real busy this week ;)
Thank you for your reply and the hindsight on Quake's renderer!
It's pretty much what I've done now. I implemented a red black tree but it also keep all the items in a linked list that I can use for rendering.
What I can't figure out how to use the tree sorting properties to efficiently do the object collision detection. Currently the only thing I can think that would make the tree somewhat useful is to know where to stop looking in my list. For example, let's say the user click at 40,30. I can search in my tree for the node that is immediately after that and traverse the list from the start to that node. I need to do that because any objects could cover the whole map. Performance for this would degrade as you go further down and to the right in the map and I don't like this.
Thank you!
-Roxy
Thank you for your reply and the hindsight on Quake's renderer!
It's pretty much what I've done now. I implemented a red black tree but it also keep all the items in a linked list that I can use for rendering.
What I can't figure out how to use the tree sorting properties to efficiently do the object collision detection. Currently the only thing I can think that would make the tree somewhat useful is to know where to stop looking in my list. For example, let's say the user click at 40,30. I can search in my tree for the node that is immediately after that and traverse the list from the start to that node. I need to do that because any objects could cover the whole map. Performance for this would degrade as you go further down and to the right in the map and I don't like this.
Thank you!
-Roxy
Collision detection is a different issue entirely. You could look into sweep and prune or some form of spatial partitioning.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
