GML Using DS Grids For Calculations

Bart

WiseBart
GM Version: ALL (the code makes use of ds_grid accessors but that is not a requirement)
Target Platform: ALL
Download: N/A
Links: N/A

Summary

This tutorial series shows how certain calculations can be done using ds_grids.
Each tutorial focuses on a specific calculation or algorithm.

Tutorial 1: The basics

This first tutorial introduces the basic idea.
We look at a way to calculate many dot products seemingly at once.

(Of course a loop is executed in the background but in this case it's nothing that we, as the programmer, need to worry about)

Representing vectors in ds_grids


First we need a way to store vectors in a ds_grid.
That's actually pretty straightforward to do: in each column we store a vector's components.
The number of rows gives us the size of the vectors we're working with (vec2, vec3).
In this case, we extend this idea to a "list" of vectors, where each column contains a vector:
GML:
// Let's take enough vectors
vectors = 100;

// Create the grid, all values are set to 0 by default
// (i.e. the grid contains all zero vectors)
grd_vectors = ds_grid_create(vectors, 3);

// Vector 1
grd_vectors[# 0, 0] = 0;
grd_vectors[# 0, 1] = 1;
grd_vectors[# 0, 2] = 2;

// Vector 2
grd_vectors[# 1, 0] = 3;
grd_vectors[# 1, 1] = 4;
grd_vectors[# 1, 2] = 5;

// Etc.
// ...

! Keep in mind when working with ds_grids that the x coordinate represents the column and the y coordinate represents the row.
Each column contains a vector and the rows contain the components.


If we now run the game in debug mode and have a look at grd_vectors we see the following:
debugger_grd_vectors.PNG

Quite intuitive. For each vector in the list we can click the (+) in front of it to see its components.
Time to do some maths with this!

Interpreting the formula

Once we have the data in the grid, we can truly go full speed.
As the most simple example, let's take a look at a common mathematical operation: the dot product.
For two vectors with 3 components, it looks like this:
GML:
dot = ax*bx + ay*by + az*bz;
The thing here is to actually get an idea of what the formula does.
We see:
  • Three times a multiplication *
  • Two times an addition +
The interesting thing is that the multiplications are done component-wise, so "the x value of a" times "the x value of b", "the y value of a" times "the y value of b", etc.
That makes ds_grids particularly interesting for this since we can use ds_grid_multiply_grid_region and have those 3 multiplications done with a single line of code.
And it gets even better: if we pass the entire grid as the region, i.e. the "list of vectors", the multiplications are performed on all pairs of vectors at once!

For the addition, we can use ds_grid_sum on the column of resulting products to get the actual dot product of two specific vectors.

The code

GML:
// Create the grids that we'll use
vectors = 100;

grd_A = ds_grid_create(vectors, 3);
grd_B = ds_grid_create(vectors, 3);
grd_result = ds_grid_create(vectors, 3);

// Add two "vectors" that are the inputs of the first dot product
grd_A[# 0, 0] = 0;
grd_A[# 0, 1] = 1;
grd_A[# 0, 2] = 2;

grd_B[# 0, 0] = 3;
grd_B[# 0, 1] = 4;
grd_B[# 0, 2] = 5;

// First copy the values in grd_A to the grd_result since we don't want to overwrite values!
ds_grid_copy(grd_result, grd_A);
// Perform the multiplication component per component
ds_grid_multiply_grid_region(grd_result, grd_B, 0, 0, ds_grid_width(grd_result)-1, ds_grid_height(grd_result)-1, 0, 0);  // ax*bx, ay*by, az*bz

// Get the final result by taking the sum of the products (note the indices!)
dot = ds_grid_get_sum(grd_result, 0, 0, 0, 2);  // (ax*bx)+(ay*by)+(az*bz)
We first define one grid for the list of left inputs of the dot product, one grid for the list of right inputs and one for the products.
Then we set two vectors. Obviously you can define as many as 100 in this example and the code won't change.

We then copy the values in A to the results grid since we obviously don't want to overwrite them during the calculations - only as an input - and them multiply the components for all vectors.
From then on it's possible to get the result of each dot product using ds_grid_sum.

If we look at our example and do the maths ourselves we get 0*3+1*4+2*5 = 14
Which corresponds to the value of dot.


And that's all for now. We basically made an alternative to dot_product_3d that does at least part of the math "in parallel" for several pairs of vectors at once.
But we're not entirely there yet. The current method requires no less than 3 ds_grids and we still need to use a loop if we want to get the dot product for each pair of vectors.

In the next tutorial, we'll have a look at how to fix that and optimize the calculation even further!
 
Last edited:

Bart

WiseBart
Tutorial 2: Improving the ds_grid-based dot product

In this tutorial we improve the ds_grid-based dot product.
We also have a look at the different functions to perform an addition using ds_grids.

The drawbacks of the current approach

The current approach works. But there should be no reason to use ds_grid_get_sum to get each result.
Basically, the calculation isn't done yet.
In the end, we need one value for each pair of vectors: the dot product.
In the ideal case, it'd be readily available via a simple lookup:
GML:
dot = grd_results[# index_of_calculation, index_of_row_that_stores_the_result];
Another thing that's not so neat is that we're using 3 grids.

The solution

There are quite a few more functions than the ones we used so far.
In the end we need a sum, so an addition of terms.
Let's have a look in the manual on DS Grids.
The ds_grid_add_... functions are particularly interesting.
ds_grid_add isn't too useful in this case, since it only adds a value to a single cell.
ds_grid_add_region looks more interesting but, then again, it only adds a constant value to each cell in the region. It's one to keep in mind, though!
ds_grid_add_grid_region is the one we're looking for. It adds the values in a region of a grid to the values of a region in a different grid but ALSO adds the values in a region of a grid to the values in another, non-overlapping region within that same grid (notice the potential for optimization here!)

How do we implement all this?

First we have to determine an important thing: can the calculation be done destructively or non-destructively?
Essentially, this means the following:
GML:
// Create two vectors using either a function or using the new GM2.3 constructors
// The underlying implementation isn't important
a = Vector3(1, 0, 0);
b = Vector3(0, 1, 0);

// Destructive, the original value of a is lost
// a contains (a+b) after execution
a.add(b);

// Non-destructive
// Returns a new Vector3 instance, a and b keep their values
c = sum(a, b);
This is a lot like using temporary values to store results when working with normal variables.
When working with grids the same basic idea applies but the temporary values either become additional grids or additional grid rows.

The following is a way to perform the calculation using a single grid.
The values still need to be copied from the two "input" grids.
GML:
// Contents of a single line in the grid after each calculation step
// Empty cells indicate no change from the previous step
// N/A means cells aren't accessible anymore
//
// | Row | Step 1 | Step 2    | Step 3                | Step 4                          | Step 5                          |
// | 0   | v1.x   | v1.x*v2.x | v1.x*v2.x             | v1.x*v1.x+v1.y*v2.y + v1.z*v2.z | v1.x*v1.x+v1.y*v2.y + v1.z*v2.z |
// | 1   | v1.y   | v1.y*v2.y | v1.y*v2.y + v1.z*v2.z |                                 | N/A                             |
// | 2   | v1.z   | v1.z*v2.z |                       |                                 | N/A                             |
// | 3   | v2.x   |           |                       |                                 | N/A                             |
// | 4   | v2.y   |           |                       |                                 | N/A                             |
// | 5   | v2.z   |           |                       |                                 | N/A                             |
The steps written down:
  1. Copy the values of v1 and v2 to the grid
  2. Calculate the products of corresponding components in the same way we did in the first tutorial
  3. Perform the first addition
  4. Perform the second addition. In this case add the result of step 3 to the product of the x components. This gives us the dot product.
  5. The dot product for all pairs of vectors ended up in row 0. Resize the grid to get rid of the temporary values.
When we do it this way, the temporary grid for the calculations is also the grid that stores the final result.

Notice for the additions how we keep adding to the sum to finally end up at row index 0.
The total number number of additions is 2, one less than the number of components of each vector.
If we want to generalize this idea further to include vectors of arbitrary length, we'll still need to put a loop around ds_grid_add_grid_region.
But hey, let's be happy with what we have for now ;)

Now on to the code!

The code

This time we write a script/function so we can reuse the code. The first argument takes the left operand and the second argument takes the right operand.
We pass these in as grids, so as "lists of vectors".
The dot products are calculated for the vectors in corresponding columns.

GML:
// ds_grid_vec3_dot(grd_left_vectors, grd_right_vectors)
var vectors = ds_grid_width(argument0);
var max_index = vectors-1;                      // No need to type more than we have to
var grd_result = ds_grid_create(vectors, 6);    // Width is 6 since we need to store the components of 2 vec3's

// Step 1
ds_grid_set_grid_region(grd_result, argument0, 0, 0, max_index, 2, 0, 0);
ds_grid_set_grid_region(grd_result, argument1, 0, 0, max_index, 2, 0, 3);

// Step 2
ds_grid_multiply_grid_region(grd_result, grd_result, 0, 3, max_index, 5, 0, 0);   // X*X, Y*Y, Z*Z

// Step 3
ds_grid_add_grid_region(grd_result, grd_result, 0, 2, max_index, 2, 0, 1);        // Y*Y + Z*Z
// Step 4
ds_grid_add_grid_region(grd_result, grd_result, 0, 1, max_index, 1, 0, 0);        // X*X + (Y*Y + Z*Z)

// Step 5
ds_grid_resize(grd_result, no_vectors, 1);

return grd_result;
The returned grid contains the dot product for all pairs of vectors that we passed in.
We can look it up using a simple ds_grid_get or use the grid accessor #.

And that's all for this tutorial!

In the next tutorials we'll do more complex calculations and have a look at the limitations of using ds_grids to do calculations.
 
Last edited:
Top