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

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++推箱子.zip

    8. **深度优先搜索(DFS)** 或 **广度优先搜索(BFS)**:这两种图遍历算法常用于解决推箱子问题,BFS通常能保证找到最优解,而DFS可能会找到一个可行解。 9. **动态规划**:在更复杂的优化问题中,动态规划可能被...

    推箱子算法, 一个不错的算法, 转载

    推箱子算法的设计通常基于状态空间搜索,如深度优先搜索(DFS)、广度优先搜索(BFS)或者A*搜索。这些算法的目标是找到从初始状态到目标状态的最小步数解决方案。以下是对这些算法的详细介绍: 1. **深度优先搜索...

    C# 推箱子 自动寻路

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

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

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

    用C++写的推箱子

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

    推箱子游戏的源代码(VC编译,可以自动演示走法)

    这种自动搜索算法可能是基于深度优先搜索(DFS)、广度优先搜索(BFS)或者A*搜索算法,这些算法在游戏路径规划中非常常见。自动演示功能对于理解和优化算法,以及分析关卡难度都很有帮助。 压缩包中的"开源盛世...

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

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

    推箱子游戏代码.zip

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

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

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

    自行设计推箱子小游戏

    6. **解谜算法**:虽然不是必须的,但为了提供自动解决谜题的功能,可以研究和实现解谜算法,如A*搜索或深度优先搜索。这可以帮助玩家找到最优解,或者用于生成难度适中的关卡。 7. **关卡编辑器**:让玩家能够自己...

    C#写的推箱子游戏(鼠标操作使用了广度搜索算法)

    总的来说,"C#写的推箱子游戏(鼠标操作使用了广度搜索算法)"是一个综合了图形界面交互、算法应用、游戏规则实现等多个方面的项目。开发者通过C#编程实现了游戏逻辑,并巧妙地利用BFS算法解决了游戏中的关键问题,...

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

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

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

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

    C++推箱子游戏

    在这个C++版本的推箱子游戏中,开发者利用了计算机科学中的基本算法——广度优先搜索(BFS)来生成和验证游戏地图的可行性。下面我们将深入探讨这一游戏的实现原理和技术细节。 首先,我们要理解BFS的基本概念。...

    3d版推箱子

    《3D版推箱子》是一款基于经典益智游戏“推箱子”的三维版本,它在保留原版游戏核心玩法的同时,引入了更为丰富的视觉效果和空间挑战。推箱子游戏的算法设计是实现这款游戏的关键,让我们深入探讨一下3D版推箱子背后...

    八数码问题宽度优先搜索(Java实现)

    【宽度优先搜索(BFS)】是一种用于寻找图或树中两个节点之间最短路径的搜索算法。在八数码问题中,BFS被用来找到最小步数的解决方案。BFS的特点是从起始状态开始,逐步扩展出所有可能的子状态,并优先检查距离起始...

    推箱子java代码(简单)

    9. **算法**:虽然这是一个简单的游戏,但某些高级版本可能涉及到更复杂的算法,如解决推箱子谜题的搜索算法(如深度优先搜索DFS、宽度优先搜索BFS、A*搜索等)。 10. **测试**:为了确保游戏的正确性,需要进行...

    广度优先搜索例题及代码

    本资源摘要信息旨在详细解释广度优先搜索的实现机理,并提供了一个实际的代码示例来帮助读者更好地理解广度优先搜索的应用。 在计算机科学中,广度优先搜索(Breadth-First Search,BFS)是一种常见的图搜索算法。...

Global site tag (gtag.js) - Google Analytics