解决魔方拼图(译文)
By robot-v1.0
本文链接 https://www.kyfws.com/games/solve-rubik-cube-puzzle-zh/
版权声明 本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!
- 11 分钟阅读 - 5036 个词 阅读量 0解决魔方拼图(译文)
原文地址:https://www.codeproject.com/Articles/110672/Solve-Rubik-Cube-Puzzle
原文作者:ATUL_LOONA
译文由本站 robot-v1.0 翻译
前言
Brain teaser solve Rubik cube puzzle on system
脑筋急转弯解决系统上的魔方难题
介绍(Introduction)
这是什么(What It Is)
魔方是由匈牙利雕塑家和建筑学教授Erno Rubik于1974年发明的3D机械拼图.原名"魔方"的魔方获得了当年德国年度最佳拼图游戏特别奖.(The Rubik’s Cube is a 3-D mechanical puzzle invented in 1974 by Hungarian sculptor and professor of architecture Erno Rubik. Originally called the “Magic Cube”, Rubik cube won the German game of year special award for Best Puzzle that year.) 在经典的魔方中,六个面的每一个都覆盖有九种贴纸,其中包括六种纯色(传统上是深蓝色,红色,蓝色,橙色,绿色和黄色).枢轴机构使每个面都可以独立旋转,从而混合了颜色.为了解决难题,每个面孔都必须是纯色.(In a classic Rubik’s Cube, each of the six faces is covered by nine stickers, among six solid colors (traditionally darkblue, red, blue, orange, green, and yellow). A pivot mechanism enables each face to turn independently, thus mixing up the colours. For the puzzle to be solved, each face must be a solid colour.)
它能做什么(What It Does)
解决计算机系统上的rubic cube拼图.下图显示了计算机版本:(Solve rubic cube puzzle on computer systems.The image below shows the computer version:) 使用说明独立地旋转立方体面.玩赢.(Use directions to turn the cube face independently. Play and win.)
如何使用它(How to Use It)
- 下载代码-1.69 MB(Download code - 1.69 MB)
- 安装.NET 3.5 Framework(Install .NET 3.5 Framework)
- 下载并播放-348.25 KB(Download and play - 348.25 KB) 请享用:).(Enjoy:).)
关于代码的所有内容(我将以"问题/答案"的形式针对本文)(All about Code (I will target this article in the form of Questions/Answers))
注意(Note):接下来的六个问题是非常基本的,一个可以跳过.(: The next six questions are very basic, one can skip them.)
问:对其他程序员而言,学习曲线是什么?使用了哪些所有技术/算法?(Q.What is the learning curve for fellow programmers ? What all technologies/algorithms are used?)
人们可以学习如何仅使用基本数学计算就可以在2D表面(计算机屏幕)上准确地投射3D模型.代码涉及使用透视投影,隐藏表面去除算法,.NET 3.5框架中的linq,GDI +,大量矩阵计算.(One can learn how to cast 3D model on 2D surface (computer screen) accurately using only basic mathematics calculations. Code involves using perspective projection, hidden surface removal algorithms, linqs in .NET 3.5 framework, GDI+, lot of matrix computations.)
问:什么是坐标系?(Q.What is coordinate system ?)
一种通过从原点开始的坐标在给定维度的空间中表示点的方法.下图显示了3维坐标系,X,Y,Z轴彼此垂直. IMP:Z轴垂直于屏幕.(A method of representing points in a space of given dimensions by coordinates from origin.The image below shows 3 dimensional coordinate system,the axis X, Y, Z are perpendicular to each other. IMP: Z axis is perpendicular to screen.)
问:有什么意义?(Q.What is a point ?)
点是对3D世界中位置的参考,点由相对于坐标系的x,y,z坐标表示.(A Point is a reference to position in 3D world, point is represented by x,y,z coordinate with respect to coordinate system.)
问:什么是立方体?(Q. What are cubes ?)
如下图所示,通过连接8个点(每个点连接到其他3个点)而形成的具有六个正方形或矩形边的三维形状.(A three-dimensional shape with six square or rectangular sides formed by connecting 8 Points(each point connect to 3 other points) as shown below.)
问:什么是魔方?(Q. What make up a Rubik cube ?)
在3D世界中精心放置的27个立方体构成了一个更大的立方体,称为Rubik立方体.(27 carefully placed cubes in 3D world make a larger cube called Rubik cube.)
问:一个简单的多维数据集的坐标是什么?(Q. What are the coordinates of a simple cube ?)
如下图所示,简单立方体的坐标格式为POINTNUMBER(X,Y,Z)(As shown in the image below, the coordinates of a simple cube are in format POINTNUMBER(X,Y,Z)) 1(0,1,1),2(1,1,1),3(1,0,1),4(0,0,1),5(0,1,0),6(1,1 ,0),7(1,0,0),8(0,0,0).(1(0,1,1) ,2(1,1,1) ,3(1,0,1) ,4(0,0,1) ,5(0,1,0) ,6(1,1,0) ,7(1,0,0) ,8(0,0,0).)
下图显示了z轴垂直于计算机屏幕的坐标系,下一个图像是通过连接8个点形成的立方体,下一个图像是放置9个立方体的位置,形成了魔方的最底层.(The image below shows the coordinate system where z axis is perpendicular to the computer screen, the next image is of cube formed by connecting 8 points, the next image is placement of 9 cubes forming the bottom layer of Rubik cube.)
图片1(Image 1)
问:如何围绕X,Y,Z轴旋转3d坐标系中的点?(Q. How to rotate a point in 3d coordinate system around X,Y,Z axis ?)
围绕z轴旋转点的过程包含三个基本步骤:(Rotation of a point around z axis, there are three basic steps:)
- 转换为旋转中心点,下面的代码将点(x1,y1)转换为中心点(Translate to center point around which to rotate, the code below translates point (x1,y1) to center point)点.(point.)
- 绕中心点旋转,下面的代码使用以弧度表示的角度绕z轴旋转平移点(tempy1,tempx1).(Rotate around center point, the code below rotates translated point (tempy1,tempx1) around z-axis using angle which is expressed in radians.)
- 转换回原始点,如下所示:(Translate back to original points, as done below:) x1,y1是围绕z轴旋转的最终坐标.稍微修改上面的公式,使绕x,y轴旋转成为可能.(x1,y1 are final coordinates as a result of rotation around z axis. Slightly modify the above formula to make rotation about x,y axis possible.)
问:如何将立方体面绕Z轴旋转90度?(Q.How to rotate a cube face around Z axis by 90 degrees ?)
多维数据集面有9个多维数据集,表示72个空间点.计算面的中心点,对所有72个点应用旋转逻辑. :)(A Cube face has 9 cubes, meaning 72 points in space. Calculate the center point of face, apply rotation logic on all 72 points. :))
问什么是相机,相机角度,相机位置,查看器位置?(Q What is Camera, Camera Angles, Camera position, Viewer position ?)
相机注视着3d空间中的魔方,相机位置是相机相对于坐标系的位置,相机角度是相机如何倾斜的角度.观看者位置是观看者相对于计算机屏幕的位置.实际上,我做了另一个POC,了解所有与相机相关的内容.(A camera is eye watching a Rubik cube in 3d space, Camera position is position of camera with respect to coordinate system, camera angles are angles of camera how it is tilted. Viewer position is position of viewer with respect to computer screen. Actually I did another POC understanding all camera related stuff.) 链接在这里(Here is the link) 了解更多信息.摄像机位置,摄像机角度,观察者位置都经过仔细设置,以提供最佳拍摄效果.下面的代码显示了相机参数,在使用相机参数时要小心,这会导致魔方变形.(for more information. Camera position, camera angles, viewer position are set carefully to give best shot. The below code shows the camera parameters, be careful when playing around with camera parameters, it can result in distorted rubikcube.)
Point3D cameraPosition = new Point3D(-1, 90, 90, 140);
Angles angles = new Angles(0, 0, 0);
Point3D viewer = new Point3D(-1, 0, 0, 500);
rubikCube.draw(e.Graphics, cameraPosition, angles, viewer);
问:Point3D类的作用是什么?(Q. What is the Role of Point3D Class ?)
Point3D
类表示坐标系的点,将坐标存储在x,y,z变量中,将索引存储在(class represents points of coordinate system, store coordinates in x,y,z variables, index in) Point3D
构造函数引用多维数据集中的位置(出于计算目的).参见图1:(constructor is reference to position in cube (for calculation purpose). See Image 1:)
public Point3D(int index, double Xcoor, double Ycoor, double Zcoor);
注意(Note):变量x,y,z in(: Variable x,y,z in) Point3D
类被初始化,并且在任何操作中都不会更改,仅用作计算的参考.(class are initialized and are never changed in any operations, only used as reference for calculations.)
问:Point3d类将执行哪些操作?(Q.What operation are performed by Point3d class ?)
-
计算最终位置(Calculate final location of)
Point3D
从相机位置,相机角度观看时,在3d空间中将最终坐标存储在(in 3d space when viewed from camera position, camera angles, store the final coordinates in)Point3D
x1,y1,z1.下图显示了矩阵计算.(x1,y1,z1. The image below shows matrix computations.) -
将旋转顺序应用于(Apply sequence of rotation to)
POINT3D
根据用户操作进行坐标调整,围绕中心点旋转该点(作为参数传递,这是RUBIK CUBE CENTER POINT).(coordinate as a result of user actions, rotate the point around the center point (passed as parameter this is RUBIK CUBE CENTER POINT).) -
这是"透视投影"中最重要的部分.这是关于如何在2D屏幕上投影3D空间中的点,以便不偏离真实外观的.查看器是查看器相对于屏幕的位置,计算最终的x,y并将其返回.(This is the most important part “perspective projection”. It’s all about how a point in 3D space is projected on 2d screen so that there is no deviation from real look and feel. Viewer is position of viewer with respect to screen, calculate the final x,y and return it.)注意(Note):所有图形功能仅以X,Y坐标为参数.(: All graphics functions take only X,Y coor as parameter.)
问:多维数据集类的作用是什么?(Q What is the Role of Cube Class ?)
这是复杂性开始的地方.我们知道立方体是通过在空间中连接(精心放置)8个点而形成的,立方体存储了8个点的集合并负责其绘制,以便填充需要封闭区域的计算机图形,如果立方体有6个封闭的区域区域称为面孔.多维数据集存储形成多维数据集面的点的集合.(This is where the complexity starts. We know that cube is formed by connecting (carefully placed) 8 points in space, cube stores collection of eight points and is responsible for its drawing, in order to fill something computer graphics need a enclosed region, in case of cube we have 6 enclosed regions called faces. Cube stores collection of points which form a cube face.)
- (1,2,3,4)代表脸1,((1,2,3,4) represents face 1,)
- (2,6,7,3)代表脸2((2,6,7,3) represents face 2,)
- (5,6,7,8)代表面3,((5,6,7,8) represents face 3,)
- (1,8,6,5)代表脸4,((1,8,6,5) represents face 4,)
- (1,5,8,4)代表脸5,((1,5,8,4) represents face 5,)
- (8,7,3,4)代表脸6,((8,7,3,4) represents face 6,) 每个面孔都有与之关联的颜色.多维数据集记住对其应用的旋转顺序,如以下代码所示:(Each face has a color associated with it. Cube remembers the sequence of rotations applied on to it as shown in the code below:)
switch (direction)
{
case DIRECTION.XAXIS:
listRotationangles.Add(new Angles(rotationAngles.xAngle, 0, 0));
break;
case DIRECTION.YAXIS:
listRotationangles.Add(new Angles(0, rotationAngles.yAngle, 0));
break;
case DIRECTION.ZAXIS:
listRotationangles.Add(new Angles(0, 0, rotationAngles.zAngle));
break;
}
问:绘制多维数据集时遵循什么操作顺序?(Q What sequence of operation Cube follow while drawing ?)
-
应用(Apply)
FullFinalTransformation
在8点上.(on 8 points.) -
将旋转顺序(先前存储的)和当前旋转顺序(由用户操作产生)应用于8个点.将当前旋转添加到(Apply sequence of rotations(previously stored) and current one(this arises from user action) on 8 points. Add the current rotation in)
listRotationangles
.(.) -
应用(Apply)
PerspectiveProjection
在8点上投影到计算机屏幕上.(on 8 points to project on computer screen.) -
由于上述所有操作,我们准备在2d空间中的所有点都可以在计算机屏幕上绘制.(As a result of all previous actions, we have all points in 2d space ready to be drawn on computer screen.)
-
选择要绘制哪个立方体面最棘手.要记住的最重要的一点是,在查看多维数据集时,在任何时候都只能看到3个面.(Choosing which cube face to draw is most tricky. The most important point to be kept in mind is that at any point while viewing a cube only 3 faces are visible.) 在这里,隐藏的表面去除算法适用.(Here, the hidden surface removal algorithm fits in.)
-
我必须选择三张脸.(I have to choose three faces.)
-
将3个X值最高的最高点存储在世界空间中(Store 3 top most points whose Z coor in max in world space in collection)
lsttop
.(.) -
找到包含所有点的面(Find the face which consists of all points in)
lsttop
,画脸.(, draw the face.) -
找到不与已绘制面相交的已绘制面附近的面,然后对其进行绘制.(Find the face adjacent to drawn face, which does not intersect with already drawing face, draw them.)完成绘制一个立方体.(done with drawing a cube.)
问:Rubik Cube类的作用是什么?(Q What is the Role of Rubik Cube Class?)
魔方负责在世界坐标系中放置27个魔方,如下所示:(Rubik cube is responsible for placing 27 cubes in world coordinate system as shown below:) 下面的代码显示了如何在3d空间中放置27个多维数据集.(The code below shows how to place 27 cubes in 3d space.)
for (int j = 0; j < 3; j++)
{
for (int k = 0; k < 3; k++)
{
for (int i = 0; i < 3; i++)
{
cubes[i + k * 3 + j * 3 * 3] = new cube(i + k * 3 + j * 3 * 3);
CubesAtposition.Add(i + k * 3 + j * 3 * 3, i + k * 3 + j * 3 * 3);
xplus = 11;
yplus = 11;
zplus = 11;
cubes[i + k * 3 + j * 3 * 3].POINTS[0] = new Point3D(1, offset + i * xplus + i *
xspace, yplus + j * yplus + j * yspace, zplus + k * zplus + k * zspace);
cubes[i + k * 3 + j * 3 * 3].POINTS[1] = new Point3D(2, xplus + i * xplus + i *
xspace, yplus + j * yplus + j * yspace, zplus + k * zplus + k * zspace);
cubes[i + k * 3 + j * 3 * 3].POINTS[2] = new Point3D(3, xplus + i * xplus + i *
xspace, offset + j * yplus + j * yspace, zplus + k * zplus + k * zspace);
cubes[i + k * 3 + j * 3 * 3].POINTS[3] = new Point3D(4, offset + i * xplus + i *
xspace, offset + j * yplus + j * yspace, zplus + k * zplus + k * zspace);
cubes[i + k * 3 + j * 3 * 3].POINTS[4] = new Point3D(5, offset + i * xplus + i *
xspace, yplus + j * yplus + j * yspace, offset + k * zplus + k * zspace);
cubes[i + k * 3 + j * 3 * 3].POINTS[5] = new Point3D(6, xplus + i * xplus + i *
xspace, yplus + j * yplus + j * yspace, offset + k * zplus + k * zspace);
cubes[i + k * 3 + j * 3 * 3].POINTS[6] = new Point3D(7, xplus + i * xplus + i *
xspace, offset + j * yplus + j * yspace, offset + k * zplus + k * zspace);
cubes[i + k * 3 + j * 3 * 3].POINTS[7] = new Point3D(8, offset + i * xplus + i *
xspace, offset + j * yplus + j * yspace, offset + k * zplus + k * zspace);
cubes[i + k * 3 + j * 3 * 3].Colors[0] = Color.Red;
cubes[i + k * 3 + j * 3 * 3].Colors[1] = Color.Blue;
cubes[i + k * 3 + j * 3 * 3].Colors[2] = Color.Yellow;
cubes[i + k * 3 + j * 3 * 3].Colors[3] = Color.Green;
cubes[i + k * 3 + j * 3 * 3].Colors[4] = Color.DarkTurquoise;
cubes[i + k * 3 + j * 3 * 3].Colors[5] = Color.DarkOrange;
}
}
}
Rubik多维数据集负责旋转多维数据集面,每个面都可以旋转,甚至整个Rubic多维数据集都可以在X,Y,Z轴上旋转,Rubik多维数据集保持了多维数据集位置和多维数据集编号之间的映射,rubik多维数据集中的每个多维数据集都有一个关联的多维数据集编号有了它,当旋转一个面时,立方体位置处的立方体编号将在映射中更改.(Rubik cube is responsible for rotating cube faces, every face can be rotated, even whole Rubic cube can be rotated on X,Y,Z axis, Rubik cube maintains a mapping between cubeposition and cubenumber, every cube in rubik cube has a cube number associated with it, when a face is rotated, the cubenumber at cubeposition is changed in mapping.)
Dictionary<int, int> CubesAtposition = new Dictionary<int, int>();
魔方表面最重要的挑战是必须按什么顺序绘制魔方,才能获得完美的图像(不重叠也不变形).首先绘制距离摄像机位置最远的多维数据集.(The most important challenge Rubik cube face is in what order cubes must be drawn so that a perfect picture is possible (no overlapping no distortion). Cubes which are farthest from the camera position are drawn first.)
for (int index = 0; index <= 26; index = index + 1)
{
double distance = 0;
collectionPoint3d[index] = cubes[index].CalculateCentrePointAfterRotate(cameraPosition,
angles, cubes[index].CuberRotationAngles, point3d, cubes[index].dir);
distance = Math.Sqrt((cameraPosition.x - collectionPoint3d[index].x) *
(cameraPosition.x - collectionPoint3d[index].x)
+ (cameraPosition.y - collectionPoint3d[index].y) *
(cameraPosition.y - collectionPoint3d[index].y)
+ (cameraPosition.z - collectionPoint3d[index].z) *
(cameraPosition.z - collectionPoint3d[index].z));
listdistance[index] = distance;
}
var sortedDict2 = (from entry in listdistance
orderby entry.Value descending
select entry.Key);
foreach (int key in sortedDict2)
{
cubes[key].Draw(g, cameraPosition, angles, viewer,
cubes[key].CuberRotationAngles, point3d, cubes[key].dir);
}
一小段代码检查游戏的完整性.(The little piece of code check for game completeness.)
public bool Check()
{
bool bCheck = true;
for (int iPos = 0; iPos < 27; iPos++)
{
if (CubesAtposition[iPos] != iPos)
{
bCheck = false;
break;
}
}
return bCheck;
}
我已经完成了这篇文章.一定要写信给我(I am done with the article. Do write to me at)Atulloona4@gmail.com(Atulloona4@gmail.com)如有任何疑问,请投票.(for any queries and please do vote.) 谢谢!(Thanks!)
许可
本文以及所有相关的源代码和文件均已获得The Code Project Open License (CPOL)的许可。
C# 新闻 翻译