Avoiding looping through everything

Newbie & Debugging Questions
#1

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 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! 8)

#2

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.

#3

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.

#4

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.

#5

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 :slight_smile:

#6

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?


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;
}
#7

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?

#8

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:


	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;
	}
#9

Nope, it’s more like (pseudocode):


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
}
#10

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.

#11

[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.
[/quote]
This would be what I would do.
An Area-Rectangle, if entities collide with it, there you go.

#12

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

#13

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

#14

That’s quite clever. :smiley: 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?

#15

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.

#16

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

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");

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.

#17

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

#18

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

#19

That’s what this whole topic is about.

#20

[quote]You have a 2D landscape, in a tower-defence something (RotT for instance) where towers shoot at nearby enemies.
[/quote]
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.