Vectors, Floating Points, Complex Numbers and further Maths

[Jeoshua]

While exploring the options in TLISP available to us, I have discovered a few things about the Vector type available to us, and about vector maths, in general:

• These objects are actually floating point numbers, but they are not accessible through TLISP in standard (IEEE 754) format.
• The format used is called "Metric" in the Euclid.h file found in the source code repository (Transcendence/Includes/Euclid.h), which is typedef double
• Microsoft's VC++ "double" is an 8 byte (64 bit) float, so therefore Vectors are a pair of 2 64-bit floating points
• The list format accessible through TLISP uses 4 pairs of 32 bit integers when accessed, which matches up exactly.
• A bit of experimentation shows, roughly:
  • Transcendence defines LIGHT_SECOND = 299792.5, which is it's approximate value in kilometers.
  • 1 light second = (sysVectorPolarOffset nil 0 1) -> (0 1091718210 0 0)
  • X-coordinate of this is: (0 1091718210)
  • 1 light second on the X component is = (0 1091718210)
  • The hexadecimal notation for the second component = 0x41124C42
  • Assuming this is an MSVC++ double type, this translates to 299792.5
  • 2 light seconds / 2 light seconds = (sysVectorDivide (sysVectorPolarOffset nil 0 2) 599585) -> (0 1072693248 0 0)
  • Again, assuming a standard IEEE 754 float form, this comes out to 1, as it should.
• Therefore, in to put all this in easy to understand terms:
  • Vectors are MSVC++ double type numbers, stored broken bitwise into two 32 bit integers, stored little endian.
  • List offset 0: Low bits of the mantissa.
  • List offset 1: Sign bit in first binary position, following 8 digits are the exponent, remaining are the high bits of the mantissa.

When it comes to Vectors and maths, very similar structures are often used to represent Complex numbers, a concept which Common Lisp, Scheme, and C++ commonly understand, but not TLISP, even tho all the features are already half implemented. In most respects, they are equivalent to 2d vectors, with slight differences in how they respond to some mathematical operations, such as multiplication, division, exponents, and powers. Supporting this type would also allow one to find roots of negative powers, and to perform a lot of maths that are impossible right now.

Lisp-like languages typically have a "type" flag associated with their variables. TLISP is no exception, having types defined for int32, string, list, atom, etc. There need to be a few more "types" added to TLISP's repertoire to bring the scripting language "up to code", so to speak. Lisp-like languages also commonly split these groups into larger groupings, to facilitate translation between one type and another more transparently, should a function require or return a limited group of types:

• Vector: Currently just a list of size 4, with the above confusing double integer representation. This should be elevated to a first class type, distinguishable with (typeof x) as a "vector", which would aid greatly in keeping the source code sane and easier to implement further expansions and improvements to these elements.
• Float: Currently a list of size 2, only found paired up in Vectors. This could be changed to be a C++ double in memory, with the script parser being modified to understand 0.5, 1.5e10, and other common representations for floating points.
• Complex: With full support for Floating points, and the current support for vectors, Complex numbers could be implemented. Their form could either be represented in memory at Vectors currently are, as a list containing two Float types, or even as another bitwise breakdown of a native c++ type. The script parser would need to understand when these complex numbers are being given, either as a vector (x, i), something approaching Common LISP's format #C(x i), with a constructor (complex x i), or in algebraic form x + yi.
• Ratio: The type is already used when getting returns from the power function, when one gives fractional inputs as a list of size 2 with the following format: (list numeratorInteger denominatorInteger). The script parser would then need a change to understand fractional numbers given in the form 1/2 or 8%. However, with floating point support, the power function could be changed to only return floats or ints, depending on the type given, and the Ratio type could thusly be completely avoided.

Using native C++ types would be preferred, where possible. Exposing these highest level operations directly to the scripting engine, and doing most of the heavy lifting in the C++ environment, will increase the speed of scripting operations, and the game overall, by more than a few orders of magnitude. Current functions such as the mathematical operations (add, subtract, multiply, divide, power, etc) and conversion functions (int) would need to be modified to handle the new types. The algebraic rules governing these types are well defined and could be found in most standard math libraries. New basic utility functions for these types would also have to be written, such as constructors (float x), (complex x i), etc, and type-casters (using the same notation, basically as overloaded functions similar to int). New math functions would be needed for some types, such as (dotProduct vectorA vectorB), or (realPart complex). These are pretty easy to find, understand, and in most cases, code. Most are available already in math.h and would only require the functions to be exposed to TLISP.[/list]

Euclid.h also contains an array of utility functions which can be run on class CVector. Many of these would be extremely useful in TLISP, if they were to be exposed through the API:

• GetX and GetY: Does exactly what it says on the tin. Returns either component of the Vector as a floating point. Can be used in a geometric setting to help find the sine and cosine of a Vector, in a cheap way.
• SetX and SetY: Again, exactly what it says on the tin. Sets only the component specified.
• Norm: Normalizes a vector (set to be length 1, at the same angle as the original Vector).
• Perpendicular: Gives a Vector perpendicular to the given vector. (X, Y) -> (-Y, X)
• Reflect: Gives a Vector exactly opposite of the given vector. (X, Y) -> (-X, -Y)
• Rotate: Rotates a Vector by a given number of degrees.
• Other: There are also utility functions in this header file that would be directly useful for translating, rotating, scaling, and other operations that we currently cannot do with vectors, and often have need for

I realize that this has been a long read, but I feel that nothing could be more limiting than the current situation, where integer types are used almost exclusively, except when they aren't, and when they aren't they're not compatible with any other function than the class they came from. Transcendence is 10 years old now, and is still using a basic layout of maths in it's scripting engine that would seem primitive even on a computer from the 1960s, the decade of the birth of LISP. It's time to bring it up to at least the level of expressiveness that was available in the early versions of the language it seems to be emulating.

[pixelfck]

Nice analysis. I think you may want to send George a PM to bring the post under his attention in case he missed it.

~Pixelfck

[Jeoshua]

I had intended to, but after a few hours of researching, writing, editing, researching again, rewriting, reediting, etc, I got tired and had to take a nap

[george moromisato]

This is great. Ultimately, I would like to do the work to expose floats to TLisp (and to turn vectors into real types). But that's definitely a fair amount of work. Right now I'm spending most of my time either on new content or on marketing, and I can't spend too much time. [Most of my discretionary budget is going to making progress on this task: http://forums.kronosaur.com/viewtopic.php?f=3&t=6540]

But I'd love to tackle some of the low-hanging fruit.

What are some simple improvements that would yield the highest benefit?

[Jeoshua]

Just having that one standard C++ function, atof(string), exposed to the TLISP scripting system, would have far reaching consequences, and would allow us to hit the ground running with floating points extremely early. It's known in Common Lisp, for any not familiar, as a constructor. Creating a function, (float x), which takes either a string or an integer, and returns x as the above mentioned 2-tuple list similar to that found in Vectors, would be the easiest method to start with. (int x) would have to be modified, as well, to be able to cast this 2-tuple list representation of a float into a standard integer.

I also think it's very fitting to start off with the constructor, and the presence of the SysVector* set of math operations would provide, coupled with this constructor and type caster, an immediate ability to use the floats, for the cost of one new function, and a minor modification to one existing function. Everything else comes naturally and easily, in steps, from this change. It doesn't even require the engine to do anything more than naively pass a string to the function, and to store the result split bitwise as two integers in a list.

The second piece of low hanging fruit would be the Vector and Float types. If Vectors are to be two floats in a list, and Floats are an IEEE 754 double precision type split into two integers, then having (typeof x) return "vector" or "float" where expected would be a good thing to implement and extremely useful in scripting. Right now, they just look like lists, and that gives no information about their actual content. Again, tho, this is not strictly required, and can be left until later.

More importantly than that, if throwing out Complex numbers for the time being, would be the various transforms of Vectors. Since most of the important bits of Complex mathematics in regards to a 2d game can be represented by rotations and scalings, these are the only two functions there is an immediate need for. Being able to perform Vector-on-Vector transforms would go a long way, and in some ways is more powerful than Complex numbers. To scale a vector by a vector is a straight multiplication of (X1, Y1) * (X2, Y2) = ((X1 * X2), (Y1 * Y2)), and that function is already an overloaded operator for type CVector. All that needs to be changed, to allow this, is to not throw an error when using (sysVectorMultiply vector1 vector2), and multiply the two vectors.

Rotation in 2 dimensions wouldn't benefit from a Vector-on-Vector operation, but is nonetheless a very needed operation, even if it is rotation by a scalar. This would allow reflections, rotations, and perpendicular vectors to be calculated easily, which is not now possible without some tricky coding, and would not require a lot of work. If floats are in the game, this rotation could be given in radians, too, which would allow a wide range of computations common to trigonometry without converting between degree angles, and make up for the lack of Complex numbers where it counts the most.

Decomposing of vectors would also be easy to code and extremely useful. It is possible, right now, to get the Y coordinate of a Vector by using (list (@ vector 2) (@ vector 3)), but that is kludgy, and requires many operations where only one should be strictly required.

These three vector operations, taken in tandem, would allow a wide range of trigonometry functions to be calculated in a trivially simple fashion, such as sines, cosines, tangents, and other such mathematical goodies. I know I have heard a lot of coders talking about the difficulty of aiming code, or AI pathing. The availability of these kinds of manipulations on Vectors would go a long way toward providing adequate solutions for these problems, and come easily from these three basic operations on Vectors: Scaling, Rotating, and Decomposing.

And finally, the mathematical operations would be the last bit that would be strictly required. For example, (add int float) or (multiply float float) should return a sane answer, and that would be a trivial change if most of the above were implemented. C++ can already add, subtract, multiply, divide, exponentiate, and perform modulo operations between arbitrary combinations of integers and floats, without any added code required. The only thing that needs to be changed is how they are processed, and entered into memory. This is the only real time consuming part of all this, since there are many operations that need to be changed, but the changes in most cases would be so minor that this could be done as a side project while other things are worked on, as the need arises. We already have the basic maths available to us in the sysVector* operations, so this can take a back seat to other concerns.

Low Fruits:

• Constructor/Converter function (float x) to cast types into floats, and an addition to the (int x) function to change these 2-tuple lists of integers into IEEE 754 floats.
• Float and Vector type definitions in (typeof x)
• Rotation of vectors by degree or radian (with radians requiring floating points) (sysVectorRotate vector rotation) -> vector
• Scaling of vectors by multiplication by another vector. (sysVectorMultiply vector1 vector2) -> vector
• Decomposing of vectors into their x and y float components. (sysVectorGetX vector) (sysVectorGetY vector) -> float

With those, most of the other things required for higher maths would be derivable and script-able, until such a time as the type system gets a more thorough overhaul. Even the simple addition of a constructor and type caster for Floats open a lot of doors, and Rotation, Scaling, and Decomposing of Vectors allows extremely advanced maths for very little effort.

[Jeoshua]

I know you wanted a short list, but I'm sorry my mind doesn't work that way. I did my best to consolidate the most saliently important and easy to code bits into a coherent list, ranked by how easy they are to do vs how useful they could be. Again, the constructor (float x), taking a string or an int, and returning some representation of a floating point, along with a modification to the (int x) function to reverse this operation, are all that is strictly required as a starting point. That is a project that could be done in a weekend, or maybe even a single day, and provide immediate usefulness.

All the rest can wait, although the Vector transforms are also pretty simple to put in. The functionality I have described is already in the header files, and only needs to be exposed to the scripting system in some way. In the case of the Vector-on-Vector scaling, it could be as simple as 2 lines of code in SysVectorMultiply.