Quickly get an object from arrayList

Performance Tuning
#1

Hi there, I have some performance issues with my entities in my game, and I found out why, here is the problematic part of the code.

Entity.java


if(ScreenIngame.getEntity(this.getPbX(), this.getPbY(), EntityFire.class) != null && this.isDestructible())
{
      this.deleteEntity();
}

the getEntity method which returns an entity of the class parameter in given position


    public static Entity getEntity(int pbX, int pbY, Class<?> cls)
    {
        for (Entity entity : entityList)
        {
            if (entity.getPbX() == pbX && entity.getPbY() == pbY && entity.getClass() == cls)
            {
                return entity;
            }
        }
        return null;
    }

In case you are wondering why I called the position “pbX” and “pbY”, the “b” stands for “block”.

So what I say in those bit of code is that if there is an EntityFire at the same position as the entity. The said entity will be deleted.

The problem is that there is like 270 active entities in the game at any given moment, so every frame all entities, call for the loop to find if they are in fire which take tens of thousands of loops per frame.

So is there a way to get all entities of an arrayList that are in given position without having to loop through all the entities ?

#2

You need a simple indexing data structure that indexes based on a 2D integer value.
Depending on:

  • the size of your integer lattice/grid (i.e. the possible coordinates that an entity can have)
  • the sparseness/terseness of the 2D integer lattice/grid (how much of the possible 2D coordinates actually contain entities)
  • the frequency of change (how often does every entity change its coordinates)
  • how many entities can share the same (x, y) location
    you can first try to go with a simple: HashMap
    where the key could be a 64-bit Long, which is [icode](((long)x << 32) | y)[/icode], and the value is your entity.
    This is for the case where you have a sparse grid (few entities in it compared to the overall size of the grid). And 270 entities does not sound much at all.
    And it is also for the case where only one entity can be at the same location at any given time.
    Otherwise you could also help yourself with a simple sequence/collection/linkedlist/arraylist as the value of your HashMap.
    The benefit of using a simple HashMap is that querying is constant-time (very very very fast) and updating the data structure when entities change their position is also quite cheap.

If you need more elaborate data structures, then also have a look at a quadtree.
But a simple HashMap will get you going in no time and is your friend for well over 1000 entities.

Also: http://cs.stackexchange.com/questions/22251/what-is-the-best-way-to-index-lookups-on-a-2d-array-of-integers-that-is-boundles

#3

Thanks for the wonderful reply ;), the world of the game is actually only 20 by 11 blocks. Every block is counted as an entity, there is a maximum of about 10 entities per block. Some entities change their location about every 1 second.

Also you lost me at

(((long)x << 32) | y)

I know that these are binary operators but I don’t get where and how it works.

#4

It just means your x coordinate will take up the leftmost side of the long bits, and the y coordinate will use the rightmost side.

#5

[quote=“Zeldar,post:3,topic:56440”]
The purpose of that line is to store two integers in one long.

Imagine the integers x and y as binary strings. An int is 32 bits in length, and a long is 64 bits in length, which means we can pack two ints into one long. If the value of x is 127, in binary it looks like this:

00000000000000000000000001111111

When we cast it to a long, it looks like this:

0000000000000000000000000000000000000000000000000000000001111111

We’re using a longer string to represent the same number, which is the reason for all the new zeroes on the left. Then we shift it 32 places – the length of an int – to the left:

0000000000000000000000000111111100000000000000000000000000000000

This is the meaning of “x << 32.” For our purposes, it gives us room to store a second integer on the right side.

That leaves the integer y. Let’s say its value is 72. In binary, it looks like this:

00000000000000000000000001001000

The operator | is a bitwise “or,” which means that every bit in the result has a value of 1 where at least one of the operands has a value of 1. This might be easier to understand in table form:

[tr][td]A[/td][td]B[/td][td]A | B[/td][/tr]
[tr][td]1[/td][td]1[/td][td]1[/td][/tr]
[tr][td]1[/td][td]0[/td][td]1[/td][/tr]
[tr][td]0[/td][td]1[/td][td]1[/td][/tr]
[tr][td]0[/td][td]0[/td][td]0[/td][/tr]

Since “(long)x << 32” produces a long, for the purposes of the “or” operation, y gets promoted to a long as well. Look at the strings next to each other:

0000000000000000000000000111111100000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000001001000

The result of the or operator looks like this:

0000000000000000000000000111111100000000000000000000000001001000

You can see that it’s almost like we “dropped” one number into the other, where we made room for it. What actually happened is that every 1 in the left-hand operand (x << 32) corresponded to a 0 in the right-hand operand (y), and every 1 in the right-hand operand corresponded to a 0 in the left-hand operand as well, thereby putting the two original 32-bit patterns side by side.

Hopefully that explanation makes at least some sense.

As for the ideal data structure here, a HashMap won’t work if you can have multiple entities per cell.

if(ScreenIngame.getEntity(this.getPbX(), this.getPbY(), EntityFire.class) != null && this.isDestructible())
{
      this.deleteEntity();
}

Instead of running the above check for every entity every frame, do it when a new entity enters a cell. When you spawn fire, have it check if it overlaps with a destructible block. When you spawn a destructible block, have it check for fire.

#6

Did you profile this? Because looping over 270 entities should be a non-issue. If you are having some exponential increase of computation time per added entity, then you have an algorythmic problem that won’t be solved by improving the access-time, but only by eleminating inner loops and such.

Better explain what you want to do, profile your code and post more of it including a bigger scope.

I highly doubt that the code you’ve shown up until now can be optimized so much to provide a significant gain in performance…

#7

Yeah I forgot to mention that the fps drop happens only when I play it on my android phone, and yes this is the exact line that is the problem, without it, my phone run the game at 60 fps, and with it, it go down to about 35 fps. I think I’ll try to do boxsmith’s method to call this bit of code less frequently.

As for the hashmap wouldn’t it be possible to makes the values a list of entities so that we can put multiple entities in one cell, or it’s just not efficient?

#8

What if you don’t compare the classes? (As far as performance goes)