Quadtree causing possible memory leak

(Adam Edney) #1

If your memory usage is increasing by 10 mb a second, is that a issue? so every 1 to 2 seconds, the memory needs to be cleared which affects frame rate. I made a quad tree collision detection and now working on improving performance, so i would like to stop the memory from keep increasing.

I am removing a lot of entities every frame because that how the quad tree work (around 100)

 objects.length = 0;
		for (var i:Number = 0; i < Quadtree_list.length ; i++)
		{
			if (Quadtree_list[i] != null)
			{
				Quadtree_list[i].clear();
				world.remove(Quadtree_list[i]);
				Quadtree_list[i] = null;
			}
		}

or is that not a issue, it could be something else?

(Jacob Albano) #2

I honestly don’t know how this is working at all. You clear the list, but then you pass the (empty) list to the remove function, and then you set it to null? I assume you’re reallocating the elements of Quadtree_list each frame, which would itself cause the memory usage to increase.

(Adam Edney) #3

Ok this what happens in it simplest form.

Quadtree_list hold a entities called “quad_tree” in each “quad_tree” it can hold up to 4 “quad_tree” and this happens up to 5 times so you can see there can be a lot of entities. This can only last for one frame, so every frame this will happen, so the code above removes all the “quad_tree” each frame. But for some reason it coursing a lot of memory leakage.

(Jacob Albano) #4

Okay, I see. I assumed you were using regular arrays.

So in this context it doesn’t make sense for your quadtree to be an Entity. It should just be a data structure that keeps track of other Entities. Adding, removing, and recreating all those instances every frame is what’s causing your leak.

(Adam Edney) #5

Well Quadtree_list is a vector, what should i do then? to help reduce memory usage? How do you make a data structure in this context?

Sorry for having three questions on one line lol.

(Jacob Albano) #6

A data structure is just a way of storing objects. Quadtrees, linked lists, graphs, etc, are all data structures.

Using a vector is fine; under the hood Actionscript treats it just the same as an array.

A question for you: I see you setting Quadtree_list[i] = null. How do you reset it later, so it’s not null? In order to keep memory usage down, you need to keep your quadtree allocation-free whenever possible. This means if your entities haven’t moved or had their numbers changed, you shouldn’t ever be using new <class>.

(Adam Edney) #7

I now made it like this.

	 public function clear():void
	 {
		objects.length = 0;
		for (var i:Number = 0; i < Quadtree_list.length ; i++)
		{
			if (Quadtree_list[i] != null)
			{
				Quadtree_list[i].clear();
			}
		}
	 }

so now I’m do not need to make a “quad_tree” every frame, which help reduce memory increase by over 50% but it still leaking.

I found out that this is leaking a lot / all the memory. its the collision check, so it checks if two rectangles are colliding.

for (var x:int = 1 ; x < returnObjects.length; x++)
{
if (object_list[i] != returnObjects[x])
{
var length_X:Number = Math.abs(object_list[i].x - returnObjects[x].x);
var length_Y:Number = Math.abs(object_list[i].y - returnObjects[x].y);
var half_width_box1:Number = object_list[i].width*0.5;
var half_width_box2:Number = returnObjects[x].width*0.5;
						 
var half_height_box1:Number = object_list[i].height*0.5;
var half_height_box2:Number = returnObjects[x].height*0.5;
						 
var gap_between_boxes_X:Number = length_X - half_width_box1 - half_width_box2;
var gap_between_boxes_Y:Number = length_Y - half_height_box1 - half_height_box2;

if (gap_between_boxes_X <= 0 && gap_between_boxes_Y <= 0 )
{ 
object_list[i].hit = true; returnObjects[x].hit = true; 
}
}
}

What would be the main reason, the temporary variable or just because it needs a lot or memory to work it out? Can i streamline this collision check?

But thanks for the help so far, you have been great.

(Jacob Albano) #8

There’s nothing there that should be causing a leak. I’m afraid I don’t know what to tell you at this point.

(MartĂ­ Angelats i Ribera) #9

There are different points here:

  • How many boxes are you using (check that you don’t have a bug that add more boxes than the necessaries. This could cause this memory leak).
  • You don’t need to use all this mathematic operations if they are rectangles (see code below).
  • Why the loop starts with the 1 instead of the 0?

The first one is the onethat could really create a big trouble.

The (pseudo)code that i was talking (seems bigger but the most part of the operations are using booleans what’s faster):

public function colliding(box1x:Number, box1y:Number, box1Width:Number, box1Height:Number, box2x:Number, box2y:Number, box2Width:Number, box2Height:Number):Boolean
{
    var box1X2:Number = box1X + box1Width;
    var box1Y2:Number = box1Y + box1Height;
    var box2X2:Number = box2X + box2Width;
    var box2Y2:Number = box2Y + box2Height;
    
    return ((box1X > box2X && box1X < box2X2) || (box1X2 > box2X && box1X2 < box2X2))   &&   ((box1Y > box2Y && box1Y < box2Y2)||(box1Y2 > box2Y && box1Y2 < box2Y2));
}

If you’re using Rectangles:

public function colliding(box1:Rectangle, box2:Rectangle):Boolean
{
    var box1X2:Number = box1.x + box1.width;
    var box1Y2:Number = box1.y + box1.height;
    var box2X2:Number = box2.x + box2.width;
    var box2Y2:Number = box2.y + box2.height;
    
    return ((box1.x > box2.x && box1.x < box2X2) || (box1X2 > box2.x && box1X2 < box2X2))   &&   ((box1.y > box2.y && box1.y < box2Y2)||(box1Y2 > box2.y && box1Y2 < box2Y2));
}

PD: Could be great to be able to have a look at the full project. Maybe the problem is not in this segment of code.