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 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
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:
After doing this for all instances, the controller calculates all z values using a couple of
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
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?
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
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 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
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;
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: