CODEWITHSUNDEEP
javaalgorithmoopdata-structurescomplexity-theory
Kaushik Shankar
Kaushik Shankar

Reputation: 5619

What is the best data structure to use for type-based querying?

I am in the process of making a game, and in that process I have come across a bit of a problem.

I have many different types of game elements. These are all of type Entity.

There are many types of Entities, including ones that are visible and need to be drawn on the screen. These entities are of type VisibleEntity which extends Entity.

Like this, I have many different hierarchical types for the elements in the game.

My question is this:

What data structure has the best run-time complexity when issuing the following types of queries?

1) get objects of type Entity

2) get objects of type VisibleEntity

3) get objects of type SomeSpecificGameObject

The trivial solution is to store them all in a list, and iterate through them all, and if they are of the type specified, add them to a list that is to be returned.

Obviously, it is not feasible when computation is done at every frame for certain elements in the screen.

What is the best way to keep track of all this?

I appreciate any response!

Upvotes: 0

Views: 150

Answers (3)

ccleve
ccleve

Reputation: 15779

The other trivial solution is to maintain one list per type. Store each list in a hashmap, with the type as the key. It's about as instant as you can get, and will only cost you one pointer per item. It also makes it possible to add the same object to more than one list. That will handle your hierarchy.

If you want to reduce the space required by the approach above, have each list-of-entities object also store pointers to the lists of its subclasses. That way, a VisibleEntity would live only in the VisibleEntity list, and not in the lists for its subclasses. To find all VisibleEntities, you do a hash lookup for the the main list, and then do a recursive search through the children for the subclasses. This is a simple tree structure.

class MyEntityList {
    List<Entity> entityList = new ArrayList();
    List<MyEntityList> subclassLists = new ArrayList();
}

Depending on the height of your tree and the number of objects, you might be better off with the first approach. It's a complexity vs time vs space tradeoff.

Upvotes: 4

meriton
meriton

Reputation: 70564

Obviously, it is not feasible when computation is done at every frame for certain elements in the screen.

That really depends on the number of objects. A modern cpu cycles several billion times each second. Assuming the check and add to the list takes 10 cycles and you do 100 frames per second, iterating over a list of 1000 elements for each frame will cause a cpu utilization of 0.1%. So on the contrary, the naive solution is very feasible unless you have thousands of game objects, or need to query by type many times per frame. The recommandation, as usual, is to implement the simplest thing that could possibly work, measure the performance impact, and optimize only if that impact is significant.

That said, the next simplest thing is to do:

abstract class Entity {
    private static Map<Class<?>, Set<? extends Entity>> byType = new HashMap<>();

    public static <E extends Entity> Set<E> allOfType(Class<E> clazz) {
        @SuppressWarnings("unchecked")
        Set<E> set = (Set<E>) byType.get(clazz);
        if (set == null) {
            set = new LinkedHashSet<E>();
            byType.put(clazz, set);
        }
        return set;
    }

    @SuppressWarnings({ "rawtypes", "unchecked" })
    protected Entity() {
        for (Class c = getClass(); c != Object.class; c = c.getSuperclass()) {
            allOfType(c).add(this);
        }
    }

    @SuppressWarnings({ "rawtypes", "unchecked" })
    protected void destroy() {
        for (Class c = getClass(); c != Object.class; c = c.getSuperclass()) {
            allOfType(c).remove(this);
        }
    }
}

which you'd use like

for (VisibleEntity ve : Entity.allOfType(VisibleEntity.class)) {
    ve.render();
}

The approach can be generalized to index by things other than classes, simply use another key type for the map, and insert and remove from the category sets at appropriate times.

Upvotes: 1

BillRobertson42
BillRobertson42

Reputation: 12883

I don't really think that using a class hierarchy to indicate whether or not an object has a certain attribute or not is the best idea.

You might want to keep objects that could be rendered in the game engine in an octree, and certainly they will need to have some way of being drawn; so that may be a good candidate for a type (in the sense that an interface is a type).

As to other arbitrary attributes, you can represent them generically and then maintain indices for quick retrieval, or like you said, keep them in lists and have a simple filter function that can return you a sub-set of objects that match specific criteria. If there aren't too many objects then the second approach ought to work fine. The threshold value for 'too many' is a value that you'll probably have to figure out with some testing.

Upvotes: 1

Related Questions