Matrix support and operations

[nonunknown]

** Based on any issue? **
godotengine/godot#26793

** Solution **
Implement basic matrix operations, these are building blocks for NNs (Neural Networks) and other stuff

** API Description **

The Matrix will be a class containing the following methods:

ArrayToMatrix(arr:Array) -> void - Convert a input array to a 1 column matrix e.g: [1,2,3] will result in a matrix: [[1],[2],[3]]
MatrixToArray() -> Array - The inverse operation of the above method
PrettyPrint() -> void - Prints a Matrix the beatiful way
SetRandomData(int rows, int columns) -> void - Generate a random value with rows and columns
SetData(arr:Array) -> void - Set the matrix data e.g: [[1,2,3],[4,5,6]] a Matrix 2x3
Transpose() -> void - Rows becomes columns and vice-versa e.g: [[1,2,3],[4,5,6]] will become [[1,4],[2,5],[3,6]]
Multiply(by:Matrix) -> Matrix - Returns Matrices multiplication result
MultiplyScalar(value:float) -> Matrix - Multiply a entire matrix with a single value
Hadamard(by:Matrix) -> Matrix - Different from matrices multiplication each value from Matrix A is multiplied with each value from B
Add(by:Matrix) -> Matrix - Returns a Matrices Addition operation result
Subtract(by:Matrix) -> Matrix - Returns a Matrices Subtraction operation result

[Xrayez]

I think it makes sense to add basic support for this. Regarding NN, there's even godotengine/godot#30613 which attracted quite a bunch of 👍, so this would facilitate NN development indeed.

Note that the methods should follow snake_case convention, the same as Godot codebase.

ArrayToMatrix(arr:Array) -> void - Convert a input array to a 1 column matrix e.g: [1,2,3] will result in a matrix: [[1],[2],[3]]

This could be void create_from(const Variant& p_value), so as to not limited to Array datatype (Vector2, Vector3, Quat etc.). Search for "create_from" in the Godot documentation for instance.

MatrixToArray() -> Array - The inverse operation of the above method

Taking into account above, to_array()? This seems to be a common naming convention for conversion methods (see below).

PrettyPrint() -> void - Prints a Matrix the beatiful way

This can be implemented by overriding _to_string() virtual method, see godotengine/godot#27886. EDIT: not possible via C++ currently, see godotengine/godot#38819.

SetRandomData(int rows, int columns) -> void - Generate a random value with rows and columns

I'd rename this to something which doesn't imply corresponding getter, something like randomize(rows, columns). Perhaps even adding methods such as rand, rand_range as seen at global scope.

SetData(arr:Array) -> void - Set the matrix data e.g: [[1,2,3],[4,5,6]] a Matrix 2x3

Should have corresponding get_data, and added as a property. This way the Matrix class could be implemented as a Resource, so it can be stored to disk.

Transpose() -> void - Rows becomes columns and vice-versa e.g: [[1,2,3],[4,5,6]] will become [[1,4],[2,5],[3,6]]
Multiply(by:Matrix) -> Matrix - Returns Matrices multiplication result
MultiplyScalar(value:float) -> Matrix - Multiply a entire matrix with a single value

✔️

Hadamard(by:Matrix) -> Matrix - Different from matrices multiplication each value from Matrix A is multiplied with each value from B

As someone not particularly versed in linear algebra, I find this to be not descriptive, maybe rename to multiply_hadamard? They would even appear close to other multiply_* methods in the documentation as well.

Add(by:Matrix) -> Matrix - Returns a Matrices Addition operation result
Subtract(by:Matrix) -> Matrix - Returns a Matrices Subtraction operation result

✔️

---

Regarding the usage of Array, I think it does makes sense for GDScript, but essentially we're only interested in scalar values for which there's PoolRealArray. I'd concentrate the effort on implementing this functionality in C++ only (with and/or without using Godot types, so the class could also be used in pure C++), and then create a "binding" class which would convert incompatible values, if necessary (see how it's done in Godot's core/bind/core_bind.h, for instance), but again might not be necessary depending on the complexity of the class.

I mean, internally, it would be best if the matrix data is represented in a single PoolRealArray I guess (you could also encode the number of columns and rows at the beginning of the array). This could also simplify the process of storing such a matrix to disk, and potentially improve performance since the cost of using a generic Array could be dramatic. In general, perhaps it could be written to work closer to atomic types on C++ level, and then just fetch the data when needed, needs experimenting.

What about changing the elements of the existing matrix? Talking about set_element(int p_row, int p_column, real_t p_value).

Also, for a class like this, I'd also expect some unit tests to be written. 😛

[nonunknown]

Matrix is nothing else than a array of arrays:

[[1,2],[2,3]] - to repesent:

|1x2
|3x4

in my class I'm using vector<vector<float>> - Array of Array of floats, I think to be more precisice should be doubles, cuz AI doesnt use integers (Real). the double has way more precision in prediction stuff and precise results!!

here's the representation in cpp header:

#define t_data std::vector<std::vector<float>>

[Xrayez]

I don't know how exactly matrix data is usually implemented, but representing a matrix as a vector of vector of doubles seems to be wasteful. I've just looked up some existing C libraries which perform matrix operations, for instance see https://github.com/nhomble/yasML/blob/master/yasML.h. In fact the API could be taken as a reference for implementing similar functionality in Godot to work natively with Godot data types.

In there, the matrix is represented as a structure with a pointer to double data. In a way, that's how Image is implemented in Godot, which uses PoolByteArray, that's why I suggested implementing the same functionality with PoolRealArray (which does contain doubles, AFAIK), and you can access the underlying data using raw pointer access similarly.

I guess performance is the number one reason why this feature proposal is created, so I'm suggesting implementing this in a way which could be faster. 🙂

[nonunknown]

Hmm I took a look at this yasML, seems to be way better implemented, I see no reasons to just port it to godot types

[Xrayez]

Yes, the way I see it, you'd need to expose rows, columns as properties for Matrix, changing them could also be allowed to either shrink or grow the matrix dynamically, and data to expose as PoolRealArray property, which would pack the matrix data.

Then provide public API which can happily accept data in Array format for GDScript. But internally, it's better that the data is indeed PoolRealArray (not to be confused with PoolIntArray), should simplify implementation further for computation.

[nonunknown]

Matrices doesnt need to grow dinamically, in ML at least, once defined you just create another with calculations:

Matrix A,B the sum will result in a Matrix C, same for any operation like transpose!

[Xrayez]

Yeah, the ability to grow a matrix dynamically could be added later, if needed.

[nonunknown]

I agree, but in another class like DynamicMatrix, cuz dynamic requires more processing and memalocations

[Xrayez]

I've implemented Grid2D structure in #45 and the class can be used for storage and modification purposes, you'd still have to implement per-grid operations yourself. Of course I think there's no need for that due to performance issues which come from using Variant as built-in type, this would mostly solve convenience issues but not performance, therefore I think creating Matrix2D class is still needed to implement this proposal properly.

The base implementation behind #45 is an example of how Matrix2D can be implemented as well, but to work with purely float/real_t values for performance. As you see, there's really only Vector<Variant> array which represents the grid.

Likewise, if you look at BitMap class implementation, you'll see a similar Vector<uint8_t> bitmask structure used there (packs booleans into bytes).

Alternatively, this could be implemented as row-column as seen in Array2D in Godot Next https://github.com/godot-extended-libraries/godot-next/blob/9d2a0da2921d32fc7838a2a7175e4ecf34584038/addons/godot-next/references/array_2d.gd, but according to my endeavors implementing such structures, this may add unnecessary complexity (but perhaps would add more flexibility, of course flexibility may come with performance costs again)...

[nonunknown]

well, the main target for matrix support is machine learning, which relies on performance!

[otoomet]

It is great to have a matrix data structure. In terms of machine learning type of usage, one should also add the main linear algebra methods besides matrix multiplication, in particular

• matrix inverse, maybe also it's variants like $(X' X)^{-1}$ and linear equation solutions.
• decomposition, eigenvalues
• determinants

I do not think it makes sense to implement this functionality from scratch, rather use an existing package that uses well-tested and documented algorithms, can leverage modern cpu features (like AVX) and such.

It would also be nice to design API in a way that the backend library can be swapped out, e.g. if someone needs float32 tensors (a common data type on gpu-s).

[Xrayez]

It would also be nice to design API in a way that the backend library can be swapped out, e.g. if someone needs float32 tensors (a common data type on gpu-s).

Geometry component in Goost has ability to define various backends for polygon clipping/decomposition: https://github.com/goostengine/goost/blob/b6361fc9eff6047463bd030e5e63ad30ae90ee23/core/math/geometry/2d/poly/poly_backends.h, so similar approach could be taken I guess.

As long as those backends are implemented cleanly to hide implementation details, it's ok, but it would likely make sense to start simple by integrating a single library without introducing backends system.

Geometry component has various backends just because of known limitations that don't always work depending on concrete use cases (like inability to handle degenerate input). Matrix operations/linear algebra could also have similar limitations, but I guess it would be more about performance and level of computational robustness there.

[davidholiday]

the other thread on this was closed so cross-posting here on the open one

for my purposes I really just need basic matrix operations on arbitrarily sized matrices. my first foray into this was implementing a rudimentary engine in GDScript but the performance was way to bad for the game to be playable. I'm going to try injecting a boost libary called ublas into my project as a GDNative object and use it to handle the heavy-lift-maths as well as the drawing.

[Xrayez]

Frankly I still haven't needed support for matrix operations myself, but at some point I realized that I may need to solve a system of equations.

For instance, I need to calculate trajectories and/or time of impact of a projectile (for AI). There's even a proposal for it at Godot: godotengine/godot-proposals#740. I realize that physics could be simulated, but if we're talking about solving for:

• time of impact
• exact position of impact
• shooting angle
• shooting power

This likely asks for solving (non)-linear equations via matrices to do this efficiently in real-time. I've actually managed to solve a quadratic equation for this kind of thing in GDScript, but fail to solve this when other forces affect a projectile (like wind).

Some months ago I delved into some physics stuff, and even ported Box2D Lite to GDScript for learning purposes: https://github.com/Xrayez/box2d-lite-gdscript. Physics have various constraints (such as interpenetration and joints) that must be solved. It turns out that most physics engines don't find an exact solution (using matrices) as it would greatly degrade performance with many physics bodies, so iterative methods are predominantly used there. However, for other use cases that don't require heavy real-time calculations with n number of entities, finding an exact solution would be ideal for a use case of finding trajectories etc.

If someone has any ideas, what exactly is needed to know in order to solve a problem I described above with matrices, that would be great, and perhaps this could speed up the process of implementing matrix operations in Goost, as I'm mostly goal-oriented. 🙂

[Xrayez]

Graph data structure could return adjacency matrix representation. See godotengine/godot-proposals#3848.

[davidholiday]

I'll take a look. not sure if that's what I need though. honestly for now I've decided to pivot to a different game idea that I can whip up w/o need for deep maths the engine can't handle right now without some c++ work to either implement what I already wrote in GDScript or to hook into another library. I do want to revisit this at some point but right now I'm focusing everything on this 2d sprite game I have in mind I think is going to be rad...

[Xrayez]

No worries, I'm just cross-referencing issues/proposals, which are only part of the solution, or just connected to the topic somehow.

In the case of graphs, it means that if we get to implement graph data structure as seen in #172, then it may ask for a method to return an adjacency matrix (with weights and whatnot), so that would be the initial reason/need to implement the Matrix class for that purpose, which should be easy enough to add without introducing any kind of math operations as of now.

[Jorvan758]

This is the feature I want the most and it surprises me how long it has been ignored.

[Xrayez]

@Jorvan758 I no longer maintain the project. If you imply that this kind of feature is ignored by Godot, that's also unfortunate... For these reasons and more, I have abandoned Godot altogether, and everything related to it. I have invited interested contributors to lead the Goost project, but they haven't done a lot. In any case, maintaining a semi-fork of Godot is quite demanding, I'd say, even when in reality, Goost is a module for Godot. See #200 for unfinished port of Goost to match up with Godot 4, if curious.