テトリス ゲームのピースを表現して回転させるための最適なアルゴリズム (および説明) は何ですか? 私はいつもピースのローテーションと表現のスキームがわかりにくいと感じています。
ほとんどのテトリス ゲームは、ローテーションごとに単純な「ブロックの配列を作り直す」方法を使用しているようです。
http://www.codeplex.com/Project/ProjectDirectory.aspx?ProjectSearchText=tetris
ただし、事前に構築されたエンコードされた数値とビット シフトを使用して各ピースを表すものもあります。
http://www.codeplex.com/wintris
数学を使用してこれを行う方法はありますか (セルベースのボードで機能するかどうかはわかりません)?
形状は限られているので、固定テーブルを使用し、計算は行いません。それは時間を節約します。
しかし、回転アルゴリズムがあります。
中心点を選択し、pi/2 回転します。
ピースのブロックが (1,2) から始まる場合、時計回りに (2,-1)、(-1,-2)、(-1, 2) に移動します。これを各ブロックに適用すると、ピースが回転します。
各 x は前の y であり、各 y - 前の x です。これにより、次の行列が得られます。
[ 0 1 ]
[ -1 0 ]
反時計回りの回転には、次を使用します。
[ 0 -1 ]
[ 1 0 ]
テトリスゲームで回転がどのように機能するかを理解しようとしたとき、これがスタックオーバーフローで最初に見つけた質問でした。この質問は古いものですが、私の入力は、他の人がこれをアルゴリズムで理解しようとするのに役立つと思います。まず、各ピースのハードコーディングとローテーションが簡単になることに同意しません。Gamecatの答えは正しいですが、詳しく説明したいと思います。Javaで回転の問題を解決するために使用した手順は次のとおりです。
形状ごとに、その原点がどこにあるかを決定します。このページの図のポイントを使用して、原点を割り当てました。実装によっては、ユーザーがピースを移動するたびに原点を変更する必要がある場合があることに注意してください。
回転は、原点がポイント（0,0）にあると想定しているため、回転する前に各ブロックを移動する必要があります。たとえば、原点が現在ポイント（4、5）にあるとします。つまり、形状を回転させる前に、各ブロックを（0,0）を基準にして、x座標で-4、y座標で-5に変換する必要があります。
Javaでは、一般的な座標平面は左上隅の点（0,0）で始まり、右下に向かって増加します。私の実装でこれを補うために、回転する前に各ポイントに-1を掛けました。
これは、反時計回りに回転した後の新しいx座標とy座標を計算するために使用した式です。これについての詳細は、回転行列の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());
}
この方法は、図形を左に回転させるために必要なすべての方法です。これは、すべての図形の各回転を定義するよりもはるかに小さいことがわかります（言語によって異なります）。
これは、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 アフィン行列変換に基づいています。私がどうやってこれにたどり着いたかに興味があるなら、私に知らせてください。
個人的には、私は常に回転を手で表現してきました。形状がほとんどないため、そのようにコーディングするのは簡単です。基本的に私は（擬似コードとして）持っていました
class Shape
{
Color color;
ShapeRotation[] rotations;
}
class ShapeRotation
{
Point[4] points;
}
class Point
{
int x, y;
}
少なくとも概念的には、点の多次元配列を直接形にすることもできます:)
行列を回転するには、数学演算を適用する必要があります。マトリックスがある場合は、次のように言います。
Mat A = [1,1,1]
[0,0,1]
[0,0,0]
それを回転するには、その転置を掛けてから、この行列 ([I]identity [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) になります。
表現
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]
各形状には 4 つの可能な方向しかないため、形状に状態の配列を使用し、時計回りまたは反時計回りに回転すると、形状状態のインデックスが単純に増減します (インデックスのラップアラウンドを使用)。回転計算などを実行するよりも速いと思います。
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]])
ここで、行列の回転から回転アルゴリズムを導き出しました。要約すると、ブロックを構成するすべてのセルの座標のリストがある場合、たとえば [(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 ブロック、2O ブロック、および3他のすべてのブロックの場合です。
テトロミノの中央の正方形の座標 (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;
}
}
3x3 サイズのテトリス ピースの場合、ピースの x と y を反転させてから、外側の列を交換します。
配列サイズが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}};
*/
すべての形状の 4 つの点に対して、形状の位置と 4 つの座標のセットを使用しました。2D 空間にあるため、ポイントに 2D 回転行列を簡単に適用できます。
ポイントはdivであるため、cssクラスはオフからオンになります。(これは、前のターンの css クラスをクリアした後です。)
少なくとも 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/テトロニモ