成本控制部工作职责

1嵌入式系统开发设计课程设计设计题目软件中的典型算法分析学院名称信息科学与技术学院专业名称学生姓名学生学号任课教师设计成绩教务处制2015年3月24日2软件中的典型算法分析摘要此次课程设计为加农炮游戏，这是一款基于Linux平台，运用QtCreater软件开发的一款小游戏。本文将从加农炮的设计及实现出发，分析在实现过程中的一些典型算法。其中包括坐标转换算法、碰撞检测算法、边界检测算法、定时器驱动等。关键词：坐标转换算法；碰撞检测算法；边界检测算法；定时器驱动；QtCreater1、加农炮整体实现流程1.1加农炮设计与实现简述这是一款基于Linux平台，运用QtCreater软件开发的一款加农炮小游戏。游戏的界面为一个窗口，在窗口的右边从上到下以此是：quit按钮，该按钮的作用是用于关闭游戏与窗口中×的作用相同；AngelLED显示屏，屏上显示的数据就是炮台当前的角度，下边是一个滚动滑条用于控制炮台的角度，炮台角度的范围是0度~70度，当滑条向左边滑动，炮台的角度变小，当滑条向右边滑动，炮台的角3度变大；ForceLED显示屏，屏上显示的数据是炮台射出的炮弹的力度，下边的滑条用于控制炮台射出炮弹的速度，炮弹的速度范围是0~50，当滑条向右边滑动，炮弹的力度变大，当向左边滑动，炮弹的力度变小。窗口的上边一栏从左到右分别是：Shoot按钮，当用户按下这个按钮后炮台会发射一个炮弹，炮弹的轨迹遵循物理定理，将成一个抛物线运动；HitsLED显示屏，屏上的数据显示的是炮台发出的炮弹击中木块的次数，最多显示为15；ShootsLeftLED显示屏，屏上的数据显示的是炮台还可以发出的炮弹数，默认的初始值为15，最小为0；NewGame按钮，当用户按下这个按钮时，其将进入一个新游戏，所有的值都变为初始值。窗口的右下方的大屏幕即为游戏显示界面，炮台位于游戏显示界面的左下角，在游戏显示界面的任意位置处有一个小木条。当用户打开游戏界面后按下Shoot按钮时，炮台自动发射一个炮弹，如果炮弹击打到小木块，炮弹和小木块会同时消失，同时会在游戏显示界面的另外一个任意位置显示出另外一个小木块，如果用户发射出的炮弹没有击打到小木块，用户可以通过调整炮台的角度，发射炮弹的力度来调整炮弹的运动轨迹以此来使炮弹能够击打到小木块，当用户发射够15枚炮弹是，游戏显示界面会显示GameOver同时游戏显示界面的炮台和炮弹会消失，当没有发射完后，用户继续发射。如果用户没有发射完炮弹就想进行新游戏，这个操作也是被允许的。自定义窗口部件：•lcdrange.h包含LCDRange类定义。4•lcdrange.cpp包含LCDRange类实现。•cannon.h包含CannonField类定义。•cannonfield.cpp包含CannonField类实现。•main.cpp包含MyWidget和main。1.2流程图561.3加农炮模块分析及整体界面1.3.1按钮按钮是执行游戏界面的退出功能；是执行炮弹的发射功能；按钮式执行新游戏的功能。1.3.2LED显示击中木块数显示屏；可发送炮弹数显示屏；炮台角度显示屏及滑动条；力度显示屏及滑动条。其中，Angel和Force滚动条，两个作用分别用于控制炮台的角度与力度。71.3.3加农炮界面2、坐标转换算法2.1坐标转换原理我们已经能够使用QPainter的相关函数画出一些东西了。接下来，我们要看的是QPainter的坐标系统。同很多坐标系统一样，QPainter的默认坐标的原点(0,0)位于屏幕的左上角，X轴正方向是水平向右，Y轴正方向是竖直向下。在这个坐标系统中，每个像素占据1x1的空间。你可以把它想象成是一张坐标值，其中的每个小格都是1个像素。这么说来，一个像素的中心实际上是一个“半像素坐标系”，也就是说，像素(x,y)的中心位8置其实是在(x+0.5,y+0.5)的位置上。因此，如果我们使用QPainter在(100,100)处绘制一个像素，那么，这个像素的中心坐标是(100.5,100.5)。这种细微的差别在实际应用中，特别是对坐标要求精确的系统中是很重要的。首先，只有在禁止反走样，也就是默认状态下，才会有这0.5像素的偏移；如果使用了反走样，那么，我们画(100,100)位置的像素时，QPainter会在(99.5,99.5)，(99.5,100.5)，(100.5,99.5)和(100.5,100.5)四个位置绘制一个亮色的像素，这么产生的效果就是在这四个像素的焦点处(100,100)产生了一个像素。如果不需要这个特性，就需要将QPainter的坐标系平移(0.5,0.5)。这一特性在绘制直线、矩形等图形的时候都会用到。下图给出了在没有反走样技术时，使用drawRect(2,2,6,5)绘制一个矩形的示例。在NoPen的情况下，请注意矩形左上角的像素是在(2,2)，其中心位置是在(2.5,2.5)的位置。然后注意下有不同的Pen的值的绘制样式，在Pen宽为1时，实际画出的矩形的面积是7x6的(图出自C++GUIProgrammingwithQt4,2ndEdition)：在具有反走样时，使用drawRect(2,2,6,5)的效果如下(图出自C++GUIProgrammingwithQt4,2ndEdition)：9注意我们前面说过，通过平移QPainter的坐标系来消除着0.5像素的差异。下面给出了使用drawRect(2.5,2.5,6,5)在反走样情况下绘制的矩形(图出自C++GUIProgrammingwithQt4,2ndEdition)：请对比与上图的区别。在上述的QPainter的默认坐标系下，QPainter提供了视口(viewport)窗口(window)机制，用于绘制与绘制设备的大小和分辨率无关的图形。视口和窗口是紧密的联系在一起的，它们一般都是矩形。视口是由物理坐标确定其大小，而窗口则是由逻辑坐标决定。我们在使用QPainter进行绘制时，传给QPainter的是逻辑坐标，然后，Qt的绘图机制会使用坐标变换将逻辑坐标转换成物理坐标后进行绘制。通常，视口和窗口的坐标是一致的。比如一个600x800的widget(这是一个widget，或许是一个对话框，或许是一个面板等等)，默认情况下，视口和窗口都是一个320x200的矩形，原点都在(0,0)，此时，视口和窗口的坐标是相同的。注意到QPainter提供了setWindow()和setViewport()函数，用来设置视口和窗口的矩形大小。比如，在上面所述的320x200的widget10中，我们要设置一个从(-50,-50)到(+50,+50)，原点在中心的矩形窗口，就可以使用painter.setWindow(-50,-50,100,100);其中，(-50,-50)指明了原点，100,100指明了窗口的长和宽。这里的“指明原点”意思是，逻辑坐标的(-50,-50)对应着物理坐标的(0,0)；“长和宽”说明，逻辑坐标系下的长100，宽100实际上对应物理坐标系的长320，宽200。或许你已经发现这么一个好处，我们可以随时改变window的范围，而不改变底层物理坐标系。这就是前面所说的，视口与窗口的作用：“绘制与绘制设备的大小和分辨率无关的图形”，如下图所示：除了视口与窗口的变化，QPainter还提供了一个“世界坐标系”，同样也可以变换图形。所不同的是，视口与窗口实际上是统一图形在两个坐标系下的表达，而世界坐标系的变换是通过改变坐标系来平移、缩放、旋转、剪切图形。为了清楚起见，我们来看下面一个例子：voidPaintedWidget::paintEvent(QPaintEvent*event){QPainterpainter(this);QFontfont(Courier,24);painter.setFont(font);painter.drawText(50,50,Hello,11world!);QTransformtransform;transform.rotate(+45.0);painter.setWorldTransform(transform);painter.drawText(60,60,Hello,world!);}为了显示方便，我在这里使用了QFont改变了字体。QPainter的drawText()函数提供了绘制文本的功能。它有几种重载形式，我们使用了其中的一种，即制定文本的坐标然后绘制。需要注意的是，这里的坐标是文字左下角的坐标(特别提醒这一点，因为很多绘图系统，比如Java2D都是把左上角作为坐标点的)！下面是运行结果：我们使用QTransform做了一个rotate变换。这个变换就是旋转，而且是顺时针旋转45度。然后我们使用这个变换设置了QPainter的世界坐标系，注意到QPainter是一个状态机，所以这种变换并不会改变之前的状态，因此只有第二个Hello,world!被旋转了。确切的说，被旋转的是坐标系而不是这个文字！122.2坐标变换在加农炮中的实现CannonField::CannonField(QWidget*parent):QWidget(parent){r=QRect(0,0,0,0);target=QRect(0,0,0,0);timerCount=0;currentAngle=45;currentForce=45;setPalette(QPalette(QColor(250,250,200)));setAutoFillBackground(true);}voidCannonField::paintEvent(QPaintEvent*/*event*/){QPainterpainter(this);painter.drawText(200,200,tr(Angle=)+QString::number(currentAngle)+\t+tr(Force=)+QString::number(currentForce));painter.setPen(Qt::NoPen);painter.setBrush(Qt::blue);painter.drawRect(r);painter.drawRect(target);13painter.translate(0,rect().height());painter.drawPie(QRect(-35,-35,70,70),0,90*16);painter.rotate(-currentAngle);painter.drawRect(QRect(30,-5,20,10));}3、碰撞检测算法3.1碰撞检测算法原理目前碰撞检测算法主要有两种,一种是转化为判断线面的相交问题,另一种是建立在包围盒基础上,并对其不断完善的算法。这两种算法的原理为:第一种:以视点为起点,前进步长为长度形成线段,将此线段与场景中的所有可见面进行相交运算,如果有交点(相交),则表示发生了碰撞。第二种:如果是物体与场景之间的碰撞检测,则沿前进方向作一条射线,射线首先与包围盒检测相交,然后再作多变性相交检测;如果是三维实体之间的碰撞检测,给三维对象建立包围盒,计算包围盒在三维空间的相交情况,具体做法是先用包围盒(球)进行两两碰撞检测,如果碰撞了包围球,则用多边形碰撞检测方法进行计算,但场景实体很多的话,14这个方法的效率比较低。传统的算法都是要给模型建立包围盒,包围盒分为盒状和球状,其中以球状的比较简单,只需记录圆心和半径即可检测碰撞,矩形包围盒相对比较麻烦。但是,这两种用于检测碰撞不够精确,扩大了检测的区域,有些还没有碰撞的物体,也可能会被检测为已碰撞。算法的提出主要是为了解决在场景中进行漫游时视点的碰撞问题,所以假定物体的运动轨迹为直线,并通过对模型生成不规则多面包围体来检测碰撞。碰撞检测主要用来检测运动物体与场景内模型是否存在相互包含,运动物体可以是点也可以是实体。此算法的设计,综合了包围盒(球)算法的优点,在一定程度上克服了它的弱点。首先,选择运动物体的碰撞检测点,并记录碰撞检测点