javaScript广度优先搜索法“;自动推箱子“;(二)

接上文: javaScript 广度优先搜索法”自动推箱子”(一)http://128kj.iteye.com/blog/2078626

代码第二部分。Test-4.html

<!DOCTYPE html>

<html lang=”zh”>

  <head>

   <meta charset=”gbk”>

   <title>推箱子AI</title>

   <script src=”Storehouse.js”></script>

</head>

<body>

<h3>当前分析的状态</h3>

<div id=”state”></div>

<h3>从当前状态产生的一个新状态</h3>

<div id=”msg”></div>

</body>

</html>

<script>

var playerPos={x:5,y:5};//人开始坐标

   

        //第四关地图数据http://www.108js.com

        var map= [[“1”, “1”, “1”, “1”, “1”, “1”, “1”, “1”, “1”, “1”, “1”, “1”, “1”, “1”, “1”, “1”, “1”, “1”],

                 [“1”, “1”, “1”, “1”, “1”, “1”, “1”, “1”, “1”, “1”, “1”, “1”, “1”, “1”, “1”, “1”, “1”, “1”],

                 [“1”, “1”, “1”, “1”, “1”, “1”, “1”, “1”, “1”, “1”, “1”, “1”, “1”, “1”, “1”, “1”, “1”, “1”],

                 [“1”, “1”, “1”, “1”, “1”, “#”, “#”, “#”, “#”, “1”, “1”, “1”, “1”, “1”, “1”, “1”, “1”, “1”],

                 [“1”, “1”, “1”, “1”, “#”, “#”, “.”, “.”, “#”, “1”, “1”, “1”, “1”, “1”, “1”, “1”, “1”, “1”],

                 [“1”, “1”, “1”, “1”, “#”, “S”, “B”, “.”, “#”, “1”, “1”, “1”, “1”, “1”, “1”, “1”, “1”, “1”],

                 [“1”, “1”, “1”, “1”, “#”, “#”, “B”, “.”, “#”, “#”, “1”, “1”, “1”, “1”, “1”, “1”, “1”, “1”],

                 [“1”, “1”, “1”, “1”, “#”, “#”, “.”, “B”, “.”, “#”, “1”, “1”, “1”, “1”, “1”, “1”, “1”, “1”],

                 [“1”, “1”, “1”, “1”, “#”, “T”, “B”, “.”, “.”, “#”, “1”, “1”, “1”, “1”, “1”, “1”, “1”, “1”],

                 [“1”, “1”, “1”, “1”, “#”, “T”, “T”, “Y”, “T”, “#”, “1”, “1”, “1”, “1”, “1”, “1”, “1”, “1”],

                 [“1”, “1”, “1”, “1”, “#”, “#”, “#”, “#”, “#”, “#”, “1”, “1”, “1”, “1”, “1”, “1”, “1”, “1”],

                 [“1”, “1”, “1”, “1”, “1”, “1”, “1”, “1”, “1”, “1”, “1”, “1”, “1”, “1”, “1”, “1”, “1”, “1”],

                 [“1”, “1”, “1”, “1”, “1”, “1”, “1”, “1”, “1”, “1”, “1”, “1”, “1”, “1”, “1”, “1”, “1”, “1”],

                 [“1”, “1”, “1”, “1”, “1”, “1”, “1”, “1”, “1”, “1”, “1”, “1”, “1”, “1”, “1”, “1”, “1”, “1”]];

var dx = [-1, 1, 0, 0];//人有四个方向可移动,下,上,右,左

var dy = [0, 0, 1, -1];

var tempmap=null;//临时的地图数据

var Queue=[]; //队列,保存程序中产生的推箱子状态

var allstate=[];//保存所有状态,用于判断重复

var finish=false;//是否结束

var state=new Storehouse(playerPos,map,null,””,0);//最初状态,参数有:人的位置,地图,父状态,来到此状态的路径和步数

var state1=state;//保存最初状态

allstate.push(state);//最初状态加入数组

function isExist(sta){//判断数组allstate中是否存在sta

      for(var i=0;i<allstate.length;i++)

         if(allstate[i].equals(sta))

            return true;

     return false;

  }

function Dfs() {

   Queue.unshift(state);//最初状态进队列http://www.108js.com

     while (Queue.length!=0) {

        state = Queue.pop();//从队列中出队的节点

        document.getElementById(“state”).innerHTML=state.toString();

        // 从“人”可走的四个方向上下右左分析队列中弹出的状态”);

        for (var i = 0; i < 4; ++i) {

            switch(i){

              case 0:

                movePlay(state,-1,0,”u”);

                break;

              case 1:

                movePlay(state,1,0,”d”);

                break;

              case 2:

               movePlay(state,0,1,”r”);

               break;

              case 3:

               movePlay(state,0,-1,”l”);

               break;

            }          

            if(finish){//如果找到了答案

              return;

            }

          }

       }

     return false;

  }

function movePlay(state,m,n,direc){ //移动玩家,m行,n例,参数为偏移量

        var player=state.getPlayerPos();//玩家的位置

        var tempmap=copyArray(state.getMap());//克隆地图

        var ts=null;

        //人物的下一个位置

        var tempPos ={x:0,y:0};

        //箱子的下一个位置

        var boxPos ={x:0,y:0};

        tempPos.x=player.x+m;

        tempPos.y=player.y+n;

      

        if(!state.isOk(tempPos)) return;//位置出界

        var playerMap = tempmap[tempPos.x][tempPos.y]; //人物位置地图数值

        //人物的下个位置不能是石头,如果是,什么也不做。

        if(playerMap!=”#”){

            //人物碰到箱子或处在目标点上的箱子

            if(playerMap==”B”||playerMap==”Y”){

                 boxPos.x = tempPos.x+m;

                 boxPos.y = tempPos.y+n;

                 if(!state.isOk(boxPos)) return;

                 var boxMap = tempmap[boxPos.x][boxPos.y]; //箱子位置地图数值

                //箱子的下一位置不能是石头或箱子

                if(boxMap!=”#” && boxMap!=”B” && boxMap!=”Y”){

                    //先箱子移动

                    if(boxMap==”.”){//空地

                        tempmap[boxPos.x][boxPos.y] =”B”;

                    }else if(boxMap==”T”){//成功推了一个箱子

                        tempmap[boxPos.x][boxPos.y] = “Y”;

                    }

                    //再移动人

                    if(playerMap==”Y”){

                        tempmap[tempPos.x][tempPos.y] =”Z”;//碰到在目标点上的箱子,变成人在目标点上

                    }else{

                        tempmap[tempPos.x][tempPos.y] = “S”;//人到箱子的位置

                    }

                  

                   if(tempmap[player.x][player.y]==”Z”){//人原来在一个目标点上

                       tempmap[player.x][player.y]=”T”;//人的原来位置设为目标点

                    }

                    else {

                        tempmap[player.x][player.y]=”.”;//人的原来位置设为空地

                    }

                     ts=new Storehouse(tempPos,tempmap,state,state.getPath()+direc.toUpperCase(),state.getStep()+1);//新状态

                 

                      if(ts.isWin()){ //判断新状态是否完成任务,return;否则

                           document.getElementById(“state”).innerHTML=state1.toString();

                           document.getElementById(“msg”).innerHTML=ts.toString();

                           document.write(“胜利完成任务<br>”);

                           document.write(“推箱子路径为:”+ts.getPath()+”<br>”);

                           document.write(“所用步数为:”+ts.getStep()+”<br>”);

                          finish=true;

                          return;

                       }

                    

                       if(!ts.isBlock(new Array(),boxPos.x,boxPos.y)&&!isExist(ts)){ // 分析此状态是否是死的或已经存在”)

                         //产生了一个新状态;

                          document.getElementById(“msg”).innerHTML=ts.toString();

                          allstate.push(ts);//保存此状态

                          Queue.unshift(ts);//进队列

                       }

                }

            }else{//人物碰到空地或碰到目标点http://www.108js.com

                   if(tempmap[player.x][player.y]==”Z”){//人原来在一个目标点上

                       tempmap[player.x][player.y]=”T”;//人的原来位置设为目标点

                       if(tempmap[tempPos.x][tempPos.y]==”T”)//

                         tempmap[tempPos.x][tempPos.y]=”Z”;//人在目标点上

                       else  tempmap[tempPos.x][tempPos.y]=”S”;//新的地图数据设置为人

                    }else if(tempmap[player.x][player.y]==”S”){//人的原来位置

                       tempmap[player.x][player.y]=”.”;//人的原来位置设为空地

                       if(tempmap[tempPos.x][tempPos.y]==”T”)//

                         tempmap[tempPos.x][tempPos.y]=”Z”;//人在目标点上

                       else  tempmap[tempPos.x][tempPos.y]=”S”;//新的地图数据设置为人

                    }

                   

                 ts=new Storehouse(tempPos,tempmap,state,state.getPath()+direc,state.getStep()+1);//产生一个状态

                 if(!isExist(ts)) {

                    //新状态

                    document.getElementById(“msg”).innerHTML=ts.toString();

                    allstate.push(ts); 

                    Queue.unshift(ts);//进队列

                }

            }

        }

        //人的下个位置是石头

  }

   //克隆二维数组

    function  copyArray(arr){

var b=[];

for(i=0;i<arr.length;i++)

{

b[i]=arr[i].concat();

}

return b;

    }     

  Dfs();

</script>

最后给出源码下载。欢迎批评指正。

欢迎访问博主的网站:http://www.108js.com

发表评论

电子邮件地址不会被公开。 必填项已用*标注