RE: [Algorithms] "Entity" data structures
Brought to you by:
vexxed72
From: Davies S. <SD...@uk...> - 2002-04-03 11:12:34
|
>>There are a *ton* of cool data-driven tricks that the artists were able to put together in Halo just through objects, their properties, functions and >> attachments, and how they relate to each other. Ok, I'll bite - this sort of artist-side manipulation as a game-engine feature seems crucial to creating interesting levels, and is something I've never quite managed to find a nice structure for... Can you give us an example of one of these 'tricks' as food for thought? Cheers Sean -----Original Message----- From: Chris Butcher (BUNGIE) [mailto:cbu...@mi...] Sent: 02 April 2002 19:14 To: gda...@li... Subject: RE: [Algorithms] "Entity" data structures I guess I'd like to weigh in with an argument on the other side of the scales. We have an 'object' hierarchy which is basically what you're calling entities (although we do it all with C rather than C++ so we can do some rather scandalous memory hacking). We used a two-structure approach where there's a small fixed-size header stored in an array that then refers to a variable-size block of memory stored in a pool. You should consider that objects within the same class may differ in sizes (based on number of animating nodes that a character must store quaternions for, or things like that), and it might be useful for you to specify that objects can never change size once created. In our game the topmost level of this hierarchy is used for tracking position, orientation, velocity, game information like health, a system for physically attaching objects to other objects, a system for evaluating functions and attaching objects' output functions to other objects' inputs, and the interface to our world subdivision scheme. The advantages of thinking this through early on can't be overstated. There are a *ton* of cool data-driven tricks that the artists were able to put together in Halo just through objects, their properties, functions and attachments, and how they relate to each other. An example of a wrinkle to think out beforehand would be: you probably need position, velocity, etc at the top level so that things like AI have a single interface for querying objects about their state, but you almost certainly will want multiple different movers and collision resolvers for each class of game entity. So you can put the generic object state data at the top level and put the physics-model-specific stuff (torque, inertia, angular momentum) in a lower level where it's used. Another example: think very carefully about whether you ever want to actually instantiate entities of the base classes (like a generic object). We found that it was much simpler to enforce the rule that you could only ever instantiate a leaf class. So if you wanted a "simple" generic object, you had to make a child of the base class that didn't include any additional values or behavior. I'd also comment that the total number of classes of entities will vary based on your game. I don't know what game Jack is working on or how many entity classes they have, but we had eleven leaf classes in Halo and things would have been much easier if we'd specialised more. -- Chris Butcher AI Engineer | Halo Bungie Studios bu...@bu... <mailto:bu...@bu...> -----Original Message----- From: Jack Mathews [mailto:ja...@re...] Sent: Monday, April 01, 2002 12:50 To: gda...@li... Subject: RE: [Algorithms] "Entity" data structures Sounds very over complicated. "Entity" type class structures are one of the good things for C++ - style inheritance models. Add the fact that realistically you won't have all THAT many entities in the game and just make a base class of entity, then things like "physics entities" off of that, and a mechanism for querying the type. No need for multiple hash tables and all of that mumbo jumbo, just make it easy to program and easy for other people to manipulate. Managing entity structures is nothing compared to the game logic you apply to them, the rendering you do of them, et cetera. So don't bog yourself down with worrying much about little things like that. Honestly, the only things you really need to worry about are fast lookup and fast type determination. Jack -----Original Message----- From: Aaron Drew [mailto:ri...@ho...] Sent: Monday, March 25, 2002 6:29 AM To: gda...@li... Subject: [Algorithms] "Entity" data structures I've been busy coding away at my first ever 3D engine and I'm not faced with the task of putting it all together in some reasonably logical form. I've got collision detection, physics (both an in-the-works rigid body system and a simpler frictionless, angular-momentumless version), graphics, pathing, and AI systems. All of these systems have been designed to be as modular as possible. All systems use "handles" to refer to objects and currently use hash tables internally to find object data based on a handle. The interfaces exposed are very minimal. For example, the collision interface takes queries and returns a pointer to a list of colliding pairs. Collision granularity can be specified (eg. stop at the object-object level or descend down to tri-tri level), etc. My concern comes from the fact that each module stores some identical redundant data internally. Position and orientation are the culprits I'm mainly worried about. I guess this is a typical access problem. I mean, the physics system will need to modify the position of bodies under motion, meaning that updating the objects transform in the physics code will require me to also update the transform data that is used by pathing, AI, collision and graphics and the same for each of those other cases. I've been thinking about writing an "Entity" class to store just this information but then I realised other things might be required for game logic such as access to velocity (how hard did I hit the ground?), what is my current 'best path', etc. My latest thought that I wanted to run past the list was to create essentially a small database with a set of core fields (position and orientation, indexed by some arbitrary handle) and a set of additional fields that can be added at run-time, stored in parallel hash tables (also keyed by handle). Shared data such as velocity, game-logic states and collision states would sit in this structure, providing a centralised repository that any one module can modify. Does this sound reasonable? (This is a PC title so I thought the resulting memory access patterns would be good enough) I know Pierre and some others seem to prefer callback functions to get data to prevent duplicate storage. Are there any practical 'gotchas' that I should know about? |