“进化一条贪吃蛇”是我多年前写的程序，差点就要遗失掉了。这两天整理了一下，重新放在网上。

网址：Evolve a Greedy Snake

我是根据这篇论文 Application of Genetic Programming to the Snake Game 来写这个程序的，主要是参考它的思路。

由于是多年前写的程序，有些地方已经不符合现在的Java规范了，暂时没有做太多改动。

它是根据“遗传程序设计”的算法，在很基础的“语法模块”的基础上，从随机生成的“语法树”开始，通过杂交交叉变异进化若干代后，会自动生成贪吃蛇行动的“程序”，使得贪吃蛇越来越“聪明”，能够自动躲避障碍物，自动寻找食物。

当时研究“遗传程序设计”的动机，是希望能够找到办法，不写程序，而让程序按照需求自动产生。

这个目标虽难以实现，但至今给我很多启发。

以下是进化贪吃蛇时，采用的基础语法模块：

叶子节点集合:

Forward:贪吃蛇向前走一步 
Left:贪吃蛇向左走一步 
Right:贪吃蛇向右走一步 

函数节点集合:

ifDangerAhead:如果前方再走一步就会遇到危险，就执行第一个分支，否则执行第二个
ifDangerTwoAhead:如果前方再走两步就会遇到危险，就执行第一个分支，否则执行第二个 
ifDangerLeft:如果向右再走一步就会遇到危险，就执行第一个分支，否则执行第二个 
ifDangerRight:如果向右再走一步就会遇到危险，就执行第一个分支，否则执行第二个 
ifFoodAhead:如果前方有食物，就执行第一个分支，否则执行第二个 
ifFoodRight:如果右边有食物，就执行第一个分支，否则执行第二个 
ifFoodUp:如果上边有食物，就执行第一个分支，否则执行第二个 
ifMovingDown:如果贪吃蛇正在向下走，就执行第一个分支，否则执行第二个
ifMovingLeft:如果贪吃蛇正在向左走，就执行第一个分支，否则执行第二个 
ifMovingRight:如果贪吃蛇正在向右走，就执行第一个分支，否则执行第二个 
ifMovingUp:如果贪吃蛇正在向上走，就执行第一个分支，否则执行第二个 
progn2:先执行第一个分支,再执行第二个分支 

以下是用该算法“进化”出的一个程序（采用这个程序，贪吃蛇可以平均吃25个食物才死掉）：

ifFoodRight
|-ifDangerRight
| |-ifDangerAhead
| | |-Left
| | |_ifDangerRight
| |   |-ifDangerRight
| |   | |-Forward
| |   | |_Left
| |   |_ifDangerRight
| |     |-ifMovingRight
| |     | |-ifFoodRight
| |     | | |-ifDangerRight
| |     | | | |-ifFoodRight
| |     | | | | |-Forward
| |     | | | | |_Right
| |     | | | |_ifDangerAhead
| |     | | |   |-ifFoodUp
| |     | | |   | |-Right
| |     | | |   | |_Right
| |     | | |   |_ifDangerAhead
| |     | | |     |-Forward
| |     | | |     |_Forward
| |     | | |_ifDangerRight
| |     | |   |-ifDangerLeft
| |     | |   | |-Left
| |     | |   | |_Left
| |     | |   |_ifMovingDown
| |     | |     |-Forward
| |     | |     |_Forward
| |     | |_ifDangerAhead
| |     |   |-ifFoodAhead
| |     |   | |-Left
| |     |   | |_Right
| |     |   |_ifDangerAhead
| |     |     |-Forward
| |     |     |_Forward
| |     |_progn2
| |       |-ifDangerTwoAhead
| |       | |-ifFoodAhead
| |       | | |-Left
| |       | | |_Forward
| |       | |_ifFoodUp
| |       |   |-Forward
| |       |   |_Forward
| |       |_progn2
| |         |-Right
| |         |_Forward
| |_ifMovingRight
|   |-ifMovingLeft
|   | |-Forward
|   | |_ifFoodUp
|   |   |-Left
|   |   |_Forward
|   |_Right
|_ifDangerRight
  |-ifMovingRight
  | |-Left
  | |_Forward
  |_ifDangerAhead
    |-Right
    |_Forward