#### Bart

##### WiseBart

Hi all.

The last couple of days I've been working on an optimized way to calculate several z values on a terrain.

For this I'm using ds_grids since they give you two free loops that are implicit and incredibly fast.

Each

The basic calculation is working and already gives a great speed improvement compared to looping manually and doing a couple of

But I'd like to try optimize this even further yet at the moment I reached a bottleneck and I'm not sure if this is something that is even possible to find a solution for.

Right now I execute the following script in the Begin Step event for all

After doing this for all

In the End Step event, each

The goal here is to move all of the above code into the ds_grid calculations, optimizing the thing even further.

Basically just put in (x, y) (not multiplied by one_over_tile_size) in the ds_grid for each

In the end, the modified

I can get the multiplication by

I've been breaking my head over this the last couple of days but I don't see a solution.

The easiest thing would be if the grid functions were extended with some ds_grid_script_grid_region that allowed the execution of a custom script for each ds_grid cell/region but I don't think that's something that would be added quickly.

I hope I've been able to explain this a bit clearly

Anyone who has ideas or suggestions?

The only values that are really needed are the x and y position and the values of the triangle that position is in.

Now there is simply no way to round values once we're doing the calculations using the ds_grid so everything needs to be done in the array lookup.

Currently I multiply the x and y coordinates by

But that doesn't help to get the triangle index right, since we now need the fractional parts of the coordinates (performance cost: 2 calls to

What if we don't scale the coordinates and increase the size of

For each

The

Now there's one edge case, being the diagonals. The squares there belong to both the bottom-left and top-right triangle.

We may still be using the values of the bottom-left triangle when we crossed the diagonal and are in the top-right triangle.

But I guess that could be solved by adding a 'precision' value so the actual array size may be a multiple of the terrain dimensions.

Going to try implement this!

The last couple of days I've been working on an optimized way to calculate several z values on a terrain.

For this I'm using ds_grids since they give you two free loops that are implicit and incredibly fast.

Each

*instance*that needs a z value at a specific (x, y) coordinate gets an index in the grid. An*instance*in this case is not a GM instance but rather just one (x, y) input that needs the resulting z value as the output.The basic calculation is working and already gives a great speed improvement compared to looping manually and doing a couple of

`dot_product_3d`

's and the likes.But I'd like to try optimize this even further yet at the moment I reached a bottleneck and I'm not sure if this is something that is even possible to find a solution for.

Right now I execute the following script in the Begin Step event for all

*instances*:
GML:

```
/// @func phy_terrain_instance_set_position(index, x, y)
/// @desc Update a given instance
#macro grid_height 9
var index = argument0;
var _x = argument1 * one_over_tile_size,
_y = argument2 * one_over_tile_size;
var dx = frac(_x), dy = frac(_y);
var tri_index = (dx >= dy); // Faster than grid/array lookup!
var start = grid_height*tri_index;
var grd_values = arr_terrain_data[ _x, _y];
ds_grid_set_grid_region(grd_instance_data, grd_values, 0, start, 0, start+(grid_height-1), index, 0);
grd_instance_data[# index, 1] = dx;
grd_instance_data[# index, 2] = dy;
```

*instances*, the controller calculates all z values using a couple of`ds_grid_add_grid_region`

's and `ds_grid_multiply_grid_region`

's in the Step Event.In the End Step event, each

*instance*can read its z value.The goal here is to move all of the above code into the ds_grid calculations, optimizing the thing even further.

Basically just put in (x, y) (not multiplied by one_over_tile_size) in the ds_grid for each

*instance*, lookup the right grid data in`arr_terrain_data`

and let the ds_grid calculations handle the rest.In the end, the modified

`phy_terrain_instance_set_position`

script should look like this:
GML:

```
/// @func phy_terrain_instance_set_position(index, x, y)
/// @desc Update a given instance
#macro grid_height 9
var index = argument0;
var _x = argument1 * one_over_tile_size,
_y = argument2 * one_over_tile_size;
var grd_values = arr_terrain_data[ _x, _y]; // One lookup, grd_values contains data of both triangles (the calculation turns into something like "terrain.z + 1 * effect_of_tri0 + 0 * effect_of_tri1", etc.)
ds_grid_set_grid_region(grd_instance_data, grd_values, 0, 0, 0, grid_height-1, index, 0);
grd_instance_data[# index, 1] = _x; // Obviously these values must be set somewhere
grd_instance_data[# index, 2] = _y;
```

`one_over_tile_size`

right, get the integer and fractional parts of x and y using the ds_grid functions but the main issue is obviously getting the triangle index, since it requires some way of rounding/flooring the calculated values (I can do dx+(-1*dy) but that value still needs to turn into 0 or 1 somehow).I've been breaking my head over this the last couple of days but I don't see a solution.

The easiest thing would be if the grid functions were extended with some ds_grid_script_grid_region that allowed the execution of a custom script for each ds_grid cell/region but I don't think that's something that would be added quickly.

I hope I've been able to explain this a bit clearly

Anyone who has ideas or suggestions?

**EDIT**- Potential solution: This may actually turn out to be more straightforward than I thought.The only values that are really needed are the x and y position and the values of the triangle that position is in.

Now there is simply no way to round values once we're doing the calculations using the ds_grid so everything needs to be done in the array lookup.

Currently I multiply the x and y coordinates by

`one_over_tile_size`

so the coordinates in one single square end up ranging from 0 => 1.But that doesn't help to get the triangle index right, since we now need the fractional parts of the coordinates (performance cost: 2 calls to

`frac`

).What if we don't scale the coordinates and increase the size of

`arr_terrain_data`

?For each

*world*(x, y) position we can now link the correct ds_grid. One grid for all indices of the top-right triangle, one grid for all indices of the bottom-left triangle.The

`(x >= y)`

condition becomes implicit this way.
GML:

```
// Assume that grid index 9 contains the top-right triangle's values
// and grid index 8 contains the bottom-right triangle's values
// Non-integer values of x and y may give issues near the diagonal
x 0 1 2 3
y
0 9 9 9 9
1 8 9 9 9
2 8 8 9 9
3 8 8 8 9
```

We may still be using the values of the bottom-left triangle when we crossed the diagonal and are in the top-right triangle.

But I guess that could be solved by adding a 'precision' value so the actual array size may be a multiple of the terrain dimensions.

Going to try implement this!

Last edited: