algorithm - 俄罗斯方块旋转算法

Question

表示和旋转俄罗斯方块游戏的最佳算法（和解释）是什么？我总是觉得作品旋转和表示方案令人困惑。

大多数俄罗斯方块游戏似乎在每次旋转时都使用天真的“重新制作方块数组”：

http://www.codeplex.com/Project/ProjectDirectory.aspx?ProjectSearchText=俄罗斯方块

但是，有些使用预先构建的编码数字和位移来表示每个部分：

http://www.codeplex.com/wintris

有没有一种方法可以使用数学来做到这一点（不确定是否可以在基于单元的板上工作）？

score 32 · Accepted Answer

形状的数量是有限的，所以我会使用一个固定的表格而不进行计算。这样可以节省时间。

但是有旋转算法。

选择一个中心点并旋转 pi/2。

如果一块棋子从 (1,2) 开始，它会顺时针移动到 (2,-1) 和 (-1,-2) 和 (-1, 2)。将其应用于每个块并旋转该块。

每个 x 是前一个 y，每个 y - 前一个 x。这给出了以下矩阵：

[  0   1 ]
[ -1   0 ]

对于逆时针旋转，使用：

[  0  -1 ]
[  1   0 ]

score 30 · Accepted Answer

当我试图弄清楚旋转对我的俄罗斯方块游戏如何起作用时，这是我在堆栈溢出中发现的第一个问题。尽管这个问题很老，但我认为我的输入将帮助其他人试图通过算法解决这个问题。首先，我不同意硬编码每个部分和旋转会更容易。Gamecat 的回答是正确的，但我想详细说明一下。以下是我用来解决 Java 中的旋转问题的步骤。

对于每个形状，确定其原点的位置。我使用此页面上图表上的点来分配我的原点。请记住，根据您的实现，您可能必须在每次用户移动该片段时修改原点。
旋转假设原点位于点 (0,0)，因此您必须先平移每个块，然后才能旋转它。例如，假设您的原点当前位于点 (4, 5)。这意味着在形状可以旋转之前，每个块必须在 x 坐标中平移 -4，在 y 坐标中平移 -5，以相对于 (0,0)。
在 Java 中，典型的坐标平面从最左上角的点 (0,0) 开始，然后向右和向下增加。为了在我的实现中补偿这一点，我在旋转之前将每个点乘以 -1。
这是我用来计算逆时针旋转后新的 x 和 y 坐标的公式。有关这方面的更多信息，我会查看Rotation Matrix上的 Wikipedia 页面。x' 和 y' 是新坐标：

x' = x * cos(PI/2) - y * sin(PI/2) 和 y' = x * sin(PI/2) + y * cos(PI/2) 。
对于最后一步，我只是以相反的顺序完成了第 2 步和第 3 步。所以我再次将结果乘以 -1，然后将块转换回它们的原始坐标。

这是对我有用的代码（在 Java 中），以了解如何用您的语言进行操作：

public synchronized void rotateLeft(){

    Point[] rotatedCoordinates = new Point[MAX_COORDINATES];

    for(int i = 0; i < MAX_COORDINATES; i++){

        // Translates current coordinate to be relative to (0,0)
        Point translationCoordinate = new Point(coordinates[i].x - origin.x, coordinates[i].y - origin.y);

        // Java coordinates start at 0 and increase as a point moves down, so
        // multiply by -1 to reverse
        translationCoordinate.y *= -1;

        // Clone coordinates, so I can use translation coordinates
        // in upcoming calculation
        rotatedCoordinates[i] = (Point)translationCoordinate.clone();

        // May need to round results after rotation
        rotatedCoordinates[i].x = (int)Math.round(translationCoordinate.x * Math.cos(Math.PI/2) - translationCoordinate.y * Math.sin(Math.PI/2)); 
        rotatedCoordinates[i].y = (int)Math.round(translationCoordinate.x * Math.sin(Math.PI/2) + translationCoordinate.y * Math.cos(Math.PI/2));

        // Multiply y-coordinate by -1 again
        rotatedCoordinates[i].y *= -1;

        // Translate to get new coordinates relative to
        // original origin
        rotatedCoordinates[i].x += origin.x;
        rotatedCoordinates[i].y += origin.y;

        // Erase the old coordinates by making them black
        matrix.fillCell(coordinates[i].x, coordinates[i].y, Color.black);

    }
    // Set new coordinates to be drawn on screen
    setCoordinates(rotatedCoordinates.clone());
}

这个方法就是将你的形状向左旋转所需的全部，结果证明它比为每个形状定义每个旋转要小得多（取决于你的语言）。

score 12 · Accepted Answer

这就是我最近在基于 jQuery/CSS 的俄罗斯方块游戏中的做法。

计算块的中心（用作枢轴点），即块形状的中心。称之为（px，py）。

构成块形状的每块砖都将围绕该点旋转。对于每块砖，您可以应用以下计算...

其中每块砖的宽度和高度为 q，砖的当前位置（左上角）为 (x1, y1)，新砖的位置为 (x2, y2)：

x2 = (y1 + px - py)

y2 = (px + py - x1 - q)

要向相反方向旋转：

x2 = (px + py - y1 - q)

y2 = (x1 + py - px)

该计算基于 2D 仿射矩阵变换。如果您对我如何做到这一点感兴趣，请告诉我。

score 11 · Accepted Answer

就我个人而言，我一直只是手动表示旋转 - 形状很少，这样编码很容易。基本上我有（作为伪代码）

class Shape
{
    Color color;
    ShapeRotation[] rotations;
}

class ShapeRotation
{
    Point[4] points;
}

class Point
{
    int x, y;
}

至少在概念上 - 直接形状的多维点数组也可以解决问题:)

score 9 · Accepted Answer

您只能通过对其应用数学运算来旋转矩阵。如果你有一个矩阵，说：

Mat A = [1,1,1]
        [0,0,1]
        [0,0,0]

要旋转它，先乘以它的转置，然后乘以这个矩阵（[I]dentity [H]orizontaly [M]irrored）：

IHM(A) = [0,0,1]
         [0,1,0]
         [1,0,0]

然后你将拥有：

Mat Rotation = Trn(A)*IHM(A) = [1,0,0]*[0,0,1] = [0,0,1]
                               [1,0,0] [0,1,0] = [0,0,1]
                               [1,1,0] [1,0,0] = [0,1,1]

注意：旋转中心将是矩阵的中心，在本例中为 (2,2)。

score 8 · Accepted Answer

表示

表示最小矩阵中的每个部分，其中 1 表示四联体占据的空间，0 表示空白空间。例子：

originalMatrix = 
[0,   0,   1]
[1,   1,   1]

旋转公式

clockwise90DegreesRotatedMatrix = reverseTheOrderOfColumns(Transpose(originalMatrix))

anticlockwise90DegreesRotatedMatrix = reverseTheOrderOfRows(Transpose(originalMatrix))

插图

originalMatrix = 
  x    y    z
a[0,   0,   1]
b[1,   1,   1]

transposed = transpose(originalMatrix)
  a   b
x[0,  1]
y[0,  1]
z[1,  1]

counterClockwise90DegreesRotated = reverseTheOrderOfRows(transposed)
  a   b
z[1,  1]
y[0,  1]
x[0,  1]

clockwise90DegreesRotated = reverseTheOrderOfColumns(transposed)
  b   a
x[1,  0]
y[1,  0]
z[1,  1]

score 6 · Accepted Answer

由于每个形状只有 4 个可能的方向，为什么不使用形状的状态数组并旋转 CW 或 CCW 简单地增加或减少形状状态的索引（索引环绕）？我认为这可能比执行旋转计算等更快。

score 3 · Accepted Answer

如果您在 python 中执行此操作，基于单元格而不是坐标对，旋转嵌套列表非常简单。

rotate = lambda tetrad: zip(*tetrad[::-1])

# S Tetrad
tetrad = rotate([[0,0,0,0], [0,0,0,0], [0,1,1,0], [1,1,0,0]])

score 3 · Accepted Answer

如果我们假设 tetromino 的中心正方形的坐标 (x0, y0) 保持不变，那么 Java 中其他 3 个正方形的旋转将如下所示：

private void rotateClockwise()
{
    if(rotatable > 0)   //We don't rotate tetromino O. It doesn't have central square.
    {
        int i = y1 - y0;
        y1 = (y0 + x1) - x0;
        x1 = x0 - i;
        i = y2 - y0;
        y2 = (y0 + x2) - x0;
        x2 = x0 - i;
        i = y3 - y0;
        y3 = (y0 + x3) - x0;
        x3 = x0 - i;  
    }
}

private void rotateCounterClockwise()
{
    if(rotatable > 0)
    {
        int i = y1 - y0;
        y1 = (y0 - x1) + x0;
        x1 = x0 + i;
        i = y2 - y0;
        y2 = (y0 - x2) + x0;
        x2 = x0 + i;
        i = y3 - y0;
        y3 = (y0 - x3) + x0;
        x3 = x0 + i;
    }
}

score 3 · Accepted Answer

我从这里的矩阵旋转导出了一个旋转算法。总结一下：如果您有组成块的所有单元格的坐标列表，例如 [(0, 1), (1, 1), (2, 1), (3, 1)] 或 [( 1, 0), (0, 1), (1, 1), (2, 1)]:

 0123       012
0....      0.#.
1####  or  1###
2....      2...
3....

您可以使用计算新坐标

x_new = y_old
y_new = 1 - (x_old - (me - 2))

对于顺时针旋转和

x_new = 1 - (y_old - (me - 2))
y_new = x_old

逆时针旋转。me是块的最大范围，即4对于 I 块、2对于 O 块和3所有其他块。

score 1 · Accepted Answer

对于 3x3 大小的俄罗斯方块块，翻转你的块的 x 和 y，然后交换外列，这就是我一段时间以来的想法

score 0 · Accepted Answer

如果数组大小为 3*3 ，则最简单的旋转方式（例如逆时针方向）是：

oldShapeMap[3][3] = {{1,1,0},
                     {0,1,0},
                     {0,1,1}};

bool newShapeMap[3][3] = {0};
int gridSize = 3;

for(int i=0;i<gridSize;i++)
    for(int j=0;j<gridSize;j++)
        newShapeMap[i][j] = oldShapeMap[j][(gridSize-1) - i];
/*newShapeMap now contain:    
                               {{0,0,1},
                                {1,1,1},
                                {1,0,0}};

*/

score 0 · Accepted Answer

我为所有形状中的四个点使用了一个形状位置和一组四个坐标。由于它在 2D 空间中，因此您可以轻松地将 2D 旋转矩阵应用于点。

这些点是 div，因此它们的 css 类从关闭变为打开。（这是在清除了他们上一回合所在的 css 类之后。）

score 0 · Accepted Answer

至少在 Ruby 中，您实际上可以使用矩阵。将您的棋子形状表示为数组的嵌套数组，例如 [[0,1],[0,2],[0,3]]

require 'matrix'
shape = shape.map{|arr|(Matrix[arr] * Matrix[[0,-1],[1,0]]).to_a.flatten}

但是，我同意对形状进行硬编码是可行的，因为每个形状有 7 个形状和 4 个状态 = 28 行，而且永远不会超过这个。

有关这方面的更多信息，请参阅我在 https://content.pivotal.io/blog/the-simplest-thing-that-could-possibly-work-in-tetris 上的博客文章以及在 https 上的完整工作实现（带有小错误）://github.com/andrewfader/Tetronimo

score 0 · Accepted Answer

Python：

pieces = [
    [(0,0),(0,1),(0,2),(0,3)],
    [(0,0),(0,1),(1,0),(1,1)],
    [(1,0),(0,1),(1,1),(1,2)],
    [(0,0),(0,1),(1,0),(2,0)],
    [(0,0),(0,1),(1,1),(2,1)],
    [(0,1),(1,0),(1,1),(2,0)]
]

def get_piece_dimensions(piece):
    max_r = max_c = 0
    for point in piece:
        max_r = max(max_r, point[0])
        max_c = max(max_c, point[1])
    return max_r, max_c

def rotate_piece(piece):
    max_r, max_c = get_piece_dimensions(piece)
    new_piece = []
    for r in range(max_r+1):
        for c in range(max_c+1):
            if (r,c) in piece:
                new_piece.append((c, max_r-r))
    return new_piece

score 0 · Accepted Answer

在 Java 中：

private static char[][] rotateMatrix(char[][] m) {
    final int h = m.length;
    final int w = m[0].length;
    final char[][] t = new char[h][w];

    for(int y = 0; y < h; y++) {
        for(int x = 0; x < w; x++) {
            t[w - x - 1][y]  = m[y][x];
        }
    }
    return t;
}

在 Java 中作为单页应用程序的简单俄罗斯方块实现： https ://github.com/vadimv/rsp-tetris

algorithm - 俄罗斯方块旋转算法

16 回答 16

Related

Reference