[讨论]从贪食蛇游戏程序中引出的代码级别优化问题

smile636

     引子: 怎样移动蛇身体,先不考虑绘制
    在贪食蛇游戏中,蛇有N个身体块(先不考虑头部),当蛇移动时,身体一块一块的向前移动,简化下问题,用一个矩形来表示蛇的一块身体部分,下面来考虑怎样移动蛇

     概要:
     为蛇的身设计数据结构,设计一个函数,功能是移动蛇.

      代码级别:
      简化下蛇身由一块矩形表示,那么移动了蛇身也就相当与移动矩形的位置,可以用两个基本类型变量表示(比如两个int),我们把它称为位置数据吧.这样整个蛇身体就用一个位置数据数组表示.
      另外补充下(和主题没多大关系,但为了蛇身的完整性,所以..),每块身体形状相同,所以矩形大小相同,可以只用两个基本数据表示它的长和宽.
      针对矩形位置我们用 struct {int x, int y}Location吧,正个身身体就表示成bodyLocations[N].
      现在来设计我们的函数,函数功能:根据输入的x,y偏移量来修改蛇身每块的位置:
      void moveBodyPart(int x, int y, Location location)
      {
             location.x += x;
             location.y += y;
      }
      这个函数简单吧.

      然后我们来移动整个蛇身体,我们先在相对蛇的全局变量中定义一个蛇的长度变量吧:int bodyLength.
      void moveBody(int x, int y) //x,y为 body移动偏移量
      {
             for(int i = 0; i<bodyLength; i++)
                       moveBodyPart(int x, int y, bodyLocations);           
       }
   
       然后你在判断键盘输入的地方使用moveBody即可完成蛇身移动;
      
       优化:
       第2个函数的for循环里频繁调用了函数moveBodyPart(...),我们把两个函数合并成一个:

       void moveBody(int x, int y) //x,y为 body移动偏移量
      {
             for(int i = 0; i<bodyLength; i++)
            {
                     bodyLocations.x += x;
                     bodyLocations.y += y;
             }
        }
  
      大家讨论下这两中情况,那种要好?
      1.传递数组元素给函数;
      2.传递数组整体给函数;
-------------------------------------------------------------------------------------------------------------------------
      进一步引出问题:
      从面向对象设计出发,把每个body看成是一个对象(因为他们在逻辑上是有清晰的界限)
于是有了 class BodyPart,有了N个BodyPart对象,从上层往下层考虑问题:移动蛇身就给每个BodyPart发送移动消息,然后BodyPart调用各自的移动方法,下面简略写出代码(代码不能编译)
       class Snake::moveBody(int x, int y)
       {   
               for(int i = 0; i<bodyLength; i++)
               {
                     m_bodys.move(x, y);        //m_bodys 是一个class BodyPart数组
               }            
       }

       下面大家来思考下这两中方式的性能哪个好:
       1.      
       class Snake::moveBody(int x, int y)
       {   
               for(int i = 0; i<bodyLength; i++)
               {
                     m_bodys.move(x, y);      
               }            
       }
      2.
       void moveBody(int x, int y) //x,y为 body移动偏移量
      {
             for(int i = 0; i<bodyLength; i++)
                       moveBodyPart(int x, int y, bodyLocations);           
       }  
      
       写这个我不是为了说明面向对象设计的代码性能没有面向过程的好,这里只是讨论了问题的一面或一部分,写这个只是为了解决一个大家经常遇到的问题..以后有时间我再来讲下面向对象.
              

       时间不早了,我吃饭去了!这里讲的贪食蛇游戏不完整,大家要的话,可以问我.不过我这里目前只有两个C#版本的.
        小弟功力还不深厚, 请大家点评\抨击  香蕉皮来了..闪~
      

smile636

这个问题蛮简单,但我想要一个严格的证明,和在一定环境下同一类问题的 简洁,快的解决方式.

另外贪食蛇的数据结构可以采用数组队列,这样可以减少N多次运算.不建议采用链表式队列,这个思维方式是动态申请和释放内存.小片内存频繁的创建和释放是一个很大的耗费,也可能造成内存碎片

aear

我想说的是，优化先从算法做起，至于代码级的优化，在大多数情况下是不必要的。根据你的程序，运行效率是 O(n)，也就是说，蛇有多长，代码就要运行相对的 N  * 每段身子的处理时间。

实际上考虑蛇的移动，每个结点实际上移动到前一个结点的位置。也就是说，只有尾巴结点和头结点有变化，其他的结点不同。因此可以考虑设计一种新的数据结构，类似循环链表数组。 每次蛇移动的时候，去掉尾巴的结点，添加一个头结点就够了，运行效率是恒定的，也就是 O(1)。

其次，对于代码到底怎么运行效率高，最好使用profiler来分析，比较流行的工具是Vtune,请到intel的网站上下载，并仔细阅读优化手册。

smile636

楼上说的也对,我故意不用队列解决这个问题只是为了方便说明主题.....

这里只从代码上讨论,我上面写出的是一个从分析到设计编码的过程,在设计和分析过程中由于涉及到的东西很多,所以一开始不会去考虑太多种的情况.而我说的是关于传递样类型的参数给 函数,方法要好.这个问题比较常见,但雷同. 从设计出发时不好决定这些,它们对上层逻辑来说是 偶然性 随机性的.

smile636

晕又打错字了,[传递什么样的参数]
如是传递数组头好还是传递数组元素

是传递结构体Struct{int x, int y, int z}指针好,还是传递(x, y, z)打散了的参数好?,这个既要考虑优化问题,又要考虑 调用该使用[结构体的函数] 的代码是方便提取/合成 打散了的参数还是整个结构体. 我相信在大多数情况下是有一定答案的.想清了这个问题以后就可以直接使用结论了

euclid

多讨论点这样的细节问题很好!