python解《十滴水》算法

时间:2013-03-11 | 分类:个人日志,学习园地 | 浏览:11819 | 评论:10 | 发表评论

最近在3366玩了一个小游戏,觉得挺有意思的,游戏名字叫《十滴水》,
游戏地址:http://www.3366.com/flash/1000154.shtml

游戏规则如下:
一开始玩家有10滴水,玩家点击格子就会在格子里增加1滴水。
水滴达到4滴后再加水就会破裂,破裂后会向四个方向溅出四滴水。
点击水滴使水滴爆破产生连锁反应,利用连锁反应消掉全部水滴。
水滴用完则游戏结束,同时破裂3滴水滴会增加1滴水,过关也会增加1滴水。


我试玩了一下,居然只过了7关,作为一个24k的纯屌丝,怎么可能忍受排名比好友落后呢?
所以试着用python写了一段自动解十滴水的代码。

写解法前要先整理一下思路:
1、由于格子有6*6格,所以可以用6*6的二维数组来保存数据,
数值是水滴数,如果格子上没有水滴就是0。
如上图的水滴数可以表示为:

t_list = [
    [4, 0, 0, 1, 0, 3],
    [2, 0, 3, 3, 1, 1],
    [1, 2, 2, 4, 3, 3],
    [0, 2, 3, 4, 4, 3],
    [0, 1, 3, 2, 2, 1],
    [0, 0, 2, 2, 1, 2]
]

2、在某个格子上增加1滴水,会出现两种结果:如果增加后数值不大于4,则不会引爆水滴;
如果数值大于4,该格子的水滴数变为0,并向4个方向溅出4滴水。溅出的水滴们每次移动一格,碰到其它水滴或超出边界则停止运动。

// 这一段可以忽略不看 
一开始用了递归的方法写算法,但是有时算出的结果和在游戏里实际操作的结果不同,
因为假设有一种局面是这样的:
0 0 0 0
0 0 0 0
4 0 4 3
4 4 4 0
在第4行第2列滴上1滴水,如果用递归的方法,会先向一个方向执行运算,直到返回结果才会向另一个方向运算。
如果递归先向左运算的话,(4,2)会引爆(4,1)、(3,1)、(3,3),这时(3,4)会增加1滴水变成4滴,然后(3,3)会引爆(4,3),这样最后剩下1滴水滴。
如果递归先向右运算的话,(4,2)会引爆(4,3)、(3,3),这时(3,4)会增加1滴水变成4滴,然后(3,3)会引爆(3,1),(3,1)向右的水滴会引爆(3,4),最后所有水滴都爆掉了。
这样会出现两种不同的结果,事实上游戏里溅出的水滴都是匀速运动的,溅出的水滴到达某个格子都存在一个距离的问题,而递归不能达到这个效果,因此这里不能用递归。

不用递归的话,就要用数组把溅出的4滴水滴的坐标保存起来,比如在坐标[2,3]处增加1滴水引爆了,则引爆数组可表示为:

t_burstlist = [
    [[2,3], [2,3], [2,3], [2,3]],
]

再用一个数组来保存4个方向,分别表示向左、下、上、右移动:

t_direction = [[-1,0], [0,1], [0,-1], [1,0]]

每循环一次就把引爆的坐标加上方向值,得出新的坐标,比如第一次移动后新的坐标就是:

t_burstlist = [
    [[1,3], [2,4], [2,2], [3,2]],
]

先判断坐标点是不是超出边界(小于0或等于6),超出边界就不处理。
如果没超出边界,就判断坐标上的水滴数。
如果水滴数为0则不处理。
如果有水滴就把引爆数组里的对应的坐标置为[-1,-1],如果水滴数小于4就加上1滴水,否则就把水滴数置为0并把该坐标保存到引爆数组里。
循环直到所有水滴超出边界为止。

3、找出最优解,一般都是采用贪婪算法,类似于中国象棋的AI算法,具体过程如下:
(1)、找出所有水滴的坐标,分别在每个坐标滴上1滴水,然后找出里面最优的局面。
但是只进行1层搜索往往找不到好的走法,所以要进行多层搜索。但搜索的层数越多,得出结果所花的时间就越多。不过对于6*6的数组来说,运算量不大,一般搜10层就够了,因为解出来的结果一般只需用到5滴水,很少有超出10滴水的。
比如图上有10个格子有水滴,做法就是分别在每个坐标滴上1滴水,得到10个局面。再在每个局面的每个有水滴的坐标分别滴上1滴水,然后找出其中最优的局面替换原来的局面。这样循环n层后再看哪个局面最优,就知道该点击哪个坐标了。

(2)、怎么知道一个局面的优劣呢,这就需要用一个数值来评估了。
①一个格子上有4滴水总比1滴水好,因为4滴水容易引爆。所以可以按水滴数来评分,1滴算1分,4滴算4分。
②但是越多格子有水滴就可能越难消除,从另一个方面来说越少格子有水滴越好,所以如果一个格子有水滴就减5分。
③还有看看下面这两个3*3的局面:

4 0 4  |  4 0 0
0 0 0  |  0 0 4
0 0 0  |  0 0 0

虽然分值一样,但是第一个图需要1滴水就引爆了,第二个图需要两滴,所以还要找出图中孤立的格子(上下左右都没有其它水滴的格子),1个孤立的格子减1分。所以第一个图的评估值是-2分,第二个图是-4分。
当图上所有水滴都引爆时评估值为0分,0分是最大值。
评估方法都不是绝对的,大家可以再根据一些局面增加评估分,这样得出的结果可能更优。

(3)、在贪婪搜索中,对所有局面按评估值进行降序排序,排在前面的就是最优的局面。一旦搜到0分的局面就可以返回不用再搜索了。

4、算法写好后,测一下上面的例子:

再到游戏里点击第4行第4列的点,游戏画面变成:

可见结果是正确的(不正确就不会发出来了)。

5、目前不能自动识别游戏界面的水滴数组,所以要自己手动输入太麻烦,所以只玩到了31关,下次再写个自动识别图像的程序吧。

源码下载

标签: , , ,
本文链接: python解《十滴水》算法
版权所有: 破博客, 转载请注明本文出处。

10个评论

  1. 尤克里里
    2015/06/29 11:13:50

    大神,给讲一下如何写出这个游戏的代码

    • admin
      2015/06/30 23:06:44

      一开始随机生成一些水滴数放到二维数组,然后爆破的算法跟文章里的算法差不多

  2. 你好
    2013/09/05 15:35:33

    这个十滴水外挂效果很不错哦
    http://blog.csdn.net/liuqqwwe/article/details/10976829 :evil:

  3. 孙华
    2013/04/29 22:13:50

    对于一个逻辑思维严重缺失的非相关从业闲散人士,看得迷糊啊。

  4. 红色石头
    2013/03/26 13:36:16

    建议:评论的表单记录到cookie
    请教:你的手机短信提示是怎么做的?

    • admin
      2013/03/26 13:38:05

      这篇文章就是介绍短信通知的。//www.poboke.com/study/wordpress-comments-to-send-sms-notification.html

  5. 红色石头
    2013/03/26 13:34:51

    这个主题好友特色啊~~~QQ迷啊

  6. 小五
    2013/03/20 09:06:40

    老师,他作弊。。。
    超级羡慕变成牛人 :neutral:

  7. wamdy
    2013/03/14 22:22:49

    递归确实是模拟算法的问题所在,所幸出现问题的机会不是很大,搜索5层确实太少了,其实高于5层的时候可以用剪枝的办法提高搜索的速度和深度。

    • admin
      2013/03/14 22:32:44

      你说得太对了,确实可以用剪枝法

发表评论

您的昵称: *

您的邮箱: * (显示gravatar头像)

联系方式: