当前位置:首页 > 开发 > Web前端 > JavaScript > 正文

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

发表于: 2014-06-12   作者:128kj   来源:转载   浏览:
摘要: 接上文: javaScript 广度优先搜索法"自动推箱子"(一) http://128kj.iteye.com/blog/2078626 代码第二部分。Test-4.html <!DOCTYPE html> <html lang="zh">   <head>    &l
接上文: 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

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

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

编辑推荐
用JS写了一个“广度优先搜索法”自动推箱子,理论上无论多少箱子都可以求解,但事实上箱子多了以后
广度优先搜索是最简单的图搜索算法之一;在Prim 最小生成树算法和Dijkstra 单源最短路径算法中都采
昨天考虑了一个马跳棋盘的程序,思路很简单就是用广度优先搜索法进行搜索,不过思考过程中把我原来
图的遍历是指从图中的某一个顶点出发,按照某种搜索方法沿着图中的边对图中的所有顶点访问一次且仅
广度优先搜索(BFS:Breadth-First Search)是一种图搜索策略,其将搜索限制到 2 种操作: (a) 访问
深度优先搜索回顾 搜索算法的实现,从树的遍历角度讲,有深度优先和广度优先两种。深度优先我们在前
广度优先搜索的算法是:(1)从图中的某个节点v出发,依次访问该顶点的各个未曾被访问的邻接点,然
写在最前面的 两种图的遍历算法在其他图的算法当中都有应用,并且是基本的图论算法。 广度优先搜索
一、深度优先搜索 深度优先搜索就是在搜索树的每一层始终先只扩展一个子节点,不断地向纵深前进直到
深度优先搜索和广度优先搜索 一、深度优先搜索 深度优先搜索就是在搜索树的每一层始终先只扩展一个
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号