is there a name for this type of data structure?

Started by
16 comments, last by Norman Barrows 9 years, 4 months ago

The "interface with Update/Render methods" pattern is often called a "game object" or a "game entity".

i figured someone had already come up with a fancy name for a "list object".


IMHO, having a larger number of smaller, more homogeneous lists of self contained objects (or 'systems' of objects), combined with a more complex main loop in which the flow of data and control is explicit and easy to follow, is a far, far superior approach.

yes. this is how i do things.

i have lots of lists:

* meshes, textures, models, wavs, animations - all are stored in list type databases.

* timers, the render queue, and probably many other things in the Z gamedev library are lists.

* terrain chunks are lists of renderables.

* the chunk list is a list of lists! <g>.

* players, monsters, missiles, dropped objects, inventories, NPC stats - all are lists.

* cloud, rain, and snow particle systems are also lists.

i think you get the idea.

i've often considered "one big list" for player, targets, and projectiles, but have never actually tried it. many small lists specific to their tasks seems to make things simpler.

in all the games i've done, i've always used a separate list for each type of thing in the game. however i do tend to treat explosions (particle emitters) as projectiles, rather than having a separate list of explosions. sometimes i'll include the player as target #0 in the targets list and then have additional player data in another data structure, which lets me use some target code (such as collision checks) for the player as well. but i usually keep the player as a separate data structure (IE a list with one entry). In the case of Caveman, the player can control a whole band, like a household in The SIMs, so there's a true list for band members.

as you say, you get a lot of control that way, as far as what happens when.

Norm Barrows

Rockland Software Productions

"Building PC games since 1989"

rocklandsoftware.net

PLAY CAVEMAN NOW!

http://rocklandsoftware.net/beta.php

Advertisement

IMHO, having a larger number of smaller, more homogeneous lists of self contained objects (or 'systems' of objects), combined with a more complex main loop in which the flow of data and control is explicit and easy to follow, is a far, far superior approach.

I read something similar a few weeks ago: ,,Take a look, for example, at the work on OGRE version 2.0: Matias Goldberg, the mastermind behind that endeavor, chose to store data in big, homogenous arrays, and have functions that iterate over whole arrays as opposed to working on only one datum, in order to speed up Ogre." http://gamedevelopment.tutsplus.com/articles/what-is-data-oriented-game-engine-design--cms-21052

I am totally agree with this concept. Though I am really newbie in game development, I can clearly see the benefits of a design like that.


this leads to an abstract data type (a data structure + methods) such as a list, along with the render and update methods to operate on objects in the list and / or on the entire list.

Couldn't this be considered the "visitor pattern"?.


You end up with silly bugs, like sometimes your homing missiles are targeting a position that lags by one frame, because you're unable to ensure that all movement logic has completed before executing targeting logic... You become cursed to watch, helplessly, as your co-workers expand the interface to include PreUpdate, PostUpdate... PostPostUpdate... to work around such bugs

What if you double-buffer your modifications of game data so that all changes don't take effect until after 1 complete iteration through all objects?

What if you implement a system where each change to the underlying interfaces requires an investment of 1 week of pizza and beer provided to the rest of the team?

IMHO, having a larger number of smaller, more homogeneous lists of self contained objects (or 'systems' of objects), combined with a more complex main loop in which the flow of data and control is explicit and easy to follow, is a far, far superior approach.

I read something similar a few weeks ago: ,,Take a look, for example, at the work on OGRE version 2.0: Matias Goldberg, the mastermind behind that endeavor, chose to store data in big, homogenous arrays, and have functions that iterate over whole arrays as opposed to working on only one datum, in order to speed up Ogre." http://gamedevelopment.tutsplus.com/articles/what-is-data-oriented-game-engine-design--cms-21052

I am totally agree with this concept. Though I am really newbie in game development, I can clearly see the benefits of a design like that.

This is actually way different.

What he is doing in that link is basically copying game data into seperate arrays that contain like only renderables, etc.

He's basically doing this to avoid massive synchronization and to avoid branching.

Instead of having all threads work with one list of data, each thread is given separate copies of the data tailored for a particular use.

Like... mutex->lock(); copy data per thread applying filters; notify threads to wake up; mutex->unlock(); wait for threads to finish; repeat;


Couldn't this be considered the "visitor pattern"?.

much simpler - its just class based on a list type data structure of some sort.


What if you double-buffer your modifications of game data so that all changes don't take effect until after 1 complete iteration through all objects?

deterministic design of control code as described above by Hodgeman makes life SO much easier. I wouldn't code any other way unless i had to. i've been doing it so long now, in so many games i don't even think about it. i by and large assume that more or less any game will have at the very least a list of targets, and most likely a list of active projectiles as well, and also a player data structure or list of PCs. and making the player target #0 presents no problem, as target #0 always updates first - still deterministic.


What if you implement a system where each change to the underlying interfaces requires an investment of 1 week of pizza and beer provided to the rest of the team?

then i'd be buying a lot of beer and pizza! <g>.

Norm Barrows

Rockland Software Productions

"Building PC games since 1989"

rocklandsoftware.net

PLAY CAVEMAN NOW!

http://rocklandsoftware.net/beta.php

How about you call it the "manager pattern"?

You could have playerManager, cloudManager, treeManager... And you could use a "Manager" base class so you can have a list of generic manager classes and update them all at once in the managerManager.

o3o

How about you call it the "manager pattern"?

You could have playerManager, cloudManager, treeManager... And you could use a "Manager" base class so you can have a list of generic manager classes and update them all at once in the managerManager.

This reminds me of an article I read once.


This reminds me of an article I read once.

OMG! ROTFL!

but seriously, a game could probably be put together using mostly classes of such type.

well, except maybe for trees type structures and such....

its probably safe to say that the list (in some form, array, vector, etc. ordered, un-ordered, etc) is the most common data structure in a game.

i use them more than 2d array type structures, and i almost never use true trees. i frequently use sparse matrix lists for sparse 2d and 3d arrays.

Norm Barrows

Rockland Software Productions

"Building PC games since 1989"

rocklandsoftware.net

PLAY CAVEMAN NOW!

http://rocklandsoftware.net/beta.php

This topic is closed to new replies.

Advertisement