贪吃蛇的算法分析

贪吃蛇是一款非常经典的手机游戏。它有很多算法，这里详细分析一种比较优秀的算法。
首先介绍下主要用到的七个类：

l          WormMain：最主要的类，控制所有其它类的运行和销毁。

l          WormPit：处理键盘输入事件并实例化Worm类和WormFood类的。

l          Worm：抽象了贪吃蛇的属性和动作

l          WormFood：抽象了食物的属性和动作

l          WormScore：用来纪录分数的类

l          WormLink：抽象了蛇身上的一段，保存了这段的坐标、方向和所有状态。

l          WormException：处理异常类

基本概念介绍

节：一条蛇可以看成有许多正方形的“小格子”拼凑成，我把它称作节。节是蛇身上最小的单位。

段：当许多节连成一条直线，我称它为段。上图的贪吃蛇只有一段，如果它拐弯就变成两段。

链表：用来保存每一段的状态，链表的元素单位是段。且链表的最后一个元素表示蛇的头部段。

坐标系：MIDP中的坐标以左上角那点为(0,0)，向右则x递增，向下则y递增。

Worm类

一条完整的贪吃蛇是由一段一段组成的。链表中保存的第一个元素是蛇的尾巴段，最后一个元素是蛇的头部段。当蛇运动的时候，它头部段增加一节而尾段减少一节。如果它吃到了食物，尾部段就不减少一节。也就是说，蛇是从头部段开始长的。 

下面的代码段显示了Worm类保存的各种属性：

    /* 贪吃蛇可能移动的方向 */

    public final static byte DOWN  = 2;

    public final static byte LEFT  = 4;

    public final static byte RIGHT = 6;

    public final static byte UP    = 8;

    // 贪吃蛇的当前方向

    private byte currentDirection;

    // 保存贪吃蛇每一段的列表

    private Vector worm = new Vector(5, 2);

         // 是否需要更新状态

    private boolean needUpdate;

    // 是否在运动中

    private boolean moveOnNextUpdate;

    // 是否吃到食物

    private boolean hasEaten;

         // 贪吃蛇的初始位置、长度和方向

    private final static int INIT_X = 3;

    private final static int INIT_Y = 8;

    private final static int INIT_LEN = 8;

    private final static byte INIT_DIR = RIGHT;

 下面重点介绍下Worm类中的几个方法：

l          public void setDirection(byte direction)

这个方法用来改变贪吃蛇运动的方向，只能90度。看下面的实现代码：

if ((direction != currentDirection) && !needUpdate) {

             // 取出列表中的最后一个元素(蛇的头部)

                   WormLink sl = (WormLink)worm.lastElement();

                   int x = sl.getEndX();

                   int y = sl.getEndY();

         // 不同的运动方向坐标的改变也不一样

                   switch (direction) {

                   case UP: // 当这段向上运动的时候

                       if (currentDirection != DOWN) {

                            y--; needUpdate = true;                  }

                       break;

                   case DOWN: // 当这段向下运动的时候

                       if (currentDirection != UP) {

                            y++; needUpdate = true;                }

                       break;

                   case LEFT: // 当这段向左运动的时候

                       if (currentDirection != RIGHT) {

                            x--; needUpdate = true;                  }

                       break;

                   case RIGHT: // 当这段向右运动的时候

                       if (currentDirection != LEFT)  {

                            x++; needUpdate = true;                }

                      break;                 }

                   // 当更改方向后需要更新

                   if (needUpdate == true) {

                       worm.addElement(new WormLink(x, y, 0, direction));

                       currentDirection = direction;                 }            }

 l          public void update(Graphics g)

这个函数是更新贪吃蛇状态。每次更新都把头部增加一节，尾部减少一节。如果它吃到食物尾部段就不减少一节。看起来就像整只蛇长了一节。 

                   // 把贪吃蛇头部增加一格

             head = (WormLink)worm.lastElement();

             head.increaseLength();

                   // 如果没有吃到食物则尾部减少一格

             if (!hasEaten) {

                      WormLink tail;

                      tail = (WormLink)worm.firstElement();

                      int tailX = tail.getX();

                      int tailY = tail.getY();

                     // 如果尾部块长度为0就删除

                      tail.decreaseLength();

                      if (tail.getLength() == 0) {

                          worm.removeElement(tail);              }

                      // 尾部减少一格

                      g.setColor(WormPit.ERASE_COLOUR);

                      drawLink(g, tailX, tailY, tailX, tailY, 1);

                } else {       

                // 如果吃到食物就不删除尾部

                      hasEaten = false;               }

             needUpdate = false;

             // 确认是否在边界中

             if (!WormPit.isInBounds(head.getEndX(), head.getEndY())) {

                // 如果不在，就死了

                      throw new WormException("over the edge");          }

             headX = (byte)head.getEndX();

             headY = (byte)head.getEndY();

             //贪吃蛇的头部增加一格

             g.setColor(WormPit.DRAW_COLOUR);

             drawLink(g, headX, headY, headX, headY, 1);

             // 判断是否吃到自己

             for (int i = 0; i < worm.size()-1; i++) {

                   sl = (WormLink)worm.elementAt(i);

                   if (sl.contains(headX, headY)) {

                       throw new WormException("you ate yourself");          }            }

 l          void drawLink(Graphics g, int x1, int y1, int x2, int y2, int len)

这个函数用来画蛇的一段，一只完整的蛇是一段一段组成的。

// 把长度转换成像素长度

         len *= WormPit.CELL_SIZE;

         // (x1 == x2)说明这一段是垂直的

         if (x1 == x2) {

                   // 把x1转成像素长度

             x1 *= WormPit.CELL_SIZE;

             // (y2 < y1)说明是向上运动

             if (y2 < y1) {

// 就把头、尾左边交换并转成像素

                   y1 = y2 * WormPit.CELL_SIZE;

             } else {          

             // 把y1转成像素

                   y1 *= WormPit.CELL_SIZE;           }

             g.fillRect(x1, y1, WormPit.CELL_SIZE, len);

         } else {

                   // 这是水平的一段

             y1 *= WormPit.CELL_SIZE;

             if (x2 < x1) {

             // 就把头、尾左边交换并转成像素

                   x1 = x2 * WormPit.CELL_SIZE;

             } else {

                   x1 *= WormPit.CELL_SIZE;           }

             g.fillRect(x1, y1, len, WormPit.CELL_SIZE);        }

 l          public void paint(Graphics g)

画出一只完整的贪吃蛇

WormLink sl;

         int x1, x2, y1, y2;

         int len;

         for (int i = 0; i < worm.size(); i++) {

                   // 取出每一段，然后画出这一段，连起来就是一只完整的蛇

             sl = (WormLink)worm.elementAt(i);

             x1 = sl.getX();    x2 = sl.getEndX();

             y1 = sl.getY();    y2 = sl.getEndY();

             len = sl.getLength();

             drawLink(g, x1, y1, x2, y2, len);   }

 WormLink类

贪吃蛇是由一节一节组成的。因为它经常有一些节连成一条直线形成段，所以这是一种相对有效的方法来保存整个蛇。[X,Y]表示段头部的坐标，然后段的头部开始按照方向向后画若干节。(段的头尾和蛇的头尾不是一个概念)

下面代码段是WormLink中的段得属性：

         // 段头部坐标

    private int x, y;

    // 段长度

    private int len;

    // 移动方向

    private byte dir;

 下面重点介绍几个重要函数：

l          public void decreaseLength()

这是从段的头部减少一格

// 首先段的总长度减少1

len--;

         switch (dir) { // 不同的方向左边的改变也不一样

         case Worm.LEFT:

             x--;         break;

         case Worm.RIGHT:

             x+