Java-Gaming.org    
Featured games (78)
games approved by the League of Dukes
Games in Showcase (426)
Games in Android Showcase (89)
games submitted by our members
Games in WIP (466)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: 1 [2]
  ignore  |  Print  
  Avoiding looping through everything  (Read 7625 times)
0 Members and 1 Guest are viewing this topic.
Offline namrog84

JGO Ninja


Medals: 46
Projects: 4


Keep programming!


« Reply #30 - Posted 2011-08-05 21:09:36 »

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.

"Experience is what you get when you did not get what you wanted"
Offline Cero
« Reply #31 - Posted 2011-08-05 21:12:39 »

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

well just clearing works fine aswell

Offline pitbuller
« Reply #32 - Posted 2011-08-05 21:31:08 »

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 Wink

Cas Smiley

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!
Legends of Yore - The Casual Retro Roguelike
Offline cylab

JGO Knight


Medals: 34



« Reply #33 - Posted 2011-08-05 23:43:08 »

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

Mathias - I Know What [you] Did Last Summer!
Online princec

JGO Kernel


Medals: 284
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #34 - Posted 2011-08-06 01:08:19 »

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 Smiley

Online Riven
Showcase Moderator

JGO Overlord


Medals: 612
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #35 - Posted 2011-08-06 01:13:35 »

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 Pointing

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline JL235

JGO Coder


Medals: 10



« Reply #36 - Posted 2011-08-06 04:29:28 »

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.

Offline cylab

JGO Knight


Medals: 34



« Reply #37 - Posted 2011-08-06 12:25:28 »

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...

Mathias - I Know What [you] Did Last Summer!
Offline Mads

JGO Ninja


Medals: 24
Projects: 3


One for all!


« Reply #38 - Posted 2011-08-06 17:08:56 »

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?  Smiley

Offline Mads

JGO Ninja


Medals: 24
Projects: 3


One for all!


« Reply #39 - Posted 2011-08-06 17:17:39 »

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?  Smiley

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!
Legends of Yore - The Casual Retro Roguelike
Offline Cero
« Reply #40 - Posted 2011-08-06 17:26:10 »

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

Offline Mads

JGO Ninja


Medals: 24
Projects: 3


One for all!


« Reply #41 - Posted 2011-08-06 17:32:17 »

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 Tongue Math is just famous for it being sloow.  Lips Sealed

Offline Roquen
« Reply #42 - Posted 2011-08-06 17:57:12 »

Because of branch mispredition.
Online Riven
Showcase Moderator

JGO Overlord


Medals: 612
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #43 - Posted 2011-08-06 18:25:56 »

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.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline Roquen
« Reply #44 - Posted 2011-08-06 21:06:41 »

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).
Offline Mads

JGO Ninja


Medals: 24
Projects: 3


One for all!


« Reply #45 - Posted 2011-08-06 21:08:13 »

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  Emo
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.  Huh

Offline JL235

JGO Coder


Medals: 10



« Reply #46 - Posted 2011-08-07 05:04:07 »

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  Emo
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.  Huh

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).

Offline SHC
« Reply #47 - Posted 2013-04-02 06:39:08 »

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?

Offline Roquen
« Reply #48 - Posted 2013-04-02 08:23:42 »

You need to refine your question.
Offline SHC
« Reply #49 - Posted 2013-04-02 09:06:37 »

Suppose there is an object like in this image.



How to add the same object to both the cells?

Offline cylab

JGO Knight


Medals: 34



« Reply #50 - Posted 2013-04-02 10:32:56 »

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.

Mathias - I Know What [you] Did Last Summer!
Offline Roquen
« Reply #51 - Posted 2013-04-02 12:07:11 »

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).
Offline ra4king

JGO Kernel


Medals: 322
Projects: 2
Exp: 4 years


I'm the King!


« Reply #52 - Posted 2013-04-02 12:08:53 »

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

Offline Roquen
« Reply #53 - Posted 2013-04-02 13:11:20 »

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.
Offline cylab

JGO Knight


Medals: 34



« Reply #54 - Posted 2013-04-02 14:28:50 »

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!

Mathias - I Know What [you] Did Last Summer!
Offline Roquen
« Reply #55 - Posted 2013-04-02 14:45:57 »

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.
Offline brollysan

Junior Member


Medals: 1



« Reply #56 - Posted 2013-04-02 15:14:37 »

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.
Offline Roquen
« Reply #57 - Posted 2013-04-02 16:02:36 »

Danger Will Robinson: distance square.  Comparing two linear distances has the same result as comparing two linear distances squared using a Euclidean metric (L2).  It doesn't generalized.
Offline ReBirth
« Reply #58 - Posted 2013-04-03 04:19:17 »

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

Offline Roquen
« Reply #59 - Posted 2013-04-03 08:10:15 »

In the limit, you'd be fine!
Pages: 1 [2]
  ignore  |  Print  
 
 
You cannot reply to this message, because it is very, very old.

 

Add your game by posting it in the WIP section,
or publish it in Showcase.

The first screenshot will be displayed as a thumbnail.

xsi3rr4x (75 views)
2014-04-15 18:08:23

BurntPizza (68 views)
2014-04-15 03:46:01

UprightPath (80 views)
2014-04-14 17:39:50

UprightPath (65 views)
2014-04-14 17:35:47

Porlus (81 views)
2014-04-14 15:48:38

tom_mai78101 (105 views)
2014-04-10 04:04:31

BurntPizza (165 views)
2014-04-08 23:06:04

tom_mai78101 (261 views)
2014-04-05 13:34:39

trollwarrior1 (210 views)
2014-04-04 12:06:45

CJLetsGame (220 views)
2014-04-01 02:16:10
List of Learning Resources
by SHC
2014-04-18 03:17:39

List of Learning Resources
by Longarmx
2014-04-08 03:14:44

Good Examples
by matheus23
2014-04-05 13:51:37

Good Examples
by Grunnt
2014-04-03 15:48:46

Good Examples
by Grunnt
2014-04-03 15:48:37

Good Examples
by matheus23
2014-04-01 18:40:51

Good Examples
by matheus23
2014-04-01 18:40:34

Anonymous/Local/Inner class gotchas
by Roquen
2014-03-11 15:22:30
java-gaming.org is not responsible for the content posted by its members, including references to external websites, and other references that may or may not have a relation with our primarily gaming and game production oriented community. inquiries and complaints can be sent via email to the info‑account of the company managing the website of java‑gaming.org
Powered by MySQL Powered by PHP Powered by SMF 1.1.18 | SMF © 2013, Simple Machines | Managed by Enhanced Four Valid XHTML 1.0! Valid CSS!