Well, im making a small tilebased game and am at a point where im designing different objects(trees, monsters, catapults, lightsources) all derived from a base object class. Each tile will have its own linked list of all objects over that tile so as to help when drawing the portion of the map on the screen. I should clarify: **objects are not create and controlled from the map tile''s linked list**(used more for drawing and mapdata) There will obviously needed to be "MASTER LIST" of sorts(either a simple array of pointers to objects or linked list of objects... doesnt matter but im using linked lists for a more dynamic controlL). Whats my question? Well, how do you guys handle this with different objects? I mean, i CAN place every object created into 1 HUGE linked list and just run my UPDATEOBJECT() or my GETLIGHTSOURCE() functions on the entire list .... OR ..... I could create separate lists for objects of specific nature: -->create linked list for all STATIONARY Objects, like trees, rocks, FIRE, anything that can "change states" but doesnt move -->create Linkedlist of all MOVING Objects, like them nasty orcs or the brainless townfolk. I tend to think the second would be more efficient in some respects later in life when updating all objects at once is not needed, only objects closer to screen and such..

aka John M. Never give up. Never surrender!

Use a tree

One list, many branches, faster searches. Simple


"NPCs will be inherited from the basic Entity class. They will be fully independent, and carry out their own lives oblivious to the world around them ... that is, until you set them on fire ..."
"When you are willing to do that which others are ashamed to do, therein lies an advantage."

Hi morfe! You really seem to know your stuff, i especially like what what you seem to be doing with your AI.

Right now im thinking of 2 different identifiers of objects: a CLASS identifier(just like the class objects from which they could be created from: tree, lightsource, orc, archer,etc) AND a unique object ID for each object for possible future things such as memory of objects and any other reasons i may need it for.

Could you elaborate a little more on how you break up your trees...do you use binary trees? ...and how do you search/add nodes to your trees(on position or something else)?

aka John M.
Never give up. Never surrender!

You should have a tree, but for communication between objects, a good system is a message system. You should have each object that changes tell each object that it touched or affected. A good application for this system is to use a script that reacts to the messages. For example

OnStepOn:
KillPlayer

Hello anonymous. Right now im not at that stage where i need to worry about message systsm. Im not saying your wrong that ill probably need them, BUT i am asking about ways of holding objects. Both you and morfe say "use trees" but i need a little more to go on...dont tease me for gods sake!!

Could someone elaborate for me more on what type of "tree" you use and "how" you are creating these trees...as i asked before, are the objects placed in these trees by their x,y,z position such as in bsp tree or on the objectId number in a binary tree??? Need more input!!

aka John M.
Never give up. Never surrender!

Damn.. read some about these obvious things..


every node has a parent, that''s it

now, the root node has no parent (null)

Wow Jrz that was really helpful. You basically said nothing, since GalaxyQuest already implied he knew something about trees (binary trees at least) I''m sure he knew, or could deduce that root nodes have no parents.

On the topic of question, I''ve never used a tree to store my entities but it seems an interesting idea. I''ve used linked lists, or a hash table.

Hash table gives fast searches (providing you have a good hasing function sorted out), but iterating through all objects is not terribly intuitive.

I''m trying to think of the best key to use in a binary tree, and the thing I keep coming to is the object name or ID. You could do it by a combo of object class and ID so that objects of the same class are grouped together, and are sorted in ascending (or descending) order of their IDs.

To elaborate a bit consider the key of an object to be defined by:

key = objClass*1000 + objID;

This way the class becomes the most significant bits, and the ID is still easily extractable. Inserting into a sorted tree will group all the similarly classed objects in their own subtree, while keeping them locally in order by their IDs.

Then you could pull out the ''parent'' node of an objClass''s subtree and go nuts with it.. etc.

Ah trees.. interesting things they are.

In the end I guess you need to decide whats best for you (ie. most efficient and robust and easy to use), the key you choose to use will determine a lot of the advantages/disadvantages of the tree.

Just one last thought:
There''s no rule that you says you can''t have multiple trees each using a different kind of key. To avoid duplicate data you can have a single pool of objects, and when you allocate an object just add the object''s pointers to each of the trees.

Have fun.

Hi GalaxyQuest.

If you want to use a tree, you could use the template from STL named "map"
there are an active threads about it right now, you should check it out, to see how to use it.

I have been told that it uses the red-black tree which is an improved binary search-tree...this tree will never be deeper that
2*lg noOfElements, and since the height is the factor that says how many comparisons(worst case) you have to make to find an element, this feature is very nice to have.

Of course this wont teach you any theory on the subject, but i bet if you check out your favorite "alogorithms in [insert language here]", it will have a detailed explanation of Binary Search trees, and even one for Red/black tree''s if youre lucky

Your on the right path with the 2nd method. Create a seperate list/table/etc. for specific type of objects. I find that most of my overhead is in querying objects within an area, and the update loop calling each objects control logic. Alot of work has been done on the 3d side for efficent object spatial sorting/searching, using bsp trees, octrees, etc.

Good Luck

-ddn

I would like to thank all for your suggestions. I guess it really does depend on however i want to store the damn objects in the tree..whether its by position on the map or by object ID''s of some sort...
so thanks again and any more items u think of are totally welcome!!
(i guess i should have said i can understand trees but i figured it was implied when my question was specifically about what data to use to determine where to store objects in the tree)

AS for you JRZ. I am a student a student in com sci here in CA and before you go making a fool of yourself again...at least read the damn posts before you get all snotty.

aka John M.
Never give up. Never surrender!