Idea for a Better Broadphase

Topics: Developer Forum, User Forum
May 25, 2010 at 1:44 PM
Edited May 26, 2010 at 1:27 PM

I've had a look on you SelectiveSweep Broad-Phase Collision and i noticed that you use a quicksort (list.sort) algorith with a comparer. Normally it's better to have an InsertionSort because it's way faster with nearly sorted Lists, which i excpect the _xStubs and _yStubs List to be.

I tested it out and - with quickSort I got a usage of 0,17 of the BroadPhase and somthing between 0,98 and 1,3 in the NarrowPhase - with InsertionSort i got a BroadPhase usage of 0,11 and the same NarrowPhase usage

I testet it with around 100 bodies and some complex ones -> in my case that ment 140 fps instead of 130 fps

Heres the new code of SelectiveSweep:

public void Update()

{

InternalUpdate();

DetectInternal(ShouldDoX());

InsertSort(_xStubs, _comparer);

InsertSort(_yStubs, _comparer);

}

 

private static void InsertSort(IList<Stub> list, IComparer<Stub> stubComparer)

{

int i, j;

for (i = 1; i < list.Count; i++)

{ Stub value = list[i];

j = i - 1;

while ((j >= 0) && stubComparer.Compare(list[j], value) > 0)

{

list[j + 1] = list[j];

j--;

}

list[j + 1] = value;

}

}

 

As you can see, I used the same Comparer but only changed _xStubs.Sort(_comparer) to InsertionSort(_xStubs, _comparer) to call my method for the InsertionSort! (Same with _yStubs of course :) )

I hope this helps you in some way ;-)

Additional Notes: I noticed a tiny thing: When you remove bodies in runtime the physics simulation is very likeley to become instable - so it's better to just disable the bodies with setting Enabled to false, But the problem is, that if you have an Inactivity controller, they get enabled again, which they should not. So what I basically did - i renamed enabled to active (so the inactivityController) now sets active to true or false And i created a Field called "enabled" - if thats set to false, the objects is like a removed one (and i of course updated all the checks to ...)

So that's it for now. I want to congratulate you guys to near perfect Engine, which is easy to use and understand. I'm looking forward to the next release :)

Yours Sincerly

Coordinator
May 29, 2010 at 9:08 PM

The QuickSort algorithm implementation in .net is quite heavy for high-performance applications like FPE. It would not surprise me a bit that an insertion sort would do better i almost all cases.

Could you wrap this change in a patch and upload it to our patch section?