Data Structures

Newbie & Debugging Questions
#1

Hi All,

I have been trying to think of a better way to hold all of the objects (planets, ships, etc) that make up my game in memory.

I have come across the TreeSet in one of my (i’ll admit old) JAVA text books, and from the way it was breifly described, it seems a great way to organise all my objects, as they will all be uniuque and all have parent and child nodes.

is the TreeSet the way to go? Are there any obvious dissadvantages in using this data structure?

I have been serching on google for some tutorials as to how to use the TreeSet, but there seems to be little aditional information out there than the few paragraphs in the textbook. This has lead me to beleive that it may be depreceated, or no-longer supported.

If anyone has any hints it would be great :slight_smile:

Thanks,
Matt

#2

TreeSet is probably not what you want. Just use one of the lists - ArrayList or LinkedList. They have different performance characteristics depending on how you use them, but I doubt it’s going to be an issue for you. I’d recommend ArrayList.

#3

TreeSet doesn’t give you access to the nodes or to the parent-child relationship. It’s a self-balancing tree, which means it rearranges itself to give good performance. If you want a collection in which no element is repeated (a set) and which remains sorted according to some sorting criterion then TreeSet is the class you’re looking for. Otherwise it isn’t. If you want a general tree structure you’ll have to write it yourself or find some third party library.

#4

Ok, I think I missunderstood exactly how the TreeSet works.

I am probably going to store space-ships in one structure and things like projectiles and sprites in another. Eventualy I would want to be able to handle upto 5000+ ships at any one time and 10,000+ projectiles (this project is for a space RTS).

Obviously this would put a huge importance on performance, expecialy for projectiles, particles, etc.

pjt33: whould this be an example of when the Set structures should be used?

I already have a self-coded tree structure that I am using for my environmental objects (stars, planets, moons, etc) and could look at making this more general.

#5

Start out simple to get it working. ArrayList should be fine. But when you get up to the full online RTS example you may want to look at using Entity systems.

#6

In the Java contect, what is an Entity system?

I’ve heard them called ‘like an agent based sytem but…’, bit I’m not really sure what makes them different, and to be honist I think that the person explaining them hadent much of an idea either :slight_smile:

I’m currently at university reading Ageht Oriented Systems Engineering, so if this is the case, that could be a fun little project to play with.

My only reason for shying away from an agent based aproach in this particular case is that generaly agents run within their own thread, and I’m not even sure if it is possible to run 5000+ threads on a ‘normal’ desktop pc or laptop.

Then again, I havent tried… looks like it could an interesting experiment.
Does anyone know if there is a thread limit of the top of their head?

#7

As far as I understand, the two are completely unrelated. An agent-based system is usually used in AI-type situations, no? An Entity-based system is just a way of organizing everything in a game that is commonly used. It’s also very simple.

Basically, everything that exists in your game is an Entity. Depending on how you want to design it, an Entity has different attributes. Usually this will be something as simple as position and size. Then it probably has an act() function and a draw() function. Maybe is has calls to allow it to contain animations or sprites. Then its subclasses define more specific data, like perhaps a CombatEntity has damage, hit points, and the like, while BackgroundEntity has parallax variables.

Here is an example:


Entity
    CombatEntity
        EnemyEntity
            DragonEntity
            ZombieEntity
            etc.
        PlayerEntity
    ConversationEntity
        AllyEntity
            RogueEntity
            MotherEntity
        QuestEntity
            TimedQuestEntity
            StoryQuestEntity

Some people wouldn’t have different subclasses for every single type of thing, but it’s mostly down to taste. The game I’m working on right now has something like 40 different Entity types (one for a cloud, one for a sun, one for a skeleton, etc.), but I’ve done games where there are only 5 types or so and you just pass different things into the constructors to control different behavior. It all depends on your project.

#8

ahh, I see. actually that’s pretty muchwhat I have already.


class physicsPoint
//holds positioning, velocity, accelleration, etc

class ship extends physicsPoint impliments MouseListener
// holds all the methods and events to draw a ship on the screen, and will also have
// methods to load/save ship data to to a file/database server

class etc extends physicsPoint
// you get the idea

is this what you mean?

chears!

please forgive typos, tiny phone keyboard :confused:

#9

http://cowboyprogramming.com/2007/01/05/evolve-your-heirachy/

#10

This is a good article. I’d personally argue to not typically use a component system as an indie programmer because your classes will rarely be that complicated, so “blob” classes won’t become too bad.

#11

Thanks appel, that looks almost exactly what I need, and also highlighted a few problems with my current aproach that i hadnt properly considdered!

Actualy, that seems like a very usefull way to go. I am mainly designing this as a re-useable game library for a number of other projects I have in my sketch-book, and the idea of haveing data-driven object creation as part of the engine sounds like a fantastic time-saver in the long run.

I am mostly interested in developing online casual games, probably using the facebook api for user interaction, etc. (Actualy, the space RTS is a bit of an odd project for me, and something I have been playing with for years as a sandbox for trying out new code).

I’m really glad you linked me this. One project I have on my ‘near future’ list requires prosedural item generation (also alowing users to combine and invent new items). Using a component-based object sustem as described in the article seems a great way to do this.

#12

I’ve taken a few moments over lunch to sketch out how I think the component based Entity would work.
Taking a cue from the article, I have created a class called ComponentManager that instanceates and hold all the components:


public class ComponentManager {
    Inventory myInventory;
    Physics myPhysics;
    Render myRender;
    StateAI myStateAI;
    
    public ComponentManager(String[] args)
    {
        for(String s : args)
        {
            if(s.equals("Inventory"))
            {
                this.myInventory = new Inventory();
            }
            if(s.equals("Physics"))
            {
                this.myPhysics = new Physics();
            }
            if(s.equals("Render"))
            {
                this.myRender = new Render();
            }
            if(s.equals("StateAI"))
            {
                this.myStateAI = new StateAI();
            }
        }       
    }
    
    public Inventory getInventory()
    {
        return this.myInventory;
    }
    
    // etc...
}

then, each component class would have its owen methods/variables that it would make available to the class owning the ComponentManager.

One thing that’s puzzling me though; when I declare my variables

 
    Inventory myInventory;
    Physics myPhysics;
    Render myRender;
    StateAI myStateAI;

do they start taking up memory THEN, or when they are instanceated?

 this.myStateAI = new StateAI();

If they take up no resources, then this structure would be fine. However, if resources are allocated as the variables are declaired, then this method would have no advantage.

Any thoughts?

Chears
Matt

#13

I like your plugged in ai, sweet.

#14

when they are instantiated

#15

Although when you declare the variable the pointer is created, no? Obviously not much memory, but something. Please correct me if I’m wrong here, Riven. :slight_smile:

#16

No. It’s an entry in the local variables of the method. Before you think ‘ah! so it taking RAM right there!’… well no, all local variables share it, and they can even share the same index, just not at the same time.

local-variable-space = max-concurrently-used-variables (which has nothing to do with multithreading…)

Example: (this takes 1 local)
`
Object a;
String b;

a = new Object();
System.out.println(a); // 1 local reserved
b= “6”;
System.out.println(b); // still 1 local reserved

// this line would make the whole method reserve 2 locals
int hashy = a.hashCode()+b.hashCode();
`

#17

Huh, that’s interesting. Very good to know. I always figured that dangling pointers were using up bits of memory, I had no idea the amount being used was based upon how many you were using concurrently. Smart design.

#18

Actually, there are no danging pointers in Java.

The GC checks the local variables for references too (naturally, or every Java app would crash). The JVM is actually quite smart about when local variables go out of scope in bytecode (even if they still are in scope in java sourcecode)

Anyway, just read up on bytecode. That’s what tells the JVM what to do, and that’s where you’ll find stacks/locals, and recently debug data too, even telling you where each variable goes in to / out of scope (counting by instruction).

#19

Yes, by dangling pointer I more meant a pointer that doesn’t go anywhere. Obviously if it’s not taking up any memory then it doesn’t actually exist as far the compiler is concerned. So it makes sense to act as you described above in the byte code. I should read up on byte code, but once I start reading and stop doing I inevitably get bored and fall asleep. :stuck_out_tongue:

#20

I organise my game objects into two data structures. First I store the actors according to their painting order which is a tree mapping an integer to a set of game objects. The integer describes how the game object will be drawn in relation to other game objects stored in the collection, lower values being drawn first and higher ones drawn later. All game objects begin with a default draw value of 0. It’s essentially a: Tree< Integer, Set >. This can also be used for cheaply iterating over all game objects.

For collisions I use a CollisionsGrid that stores objects according to their location. First they are seperated based on the class of the game object stored, so all Tanks and Infantry are stored seperately within a map. For each class the space is split into essentially a big 2D array where each element represents a section of the display (usually approximately 80x80 pixels on the screen). All game objects that overlap that section of the grid are stored in that element, which is implemented as a HashSet. A game object may also be overlapping several 2D array elements, and so will be stored in multiple elements. When checking for colliding game objects the object being tested against will be used to work out how many array elements it overlaps, and only the actors within those elements are checked for more precise (and expensive) object-to-object intersections. The array itself also expands dynamically, so it only ever stores for areas of space that game objects move to. Overall it’s essentially a: Map< Class<? extends GameObject>, Set<? extends GameObject>[][] >.

The map can also pull out not only the objects of a given class, but also all objects of a sub-class too. So if I ask for instances of ‘Tank’ then I will receive all instances of Tank any sub-classed such as ‘FlameTank’ and ‘SuperTank’. Unfortinatly checking if classes are a sub-class of each other has always been very slow for me, so internally it indexes the class hierarchies that it has stores and updates this whenever it meets a class it doesn’t know.

For the final implementation I use custom data structures for most of the above; custom trees, sets, lists and even a custom 2D array.