User:Wormbo/Random useful code snippets

On this page I will post various code snippets that are too useful to keep them to myself. Some of these probably deserve their own article pages with background information, and maybe I'll create them at some point.

Linear search one-liner

The most simple way to search for a value in an array is linear search. The following implementation is (almost) a one-liner that works on all arrays, sorted or not.

local int i;
 
i = A.Length;
do {} until (--i < 0 || A[i] == Value);

Success is indicated by i >= 0, failure by i == -1 or i == INDEX_NONE in UE3.

If the array is sorted and has more than just a few elements, you should consider using binary search instead.

Binary Search

The following very simply piece of code implements the binary search algorithm with deferred detection of equality, looking for Value in array A. If Value isn't in A, the code returns the index where Value would have to be inserted.

local int Low, High, Middle;
 
Low = 0;
High = A.Length;
while (Low < High) {
  Middle = (High + Low) / 2;
  if (A[Middle] < Value)
    Low = Middle + 1;
  else
    High = Middle;
}

As you can see, the advantage here is that each loop iteration only performs a single less-than comparison between the search value and an array element.

So, why would you combine the equality and greater-than comparisons and give up early abort? Quite simple: The equality comparison would fail most of the time anyway, so it doesn't actually give that much of an advantage, considering binary search only has an overall worst case time complexity of O(log2n). And, well, you only need to implement a less-than comparison for custom data types as opposed to less-then and greater-than. Here "less than" could actually mean "greater than" if the array is sorted in descending order or anything else, as long as it is a strict total order on the possible values for the array's type.

To figure out whether you found the value or not, an additional comparison is required:

if (Low < A.Length && A[Low] == Value)
  // found it
else
  // not found

You can assume that Low always is a valid insert index less than or equal to A.Length, so A.Insert(Low, 1); A[Low] = Value; (or A.InsertItem(Low, Value); in UE3) will always work correctly.

It is guaranteed that Low < A.Length implies A[Low] >= Value and Low > 0 implies A[Low-1] < Value. That means if you want to remove all values less than Value, you can simply do A.Remove(0, Low). To remove all values greater than or equal to Value, you use A.Remove(Low, A.Length - Low).

To find the first index with a value greater than Value, you just need a tiny modification:

local int Low, High, Middle;
 
Low = 0;
High = A.Length;
while (Low < High) {
  Middle = (High + Low) / 2;
  if (A[Middle] <= Value)
    Low = Middle + 1;
  else
    High = Middle;
}

This version can be used if you want to ensure that new instances of values considered as "equal" are inserted after all previous instances, whereas the other version of the algorithm finds an insert location before all other equal instances.

Again you can assume that Low always is a valid insert index less than or equal to A.Length. It is guaranteed that Low < A.Length implies A[Low] > Value and Low > 0 implies A[Low-1] <= Value. That means if you want to remove all values less than or equal to Value, you can simply do A.Remove(0, Low). To remove all values greater than Value, you use A.Remove(Low, A.Length - Low). Note how the "or equal to" now is part of the other side of the array.

Finding common string prefix

For incremental encoding you need to find the common prefix of two strings. Usually you'd do that by comparing corresponding characters of both strings, starting from the front, but UnrealScript is quite inefficient for that. I found that, at least in UT2004, you could use the StrCmp() function to compare string prefixes. Now you only need to find the largest prefix length at which both string starts are still equal. Technically this is a searching operation and the easy way to do it would be a linear search. But if there's a reasonably good chance the strings have large common parts, you could even abuse binary search for this. The following code snippet finds the largest common prefix length of strings A and B:

local int Low, High, Middle;
 
Low = 0;
High = Min(Len(A), Len(B));
while (Low < High) {
  Middle = (High + Low) / 2;
  if (StrCmp(A, B, Middle) == 0)
    Low = Middle + 1;
  else
    High = Middle;
}

Looks scary? I hope so. ;-)

Collapsing whitespace

This code will remove leading and trailing whitespace from a string and simultaneously collapse any sequence of space and tab characters into a single space:

static final function string CollapseAndTrimWhitespace(string S)
{
  S = " " $ Repl(S, Chr(9), " ") $ " "; // replace tabs with spaces and enclose in space chars for collapsing
  while (InStr(S, "  ") != -1) { // need whitespace collapsing?
    S = Repl(S, "  ", " "); // collapse two adjacent spaces to a single space
  }
  return Mid(S, 1, Len(S) - 2); // remove enclosing space chars
}

I know, InStr() and Repl() are really linear time operations, causing the algorithm to be something like O(n*logn). But as usual UnrealScript's slowness adds a high constant part to them, essentially making them constant time for reasonably short strings (up to a few hundred characters), and the whole function sort-of O(logn).

Integer modulo operator

The modulo operator % in UnrealScript is only defined for float operands, which can cause bad rounding errors if you use it with large int values. The following code overloads the modulo operator for int values:

static final operator(18) int % (int A, int B)
{
  return A - (A / B) * B;
}

This has similar semantics as the float modulo operator, i.e. it may return negative values if you pass in negative operands. Note that (A/B)*B is not the same as A due to integer division dropping any potential remainder.

ArcTan function

Need the standard one-parameter version of the atan function and your version of the game only provides the two-parameter version? Try this one:

static final function float ArcTan(float A)
{
  return ATan(1, A);
}

Vector magic

Distance of point from line

This one might be useful e.g. for determining by how much a shot missed a target:

dist = VSize(Normal(ShotDir) cross (TargetLocation - ShotStart));

This formula relies on the fact that the length of the cross product is the product of the two vector lengths times the sine of the angle between them. Note that the resulting vector of the cross product itself is actually orthogonal to both the shot direction and the vector pointing from the shot start to the target direction.

In front or behind?

You'd probably use this one in combination with the above to figure out whether the target was actually shot at:

bInFront = (ShotDir dot (TargetLocation - ShotStart)) > 0;

If you normalize both vectors, the dot product actually gives you the cosine of the angle between them. If you don't, the cosine is multiplied by the product of the two vectors' lengths. Either way, the cosine is positive for angles smaller than 90° and negative for angles greater than 90°.

Closest point on a line

If you want to know the point on a line that is closest to some other point (usually) not on the line, you need to project the other point onto the line:

ClosestPoint = ShotStart + Normal(ShotDir) * (Normal(ShotDir) dot (TargetLocation - ShotStart));

You can obviously skip normalization if the shot direction already is a unit vector.

Vector to Rotator alternative

The following code converts a vector to a rotator. Instead of the yaw-then-pitch order of the vector->rotator typecast, this conversion sort-of applies pitch-then-yaw order. Short explanation:

• The typecast calculates a rotator that gets from vect(1,0,0) to the target direction by first rotating around the vertical axis, then around the resulting left/right axis.
• This conversion calculates another rotator that gets from vect(1,0,0) to the target direction, but it first rotates around the left/right axis and then around the resulting upward axis.

local vector Dir; // input
local rotator Result;
local vector X, Y, Z; // temp
 
Z = Normal(Dir cross vect(0,1,0));
X = Normal(Dir);
Y = Z cross X;
Result = OrthoRotation(X, Y, Z);

Float to int cast

This isn't your standard typecast. Sometimes you want to access the actual bits a float value consist of, e.g. to send it via a TcpLink or UdpLink. UnrealScript doesn't provide any function to do that, but prior to Unreal Engine 3 it is possible to exploit loopholes in the compiler to achieve this kind of bitwise conversion.

To convert between float and int this way, you need two classes. Even if you only want to convert in one direction, you still need both. Don't ask how this works, I won't explain. And again: This will only work in Unreal Engine 1 and 2, because the compiler no longer allows it in Unreal Engine 3.

class IntConverter extends Object abstract;
 
var int Value;
 
static final function float ToFloat(int value)
{
    default.Value = value;
    return Super(FloatConverter).ReturnFloat();
}
 
static final function int ReturnInt()
{
    return default.Value;
}

class FloatConverter extends Object abstract;
 
var float Value;
 
static final function int ToInt(float value)
{
    default.Value = value;
    return Super(IntConverter).ReturnInt();
}
 
static final function float ReturnFloat()
{
    return default.Value;
}

To use the conversion, you simply call the static ToInt or ToFloat method:

local float f;
local int i;
 
f = 123.45;
log(f @ class'FloatConverter'.static.ToInt(f));
 
i = 12345;
log(i @ class'IntConverter'.static.ToFloat(i));