Author Topic: Has anyone fixed FlxQuadTree yet?  (Read 5018 times)

moly

  • Member
  • **
  • Posts: 18
  • Karma: +0/-0
    • View Profile
Has anyone fixed FlxQuadTree yet?
« on: Wed, Aug 22, 2012 »
I'm currently working on some mobile stuff with flixel, and I've found that FlxQuadTree is causing serious performance issues. FlxG.overlap is creating a new FlxQuadTree every frame, which seems to create several new FlxQuadTrees itself, which all create multiple new FlxLists. This is causing the garbage collector to go crazy and slow the whole app down.

I tried googling the problem and came across this: http://coldconstructs.com/2011/03/memory-management-in-flixel/
He's also noticed that FlxQuadTree is bad, but unfortunately doesn't provide a solution except to "build a persistent static grid".

Does anyone know either:
a) How to build a persistent static grid in flixel or
b) How to prevent FlxQuadTree from creating so many instances every frame?

ratalaika

  • Member
  • **
  • Posts: 23
  • Karma: +0/-0
    • View Profile
Re: Has anyone fixed FlxQuadTree yet?
« Reply #1 on: Wed, Aug 22, 2012 »
If you are using Android I recommend you to check -> http://forums.flixel.org/index.php/topic,6190.0.html

Any way I port the FlxQuadTree and it do not give me that kind of error :S.

Maybe you could check with a previous version of flixel...

moly

  • Member
  • **
  • Posts: 18
  • Karma: +0/-0
    • View Profile
Re: Has anyone fixed FlxQuadTree yet?
« Reply #2 on: Sun, Aug 26, 2012 »
I think I've solved this myself. I went looking through the flixel-ios code on github and found this: https://github.com/ericjohnson/canabalt-ios/blob/master/flixel-ios/src/Flixel/FlxQuadTree.m

While I don't know Objective-C, the code near the top of the file seems to be object-pooling related. I decided then to try and implement something similar in the Flash version. First I created a very basic object pool class:

Code: [Select]
package org.flixel.system
{
    /**
     * ...
     * @author moly
     */
    internal class ObjectPool
    {
        protected var _objects:Array;
        protected var _objectClass:Class;

        public function ObjectPool(ObjectClass:Class)
        {
            _objectClass = ObjectClass;
            _objects = new Array();
        }

        public function getNew():*
        {
            var object:* = null;
            if (_objects.length > 0)
                object = _objects.pop();
            else
                object = new _objectClass();
            return object;
        }

        public function disposeObject(OldObject:Object):void
        {
            _objects.push(OldObject);
        }
    }
}

Then I altered FlxQuadTree and FlxList to use the new class: https://gist.github.com/3479809

The main changes are:
FlxQuadTree and FlxList both have their own pool.
When a FlxQuadTree or FlxList is destroyed, it gets added to its pool so that it can be resused.
If FlxQuadTree wants to create a new object, it gets it from the relevant pool instead.

I also modified FlxG::overlap() like so:
Code: [Select]
static public function overlap(ObjectOrGroup1:FlxBasic=null,ObjectOrGroup2:FlxBasic=null,NotifyCallback:Function=null,ProcessCallback:Function=null):Boolean
{
    if(ObjectOrGroup1 == null)
        ObjectOrGroup1 = FlxG.state;
    if(ObjectOrGroup2 === ObjectOrGroup1)
        ObjectOrGroup2 = null;

    FlxQuadTree.divisions = FlxG.worldDivisions;
    var quadTree:FlxQuadTree = FlxQuadTree.quadTreePool.getNew();
    quadTree.init(FlxG.worldBounds.x,FlxG.worldBounds.y,FlxG.worldBounds.width,FlxG.worldBounds.height);
    quadTree.load(ObjectOrGroup1,ObjectOrGroup2,NotifyCallback,ProcessCallback);
    var result:Boolean = quadTree.execute();
    quadTree.destroy();
    return result;
}

To test, I modified the particles demo from the flixel features page to use 300 particles and to check for overlaps between all of them. On my laptop I managed around 40fps for standard flixel and 55fps for my modified version with object pooling, which is pretty good. As you'd expect, the higher the number of overlap checks the more noticeable the difference; I tested a number of simpler games and they didn't seem to improve as much.

Hopefully this is useful to someone else. Let me know if anyone finds any problems with anything here.

Charlie Riot

  • Highly Super
  • Member
  • **
  • Posts: 69
  • Karma: +0/-0
    • View Profile
Re: Has anyone fixed FlxQuadTree yet?
« Reply #3 on: Sun, Aug 26, 2012 »
You are incredible! I have implemented this into my rather large project (10,000+ lines, 20mbs) and received a huge performance boost, particularly with emitters. I was close to having to cut-down an entire section of my game - a forest with floating particle-pollen drifting through the air - but now that isn't necessary. Thank you so much!

EDIT: I should also mention that the loading time between levels has increased slightly, but it's worth it.
« Last Edit: Sun, Aug 26, 2012 by Charlie Riot »

LaughingLeader

  • Member
  • **
  • Posts: 64
  • Karma: +0/-0
    • View Profile
    • LaughingLeader Blog
Re: Has anyone fixed FlxQuadTree yet?
« Reply #4 on: Wed, Aug 29, 2012 »
[Great stuff here]

Awesome work. I'm currently implementing it into my own project, and hoping to see some nice performance boosts.

I see you've changed overlap to work in the new fixes, but what about overlapTileMap? Would the changes in overlapTileMap be pretty much the same as what you changed in overlap?

Just wanted to check with you in case you modified overlapTileMap too, and forgot to mention it.

Thanks.

moly

  • Member
  • **
  • Posts: 18
  • Karma: +0/-0
    • View Profile
Re: Has anyone fixed FlxQuadTree yet?
« Reply #5 on: Wed, Aug 29, 2012 »
I can't find any function named "overlapTileMap" in flixel v2.55. Could you be more specific about what code you are referring to?

zaphod

  • Member
  • **
  • Posts: 25
  • Karma: +0/-0
    • View Profile
Re: Has anyone fixed FlxQuadTree yet?
« Reply #6 on: Wed, Aug 29, 2012 »
I've done this kind of optimization in my fork: https://github.com/Beeblerox/flixel (there are couple other fixes and improvements mentioned on forum)
This optimization affected FlxObject, FlxQuadTree, FlxList and FlxG classes so engine can reuse lists, quadtrees and rectangles without constantly creating them.

LaughingLeader

  • Member
  • **
  • Posts: 64
  • Karma: +0/-0
    • View Profile
    • LaughingLeader Blog
Re: Has anyone fixed FlxQuadTree yet?
« Reply #7 on: Wed, Aug 29, 2012 »
I can't find any function named "overlapTileMap" in flixel v2.55. Could you be more specific about what code you are referring to?

I'm glad you said that actually, as I'm wondering the same thing now. I'm not sure if it's something from a fix I found months ago, or just something random I was experimenting with (also months ago). Either way, I don't appear to be using it, and it seems to be from from my old days of not commenting code, so it's gone now.

Sorry about that.  :-[

moly

  • Member
  • **
  • Posts: 18
  • Karma: +0/-0
    • View Profile
Re: Has anyone fixed FlxQuadTree yet?
« Reply #8 on: Wed, Aug 29, 2012 »
I've done this kind of optimization in my fork: https://github.com/Beeblerox/flixel (there are couple other fixes and improvements mentioned on forum)
This optimization affected FlxObject, FlxQuadTree, FlxList and FlxG classes so engine can reuse lists, quadtrees and rectangles without constantly creating them.

It looks like your recycle function is iterating through the entire pool until if finds an object with exists == false, which will become very slow as the pool increases in size. My code only stores destroyed objects in the pool, so you can just fetch the first item off the top.

Gama11

  • Contributor
  • ****
  • Posts: 390
  • Karma: +0/-0
    • View Profile
Re: Has anyone fixed FlxQuadTree yet?
« Reply #9 on: Thu, Sep 6, 2012 »
I've implemented moly's fix as well - my project isn't all that large, but it has a fair amount of sprites and overlaps. Not sure if that boosted the performance all that much - I tested it on my Android phone and got a *slightly* higher framerate (about 2 FPS). Just did that because I knew mobile (in-browser) performance is terrible and won't cap, so, yeah. I guess it'll help players with olders PC's a bit.

Anyway, thx a lot for this fix! I feel like it should be promoted a bit more, so more ppl can actually see and use it.

CrazySam

  • Member
  • **
  • Posts: 7
  • Karma: +0/-0
    • View Profile
Re: Has anyone fixed FlxQuadTree yet?
« Reply #10 on: Mon, Sep 24, 2012 »
It looks like your recycle function is iterating through the entire pool until if finds an object with exists == false, which will become very slow as the pool increases in size. My code only stores destroyed objects in the pool, so you can just fetch the first item off the top.

It's a little awkward, but the issue you mention would not occur in Zaphod's fork. The only place FlxQuadTrees are used within the engine is in FlxG.overlaps, like so:

Code: [Select]
var quadTree:FlxQuadTree = FlxQuadTree.recycle(FlxG.worldBounds.x, FlxG.worldBounds.y, FlxG.worldBounds.width, FlxG.worldBounds.height);
quadTree.load(ObjectOrGroup1, ObjectOrGroup2, NotifyCallback, ProcessCallback);
var result:Bool = quadTree.execute();
quadTree.destroy();

So we first call recycle, which either creates a new tree, or returns the first tree that has "exist==false" (and calls FlxQuadTree.reset(...), which sets "exist=true"). And at the end we call "destroy()" on the tree, which sets "exist=false". So in reality, that loop will always break during the first iteration when we call it from overlap (the FlxQuadTree.reset(...) recycles some more trees, so the while loop has a legitimate purpose).

It's arguable whether pushing and popping objects from an array when they're created / destroyed is more efficient than adding them once to the array and checking a bool before recycling the pooled object. But now that I understand what's going on, I like Zaphods implementation better. I just wish he also provided an implementation of FlxObjectPool for general use.
« Last Edit: Mon, Sep 24, 2012 by CrazySam »

zaphod

  • Member
  • **
  • Posts: 25
  • Karma: +0/-0
    • View Profile
Re: Has anyone fixed FlxQuadTree yet?
« Reply #11 on: Thu, Sep 27, 2012 »
@crazysam: it isn't that hard to write such a class. So I'll do it :) And thanks for idea!

moly

  • Member
  • **
  • Posts: 18
  • Karma: +0/-0
    • View Profile
Re: Has anyone fixed FlxQuadTree yet?
« Reply #12 on: Fri, Sep 28, 2012 »
It's a little awkward, but the issue you mention would not occur in Zaphod's fork. The only place FlxQuadTrees are used within the engine is in FlxG.overlaps, like so:

Multiple FlxQuadTree's are also created within FlxQuadTree::addObject. You can check for yourself that issue does occur in his fork, add a trace to FlxQuadTreeCache::recycle:

Code: [Select]
public function recycle(x:Number, y:Number, width:Number, height:Number, parent:FlxQuadTree = null):FlxQuadTree
{
    var tree:FlxQuadTree;
    var i:int = 0;

    while (i < _length)
    {
        tree = _trees[i] as FlxQuadTree;
        if (tree.exists == false)
        {
            tree.reset(x, y, width, height, parent);
            trace(i);
            return tree;
        }
        i++;
    }

    return add(new FlxQuadTree(x, y, width, height, parent));
}

I tried this on the Mode demo and at times it took up to 80 iterations to find a tree to recycle. Zaphod's pooling classes are highly inefficient for this purpose.

CrazySam

  • Member
  • **
  • Posts: 7
  • Karma: +0/-0
    • View Profile
Re: Has anyone fixed FlxQuadTree yet?
« Reply #13 on: Sat, Sep 29, 2012 »
Can't argue with a man that does his homework and tests the code  :P 

Thanks for taking the time and explaining, I submitted a pull request for a more efficient pooling mechanism (based on simple Linked Lists) to the HaxeFlixel engine. You can see it here.

Performance gains weren't very substantial from what I could tell (no way to get accurate perf measurements easily on Android, but I saw a 2 fps difference in BunnyMark).