0
\$\begingroup\$

I need a function that allows me to rotate a grid data structure an arbitrary number of times 90 degrees clockwise. Currently it doesn't appear as though the function has any effect on the ds_grid.

Below is the code I'm currently using, the function that calls it looks like: ds_grid_rotate_alt(global.grid, irandom(3), 10);.

/// @description rotate grid clockwise 90 degrees x times

var grid = argument0;
var turns = argument1;
var width = argument2;

var gx = 0;
var gy = 0;

if turns > 0
{
    var grid_copy = ds_grid_create(width, width);

    for (gy = 0; gx < width; gy++)
    {
        for (gx = 0; gx < width; gx++)
        {
            //grid copy 
            var data = ds_grid_get(grid,gx,gy);
            ds_grid_set(grid_copy,width-gy,width-gx,data);
        }
    }
    //copy results back to origional grid
    ds_grid_copy(grid_copy,grid);
    ds_grid_destroy(grid_copy);

    turns -= 1;
    ds_grid_rotate_alt(grid,turns,width);
}
\$\endgroup\$
  • \$\begingroup\$ Your ds_grid remains unchanged because of line 24: the function ds_grid_copy() is copying the original grid to the copy grid, thus overwriting your previous calculations. \$\endgroup\$ – liggiorgio Apr 3 '18 at 13:43
1
\$\begingroup\$

As commented, you must change the arguments of the ds_grid_copy() function, for it isn't saving your calculations.

Taking a look at your code, I came up with a function that does exactly what you want, and that works linearly without the need of being (needlessly) recursive.

Since ds_grids are basically matrices, we can use maths to work with them. Your function uses width as matrix size, so it's safe to suppose it's a square matrix. Let A be a 4x4 square matrix, and we want to rotate it 90 degrees clockwise; it comes that such a rotation is the same as first transposing then horizontally flipping the matrix:

enter image description here

You can try it with a squared paperboard, the result is the same. There's a formal explanation for that, but we are interested in the implementation.

Also, every four rotations we get to the starting configuration (rotating 360 degrees equals not rotating at all), so we can consider the modulo of the variable turns and 4 instead of performing unnecessary rotations leading to the same result over and over, saving this way useful CPU time.

So, now we are at the point of considering only three different rotations: 90, 180, and 270 degrees clockwise. We can do another consideration: why rotate clockwise three times if we can do just one rotation clockwise? Math helps us, because if we flip horizontally before transposing, the result is we are rotating 90 degrees counter-clockwise, thus 270 degrees clockwise:

enter image description here

Finally, 180 degrees rotations are the same be them CW or CCW. We may say we rotate 90 degrees twice, actually rotating by 180 degrees equals to flip both horizontally and vertically, irrespective of the order of transforms:

enter image description here

The only operations involved are transposition, horizontal and vertical flip, and we just combine them to get our desired rotations. We may create three separate functions and execute them as needed, but we can still do some work offline and create a single function that executes two of these transforms at once.

Transposition moves value in a given cell to the target cell by swapping starting coordinates.

Trasposition
A[u,v] → A[v,u]

Flipping involves reversing the coordinates from the end of the row or column (W is max width, H is max height).

Horizontal flip
A[u,v] → A[W-(u+1),v]

Vertical flip
A[u,v] → A[u,H-(v+1)]

We combine transposition and flipping to get 90 degrees rotations (mind I removed parentheses and changed signs accordingly):

Transposition, then hor. flip (90° CW)
A[u,v] → A[W-v-1,u]

Hor. flip, then transposition (270° CW - 90° CCW)
A[u,v] → A[v,W-u-1]

Finally, the 180 degrees rotation:

Hor. flip, then vert. flip or viceversa (180° CW/CCW)
A[u,v] → A[W-u-1,H-v-1]

You can now use these pseudocode assignments to create your rotated matrix in a single step, without any unnecessary iteration or recursion.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.