Avoiding looping through everything

Newbie & Debugging Questions
#41

I don’t know, but, why would

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

be slow, even if its done many times =0

#42

That wouldn’t, if that’s the implementation of it :stuck_out_tongue: Math is just famous for it being sloow. :-X

#43

Because of branch mispredition.

#44

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.

#45

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

#46

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 and that would be fine, but when doing this:


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

it fails :emo:
Is there really no way around doing


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

#47

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

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

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

#48

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

#49

You need to refine your question.

#50

Suppose there is an object like in this image.

How to add the same object to both the cells?

#51

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


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:



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.

#52

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

#53

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

#54

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.

#55

Pay attention that

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!

#56

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.

#57

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.

#58

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.

#59

How about reduce the tiles’ size and use Manhattan? :confused:

#60

In the limit, you’d be fine!