javaScript 广度优先搜索法"自动推箱子"（二）

128kj

浏览: 601213 次
来自: ...

最近访客更多访客>>

hcmfys

caizi12

sdtvyyb_007

hanqunfeng

博主相关

博客

微博

相册

留言

关于我

文章分类

社区版块

存档分类

博客分类：

javascript

javascript.html html5 算法编程

接上文： 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

50059.zip (10.3 KB)
下载次数: 3

0
顶

1
踩

分享到：

HTML5 Canvas学习笔记(1)处理鼠标事件 | javaScript 广度优先搜索法"自动推箱子" ...

2014-06-12 09:57
浏览 1340
评论(0)
分类:编程语言
查看更多

发表评论

您还没有登录,请您登录后再发表评论

最近访客更多访客>>

博主相关

文章分类

社区版块

存档分类

最新评论