Java-Gaming.org    
Featured games (81)
games approved by the League of Dukes
Games in Showcase (498)
Games in Android Showcase (115)
games submitted by our members
Games in WIP (563)
games currently in development
News: Read the Java Gaming Resources, or peek at the official Java tutorials
 
    Home     Help   Search   Login   Register   
Pages: [1]
  ignore  |  Print  
  What are the ways to optimize game?  (Read 1664 times)
0 Members and 1 Guest are viewing this topic.
Offline SHC
« Posted 2013-04-09 05:54:10 »

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.

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
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.

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
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.

Offline HeroesGraveDev

JGO Kernel


Medals: 254
Projects: 11
Exp: 2 years


┬─┬ノ(ಠ_ಠノ)(╯°□°)╯︵ ┻━┻


« Reply #1 - Posted 2013-04-09 06:40:26 »

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.

Offline pitbuller
« Reply #2 - Posted 2013-04-09 08:56:35 »

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.
Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline princec

JGO Kernel


Medals: 380
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #3 - Posted 2013-04-09 10:01:52 »

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 Smiley

Offline brollysan

Junior Member


Medals: 1



« Reply #4 - Posted 2013-04-09 13:30:13 »

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

JGO Kernel


Medals: 380
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #5 - Posted 2013-04-09 13:39:14 »

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

Cas Smiley

Offline SHC
« Reply #6 - Posted 2013-04-09 13:45:33 »

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

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
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.

Offline loom_weaver

JGO Coder


Medals: 17



« Reply #7 - Posted 2013-04-09 13:56:41 »

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

JGO Kernel


Medals: 380
Projects: 3
Exp: 16 years


Eh? Who? What? ... Me?


« Reply #8 - Posted 2013-04-09 13:59:56 »

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:

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
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 Smiley

Offline SHC
« Reply #9 - Posted 2013-04-09 14:53:33 »

Got a problem in calculating the indices.

1  
2  
3  
4  
5  
6  
7  
8  
9  
10  
11  
12  
13  
14  
15  
16  
17  
18  
19  
20  
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.

Games published by our own members! Check 'em out!
Legends of Yore - The Casual Retro Roguelike
Offline brollysan

Junior Member


Medals: 1



« Reply #10 - Posted 2013-04-09 19:30:39 »

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.
Offline SHC
« Reply #11 - Posted 2013-04-10 06:05:52 »

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.

Pages: [1]
  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.

radar3301 (12 views)
2014-09-21 23:33:17

BurntPizza (30 views)
2014-09-21 02:42:18

BurntPizza (20 views)
2014-09-21 01:30:30

moogie (20 views)
2014-09-21 00:26:15

UprightPath (28 views)
2014-09-20 20:14:06

BurntPizza (32 views)
2014-09-19 03:14:18

Dwinin (48 views)
2014-09-12 09:08:26

Norakomi (74 views)
2014-09-10 13:57:51

TehJavaDev (102 views)
2014-09-10 06:39:09

Tekkerue (50 views)
2014-09-09 02:24:56
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!