Java-Gaming.org    
Featured games (81)
games approved by the League of Dukes
Games in Showcase (483)
Games in Android Showcase (110)
games submitted by our members
Games in WIP (550)
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 8100 times)
0 Members and 1 Guest are viewing this topic.
Offline Mads

JGO Ninja


Medals: 26
Projects: 3
Exp: 6 years


One for all!


« Posted 2011-08-04 20:51:10 »

You always want to use a minimum of CPU per game cycle, right? Looping through all entites, for all entities is therefore not an option and should be done differently. I can do that, most of the time. Please consider this situation:

You have a 2D landscape, in a tower-defence something (RotT for instance) where towers shoot at nearby enemies. How does each tower know, what enemy to target? I actually tried to look in the source code in RotT to find out what the solution used there, and it seems like they're doing what I'd do (roughly):
Loop through all targetAble enemies (quickly returning an ArrayList<Type> of the type that is targetAble - data models is not my concern), and get the distance to them, using... hypotenuse of a triangle. Then just keeping in mind which one was the closest one, and bam - we have our answer.
But, Math can be expensive - if we have enough towers and enough enemies, we're going to run out of CPU sometime, if we want to loop through things like that.

What can I do to optimize performance, in these situations? I know I can get a copy of Riven's (awesome) fastMath, and I should also ONLY loop through enemies that actually COULD be targeted if they're close enough. Anything else? Practises? Any collections better than others?
Smart ways of sorting collections?

Thanks for being awesome JGO!  Cool

Offline ra4king

JGO Kernel


Medals: 345
Projects: 2
Exp: 5 years


I'm the King!


« Reply #1 - Posted 2011-08-04 20:57:10 »

An faster way is to first find all Targetable enemies that are inside an area and then using the distance formula to find the closest one.

Offline Riven
« League of Dukes »

JGO Overlord


Medals: 781
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #2 - Posted 2011-08-04 21:07:39 »

For a 2D world you can use a quad-tree.

That is recommended everywhere, but in my opinion a horrible solution. It complicates things and often results into sub-par performance.


What I did in a 2D fluid-simulator was to create an evenly spaced grid that contained the whole world. You'd fill every cell with the entities that are in that cell. If you're interested which entity can attack which enntity, you just have to check which cells are reachable (loop through rectangles of cells from the source) and iterate over the enitities contained in those cells.

I had even an algorithm that continuously changed the cell-dimensions, searching for the sweet spot.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline cylab

JGO Ninja


Medals: 43



« Reply #3 - Posted 2011-08-04 21:20:42 »

I second the grid approach. You can manage the cells you put your entities in very fast by just dividing the position coordinates by the cell size - when using power of two cells you can even optimize this with bit shifts.

Quad trees are only usefull if you have a *vast* amount of irregular placed entities and a *very* big world. It probably only makes sense nowerdays if you have to save memory, too.

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

JGO Kernel


Medals: 362
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #4 - Posted 2011-08-04 21:23:49 »

The grid cell thing is what I use in Revenge because I'm 99% of the time doing checks for collisions between small objects that are at most 2-3 grid cells in width or height versus other objects of that sort of size. It's highly efficient. I used to use a quadtree but it's much slower.

It would indeed be faster to grab a square chunk out of the world around a turret and then only loop through the entities in that square chunk. Even using grid cells the implementation is pretty fast provided you're not asking for too big a square chunk. In which case you'd be better off with a quadtree, or more likely, simply iterating through every single entity, as let's face it, a distance calc is cheap as chips, being two mults and an add (no need for sqrt if you just need to find who's closest).

Cas Smiley

Offline pitbuller
« Reply #5 - Posted 2011-08-05 07:47:24 »

Would this be fastest way to get first unit at range from the list if using bruteforce? Or is it faster just do the all math at once and then compare only one time?

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
public Unit getNearestUnit(int x, int y, int radius) {
  for (Unit unit : unitList) {
    final double dx = unit.getCenterX() - x;    
    if (radius < dx ){
      final double dy = unit.getCenterY() - y;
      if radius < dy{
        if ((dx * dx + dy * dy) < (radius * radius)){
          return unit;
        }
      }
    }                        
  }
  return null;
}
Offline Mads

JGO Ninja


Medals: 26
Projects: 3
Exp: 6 years


One for all!


« Reply #6 - Posted 2011-08-05 08:08:54 »

How big would said sqaures be? So, each cycle, I'm checking all entities, if they collide with all the rectangles, until a match if found?
That sounds intensive, is that really how it should be done? Can I assign entities to tiles easier than that? 

Offline pitbuller
« Reply #7 - Posted 2011-08-05 10:34:11 »

I made lot of micro benchmarks and noticed that if/if/if style is really slow, over double time slower when radius is about 10% of map size.
Also I noticed that for (Unit unit : unitList) is deadly slow. That kind of loop iterating cost lot more than all inside of it. It made method over three time slower than raw get index loop.

Fastest method for that function is:
1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
   public static Unit getNearestUnit4(int x, int y, int radius) {
      int size = 0;
      Unit unit;
      final float xx=x;
      final float yy=x;
      final float r = radius * radius;
      final int maxx = unitList.size();
      for (int i = 0; i < maxx; i++) {
         unit = unitList.get(i);
         final float dx = unit.x- xx;
         final float dy = unit.y- yy;
         if (r >= (dx * dx + dy * dy)) {
            return unit
         }
      }
      return null;
   }
Offline cylab

JGO Ninja


Medals: 43



« Reply #8 - Posted 2011-08-05 11:06:47 »

How big would said sqaures be? So, each cycle, I'm checking all entities, if they collide with all the rectangles, until a match if found?

Nope, it's more like (pseudocode):
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  
38  
39  
40  
41  
42  
43  
44  
45  
46  
47  
48  
49  
50  
51  
52  
53  
54  
55  
56  
57  
init()
{
  cellSizeInBits = 6 // so a cell is 64x64
 cellSize = 1 << cellSizeInBits

  cols = gameArea.width / cellSize
  rows = gameArea.height / cellSize

  grid = new List[cols][rows]
}

(..)

updateGrid( movableEntities )
{
  foreach entity in movableEntities
  {
    oldCellX = entity.x >> cellSizeInBits
    oldCellY = entity.y >> cellSizeInBits

    updatePosition( entity )

    newCellX = entity.x >> cellSizeInBits
    newCellY = entity.y >> cellSizeInBits

    // only update grid if needed to avoid costly collection updates
   if( oldCellX!=newCellX || oldCellY!=newCellY )
    {
      grid[oldCellX][oldCellY].remove( entity )
      grid[newCellX][newCellY].add( entity )
    }
  }
}

(...)

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
}

Mathias - I Know What [you] Did Last Summer!
Offline pitbuller
« Reply #9 - Posted 2011-08-05 11:25:34 »

Should we do benchmark for average game situations. Map and unit size should be fixed but towers and unit count be variable. Maybe couple different combination.
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline Cero
« Reply #10 - Posted 2011-08-05 12:20:48 »

Quote
It would indeed be faster to grab a square chunk out of the world around a turret and then only loop through the entities in that square chunk.

This would be what I would do.
An Area-Rectangle, if entities collide with it, there you go.

Offline pitbuller
« Reply #11 - Posted 2011-08-05 12:26:55 »

But how to do this effectively. Every unit need to be looped for updating those area rectangles.
Offline cylab

JGO Ninja


Medals: 43



« Reply #12 - Posted 2011-08-05 12:31:38 »

read my pseudocode, it handles both, grabbing a square chunk for tests and keeping it relatively cheap.

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

JGO Ninja


Medals: 26
Projects: 3
Exp: 6 years


One for all!


« Reply #13 - Posted 2011-08-05 13:01:39 »

How big would said sqaures be? So, each cycle, I'm checking all entities, if they collide with all the rectangles, until a match if found?

Nope, it's more like (pseudocode):
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  
38  
39  
40  
41  
42  
43  
44  
45  
46  
47  
48  
49  
50  
51  
52  
53  
54  
55  
56  
57  
init()
{
  cellSizeInBits = 6 // so a cell is 64x64
 cellSize = 1 << cellSizeInBits

  cols = gameArea.width / cellSize
  rows = gameArea.height / cellSize

  grid = new List[cols][rows]
}

(..)

updateGrid( movableEntities )
{
  foreach entity in movableEntities
  {
    oldCellX = entity.x >> cellSizeInBits
    oldCellY = entity.y >> cellSizeInBits

    updatePosition( entity )

    newCellX = entity.x >> cellSizeInBits
    newCellY = entity.y >> cellSizeInBits

    // only update grid if needed to avoid costly collection updates
   if( oldCellX!=newCellX || oldCellY!=newCellY )
    {
      grid[oldCellX][oldCellY].remove( entity )
      grid[newCellX][newCellY].add( entity )
    }
  }
}

(...)

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
}


That's quite clever. Cheesy What's ip with the bit shifting instead of division? Is it faster to do it this way, compared to not specifying the tiles in bits?

Offline Riven
« League of Dukes »

JGO Overlord


Medals: 781
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #14 - Posted 2011-08-05 13:07:14 »

1  
2  
3  
4  
5  
6  
    // only update grid if needed to avoid costly collection updates
   if( oldCellX!=newCellX || oldCellY!=newCellY )
    {
      grid[oldCellX][oldCellY].remove( entity )
      grid[newCellX][newCellY].add( entity )
    }


In my experience it is much faster to clear the grid cells and fill them again, as the remove(..) method is extremely slow compared to a lot of add(...) calls.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline Cero
« Reply #15 - Posted 2011-08-05 13:50:31 »

But how to do this effectively. Every unit need to be looped for updating those area rectangles.

In my game I have to iterate over all objects anyway each frame, but it's also not costly at all.

1  
2  
3  
4  
5  
6  
7  
8  
Rectangle one = new Rectangle(Util.getRandom(1, 9000), Util.getRandom(1, 9000), Util.getRandom(1, 9000),Util.getRandom(1, 9000));
Rectangle two   = new Rectangle(Util.getRandom(1, 9000), Util.getRandom(1, 9000), Util.getRandom(1, 9000),Util.getRandom(1, 9000));
long before = System.nanoTime();
for (int i=0;i<5000;i++)
{
   if (one.intersects(two)) ;
}
System.out.println((System.nanoTime()-before)/1000L+"us");

1  
905us

Most of the array will be null objects anyway. Well if you use arrays... I never use ArrayLists because I have better control with just arrays and seems faster aswell, no overhead.
Not even 1ms. Five THOUSAND objects.
I think its fast enough.

Offline Riven
« League of Dukes »

JGO Overlord


Medals: 781
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #16 - Posted 2011-08-05 14:02:26 »

I think you missed the case of the inner loop: which entities can see which entities.

In that case your brute-force loop just got 5000x slower: 4525ms

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline Cero
« Reply #17 - Posted 2011-08-05 14:22:58 »

I think you missed the case of the inner loop: which entities can see which entities.

In that case your brute-force loop just got 5000x slower: 4525ms

yea well, in case you really have to check every entity with every entity.
I would make towers a separate  array or something.
well for a RTS its not ideal, but 5000 objects seems high obviously.
And also, thats with 5000 objects which are not null. iterating over nulled objects is fast. First line of the loop is -> if != null

In starcraft 1 each could have (without taking over another race) build like what 200 units max.

But I agree, if you really have a lot of objects hanging around, and many of them need to check each other, then you have to do more low level performance thinking

Offline Riven
« League of Dukes »

JGO Overlord


Medals: 781
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #18 - Posted 2011-08-05 14:25:15 »

That's what this whole topic is about.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline Cero
« Reply #19 - Posted 2011-08-05 14:30:38 »

That's what this whole topic is about.

Quote
You have a 2D landscape, in a tower-defence something (RotT for instance) where towers shoot at nearby enemies.

Just saying, kinda doubt we are talking about more entities than starcraft would have, for example.
And then, these algorithms seem like overkill to me =P

Because, I mean... I'm sure most people of you are extremely skilled programmers, but adding complexity like that is always a risk, may cause bugs and requires total understanding and control.

Offline princec

JGO Kernel


Medals: 362
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #20 - Posted 2011-08-05 14:36:51 »

Well... I think, entity-wise, Starcraft and Revenge of the Titans are roughly similar - and I had to pull a few "tricks" like this to get Revenge running at 60fps. Even on my beast of an i7 in survival mode (which is when I first discovered the performance limitations of quadtrees)

Cas Smiley

Offline Riven
« League of Dukes »

JGO Overlord


Medals: 781
Projects: 4
Exp: 16 years


Hand over your head.


« Reply #21 - Posted 2011-08-05 14:39:38 »

Riiight. So let's say your extremely simplified code can be used as a baseline... (it can't be, but let's just assume it is)

If you scale it back to 200 units, it takes 7.24ms per frame. At 60Hz that'd be 434ms per second.

So to wrap up, even with only 200 units, you'd be wasting enormous amounts of CPU cycles. When you'd have 2 players with each 200 units, you'll spend 868ms per second purely on basic visibility checking, while it could easily be 5ms instead.

Hi, appreciate more people! Σ ♥ = ¾
Learn how to award medals... and work your way up the social rankings
Offline pitbuller
« Reply #22 - Posted 2011-08-05 15:17:44 »

My point was to Cero. Its same if you loop units and check if they "collide" with towers or loop towers and check if they "collide" with units. Same amount of method calls. Grid aproach is really nice but I would want see the benchmark where there is 200units with bruteforce vs grid aproach. Grid algorithm scale much better but what is break even point?
Offline Roquen
« Reply #23 - Posted 2011-08-05 15:20:11 »

Brute force is n2.
Offline pitbuller
« Reply #24 - Posted 2011-08-05 15:38:06 »

Still brute force is pretty fast with(only) 200 units and 200towers would be: 200*200 = 40000. Its hardly even costly. Was bored at work and I clocked that 10million range checks cost only 900ms.
Offline princec

JGO Kernel


Medals: 362
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #25 - Posted 2011-08-05 15:49:05 »

It all depends on just how crappy a machine you want it to run on and what else you need to accomplish inside a frame. But still, it's fun doing things the fastest way if you can Smiley Revenge ended up having upwards of 1000 entities in it which is half a million collision checks with brute force, definitely way too slow, versus maybe only about 200 or 300 (yes, literally) when using grid cells. In other words I turned the absolute bottleneck which dragged my game down to 10fps into something that was so fast I couldn't even measure it any more.

Cas Smiley

<edit>Out by a factor of 10 Wink

Offline Roquen
« Reply #26 - Posted 2011-08-05 15:52:03 »

10 million checks would only be ~3K objects.  The approaching 1 sec time you got would most likely explode in a real test due to cache trashing.
Offline pitbuller
« Reply #27 - Posted 2011-08-05 15:58:24 »

It all depends on just how crappy a machine you want it to run on and what else you need to accomplish inside a frame. But still, it's fun doing things the fastest way if you can Smiley Revenge ended up having upwards of 1000 entities in it which is half a million collision checks with brute force, definitely way too slow, versus maybe only about 200 or 300 (yes, literally) when using grid cells. In other words I turned the absolute bottleneck which dragged my game down to 10fps into something that was so fast I couldn't even measure it any more.

Cas Smiley

<edit>Out by a factor of 10 Wink

At our not yet published tower defence game units don't collide with each others so there is no problem. Map size is upper limit for towers anyway so there is only 300towers and maybe 500units max. So 150 000 collision check maximum. This is still so deadly fast and use only 15micro seconds with my benchmark. Still might need to do it with grid algorithm when we are doing android version.
Offline princec

JGO Kernel


Medals: 362
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #28 - Posted 2011-08-05 19:00:16 »

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

Offline cylab

JGO Ninja


Medals: 43



« Reply #29 - Posted 2011-08-05 19:00:45 »

1  
2  
3  
4  
5  
6  
    // only update grid if needed to avoid costly collection updates
   if( oldCellX!=newCellX || oldCellY!=newCellY )
    {
      grid[oldCellX][oldCellY].remove( entity )
      grid[newCellX][newCellY].add( entity )
    }


In my experience it is much faster to clear the grid cells and fill them again, as the remove(..) method is extremely slow compared to a lot of add(...) calls.

I silently assumed that this is dependent on cell transitions per frame, but thinking about it now, it seems unlikely that my approach is faster in a real world scenario. Maybe it could be made faster in certain cases when using a list implementation specially designed for fast add/removal with the help of storing the entities' index in the entity itself (for faster lookup on removal), but it probably might not be worth it...

Mathias - I Know What [you] Did Last Summer!
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.

CopyableCougar4 (15 views)
2014-08-22 19:31:30

atombrot (28 views)
2014-08-19 09:29:53

Tekkerue (25 views)
2014-08-16 06:45:27

Tekkerue (23 views)
2014-08-16 06:22:17

Tekkerue (15 views)
2014-08-16 06:20:21

Tekkerue (22 views)
2014-08-16 06:12:11

Rayexar (61 views)
2014-08-11 02:49:23

BurntPizza (39 views)
2014-08-09 21:09:32

BurntPizza (31 views)
2014-08-08 02:01:56

Norakomi (38 views)
2014-08-06 19:49:38
List of Learning Resources
by Longor1996
2014-08-16 10:40:00

List of Learning Resources
by SilverTiger
2014-08-05 19:33:27

Resources for WIP games
by CogWheelz
2014-08-01 16:20:17

Resources for WIP games
by CogWheelz
2014-08-01 16:19:50

List of Learning Resources
by SilverTiger
2014-07-31 16:29:50

List of Learning Resources
by SilverTiger
2014-07-31 16:26:06

List of Learning Resources
by SilverTiger
2014-07-31 11:54:12

HotSpot Options
by dleskov
2014-07-08 01:59:08
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!