本帖最后由 陆权允 于 2017-4-1 18:56 编辑
贪食蛇相信大家都玩过吧。 之前在逛贴吧的时候看到过一副很BT的动态图
人做这样的事情还是很有难度的。 今天我们考虑用java写一个贪食蛇的简单AI,来实现上面图片中的吃满屏幕的情况。
贪食蛇网上代码也很多，大家也写了无数遍了，在这里就不详细描述，主要说下AI的思路。
这里主要用到了BFS算法，BFS在二维数组中搜索两点间最短距离用到
当然也还有一些其他算法也可以用，我只试过BFS，DFS和A*
第一步先让蛇动起来
如果一开始就想一次写好AI，会不知道从哪里开始写，所以我们先从简单的开始，然后慢慢改进。
我们先用BFS算法搜到蛇头到食物间的最短距离，然后让蛇按这个最短路径去吃食物。
蛇看到食物就直奔食物去了，也没想想如果吃了食物是不是还有活路。蛇总要为自己的下一步行动做考虑，这样才能活的久一点。
我们现在先让蛇学聪明点，让蛇每走一步就停下来，想想人生，欣赏下风景，看看前面通往美食的路上是否充满陷阱。
当然，只停下来想想是没有用的，实践出真知。现在蛇必须会一项技能，叫分身术，这个分身术有点厉害，这个分身可以进入另一个平行世间，分身在平行世界里面无论做了什么都不会影响蛇自己的世间。但是分身在平行世界了中了陷阱，它就回到现实世界并告诉蛇，前面的路不安全。
(这里 我们还可以 进一步思考，让分身再分身一个分身到另一个平行世界...可以用递归来做，好复杂，本人能力有限，尝试了一下就放弃了...)
蛇这么BT技能，用到的就是java中的克隆(clone)。
现在我们的蛇吃食物的策略就是，看到食物，让分身到平行世界里走一步看有没有危险，如果有危险，就告诉蛇前面的路不能走。如果没有危险，蛇就朝食物走一步。
这里我们还要分析下，什么是危险，或者什么是安全。
仔细看第一幅图，我们可以发现，那条蛇迷人的步伐都只是为了追着自己的尾巴。。*蛇头每走一步，蛇尾就空出一步，所以蛇头到蛇尾有路径就算安全*，那危险就是蛇头找不到蛇尾。
蛇头找不到蛇尾只是危险，但不一定会死掉。
为了避免死掉，只要是危险，我们就应该避免。
那蛇现在的思路就是：
看到美食，让分身探路，没有危险，朝美食走最短距离，有危险。走蛇头到蛇尾的最远距离(为什么是最远距离。最远距离蛇身会紧紧挨在一起，可以空出空地来)，直到蛇可以安全的吃食物；
当然还有看不到美食的情况，美食随机出现在蛇身围起来的封闭空间里了。这个时候 蛇走蛇尾的最远距离，直到蛇头和美食间有最短距离。
当蛇头无路可走游戏结束。
|
|
收藏
淘帖
踩
