`
128kj
  • 浏览: 601180 次
  • 来自: ...
社区版块
存档分类
最新评论

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

阅读更多
    用JS写了一个“广度优先搜索法”自动推箱子,理论上无论多少箱子都可以求解,但事实上箱子多了以后,就。。。;
有需要的拿出发挥,修改,高手就可以跳过了。。。

代码随后给出,先看运行效果:
第一关:http://www.108js.com/article/article5/zip/50059/Test-1.html
第四关:http://www.108js.com/article/article5/zip/50059/Test-4.html
第五关:http://www.108js.com/article/article5/zip/50059/Test-5.html

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

效果图:



上图是最初状态:S代表推箱子的人,#表示墙,有五个箱子B要推到目标点T,其中有一个箱子已经到了目标点,用Y表示。
下图是程序最后给出的解答:
   R,D,L,U 表示箱子向某个方向移动
   r,d,l,u 表示人向某个方向移动

代码分两部分:
第一部分:Storehouse.js
/*仓库类,表示推箱子过程中的一种状态*/
(function(){
   function Storehouse(playerPos,map,parent,path,step){
    this.playerPos=playerPos;//人的位置
    this.map=map;//地图
    this.parent=parent;//父状态
    this.path=path;//从最初状态来到此状态的路径
    this.step=step; //来到此状态的步数
   }
   //获取人的位置
   Storehouse.prototype.getPlayerPos=function() {
        return this.playerPos;
    }
   
   //获取地图
    Storehouse.prototype.getMap=function() {
        return this.map;
    }

     //获取路径
     Storehouse.prototype.getPath=function() {
        return this.path;
    }
     
     //获取步数
   Storehouse.prototype.getStep=function() {
        return this.step;
    }

    Storehouse.prototype.getBoxList=function() {//获取此状态中的所有箱子
        var boxlist=[];
        for(var i=0;i<this.map.length;i++){
            for(var j=0;j<this.map[i].length;j++){
               if (this.map[i][j] == 'B'||this.map[i][j]=="Y")//箱子在目标上
                  boxlist.push({x:i,y:j});//箱子坐标
            
            }
    }
      return boxlist.sort(order);
  }

     //位置是否越界http://www.108js.com
    Storehouse.prototype.isOk=function(pos){
        if(pos.x<0||pos.x>=map.length) return false;
        if(pos.y<0||pos.y>=map[0].length) return false;
        return true;
     }

     Storehouse.prototype.getEndList=function() {//获取此状态中的所有目标点
        var endlist=[];
        for(var i=0;i<this.map.length;i++){
            for(var j=0;j<this.map[i].length;j++){
               if (this.map[i][j] == "T"||this.map[i][j]=="Y"||this.map[i][j]=="Z")//箱子在目标上,人在目标点
                  endlist.push({x:i,y:j});//目标坐标
            
            }
    }
      return endlist.sort(order);
      //return endlist;
  }

  //剪枝函数,玩家的阻碍点,箱子的死点,用递归进行分析http://www.108js.com
   Storehouse.prototype.isBlock=function(array,row,col) {
        var b=false;
        if ((this.map[row][col] == '.') || (this.map[row][col]=="T")||this.map[row][col]=="S"){
            b=false;
        }else if ((this.map[row][col] == '#') || contains(array,{x:row,y:col})!=-1) {
            b = true;
             array.push({x:row,y:col});
        } else if (this.map[row][col]=="B") {
             array.push({x:row,y:col});
             b = (((this.isBlock(array, row + 1, col) || this.isBlock(array, row - 1, col))
                        && (this.isBlock(array, row, col + 1) || this.isBlock(array, row, col - 1))));
             if (!b) {
               var index=contains(array,{x:row,y:col});
              array.splice(index,1);    
             }
         }
                 return b;
    }


    Storehouse.prototype.toString=function(){
         var s="";
         for(var i=0,lenx=this.map.length;i<lenx;i++){
             s=s+this.map[i].join(" ")+"<br>";
         }
       return s;
     }

     Storehouse.prototype.isWin=function() {//是否赢了,比较此状态中的所有箱子和目标点
        var boxl=this.getBoxList();
        var endl=this.getEndList();
        for (var i = 0; i < boxl.length; i++) {
            if ((boxl[i].x !=endl[i].x)||(boxl[i].y!=endl[i].y))
               return false;
        }
       
        return true;
    }

    //比较两个状态是否相等
     Storehouse.prototype.equals=function(other){
      if((this.playerPos.x!=other.playerPos.x)||(this.playerPos.y!=other.playerPos.y))
           return false;
       for(var i=0;i<this.map.length;i++){
            for(var j=0;j<this.map[i].length;j++){
               if (this.map[i][j] !=other.map[i][j])
                 return false;
            
            }
       }
       return true;
     }

    //判断数组是否包含某一点
    function contains(arr,p){
       for(var i=0,len=arr.length;i<len;i++){
             if(arr[i].x==p.x&&arr[i].y==p.y)
               return i;
       }
       return -1;
    }
          
    //箱子排序函数
  function order(s1,s2){
    if (s1.x > s2.x){
      return 1;
    }
    else if (s1.x == s2.x) { //在同一行,比较列
      if (s1.y>s2.y) {
        return 1;
      }else if(s1.y==s2.y){
        return 0;
      }else
        return -1;
    }else
       return -1;
   }
    window.Storehouse=Storehouse;
})()


请继续阅下文:javaScript 广度优先搜索法"自动推箱子"(二)http://128kj.iteye.com/blog/2078631
  • 大小: 7.3 KB
0
1
分享到:
评论

相关推荐

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

    总的来说,通过JavaScript实现的广度优先搜索法在"自动推箱子"问题中起到了关键作用,它能够系统性地遍历所有可能的玩家和箱子的移动组合,找到最短的解决方案。理解并掌握这种算法对于提升编程能力,解决类似问题...

    自动推箱子 C++源代码

    在IT领域,自动推箱子(AutoBox)是一种基于经典逻辑游戏“推箱子”(Puzzle Box)的自动化解决算法的实现。本项目采用C++编程语言编写,旨在为玩家提供一个自动化解决推箱子关卡的工具,特别是对于那些难以解决或...

    推箱子游戏--(自动推箱子)

    "推箱子游戏--(自动推箱子)"是一个经典的逻辑益智游戏,它的目标是通过控制一个角色(通常称为“箱子推手”)在二维网格环境中移动,将所有的箱子推到指定的目标位置。在这个特殊的版本中,提到的是一个自动推箱子...

    自动推箱子,数据结构实习课程

    在这个“自动推箱子,数据结构实习课程”中,我们将深入探讨如何利用C/C++语言和数据结构来解决经典的推箱子游戏问题。推箱子游戏是一个策略性的单人益智游戏,玩家需要通过移动一个可推箱子的角色,将所有箱子推到...

    C# 推箱子 自动寻路

    当然 有时小人的状态不同但是箱子的位置相同时 也可能属于两种不同的状态 因此我规定了有效连通域的概念:在不移动箱子的情况下小人可以达到的位置都属于这个有效连通域 我们通过宽度优先搜索来处理一个原始的地图 ...

    易语言源码易语言广度优先搜索实现漫水法源码.rar

    易语言源码易语言广度优先搜索实现漫水法源码.rar 易语言源码易语言广度优先搜索实现漫水法源码.rar 易语言源码易语言广度优先搜索实现漫水法源码.rar 易语言源码易语言广度优先搜索实现漫水法源码.rar 易语言...

    用C++写的推箱子

    6. **算法**:虽然简单的推箱子可以手动解决,但复杂关卡可能需要搜索算法,如深度优先搜索(DFS)、广度优先搜索(BFS)或A*算法来自动求解。 7. **错误处理**:考虑到用户可能会输入非法命令,如尝试推动堵住路径...

    人工智能实验 宽度优先搜索

    人工智能实验中,宽度优先搜索(Breadth-First Search,BFS)是一种常用的图搜索算法。在人工智能实验中,宽度优先搜索通常用于解决问题,如八数码问题、迷宫问题等。在此实验中,我们将使用C++语言实现宽度优先搜索...

    java推箱子源码(逆向搜索法)

    2,再用广度搜索法反向标记每个步骤的逆向步骤层号。 3,用深度算法结合逆向步骤层号进行整体分析。 4,对目标点的到达顺序进行了分析。最终步骤近乎是最短步骤。 5,用线程技术实现了分析过程的暂停与继续。分析后...

    VC++推箱子及源代码

    4. **推箱子游戏逻辑**:游戏的核心算法涉及到了深度优先搜索、广度优先搜索、回溯法等搜索算法。开发者需要设计数据结构(如二维数组或链表)来表示地图状态,然后利用这些算法来判断游戏的可行性和最优解。 5. **...

    C语言实现推箱子源代码

    8. **算法优化**:如果游戏包含生成随机地图或解决复杂关卡的功能,可能需要用到搜索算法,如深度优先搜索(DFS)、广度优先搜索(BFS)或A*算法。 在提供的"推箱子"文件中,包含了实现这个游戏的源代码。分析和...

    广度优先搜索 matlab

    广度优先搜索(也称宽度优先搜索,缩写BFS,以下采用广度来描述)是连通图的一种遍历策略。本程序用Matlab语言实现广度优先算法

    推箱子源码(java)

    推箱子的源码可能使用二维数组来表示地图,并运用搜索算法(如深度优先搜索DFS或广度优先搜索BFS)来验证关卡的可解性。 7. **游戏状态管理**:游戏有开始、暂停、重置和结束等状态,源码会包含状态机的设计,用于...

    H5版本的推箱子小游戏源码

    推箱子是一款经典的逻辑解谜游戏,自诞生以来就深受玩家喜爱。随着HTML5技术的发展,H5版本的推箱子小游戏应运而生,使得这款游戏可以在网页上直接游玩,无需安装任何软件或插件。本文将深入探讨H5版本推箱子小游戏...

    推箱子游戏代码.zip

    8. **可能的AI组件**:如果这个代码包含AI实现,可能会有一个部分是专门用于解决推箱子问题的算法,例如深度优先搜索、A*搜索或者基于学习的方法。 由于我们只有一个文件名“推箱子游戏代码”,没有具体代码内容,...

    二叉树的深度优先搜索与广度优先搜索实现

    广度优先搜索是一种遍历二叉树的方式,是从根节点开始,沿着树的宽度遍历树的节点。如果所有节点均被访问,则算法中止。 在遍历二叉树时,可以借助队列数据结构,由于队列是先进先出的顺序,可以先将左子树入队,...

    邻接表表示的图的深度优先搜索和广度优先搜索程序

    文章还提供了一个示例程序,演示如何使用邻接表表示的图进行深度优先搜索和广度优先搜索。 本文提供了图的邻接表表示和深度优先搜索、广度优先搜索算法的实现细节,对读者理解图的数据结构和搜索算法非常有帮助。 ...

    C语言实现:八数码问题的深度优先搜索、广度优先搜索、过程表示(全)

    ②使用广度优先搜索来解决八数码问题 ③使用过程式表示和实现八数码问题 以及相关代码详细注释 过程式知识表示是将有关某一问题领域的知识, 连同如何使用这些知识的方法,均隐式的表达为 一个求解问题的过程,每个...

    人工智能的广度优先搜索

    本文将深入探讨“人工智能的广度优先搜索”这一重要知识点,以及它与全局和局部优先算法的关系。 **一、广度优先搜索(Breadth-First Search, BFS)** 广度优先搜索是一种在图或树结构中进行遍历的方法,其基本...

Global site tag (gtag.js) - Google Analytics