贪食蛇相信大家都玩过吧。 之前在逛贴吧的时候看到过一副很BT的动态图


人做这样的事情还是很有难度的。 今天我们考虑用java写一个贪食蛇的简单AI,来实现上面图片中的吃满屏幕的情况。
贪食蛇网上代码也很多，大家也写了无数遍了，在这里就不详细描述，主要说下AI的思路。
这里主要用到了BFS算法，BFS在二维数组中搜索两点间最短距离用到
当然也还有一些其他算法也可以用，我只试过BFS，DFS和A*


第一步先让蛇动起来


如果一开始就想一次写好AI，会不知道从哪里开始写，所以我们先从简单的开始，然后慢慢改进。
我们先用BFS算法搜到蛇头到食物间的最短距离，然后让蛇按这个最短路径去吃食物。




蛇看到食物就直奔食物去了，也没想想如果吃了食物是不是还有活路。蛇总要为自己的下一步行动做考虑，这样才能活的久一点。


我们现在先让蛇学聪明点，让蛇每走一步就停下来，想想人生，欣赏下风景，看看前面通往美食的路上是否充满陷阱。


当然，只停下来想想是没有用的，实践出真知。现在蛇必须会一项技能，叫分身术，这个分身术有点厉害，这个分身可以进入另一个平行世间，分身在平行世界里面无论做了什么都不会影响蛇自己的世间。但是分身在平行世界了中了陷阱，它就回到现实世界并告诉蛇，前面的路不安全。
(这里 我们还可以 进一步思考，让分身再分身一个分身到另一个平行世界...可以用递归来做，好复杂，本人能力有限，尝试了一下就放弃了...)


蛇这么BT技能，用到的就是java中的克隆(clone)。


现在我们的蛇吃食物的策略就是，看到食物，让分身到平行世界里走一步看有没有危险，如果有危险，就告诉蛇前面的路不能走。如果没有危险，蛇就朝食物走一步。


这里我们还要分析下，什么是危险，或者什么是安全。


仔细看第一幅图，我们可以发现，那条蛇迷人的步伐都只是为了追着自己的尾巴。。*蛇头每走一步，蛇尾就空出一步，所以蛇头到蛇尾有路径就算安全*，那危险就是蛇头找不到蛇尾。


蛇头找不到蛇尾只是危险，但不一定会死掉。


为了避免死掉，只要是危险，我们就应该避免。


那蛇现在的思路就是：
看到美食，让分身探路，没有危险，朝美食走最短距离，有危险。走蛇头到蛇尾的最远距离(为什么是最远距离。最远距离蛇身会紧紧挨在一起，可以空出空地来)，直到蛇可以安全的吃食物；
当然还有看不到美食的情况，美食随机出现在蛇身围起来的封闭空间里了。这个时候 蛇走蛇尾的最远距离，直到蛇头和美食间有最短距离。
当蛇头无路可走游戏结束。

会思考人生的蛇




这张gif 我真的是用生命在优化，才将80M的视频优化到400Kb。


用爆力破解法可以遇到蛇吃满屏幕的情况。如果想写每次都能吃满屏幕，还是有很多细节需要考虑。个人能力有限，很多细节考虑不到。欢迎大家吐槽和建议

#### 思考


什么是智能？
这里贪食蛇显然是拥有了预测才显的智能。人的行动是不是也是因为人拥有强大的预测能力才显的聪明？

最后代码地址：http://git.oschina.net/gitgj/smart-snake
代码还不够完善，欢迎补充。


同时也参考了网上很多其他资料：
如何用Python写一个贪吃蛇AI

@神宫寺铃香厚颜无耻的问下，能不能加个精。