Don Gunter | 7 Oct 2006 00:18

Extracting quad tree location codes from octree location codes

Hi J

Does anyone have a reference on a fast algorithm for extracting the (x,z) location codes from a linear octree, maybe using the SIMD commands?

Ummm, I’m generating a Quadtree index off an Octree and my implementation is a “tad” slow.

For the sample run, I’m iterating an array of linear Octree IDs and outputting an array of linear Quadtree IDs location codes of each object “on the ground”.

I chose a bit copy algorithm that basically strips every third bit starting at bit [1] but it’s slower than Christmas.

Makes the sim sluggish if I sample too often and stupid if I sample too little.

 

Regards,

Don Gunter

_______________________________________________
sweng-gamedev mailing list
sweng-gamedev <at> lists.midnightryder.com
http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryder.com
Don Gunter | 7 Oct 2006 00:28

ignore last correspondence, addressed to wrong group.

My apologies

_______________________________________________
sweng-gamedev mailing list
sweng-gamedev <at> lists.midnightryder.com
http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryder.com
Jamie Fristrom | 17 Oct 2006 02:30
Picon

strategies/patterns for composition

So - we've all heard "inheritance bad, composition good" - what I'd like to know is what are people's favorite strategies for composition, in particular with game entities/actors/pawns (or whatever your engine calls them)?

A few things I've seen done for entities in a game:

Inheritance - a particle system was an entity, a sound emitter was an entity, a billboard sprite was an entity, a limb was an entity.  Entities specified their position and orientation relative to other entities (or null for world-space), so you could "composite" (using the more general, English definition of 'composition' here) features by having them all parented to the same entity with a zero position and identity orientation. 

Textbook composition - entity contains a list of pointers to features which the entity may or may not have. Features could be meshes, particle systems, sound emitters, skeletons, and more.  This actually got kind of fat, since there were thousands and thousands of entities, so for performance there was a base entity that had just the few really popular features (like a mesh pointer) and an inherited entity that had many more.  Something it couldn't do that I imagine you might want is have more than one of the same kind of feature - multiple particle systems, emitters, etc.

A more relational database approach - the features were in tables and each feature had an "entity id" field.  So there was a position/orientation table, a mesh table, a sound emitter table, etc.  (So an ambient sound emitter wouldn't need a position/orientation, for example.) To find out which features a given entity had, you did queries on the tables looking for that entity's id.  I just heard about this system, I didn't actually work with it - it turned out to be slow so the results of the queries had to be cached.  But it could theoretically handle multiple features per entity.

Is there something better out there?  And if not, what's your favorite and why?

--
Jamie Fristrom - www.torpexgames.com - www.gamedevblog.com

_______________________________________________
sweng-gamedev mailing list
sweng-gamedev <at> lists.midnightryder.com
http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryder.com
Jon Watte | 17 Oct 2006 02:50

Re: strategies/patterns for composition

I've used two different kinds of composition, and I think it works 
pretty well. Both kinds used dynamic discovery of properties and 
capabilities, so you could have three particle systems if you wanted -- 
the base component array is un-typed.

You'll need some way of wiring outputs from some components into inputs 
of other components, and define what inputs/outputs to/from components 
are visible from outside the object. I've done this with a SQL database 
schema and custom editor, and with XML files.

In general, the way you build an object is that you add the components 
you need, and wire up the inputs and outputs, which implicitly creates 
per-object state. Each component is responsible for interacting with the 
appropriate subsystems -- any Mesh Renderer would integrate with the 
rendering system; any Physics Integrator would integrate with the 
physics and collision system; any Interactable would integrate with user 
input, etc. The renderer would read the "current position" and "current 
orientation" properties; the physics integrator would read the "thrust" 
property, run collision, and integrate to provide new values of "current 
position" and "current orientation"; etc. Typing the inputs and outputs 
helps. Making sure that the surrounding system does all the grunt-work, 
and writing components is simple, also helps.

You'll find that, early on, you'll have to write a new component kind 
for each kind of object you create, but after a while, you have enough 
components that mix-and-match with configuration will start to become a 
real possibility. How flexible it is depends largely on how much 
configuration you support in each component -- scripting hooks, or 
expressions/formulas in inputs/outputs/bindings help a lot. You'll also 
end up with a large number of "known names" which need to be reasonably 
managed in some name space. For example, a vehicle might tie its thrust 
to the input component from its riding player, so binding formulas like 
"me.player.forwardMovement" are needed -- and updating the dependency of 
this formula when the player gets on/off is important!

Anyway, there you have it. Building a good system like this becomes 
fairly object heavy (get a good allocator!) and requires a lot of 
perseverance, but I believe it has paid off for us. We haven't migrated 
all our legacy objects to this new system, but for the objects that are 
migrated, it's working great! (like our entire UI, and most interactable 
objects and weapons in the world)

Cheers,

          / h+

Jamie Fristrom wrote:
> So - we've all heard "inheritance bad, composition good" - what I'd 
> like to know is what are people's favorite strategies for composition, 
> in particular with game entities/actors/pawns (or whatever your engine 
> calls them)?
>
> A few things I've seen done for entities in a game:
>
> Inheritance - a particle system was an entity, a sound emitter was an 
> entity, a billboard sprite was an entity, a limb was an entity.  
> Entities specified their position and orientation relative to other 
> entities (or null for world-space), so you could "composite" (using 
> the more general, English definition of 'composition' here) features 
> by having them all parented to the same entity with a zero position 
> and identity orientation. 
>
> Textbook composition - entity contains a list of pointers to features 
> which the entity may or may not have. Features could be meshes, 
> particle systems, sound emitters, skeletons, and more.  This actually 
> got kind of fat, since there were thousands and thousands of entities, 
> so for performance there was a base entity that had just the few 
> really popular features (like a mesh pointer) and an inherited entity 
> that had many more.  Something it couldn't do that I imagine you might 
> want is have more than one of the same kind of feature - multiple 
> particle systems, emitters, etc.
>
> A more relational database approach - the features were in tables and 
> each feature had an "entity id" field.  So there was a 
> position/orientation table, a mesh table, a sound emitter table, etc.  
> (So an ambient sound emitter wouldn't need a position/orientation, for 
> example.) To find out which features a given entity had, you did 
> queries on the tables looking for that entity's id.  I just heard 
> about this system, I didn't actually work with it - it turned out to 
> be slow so the results of the queries had to be cached.  But it could 
> theoretically handle multiple features per entity.
>
> Is there something better out there?  And if not, what's your favorite 
> and why?
>
> -- 
> Jamie Fristrom - www.torpexgames.com <http://www.torpexgames.com> - 
> www.gamedevblog.com <http://www.gamedevblog.com>
> ------------------------------------------------------------------------
>
> _______________________________________________
> sweng-gamedev mailing list
> sweng-gamedev <at> lists.midnightryder.com
> http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryder.com
>   
_______________________________________________
sweng-gamedev mailing list
sweng-gamedev <at> lists.midnightryder.com
http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryder.com

David Sveningsson | 17 Oct 2006 02:50
Favicon

Re: strategies/patterns for composition

I usually use the so called textbook solution with pointers. An entity 
contains pointers to different representations, like graphical or physical.

The graphics subsystem maintains it's own list of the graphical 
representations (pawns as I call them) and doesn't know about about the 
physical representation and thus only knows what it have to know.

When creating a new entity I only instanciate the representations I need 
for the object.

I haven't tried to have multiple representations thought but I guess it 
would be possible by just adding an additional pointer in the entity.

-- 

//*David Sveningsson [eXt]*

Freelance coder | Game Development Student
http://sidvind.com

Jamie Fristrom skrev:
> So - we've all heard "inheritance bad, composition good" - what I'd like 
> to know is what are people's favorite strategies for composition, in 
> particular with game entities/actors/pawns (or whatever your engine 
> calls them)?
> 
> A few things I've seen done for entities in a game:
> 
> Inheritance - a particle system was an entity, a sound emitter was an 
> entity, a billboard sprite was an entity, a limb was an entity.  
> Entities specified their position and orientation relative to other 
> entities (or null for world-space), so you could "composite" (using the 
> more general, English definition of 'composition' here) features by 
> having them all parented to the same entity with a zero position and 
> identity orientation. 
> 
> Textbook composition - entity contains a list of pointers to features 
> which the entity may or may not have. Features could be meshes, particle 
> systems, sound emitters, skeletons, and more.  This actually got kind of 
> fat, since there were thousands and thousands of entities, so for 
> performance there was a base entity that had just the few really popular 
> features (like a mesh pointer) and an inherited entity that had many 
> more.  Something it couldn't do that I imagine you might want is have 
> more than one of the same kind of feature - multiple particle systems, 
> emitters, etc.
> 
> A more relational database approach - the features were in tables and 
> each feature had an "entity id" field.  So there was a 
> position/orientation table, a mesh table, a sound emitter table, etc.  
> (So an ambient sound emitter wouldn't need a position/orientation, for 
> example.) To find out which features a given entity had, you did queries 
> on the tables looking for that entity's id.  I just heard about this 
> system, I didn't actually work with it - it turned out to be slow so the 
> results of the queries had to be cached.  But it could theoretically 
> handle multiple features per entity.
> 
> Is there something better out there?  And if not, what's your favorite 
> and why?
> 
> -- 
> Jamie Fristrom - www.torpexgames.com <http://www.torpexgames.com> - 
> www.gamedevblog.com <http://www.gamedevblog.com>
> 
> 
> ------------------------------------------------------------------------
> 
> _______________________________________________
> sweng-gamedev mailing list
> sweng-gamedev <at> lists.midnightryder.com
> http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryder.com

_______________________________________________
sweng-gamedev mailing list
sweng-gamedev <at> lists.midnightryder.com
http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryder.com

Nathan Martz | 17 Oct 2006 05:02
Favicon

Re: strategies/patterns for composition

We use a pretty textbook implementation, too, where an "entity" is basically an array of pointers to
components (all of the base class type). Some types of components are very popular (i.e. transform,
damageable), so entities also cache a handful of direct pointers to the most commonly accessed component
types. We shied away from the relational database approach (which I believe Thief used), largely because
it's counterintuitive and a bit cumbersome but also because our model makes it easy to spend a little
memory to get much faster component-on-entity lookups.

After much discussion, we opted to allow only one instance of each type (direct descendent) of component
per entity. In this way, our system is a bit like dynamic multiple inheritance. In the end, the decision
came down to favoring clarity and simplicity over flexibility. While it makes some sense to have multiple
sound emitter components per entity, it's not clear what it means to have multiple physics components
(does it imply some sort of intra-entity transform hierarchy?). It also means that you never have to worry
about getting an array of components back from your Entity::GetComponent() function and other such
syntactical niceities. In our model, if you want to have an entity with multiple lights (like a car with two
headlights), you would have one entity for the car and one entity for each light, usually with a component
on the main entity that has references to the two child enti
 ties (in our case, it would be the vehicle physics component).

As in David's system, our entities are a fairly high level "gameplay" concept. Our heavy duty, lower level
systems like rendering, audio, physics, and pathfinding don't know anything about components or
entities. For those systems, the components usually serve to publish data about a specific entity to the
relevant subsystem (i.e. CoRender tells the renderer what mesh to uses the relevant data from the
CoTransform on the same entity). It's a nice division that lets the game systems be fairly
general/flexible without impeding the lower level systems' ability to operate efficiently.

We differ from the system Jon Watte describes in that we have no formal representation of component
dependencies or inputs/outputs. There's no way to generically connect the float of one attribute to the
float of another, but we haven't found that sort of flexibility to be particularly helpful or necessary.
Components simply access properties of other components as necessary (though we actively discourage
unnecessary dependencies). Soft dependencies are handled gracefully if the component doesn't exist,
hard dependencies usually fire off an assert as soon as possible, which is fine, since it's not clear how,
say, an AI component should respond if it's transform was suddenly removed. Tick order is "hard coded,"
but there's a lot of complexity about exactly when and how to use multiple processors, which would be hard
to represent generically with or without components.

One of the issues we've run into with our component model is deciding what should be a component and what
should not be. Part of the problem is a tendency for programmers (especially ones new to the idea) to
over-componentize their systems (like adding a new component when a bool on an existing component would
have sufficed or requiring a component to request that the sound system play a sound). Appropriate
granularity is also a challenge; it's sometimes unclear when a given feature set should be composed of one
component or several. We've developed a few good rules of thumb (avoid bi-directional dependencies,
don't create components just to hold a bit of data, etc), but it's fair to say that we spend a non-zero amount
of time refactoring components as we learn more about the game and how it's parts relate to one another.

Some examples of types of components in our codebase:
 * Team membership
 * Health/Damage responses
 * Weaponness
 * Various sorts of physics
 * Controller (AI or player)
 * Various sorts or renderables
 * Skeletal animation

-Nathan

-----Original Message-----
From: sweng-gamedev-bounces <at> lists.midnightryder.com
[mailto:sweng-gamedev-bounces <at> lists.midnightryder.com]On Behalf Of David
Sveningsson
Sent: Monday, October 16, 2006 5:50 PM
To: sweng-gamedev <at> midnightryder.com
Subject: Re: [Sweng-gamedev] strategies/patterns for composition

I usually use the so called textbook solution with pointers. An entity 
contains pointers to different representations, like graphical or physical.

The graphics subsystem maintains it's own list of the graphical 
representations (pawns as I call them) and doesn't know about about the 
physical representation and thus only knows what it have to know.

When creating a new entity I only instanciate the representations I need 
for the object.

I haven't tried to have multiple representations thought but I guess it 
would be possible by just adding an additional pointer in the entity.

-- 

//*David Sveningsson [eXt]*

Freelance coder | Game Development Student
http://sidvind.com

Jamie Fristrom skrev:
> So - we've all heard "inheritance bad, composition good" - what I'd like 
> to know is what are people's favorite strategies for composition, in 
> particular with game entities/actors/pawns (or whatever your engine 
> calls them)?
> 
> A few things I've seen done for entities in a game:
> 
> Inheritance - a particle system was an entity, a sound emitter was an 
> entity, a billboard sprite was an entity, a limb was an entity.  
> Entities specified their position and orientation relative to other 
> entities (or null for world-space), so you could "composite" (using the 
> more general, English definition of 'composition' here) features by 
> having them all parented to the same entity with a zero position and 
> identity orientation. 
> 
> Textbook composition - entity contains a list of pointers to features 
> which the entity may or may not have. Features could be meshes, particle 
> systems, sound emitters, skeletons, and more.  This actually got kind of 
> fat, since there were thousands and thousands of entities, so for 
> performance there was a base entity that had just the few really popular 
> features (like a mesh pointer) and an inherited entity that had many 
> more.  Something it couldn't do that I imagine you might want is have 
> more than one of the same kind of feature - multiple particle systems, 
> emitters, etc.
> 
> A more relational database approach - the features were in tables and 
> each feature had an "entity id" field.  So there was a 
> position/orientation table, a mesh table, a sound emitter table, etc.  
> (So an ambient sound emitter wouldn't need a position/orientation, for 
> example.) To find out which features a given entity had, you did queries 
> on the tables looking for that entity's id.  I just heard about this 
> system, I didn't actually work with it - it turned out to be slow so the 
> results of the queries had to be cached.  But it could theoretically 
> handle multiple features per entity.
> 
> Is there something better out there?  And if not, what's your favorite 
> and why?
> 
> -- 
> Jamie Fristrom - www.torpexgames.com <http://www.torpexgames.com> - 
> www.gamedevblog.com <http://www.gamedevblog.com>
> 
> 
> ------------------------------------------------------------------------
> 
> _______________________________________________
> sweng-gamedev mailing list
> sweng-gamedev <at> lists.midnightryder.com
> http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryder.com

_______________________________________________
sweng-gamedev mailing list
sweng-gamedev <at> lists.midnightryder.com
http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryder.com
_______________________________________________
sweng-gamedev mailing list
sweng-gamedev <at> lists.midnightryder.com
http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryder.com

Paul Sinnett | 17 Oct 2006 07:08
Picon

Re: strategies/patterns for composition

On Mon, 2006-10-16 at 17:30 -0700, Jamie Fristrom wrote:
> So - we've all heard "inheritance bad, composition good" - what I'd
> like to know is what are people's favorite strategies for composition,
> in particular with game entities/actors/pawns (or whatever your engine
> calls them)? 

Jamie,

Have you read Mick West's Inner Product column "Evolve your hierarchy"
in the March 2006 issue of Game Developer? It's more an overview of the
subject than a specific implementation recipe but it might illuminate
some areas.

I suggested using such a system on a recent project but initially there
was a lot of resistance. Later, we adopted components for collision and
AI which worked fairly well. I expect some of those team members will
expand on that in future projects.

The way we implemented it was the table / database approach you
outlined. For example, objects that needed collision had a collision
object. But when they were created, the collision object was added to a
collision world. So rather than having a single collection of all
objects in the game we had a collection for each behavioural aspect. The
main loop wasn't a sequence of loops through a master entity list, but a
single loop through a sequence of component specific lists. That way we
didn't have to query because the list itself was the cached result set.

It wasn't really as neat as that since it evolved as we went along - but
that was what it was evolving into as far as I can tell. We actually had
collision pointers in the entity too although we didn't really need them
as it turned out.

_______________________________________________
sweng-gamedev mailing list
sweng-gamedev <at> lists.midnightryder.com
http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryder.com

cruise | 17 Oct 2006 12:57

Re: strategies/patterns for composition

Thus spake Jamie Fristrom...
> A more relational database approach - the features were in tables and 
> each feature had an "entity id" field.  So there was a 
> position/orientation table, a mesh table, a sound emitter table, etc.  
> (So an ambient sound emitter wouldn't need a position/orientation, for 
> example.) To find out which features a given entity had, you did queries 
> on the tables looking for that entity's id.  I just heard about this 
> system, I didn't actually work with it - it turned out to be slow so the 
> results of the queries had to be cached.  But it could theoretically 
> handle multiple features per entity.

I'm currently using this system in a MUD I'm developing. Admittedly, 
that means my performance constraints aren't as tight, so I'm not sure 
how much of my experience is useful...

I'm actually using a predicate database (thanks to Jon Blow for the 
idea), which seems to suit the kind of relationships well, and allows me 
to easily grab all location components, all components of an entity, or 
the type of a given component. Component inheritance is handled with 
inference rules in the database.

The component entry in the database can be an actual value for simple 
types (location, player name, etc.), or a pointer to a class for more 
heavyweight components (like player input or AI). That's probably 
overkill for more real-time games, but it depends on your query 
efficiency, I imagine. One advantage is it makes concurrent thread 
access easier, since all edits and reads have one entry-point.

Since I'm using the database for lots of other things anyway (player 
inventory, etc.) it made sense to use it for this also. YMMV.
_______________________________________________
sweng-gamedev mailing list
sweng-gamedev <at> lists.midnightryder.com
http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryder.com

Jamie Fristrom | 17 Oct 2006 21:05
Picon

Re: sweng-gamedev Digest, Vol 13, Issue 2

I've used two different kinds of composition, and I think it works
pretty well. Both kinds used dynamic discovery of properties and
capabilities, so you could have three particle systems if you wanted --
the base component array is un-typed.

You'll need some way of wiring outputs from some components into inputs
of other components, and define what inputs/outputs to/from components
are visible from outside the object. I've done this with a SQL database
schema and custom editor, and with XML files.

In general, the way you build an object is that you add the components
you need, and wire up the inputs and outputs, which implicitly creates
per-object state. Each component is responsible for interacting with the
appropriate subsystems -- any Mesh Renderer would integrate with the
rendering system; any Physics Integrator would integrate with the
physics and collision system; any Interactable would integrate with user
input, etc. The renderer would read the "current position" and "current
orientation" properties; the physics integrator would read the "thrust"
property, run collision, and integrate to provide new values of "current
position" and "current orientation"; etc. Typing the inputs and outputs
helps. Making sure that the surrounding system does all the grunt-work,
and writing components is simple, also helps.


Sounds interesting - but I'm not sure I grok it.  Is there a pre-existing book/paper/pattern I could look at? 
What would you say the advantages of such a system are?  The decoupling is nice - anything beyond that?

Pseudocode might look something like this?  Am I totally misunderstanding?

class Component
{
   ComponentGuts* myGuts;
   list<Output> outputs;
   list<pair<Component*,int>> inputs;  // input is an index into another components outputs
   virtual void Update() { myGuts->Update();}
};

class ComponentGuts
{
   // abstract base class for all components - defines fundamental input/output/linkage concepts, maybe something like:
   virtual void Update();
   Component* me;  // link back to owner
};

class ThingThatMovesInAStraightLine: public ComponentGuts
{
  Vector3 pos;
  Vector3 v;
  ThingThatMovesInAStraightLine( Component* me, vector3 _v, Vector3 _pos ) : ComponentGuts(me)
  {    
         pos = _pos;
         v = _v;
         me->outputs.push_back( &start );
   }
  virtual void Update() { pos = pos + v;  }
};

class MeshRenderer : public ComponentGuts
{
  Mesh m;
  MeshRenderer( Component* me, Mesh _m ) : ComponentGuts(me)
  {
  }

  Draw( )
  {
    // set world transform to first input
    graphics.SetWorld( me->inputs[0] );
    graphics.DrawMesh ( m );
  }
};

void CreateThingy()
{
  // this would later be handled by processing SQL or XML or whatever
  ThingThatMovesInAStraightLine t(...);
  MeshRenderer m(...);
  m.inputs.push_back( &t, 0 );  // hooks up t's output to m's input
}


_______________________________________________
sweng-gamedev mailing list
sweng-gamedev <at> lists.midnightryder.com
http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryder.com
Jon Watte | 17 Oct 2006 22:38

fine-grained component-based object models


Jamie Fristrom wrote:
> Sounds interesting - but I'm not sure I grok it.  Is there a 
> pre-existing book/paper/pattern I could look at? 
> What would you say the advantages of such a system are?  The 
> decoupling is nice - anything beyond that?
>

I don't know of any book or paper -- we spent a fair bit on research 
coming up with the specifics.

Some benefits are:
- new kinds of objects can be created through component assembly, rather 
than programming
- because all data dependencies are known, a globally efficient step 
order can be created
- because all data dependencies are known, EVERYTHING is (or can be) 
"live re-load"
- the data model interfaces very nicely with a networking model
- less bugs related to data dependencies, because that functionality is 
centralized into a single place that can be debugged once

The "entity" class is a system class that you don't necessarily derive 
from, and the components are attached to this entity in some order, 
based on configuration data. There are multiple phases: creation, 
attachment, data wiring, and actual operation. Components go through 
their parent entity to get to other parts of the entity; if a component 
needs a specific kind of reference, it can declare such as need (i e, 
one kind of input would be "a peer component" and it would be bound to 
the expression "find a component implementing rendering in the list of 
components of my parent").

One draw-back is the difficulty of debugging complex, data-driven 
systems, as there is no good debugger concept for those things. Good 
inspection tools are necessary. Another draw-back is the amount of 
effort required to actually implement and optimize such a system until 
it performs well from a runtime point of view. The last draw-back is 
that it's a new way of thinking, which makes it take longer to bring new 
people up on the system.

All in all, I think it's worth it. Our entire GUI, as well as all the 
data items you might want in a GUI are expressed in this system. Writing 
any kind of UI is very simple in this case. Most of the rest of the 
system is also exposed through the global application namespace, 
although not all of the system has been ported to be implemented in 
terms of these components.

Cheers,

          / h+

_______________________________________________
sweng-gamedev mailing list
sweng-gamedev <at> lists.midnightryder.com
http://lists.midnightryder.com/listinfo.cgi/sweng-gamedev-midnightryder.com


Gmane