Avoiding looping through everything

[namrog84]

Looking at the source code of ArrayList

There appears to be quite different methods between remove object and remove index.
Would there be a way to perhaps grab the particular objects location and is the remove index number any faster than remove object function?

1   2   3   4   5   6   7   8   9   10   11   12   13   14   15   16   17   18   19   20   21   22   23   24   25   26   27   28   29   30   31   32   33   34   35   36   37

public E remove(int index) {     rangeCheck(index);       modCount++;     E oldValue = elementData(index);       int numMoved = size - index - 1;     if (numMoved > 0)     System.arraycopy(elementData, index+1, elementData, index, numMoved);     elementData[--size] = null; // Let gc do its work     return oldValue; } public boolean remove(Object o) {     if (o == null) {         for (int index = 0; index < size; index++)             if (elementData[index] == null) {                 fastRemove(index);                 return true;             }     } else {         for (int index = 0; index < size; index++)             if (o.equals(elementData[index])) {                 fastRemove(index);                 return true;             }     }     return false; }   private void fastRemove(int index) {     modCount++;     int numMoved = size - index - 1;     if (numMoved > 0)         System.arraycopy(elementData, index+1, elementData, index, numMoved);     elementData[--size] = null; // Let gc do its work }

Initial tests of temporarily saving the index location during the iteration process appears to be about 5-10% faster.
myArrayList.remove(tempIndexInt) is 5-10% faster  //remove int index
myArrayList.remove(this)  //remove object

adding items to a removeme Arraylist to later remove that collection from the original list is slow.
adding items to a new list, to simply exclude "to be removed" items is even slower? 

However, this isn't a real world application, just a little test I setup.  So I am not really sure how accurate setup is.

[Cero]

well remove(Object o) calls it by itself you edited your post =P

well just clearing works fine aswell

[pitbuller]

There's not just towers but also projectiles to worry about too don't forget. But yes, 150,000 collision checks isn't really a lot, unless you really need those cycles for something else. Anything under a couple of milliseconds is going to leave you plenty of CPU to do graphics and other game logic. Or of course you can cheat at run at 30fps

Cas

We still cheat with homing missiles or instant beams. If we change this then it might be worth change lot other things too. But have to make gameplay ready and optimize after that. Still running 900fps at desktop so no problems yet(libgdx is that effective.)

Games published by our own members! Check 'em out!

[cylab]

Looking at the source code of ArrayList

There appears to be quite different methods between remove object and remove index.
Would there be a way to perhaps grab the particular objects location and is the remove index number any faster than remove object function?
(...)

Unfortunately the remove index is just one part of the equation. To make this fast, it needs to get rid of data moving to fill the gap of an removal without slowing down addition.

I was more thinking along the lines of an unsorted Bag having a stack of empty slot indices, so you can have something like

1   2   3   4   5   6   7   8   9   10   11   12   13   14

add(Collectable obj) {   emptyStackPointer--     storage[ emptySlots[ emptyStackPointer ] ] = obj   obj.setSlot( emptySlots[ emptyStackPointer ] ) } remove(Collectable obj) {    slot = obj.getSlot()    storage[ slot ] = null    obj.setSlot( -1 )    emptySlots[ emptyStackPointer++ ] = slot }

This should be very fast, but clearly has problems:
- it limits a collection to only store specific kind of objects
- you can only store a Collectable in one collection
- you need an emptySlots stack the size of the collections' capacity
- iterating the contained objects is more difficult

[princec]

Now this really is premature optimisation! We're talking about 300 removes and 300 adds per frame - and that's only for entities that have actually moved! So no turrets, just mobs and bullets. It's noise.

Cas

[Riven]

Now this really is premature optimisation! We're talking about 300 removes and 300 adds per frame - and that's only for entities that have actually moved! So no turrets, just mobs and bullets. It's noise.

The OP doesn't mention a certain amount of entities.

Hence it's perfectly valid to assume it's massive and everything has to be done to queeze out the last drop of performance

[JL235]

You could just use an array.

Otherwise here is some thought craft. Try storing the index within the object that you are storing. If you disallow random insertions and appending to the beginning (which is quite common for a lot of ArrayList usage), then you only have to update the objects indexes when an element is removed. You can skip that by storing null in an empty position, rather then compacting the array down, and store the location of the null element in an int array (a stack). When you next insert, read from the stack, decrement the size and then place the new object at that location.

If the arraycopy is slower then the stack read + size decrement, then this optimization should end up improving the speed. It does mean you are essentially removing based on reference (by telling giving each instance to hold a unique array index), rather then on equality. Presuming it totally works, I'd put money that any speed improvement is exceptionally trivial. You'd need millions (10s of millions?) of elements before you'd see any real gain.

Any real optimizations also depend heavily on what you are trying to achieve. For example are you iterating over this array to handle collisions? If so then you might consider a Grid or OctTree instead, as you can then avoid large sections of your objects.

[cylab]

I was more thinking along the lines of an unsorted Bag having a stack of empty slot indices, so you can have something like

1   2   3   4   5   6   7   8   9   10   11   12   13   14

add(Collectable obj) {   emptyStackPointer--     storage[ emptySlots[ emptyStackPointer ] ] = obj   obj.setSlot( emptySlots[ emptyStackPointer ] ) } remove(Collectable obj) {    slot = obj.getSlot()    storage[ slot ] = null    obj.setSlot( -1 )    emptySlots[ emptyStackPointer++ ] = slot }

This should be very fast, but clearly has problems:
- it limits a collection to only store specific kind of objects
- you can only store a Collectable in one collection
- you need an emptySlots stack the size of the collections' capacity
- iterating the contained objects is more difficult

Actually the emptySlot stack now seems like a bad idea after thinking about it - the limitations in iterating the contents might just be to costly. Better just use kappas Bag implementation http://www.java-gaming.org/topics/the-bag-fast-object-collection/24203/view.html and store/update the index in the Entity if removal has to be as fast as possible...

[Mads]

Hey, thanks for all the comments on this! I'm not asking this in a particular context, but more as to how the problem should be solved the most efficiently, and keeps that when scaling. It's not a matter if it makes the time, but what method is fastest, while offering the features needed in a given situation.

I very much like the idea of the grid. With that in mind, it seems wierd that quadtrees should be remarkably slower (at least to me). Can someone explain the reason for that? Also, would octrees be any good compared to quadtrees, in 2D space?

Finding the hypotenuse of a triangle gives pretty accurate results, right? But that expensive Math doesn't need to take place when comparing the entities left, after we find out what's in a given square in the grid, does it?

1   2   3

yDis = pos.y - targ.y xDix = pos.x - targ.x distance = yDis + xDis

I don't see immidiate problems with this, and it is (..it should be) faster than doing the actual geometry math? 

[Mads]

Hey, thanks for all the comments on this! I'm not asking this in a particular context, but more as to how the problem should be solved the most efficiently, and keeps that when scaling. It's not a matter if it makes the time, but what method is fastest, while offering the features needed in a given situation.

I very much like the idea of the grid. With that in mind, it seems wierd that quadtrees should be remarkably slower (at least to me). Can someone explain the reason for that? Also, would octrees be any good compared to quadtrees, in 2D space?

Finding the hypotenuse of a triangle gives pretty accurate results, right? But that expensive Math doesn't need to take place when comparing the entities left, after we find out what's in a given square in the grid, does it?

1   2   3

yDis = pos.y - targ.y xDix = pos.x - targ.x distance = yDis + xDis

I don't see immidiate problems with this, and it is (..it should be) faster than doing the actual geometry math? 

EDIT:
Actually, I do! If xDis is negative, it might give unwanted behavior. A Math.abs(xDis), would fix this. Anyone know of the expensiveness (because that's totally a word), of Math.abs?

Games published by our own members! Check 'em out!

[Cero]

EDIT:
Actually, I do! If xDis is negative, it might give unwanted behavior. A Math.abs(xDis), would fix this. Anyone know of the expensiveness (because that's totally a word), of Math.abs?

I don't know, but, why would

1	public static double abs(double a) { return (a <= 0.0D) ? 0.0D - a : a;}

be slow, even if its done many times =0

[Mads]

EDIT:
Actually, I do! If xDis is negative, it might give unwanted behavior. A Math.abs(xDis), would fix this. Anyone know of the expensiveness (because that's totally a word), of Math.abs?

I don't know, but, why would

1	public static double abs(double a) { return (a <= 0.0D) ? 0.0D - a : a;}

be slow, even if its done many times =0

That wouldn't, if that's the implementation of it Math is just famous for it being sloow. 

[Roquen]

Because of branch mispredition.

[Riven]

Because of branch mispredition.

Partly.

In my experience pulling that exact code out of Math.abs(..) and putting it in your own code (basically manually inlining) can result in major speedups.

Disclaimer: last time I tried this was about a year ago.

[Roquen]

Agree.  Plus you can nuke the negative zero filtering bit which you most likely don't care about. (the 0-a for negative or zero input).

[Mads]

Alright, I've run into a really silly problem with the Grid implementation. When creating arrays of ArrayLists, is there really no way to speficy what kind of objects can be in there? Normally I would do ArrayList<Shtuff> and that would be fine, but when doing this:

1	private ArrayList<Entity>[][] list = new ArrayList<Entity>[cols][rows];

it fails  
Is there really no way around doing

1   2

if (o instanceof Shtuff) { }

In this case? I've always been tought that not only is that hacky, it's also costly in the long run. In this case my OOP OCD screams at me, for doing instanceof.  

[JL235]

Alright, I've run into a really silly problem with the Grid implementation. When creating arrays of ArrayLists, is there really no way to speficy what kind of objects can be in there? Normally I would do ArrayList<Shtuff> and that would be fine, but when doing this:

1	private ArrayList<Entity>[][] list = new ArrayList<Entity>[cols][rows];

it fails  
Is there really no way around doing

1   2

if (o instanceof Shtuff) { }

In this case? I've always been tought that not only is that hacky, it's also costly in the long run. In this case my OOP OCD screams at me, for doing instanceof.  

I think your looking for: ArrayList< ArrayList< Stuff > >()

You'd also have to use: grid.get( x ).get( y ), rather than: grid

• [y]

Using [] is reserved exclusively for arrays (which I don't agree with).

[SHC]

1   2   3   4   5   6   7

oldCellX = entity.x >> cellSizeInBits oldCellY = entity.y >> cellSizeInBits updatePosition( entity ) newCellX = entity.x >> cellSizeInBits newCellY = entity.y >> cellSizeInBits

I had a very small doubt. What if the object is in between two or more cells? How do you work on it?

[Roquen]

You need to refine your question.

[SHC]

Suppose there is an object like in this image.



How to add the same object to both the cells?

[cylab]

In most cases you wouldn't as long as the entities are small enough. You would rather widen the maxRange in

1   2   3   4   5   6   7   8   9   10   11   12   13   14   15   16   17   18   19   20   21

findNearest(pos, maxRange) {   cellRange = maxRange  >> cellSizeInBits   posCellX = pos.x >> cellSizeInBits   posCellY = pos.y >> cellSizeInBits   nearestEntity = null   for( cellX = posCellX - cellRange; cellX < posCellX + cellRange; posCellX++ )   {     for( cellY = posCellY - cellRange; cellY < posCellY + cellRange; posCellY++ )     {       foreach entity in grid[cellX][cellY]       {          nearestEntity = compareAndReturnNearest(pos, entity, nearestEntity)       }     }   }   return nearestEntity }

to search enough cells, so that the biggest entity you would expect is also covered.


If you really have huge entities, you could just attach an array of offsets to the entity coordinates that would form a coverage grid with the same cell size as the playfields grid:

1   2   3   4   5   6   7   8   9   10   11   12   13   14   15   16   17   18   19

int[] oldCellX = new int[entity.covers.length]; int[] oldCellY = new int[entity.covers.length]; int[] newCellX = new int[entity.covers.length]; int[] newCellY = new int[entity.covers.length]; for(int i=0; i<entity.covers.length; i++) {     oldCellX[i] = entity.x+covers[i].x >> cellSizeInBits;     oldCellY[i] = entity.y+covers[i].y >> cellSizeInBits; } updatePosition( entity ) for(int i=0; i<entity.covers.length; i++) {     newCellX[i] = entity.x+covers[i].x >> cellSizeInBits     newCellY[i] = entity.y+covers[i].y >> cellSizeInBits }

This way, you would add the entity to as many grid cells as you have covered.

[Roquen]

To expand on cylab's post: It depends.  The size of the cells vs. maximum extents, what queries are important to speed up, etc.  For example for collision detection you only need to store objects in one cell, say the upper-left most one that it covers, then do a grid-based sweep-and-prune. Sketch:

1) walk grid rows from top-to-bottom
2) walk the row left-to-right
3) walk the contained entities in the cell first to last and perform broad-band collision detection with all enities "forward" in the list.  If this entity crosses one-or-more cells to the left and/or bottom of this cell's edges check all of those cells as well.

You never need to check entities to the right or above because they've already done that work.

Beyond that, again, it depends.  An example: If you've a very low probability that an entity will cover more than 4 cells (being close to a corner) then for other queries you can simply expand your search by one cell and when an entity happens to cover more than just it's nearest neighbors you note that in an auxiliary list for all further away cells (which you obviously need to check for all other queries).

[ra4king]

Damn guys, a 1.5 year old thread? Can't this be moved to a new thread?

[Roquen]

As long as the previous information isn't stale, I think its probably more useful to continue an old-thread...unless you think a different title would be more helpful.

[cylab]

Pay attention that

(entity coordinates must be) the upper-left most one that it covers

is mandatory for the sketched algorithm to work. If you use entity coordinates that are centered to the entity, you will miss collisions with big entities!

[Roquen]

It's worth noting that it must be one of the maximal extents (corners), but you could choose (say) lower-left instead, then you flip to bottom-to-top...that's what I was attempting to say.

[brollysan]

Don't do abs. Just square each number. If EVERYTHING in your game is relative to the square length. Distance = x^2 + y^2 then the "physics" of it will be fine. If rendering is an issue you can scale it back by division (try and experiment with a division factor). This stops you from doing Math calls all the time. This is how I do my particle simulations anyway.

[Roquen]

Danger Will Robinson: distance square.  Comparing two linear distances has the same result as comparing two linear distances squared using a Euclidean metric (L₂).  It doesn't generalized.

[ReBirth]

How about reduce the tiles' size and use Manhattan? :/

[Roquen]

In the limit, you'd be fine!