• 热门专题

Perl看完这个 再不敢说自己会玩贪吃蛇

作者:葡萄不吐皮  发布日期:2015-06-23 21:48:14
Tag标签:再不  
  •   某天闲逛时看见一副动图:

        

      真的是非常贪吃,各种拐弯各种吃,感觉十分有趣。

      用Perl来实现自动吃满,蓄谋已久,之前的字符贪吃蛇、深度优先算法、A*算法,都是为此篇做铺垫。

      

      那么,怎样让蛇不吃到自己呢?

      1、让蛇按照我们设计好的路线行进,在一个N*M(N、M均为偶数,奇数不讨论)的游戏区域,设计好路线如下:

        

        当花儿谢了,果子熟透,春夏秋冬一个轮回后,蛇终于吃满了。。。

      2、假设蛇总是追着自己的尾巴跑,那么永远不会死;然而,这没什么鸟用,我们需要的是一条“贪吃”的蛇。

      3、在2上稍稍改进,吃完食物后再追着尾巴,嗯,已经很接近了。但是问题来了:怎么吃到食物?吃到食物后被围死怎么办?

      其实我的想法就是解决3中的问题:

      1、使用A*算法计算到食物的最短路径

      2、模拟吃到食物后的场景,能否回到蛇尾;能--吃食物,不能--继续追着尾巴,重复1、2

      3、如果无法回到尾巴,保持当前移动方向(认命吧,要挂的节奏)

      伪码如下:

    #    while( 存活 && 未吃满){
    #        计算蛇头到食物的路径
    #        if( 有蛇头到食物的路径 ){
    #            模拟吃到食物后的场景
    #            计算是否有路径到达蛇尾
    #            if( 有路径 ){        
    #                执行蛇头到食物的路径
    #            }
    #            else{  # 没有到蛇尾的路径
    #                next
    #            }
    #        }
    #       找出当前可行方向追逐蛇尾
    #    }
    #    if(吃满){
    #        显示:祝贺
    #    }
    #    else{
    #        显示:wtf ?
    #    }

      模拟吃到食物后的场景:使用A*计算路径,并创建一条“影子蛇”用来模拟吃到食物后的状态

      计算是否有路径到达蛇尾:和“追逐蛇尾”方法类似,也可使用A*

      找出当前可行方向追逐蛇尾:

        由于移动时尾巴会变动,未尝试A*,使用指定方向深度优先搜索算法

        伪码如下:

    sub trace_tail{
        @moves=grep{可行};
        foreach(@moves){
            next if(下一步越界 || 吃到自己)
            unshift @feasible,$_ if(远离食物)
            其他方向 push @feasible
        }
        foreach(@feasible){
            next_move=cur_move+$_
            指定方向优先探索
            next_move的反向上一步设为不可通过
            每走一步,从蛇尾开始设未经过;每原路返回一次,当前位置的蛇身设不可通过
            if(有路径)return 1
        }
        执行完毕无路径,return cur_move
    }

      

      运行如下:

        

      实际上还是会被困死,虽然追逐尾巴时避开食物优先,但唯一路径可能会出现食物,不吃也得吃了。

      代码较乱,准备加好注释后贴上来。

延伸阅读:

About IT165 - 广告服务 - 隐私声明 - 版权申明 - 免责条款 - 网站地图 - 网友投稿 - 联系方式
本站内容来自于互联网,仅供用于网络技术学习,学习中请遵循相关法律法规