Miscellaneous Coding Stuff

Order Invariant Linear Transforms:

Have you ever needed to find a linear transform of a set of data points when the sample data is not ordered? You could sort both the raw data and the target data, then do the standard least-squares linear fit, but there's an easy way which does not rely on the order of the data. In order to map “Raw” to “Target”, you just need to compute the average and the standard deviation of both sets of data, then use the following equations.

Gain = +- StDev(Target) / StDev(Raw)

Offset = Average(Target) – Gain*Average(Raw)

Note that the gain may have to be negated; you lose the sign of gain as standard deviations are always positive, but you lose that information when you sort both data sets too. Also note that if you are using Excel to compute the standard deviation, you should use STDEVP(), not STDEV().

A Simple Least Squared Error Formulation:


Non-Traditional A* Application:

A* is a really nifty tool for path-finding. It is used quite a bit in games, but there are some uses for A* which I haven't seen implemented

Making A* Scalable:

You can also make A* very scalable (for an example of a huge problem domain: for my multi-agent-scheduling application checks 10.55 million nodes (that's the number of “next best node”s pulled off queue, there was 3.5 million nodes in the open/closed hash_map, and 0.46 million nodes left in the HOT queue), in 39 seconds on my Athlon 64 3000+).

The Generic Tree:

Especially in computer graphics rendering circles, there are a bunch of hierarchical bounding structures in use (KD, Octree, BIH, etc.), with many new ones continuing to appear. Many of these have a very similar fundamental base structure. Instead of re-writing a bunch of code for each tree type, I wrote some C++ template code for the base tree type.