How to efficiently manage the game world?! (Objects, I mean.)
Author
I'm making a game using OpenGL with C++, and I was thinking about a good way to manage 'everything'. I need some opinions on the current scheme I came up with:
Every interactive class gets its own list of objects (I'm using the vector class). New or created objects will get pushed into it. When an object needs to interact with another (say for collision detection), it will simply perform a check in one of its method with the entire list. The class of objects it needs to perform certain events with will be specified by some kind of setCollisionTargets() or something. The main loop will call the events (methods) for every list from top to bottom.
How viable is this? Is there a common and better way?
What your sort of describing is the functionality behind Quad/OcTrees. For an OcTree, what you have is axis aligned bounding boxes that split the world up. Each Box contains 8 other boxes, and each one of those 8 more, and so on. Within each of those boxes, there is a list (vector) of items. An item can be in more then one box.
So when you start doing some collision detection, you can limit your math to only the items in the axis aligned box. This cuts down your calculations and increases performance greatly. There are other types of scene management structures such as BSP trees, KD Trees, etc. that have different strengths and weaknesses. I suggest that you look into this and see if its what you are looking for, and if you are daring, try implementing them.
So when you start doing some collision detection, you can limit your math to only the items in the axis aligned box. This cuts down your calculations and increases performance greatly. There are other types of scene management structures such as BSP trees, KD Trees, etc. that have different strengths and weaknesses. I suggest that you look into this and see if its what you are looking for, and if you are daring, try implementing them.
Author
I guess that's basically what I needed to know. It is a major part of a game right (management-wise)?
Plus, by "An item can be in more then one box." you mean objects of the same class? Thanks.
Plus, by "An item can be in more then one box." you mean objects of the same class? Thanks.
Thats correct. When I say "an item", what I really mean is a general Object. An OcTree is comprised of these objects and only acts on those objects. If you have anything special, such as a model of a teapot, you can derive its class from this object class. The OcTree does not need to know that an object is a Tea Pot, or a Tea Cup or anything else. Therefore a tea cup and tea pot collision is just two objects colliding, according to the OcTree. Mind you, the OcTree is not designed to do collision detection and response, thats the job of a different piece of code. The OcTree just tells you what is in one, relatively small space.
Further more, you can couple this with collisions with a Frustum. This sort of check can determine what is rendered to the screen. Things that are in the Frustum can be seen by the camera and may be rendered.
There is more to it, but this is a quick overview.
Further more, you can couple this with collisions with a Frustum. This sort of check can determine what is rendered to the screen. Things that are in the Frustum can be seen by the camera and may be rendered.
There is more to it, but this is a quick overview.
For collision detection it shouldn't matter what sort of data structure you store your objects in; they all have relative performance vs simplicity merits but your collision response code has no reason to care about that.
If you use a vector for your data structure you have a nice and easy way to manage your objects; the problems occur when you have many many objects in that vector then detecting collisions between all of them will have O(n2) complexity thus it scales very badly.
More complex data structures scale much better, e.g. quad/oc trees, but they're harder to manage.
Regardless, you separate the data structure from the algorithms by way of the visitor pattern. Your objects don't search through the vector/octree themselves, instead a CollisionVisitor will do that. It iterates through all the objects looking for any that intersect. After this your collision response code can do whatever it needs to.
In a simple game, probably only the objects themselves can know what they need to do upon colliding (the player dies for example), so something like this will work:
object1->collideWith(object2);
or
collide(object1, object2);
Of course, you might want something more sophisticated along the lines of an event system where collision-listeners will respond to collision events instead.
If you use a vector for your data structure you have a nice and easy way to manage your objects; the problems occur when you have many many objects in that vector then detecting collisions between all of them will have O(n2) complexity thus it scales very badly.
More complex data structures scale much better, e.g. quad/oc trees, but they're harder to manage.
Regardless, you separate the data structure from the algorithms by way of the visitor pattern. Your objects don't search through the vector/octree themselves, instead a CollisionVisitor will do that. It iterates through all the objects looking for any that intersect. After this your collision response code can do whatever it needs to.
In a simple game, probably only the objects themselves can know what they need to do upon colliding (the player dies for example), so something like this will work:
object1->collideWith(object2);
or
collide(object1, object2);
Of course, you might want something more sophisticated along the lines of an event system where collision-listeners will respond to collision events instead.
Author
Thanks guys, it's been helpful.
About the OcTree though, I know what it's meant to do and how it goes about it, but I'm kind of having difficulty understanding exactly where to start and how to implement it in the game.
So...
1. It's a static set of points that divide up the space but up to which depth?
2. Each node has a bounding box and an associated list to tell exactly which objects are present in it? (Should require dynamic casting of some sort.)
3. Objects have a way to find out which volume it is in thus check for collision (or other stuff) with the node's list?
So basically you need to identify which box you're in and then check against the items. I'm just having trouble deciding how it should relate to the actual tree traversal.
@dmatter:
Does the CollisionVisitor actually reduce the number of calculations? Because if the objects themselves check for collision then the complexity seems to be the same. But I think I see how it would help in a bigger, more complex game.
Thanks again :)
About the OcTree though, I know what it's meant to do and how it goes about it, but I'm kind of having difficulty understanding exactly where to start and how to implement it in the game.
So...
1. It's a static set of points that divide up the space but up to which depth?
2. Each node has a bounding box and an associated list to tell exactly which objects are present in it? (Should require dynamic casting of some sort.)
3. Objects have a way to find out which volume it is in thus check for collision (or other stuff) with the node's list?
So basically you need to identify which box you're in and then check against the items. I'm just having trouble deciding how it should relate to the actual tree traversal.
@dmatter:
Does the CollisionVisitor actually reduce the number of calculations? Because if the objects themselves check for collision then the complexity seems to be the same. But I think I see how it would help in a bigger, more complex game.
Thanks again :)
Quote:Original post by glopen
1. It's a static set of points that divide up the space but up to which depth?
You can either pick an arbitrary depth or keep subidividing until you're hitting X-amount of entities in a leaf.
Quote:2. Each node has a bounding box and an associated list to tell exactly which objects are present in it? (Should require dynamic casting of some sort.)
Yes, but I don't think casts will be necessary.
Quote:3. Objects have a way to find out which volume it is in thus check for collision (or other stuff) with the node's list?
Objects shouldn't be searching through the data structure that they are contained in; that would be the job of the visitor. The objects could invoke the visitor themselves though.
Quote:So basically you need to identify which box you're in and then check against the items. I'm just having trouble deciding how it should relate to the actual tree traversal.
The visitor handles the traversal and it can handle the collision detection (although knowing whether two objects collide might only be available to the objects themselves).
Quote:Does the CollisionVisitor actually reduce the number of calculations? Because if the objects themselves check for collision then the complexity seems to be the same. But I think I see how it would help in a bigger, more complex game.
Nah, the visitor doesn't reduce the complexity; it reduces coupling and separates concerns - OO stuff.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
