What are the ways to optimize game?

Game Mechanics
#1

I have been using Quadtrees since the brute force is pretty slow in a platform game I was making. I’m checking in this loop.


for (Entity entity : EntityList)
{
    entity.update();
    entity.move();
    for (Entity entity2 : EntityList)
    {
        if (isCollision(entity, entity2))
        {
            entity.processCollision(entity2);
        }
    }
}

It almost got 400000 checks and is somewhat slow. Then I had kept a flag collisionListener in the entity and checked for collisions only for the entities having that flag set to true. This reduced the collision checks to 238 since I’m only checking the collisions on the player and enemies. This raised my fps about 10 but my CPU usage is 68%. To minimize this, I changed my game loop to this.


long now = getCurrentTime();
long gameTime = getCurrentTime();
long updateTime = 1000/30;               // Cheat to run at 30 ups
long maxFrameSkip = 5;

int frame = 0;
while(game.running)
{
    frame = 0;
    while(now + updateTime > gameTime && frame <= maxFrameSkip)
    {
        updateGame();
        gameTime += updateTime;
        frame++;
    }
    displayGame();
}

But the CPU consumption never decreased. So implemented a QuadTree from Quick Tip: Use Quadtrees to Detect Likely Collisions in 2D Space at TutsPlus. The collision checks are now 19 but the CPU consumption increased by one percent and the fps dropped by a bit.

The fps is ranging from 120-141. I know it’s great but it’s just at 38 on my old laptop running XP. What are the changes I need?

To test, I’ve made a prototype of it using GameMaker and it’s using just 13% of my CPU and at the same time is doubly fast. I am trying to meet it.

Thanks in advance for help.

#2

Maybe you could check for all entities together at the start of the update, and store the collisions.
Then the entities could just check to see if they are colliding with anything through the pre-tested collisions.

Edit: I read the code again. You are testing each pair of entities twice.

Edit 2: Hogging CPU time (by not calling Thread.sleep()) makes CPU usage MORE.

#3

Why my busy loop is busy?

Also profile before optimizing. The problem propably isn’t collision code and if it is then show some code.

#4

Stop using a quadtree and use a cell-based collision manager instead. Also don’t use nested iterators like that, and also you’re doing twice as many collision tests as you need to (if you know A hits B there’s no need to subsequently test for B hitting A).

Cas :slight_smile:

#5

for (int i=0; i<list.size(); i++) is much faster than iterating per object.

#6

Well, it’s 10% faster, which isn’t going to solve this particular problem completely, but every little helps.

Cas :slight_smile:

#7

@HeroesGraveDev

Thanks. Adding Thread.sleep(10) reduced the cpu usage to 56%. Can you say how can I calculate the sleep time on a pc so my game runs at the minimum update rate?

@Cas,

Could you show me some tutorial on making grid collision system? I’m currently trying with this. (psuedocode)


class Grid {

    ArrayList<GObject>[,] grid = null;

    int rows, cols;

    Grid (int width, int height, int cellsize)
    {
        rows = height/cellsize;
        cols = width/cellsize;
        grid = new ArrayList<GObject>[cols, rows];
    }

    insert (GObject obj)
    {
        // stuck here
    }

}

I need to get the indices of every cell the object is in.

#8

The fastest data-structure I know of for iterating over is a raw Array (and using an int index into it). I don’t know if it would be any faster than an ArrayList but it might be worth trying out and then profiling.

#9

Well, that’s basically correct so far. Every time you put something in the grid, you need to work out which cells it occupies and add it to each of the corresponding cell’s arraylists.

Then when it comes to detecting collisions you check each arraylist that has > 1 entry and only perform collision tests between each one of those. You need to ensure that for any given entity pair that you register a collision on that you only register the collision once; so stash each normalised collision pair in a Set and don’t process it again if you find it there already. Also make collision action commutative:


Set<Pair<GObject, GObject>> collisions = new HashSet<>();
Pair<GObject, GObject> temp = new Pair<>();
for (int i = 0; i < cell.size(); i ++) {
	GObject a = cell.get(i);
	for (int j = i + 1; j < cell.size(); j ++) {
		GObject b = cell.get(j);
		if (a.collidesWith(b)) {
			temp.set(a, b);
			if (collisions.contains(temp)) {
				// Already processed this collision
				continue;
			}
			collisions.add(temp);
			temp = new Pair<>();
			a.onCollisionWith(b);
			b.onCollisionWith(a);
		}
	}
}

Obviously you can optimise out a couple of object allocations there but you get the gist.

Cas :slight_smile:

#10

Got a problem in calculating the indices.


indices.Clear();
int numx = (rect.Width / 64);
int numy = (rect.Height / 64);
int x = rect.X / 64;
int y = rect.Y / 64;
x = Math.Max(x, 0);
x = Math.Min(x, cols-1);
y = Math.Max(y, 0);
y = Math.Min(y, rows-1);
// original index
indices.Add(new Point(x, y));
// extended indices
for (int nx=1; nx<numx; nx++)
{
	indices.Add(new Point(nx + x, y));
}
for (int ny=1; ny<numy; ny++)
{
	indices.Add(new Point(x, ny + y));
}

This isn’t working. The collisions aren’t detected.

#11

Int rounds down, if you are checking for intersection it will never happen. Safest bet is to round up after inting (+1 instead of expensive Math.round) since this is just used for collision testing and not actual rendering. Unless your gamecode requires 1 pixel resolution on the collision-testing.

#12

Thanks for your support guys. I’ve got it working. The CPU usage is now only 37% and on my old laptop 42%. Getting an FPS of 121-150.