Hello my name is Lefteris Stamatogiannakis (estama) and this is my first blog post :). This is going to be a technical blog post, so don’t feel bad if you are not able to follow it.
BeamNG’s physics simulation core, has to be extremely efficient. The time tolerances that we have are extreme. For example, every physics simulation cycle of the core, must be completed in less than 0.5 ms (1 ms is a thousandth of a second). In that time, we need to do all the physics calculations, collision detection, synchronization of the vehicles that run in different CPU processors, communicate with the various LUA subsystems and so on.
One of the things that we have been doing during the last months, is that we have been overhauling the physics core, fixing and optimizing it. A part of the physics core that has been improved, is an algorithm that dates from 1961, quickselect from C. A. R Hoare. There are several variations of quickselect, but the most used one is the median-of-3 variation. It is the workhorse of the selection algorithms.
For our work, i’ve started from N. Wirth’s selection algorithm , with the MODIFIND optimization from Vladimir Zabrodsky . Then the median-of-3 pivot selection was added, and finally some more work was done to the final steps of the partitioning part of the algorithm. The end result is an algorithm that is 20-30% faster than the median-of-3 quickselect.
As selection algorithms are often used in various domains (e.g. statistics, image processing), we’ve decided to share the implementation of our basic selection algorithm (imaginably named “LefSelect”).
Below is the source code, in C, of the algorithm:
#define F_SWAP(a,b) {float temp=(a); (a)=(b); (b)=temp;}
/* Note: The code needs more than 2 elements to work, and k should
not be at the extremes of the array */
float lefselect(float a[], const int n, const int k) {
int l = 0, m = n-1, i = l, j = m;
float x;
while (l < m) {
if (a[k] < a[i]) F_SWAP(a[i], a[k]);
if (a[j] < a[i]) F_SWAP(a[i], a[j]);
if (a[j] < a[k]) F_SWAP(a[k], a[j]);
x = a[k];
while (j > k & i < k) {
do i++; while (a[i] < x);
do j--; while (a[j] > x);
F_SWAP(a[i], a[j]);
}
i++; j--;
if (j < k) {
while (a[i] < x) i++;
l = i; j = m;
}
if (k < i) {
while (x < a[j]) j--;
m = j; i = l;
}
}
return a[k];
}
In BeamNG’s physics core, we use a more optimized algorithm (BeamSelect) that is even faster.
In the table below, you can see the performance of the three algorithms (QuickSelect, LefSelect, BeamSelect):
