俄罗斯方块片旋转algorithm

什么是代表和旋转俄罗斯方块游戏的最好的algorithm(和解释)? 我总是觉得片段旋转和表示方式混乱。

大多数俄罗斯方块游戏似乎在每次轮换时都使用一种天真的“重新制作块”

http://www.codeplex.com/Project/ProjectDirectory.aspx?ProjectSearchText=tetris

但是,有些使用预编码的编码数和位移来表示每一块:

http://www.codeplex.com/wintris

有没有一种方法来做到这一点使用math(不知道这将工作在基于单元格的板)?

有一个有限的形状,所以我会使用一个固定的表,不计算。 这节省了时间。

但是有旋转algorithm。

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

如果一个块从(1,2)开始顺时针移动到(2,-1)和(-1,-2)和(-1,2)。 将这个应用于每个块并旋转。

每个x是前一个y,每个y是前一个x。 其中给出了以下matrix:

[ 0 1 ] [ -1 0 ] 

对于逆时针旋转,使用:

 [ 0 -1 ] [ 1 0 ] 

当我试图找出如何旋转将为我的俄罗斯方块游戏工作,这是我发现堆栈溢出的第一个问题。 尽pipe这个问题很老,但我认为我的意见将帮助其他人试图通过algorithm来解决这个问题。 首先,我不同意硬编码和旋转会更容易。 Gamecat的回答是正确的,但我想详细说明一下。 以下是我用来解决Java中旋转问题的步骤。

  1. 对于每个形状,确定其来源将在哪里。 我用这个页面的图表上的点来分配我的原点。 请记住,根据您的实施情况,您可能需要在每次用户移动作品时修改原点。

  2. 旋转假定原点位于点(0,0),因此在旋转每个块之前,必须翻译每个块。 例如,假设你的起源当前在(4,5)点。 这意味着,在形状可以旋转之前,每个块必须在x坐标中被转换为-4,在y坐标中被转换为相对于(0,0)的-5。

  3. 在Java中,典型的坐标平面从最左上angular的点(0,0)开始,然后向右和向下增加。 为了在我的实现中对此进行补偿,我在旋转之前将每个点乘以-1。

  4. 下面是我用来计算逆时针旋转后新的x和y坐标的公式。 有关这方面的更多信息,我将查看旋转matrix上的Wikipedia页面。 x'和y'是新坐标:

    x'= x * cos(PI / 2)-y * sin(PI / 2)并且y'= x * sin(PI / 2)+ y * cos(PI / 2)。

  5. 最后一步,我只是按相反的顺序进行了第二步和第三步。 所以我再次将我的结果乘以-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()); } 

这个方法就是把你的形状旋转到左边所需的全部东西,相比定义每个形状的每一个旋转,结果都要小得多(取决于你的语言)。

就我个人而言,我一直只是用手代表轮换 – 几乎没有形状,很容易编码。 基本上我有(如伪码)

 class Shape { Color color; ShapeRotation[] rotations; } class ShapeRotation { Point[4] points; } class Point { int x, y; } 

至less在概念上 – 直接在形状上的多维点数组也可以做到这一点:)

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

计算块的中心(用作枢轴点),即块形状的中心。 调用(px,py)。

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

每块砖的宽度和高度都是q,砖的当前位置(左上angular)是(x1,y1),新砖的位置是(x2,y2):

 x2 = (y1 + px - py) y2 = (px + py - x1 - q) 

要旋转相反的方向:

 x2 = (px + py - y1 - q) y2 = (x1 + py - px) 

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

只能通过对其应用math运算来旋转matrix。 如果你有一个matrix,说:

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

旋转它,把它乘以它的转置,然后用这个matrix([I] dentity [H] orizo​​ntaly [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] 

注意:旋转中心将是matrix的中心,在这种情况下是(2,2)。

由于每个形状只有4个可能的方向,为什么不使用状态数组来形状和CW或CCW旋转简单地增加或减less形状状态的索引(与索引环绕)? 我会认为这可能比执行轮换计算和什么都快。

我从这里得到了matrix旋转的旋转algorithm。 综上所述:如果你有组成该块的所有单元的坐标列表,例如[(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是块的最大范围,即I块4个,O块2个,其他块3个。

如果你在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]]) 

表示

用最小的matrix表示每一块,其中1表示由tetriminoe占据的空间,0表示空间。 例:

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

在这里输入图像说明

旋转公式

 clockwise90DegreesRotatedMatrix = reverseTheOrderOfColumns(Transpose(originalMatrix)) anticlockwise90DegreesRotatedMatrix = reverseTheOrderOfRows(Transpose(originalMatrix)) 

插图

 originalMatrix = xyz a[0, 0, 1 ] b[ 1 , 1 , 1 ] 

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

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

在这里输入图像说明

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

在这里输入图像说明

为3×3大小的俄罗斯方块片段翻转你的作品的X和Y,然后交换外面的列这是我想出了一些时间

如果我们假设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; } } 

我已经使用了一个形状位置和四个坐标的四个点在所有的形状。 由于它在2D空间中,因此可以轻松地将2D旋转matrix应用于点。

点是div,所以他们的CSS类从closures转为开启。 (这是在清除了他们最后一次的css类之后。)

如果数组大小为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}}; */ 

在Ruby中,至less可以使用matrix。 用[[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行,它永远不会超过这个。

有关详细信息,请参阅http://pivotallabs.com/the-simplest-thing-that-c​​ould-possibly-work-in-tetris/上的博客文章,以及https:://完整工作的实现(带有小错误)。; github.com/andrewfader/Tetronimo

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