GroZZleR

Hey all,

Thanks to all of your suggestions from previous topics, I'm finally 'working on the game' sort of speak. My final (or near final) hurdle is in the controlling and creation of entities. Game entities need to be able to think (what's around me Should I get out of it's way ), update (move based on your velocity), collide (whoops I hit something), create other entities (I'm shootin' mah gun!) and render themselves.

Every problem is easy to handle individually:

Think: Can be performed inside the Update method.
Update: Entity.Update()
Collide: Run through all the entities, do some culling of what's obviously too far away, and check the rest.
Spawn: EntityFactory.Create(typeof(Bullet))
Render: Entity.Render()

Combined, however, it begins to pose a problem.

Think: How do the entities know what other entities are around them
Update: Something has to tell them to update.
Collide: The entities can't just run through the entire list of other entities, something has to do this check for them.
Spawn: As long as they can access the factory, they can create more entities.
Render: Something has to sort them for rendering.

So you need some sort of EntityManager - but EntityManager doesn't know how to sort them for rendering, so you need a Scene object. But wait, the collision map for the world probably isn't an entity - so now they need to know about the world that they're living in.

How the heck do you add an entity to 3 different managers that the entity is oblivious too (except perhaps world) to let it live its little life of reacting, moving, colliding and rendering

Anyone have insights How do you do it


Re: XNA Game Studio Express Entities: Think, Update, Create, Collide, Render -- Stumped!

X-Tatic

The answer is what is called a SceneGraph.

A Scene Graph generally stores entities in a spatial tree (geometrically, with bounding volumes).

With these trees you can determine collision, determine rendering (distance/frustum culling), sort for depth (i.e objects with transparency).

Examples of spatial trees would be:

Quadtree

Octree

BSP

KD-Tree

Good luck, you probably have some reading to do.






Re: XNA Game Studio Express Entities: Think, Update, Create, Collide, Render -- Stumped!

GroZZleR

Thanks for the response and the push in the right direction - a Quadtree is definitely going to do the job here. I just have a couple of clarifications after reading up:

1 - Where do you store the objects
Do you store the object in the node that it fits entirely in Or do you store it in EVERY node that it fits in For example: Do I always add the object to the root, then see what other nodes it's touching, and add it there

2 - What's an effective method of finding other objects
Let's say my HomingMissile object is looking for objects near it to smash into. What's a good way of getting all the objects around it My guess is you define a box with the size you want to look in - then ask the quadtree for a list of objects from nodes that are touching that box. If you're right in the middle, then you're going to get a list of objects from every single node - I suppose that's one of the worst case scenario's however.

Thanks for the clarification guys.





Re: XNA Game Studio Express Entities: Think, Update, Create, Collide, Render -- Stumped!

X-Tatic

1) There are many hybrid methods you can use, but classically you would store object references only in the leaves (the smallest nodes, having no children). You have to get a good balance between leaf size, tree depth, and object size. If leaves are too small, objects will be spready across too many leaf nodes. If leaves are too big, you wont be seperating the world enough, and your results could contain too many references. Also another problem is, if the leaf nodes are too small compared to the root, you can have too many levels in the tree, which could mean far too many checks in the worst case scenario, so much so that checking all the nodes is slower than just rendering etc.

2) The guess is a good one, but not quite accurate. The idea is, check missiles bounding box intersection with root, if it inersects, check its first child, if it intersects, check that nodes first child, all the way until it either does intersect, or you find a leaf. If it stops intersecting, you continue with the second child of the top level, etc. When you do find a leaf, you make a list of all objects it contains. After that you can do sorting on it, or whatever you need. This is also how you would build a list of things to render with frustum culling, except you check with a bounding frustum, instead of a bounding box.






Re: XNA Game Studio Express Entities: Think, Update, Create, Collide, Render -- Stumped!

GroZZleR

Thanks X-Tatic.

Your answer to #1 is just a tad bit confusing, I'd like some clarification if you don't mind -- You're saying only store objects in the leaf nodes BUT store multiple copies in all the leaf nodes that it's touching So if you're in a region of overlap, you have references of the object stored in 2 (or 4) different leaf nodes





Re: XNA Game Studio Express Entities: Think, Update, Create, Collide, Render -- Stumped!

Fluxtah

Well I can only give advice on the many articles and books I have read, I have only implemented an octree but I have been reading about both for a year or so!

If an object straddles any of the dividing planes of a node you can insert it into multiple child nodes, or just insert it right there in the current node. If inserting into multiple nodes, when it comes to render, you would need some sort of flag so you dont render it twice.

 

 





Re: XNA Game Studio Express Entities: Think, Update, Create, Collide, Render -- Stumped!

GroZZleR

Sorry, I have one more question.  You guys have been an enormous help and I hate to bug you over and over.

What do you do when objects move   Do you just remove the entire thing from a tree then re-add it   Or is there a better way to shuffle objects that are already inside the tree   It would seem if you keep removing / adding them, that's going to become slow and costly.





Re: XNA Game Studio Express Entities: Think, Update, Create, Collide, Render -- Stumped!

Fluxtah

I am not sure about this one actually I have only been dealing with static objects, I would guess that you can either re-insert it every frame (but as you mentioned this would be costly), or if you keep a reference to parent node, maybe you could do re-insert into the parent node.

Move object
1. Do I fit into this node
2. No - check parents node (back to step 1), Yes step 3
3. re-insert here (recurse insert)

I am just speculating here so take my advice with a pinch of salt! (I need to figure out this problem to at some point :) )






Re: XNA Game Studio Express Entities: Think, Update, Create, Collide, Render -- Stumped!

X-Tatic

Yes, Fluxtah's response is what I was going to say, except dont store it in the parent node. Recurse back up to the tree until you find a node that fully encompasses the objects bounds. Then recurse down adding it to appropriate leaves. In most cases you will only have to go up one level, instead of recursing the entire tree.




Re: XNA Game Studio Express Entities: Think, Update, Create, Collide, Render -- Stumped!

Fluxtah

I thought thats what my step 1 - 3 suggested :) exactly that.



Re: XNA Game Studio Express Entities: Think, Update, Create, Collide, Render -- Stumped!

X-Tatic

Fluxtah wrote:
I thought thats what my step 1 - 3 suggested :) exactly that.

Ah yes it was :)

I just saw the 'recurse insert' in brackets.






Re: XNA Game Studio Express Entities: Think, Update, Create, Collide, Render -- Stumped!

Leaf.

You might also be interested in "Loose Octrees" by Thatcher Ulrich. Its basically an octree with overlapping cells that enables quicker insertions.

Cheers,
Leaf.