128kj
- 浏览: 601640 次
- 来自: ...
-
文章分类
最新评论
-
lgh1992314：
相同的元素呢
一种离散化方法 -
HelloSummerR：
圆心的位置是随机的，于是圆的部分会落到canvas外，那样就显 ...
HTML5 Canvas学习笔记(1)处理鼠标事件 -
hlstudio：
好久没见到sokuban了，这有个java版的，带源码，可以参 ...
求推箱子的最小步数（java) -
肖泽文：
太好了，谢谢你。。有中文注释！
HTML5 推箱子游戏过关演示动画 -
swm8023：
删除操作，将最后一个叶子节点插入后也有可能上浮吧
彻底弄懂最大堆的四种操作(图解+程序)（JAVA）
接上文： 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
代码第二部分。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 旋转的“金字塔”
2015-12-24 13:25 10077效果图： 效果链接：http://www.108js.co ... -
HTML5 Canvas学习笔记(9)俄罗斯方块游戏之三（游戏面板）
2014-07-05 07:13 1408接上一遍《HTML5 Canvas学习笔记(8)俄罗斯方块游戏 ... -
HTML5 Canvas学习笔记(8)俄罗斯方块游戏之二（方块）
2014-07-04 13:08 1698接上一遍《HTML5 Canvas学习笔记(7)俄罗斯方块游戏 ... -
HTML5 Canvas学习笔记(7)俄罗斯方块游戏之一（色块）
2014-07-04 10:53 2403在网上看到一个俄罗斯方块游戏: http://www.108j ... -
HTML5 Canvas学习笔记(6)拼图游戏（数字版）
2014-06-28 17:38 2569今天网上发现了一段代码，只有界面，很不错，学习了并完成了逻辑。 ... -
HTML5 Canvas学习笔记(5)游戏得分动画
2014-06-26 17:11 1124效果图： 点击查看效果： http://www.108js ... -
HTML5 Canvas学习笔记(4)游戏界面的淡入淡出
2014-06-26 11:26 1978效果图： 点击看效果： http://www.108js. ... -
HTML5 Canvas学习笔记(3)加载游戏/动画音乐
2014-06-25 11:20 1703先要准备应付各种浏览器的声音文件，什么.mp3,.ogg ... -
HTML5 Canvas学习笔记(2)菜单高亮显示与像素字体
2014-06-23 23:13 1982看到哪，学到哪，记到哪。见谅，这些笔记就没有顺序和知识上的连贯 ... -
HTML5 Canvas学习笔记(1)处理鼠标事件
2014-06-21 17:48 2988一直在学习HTML5 Canvas相关内容，游戏，动画 ... -
javaScript 广度优先搜索法"自动推箱子"（一）
2014-06-12 09:45 1863用JS写了一个“广度优先搜索法”自动推箱子，理论上无论 ... -
HTML5 Canvas简单淡入淡出游戏启动界面
2014-06-05 12:22 2259欢迎访问博主的网站：http://www.108js.com ... -
HTML5 Canvas贝塞尔曲线动画
2014-05-22 08:35 1464点击这里可以查看动画效果： http://www.108js. ... -
javascript for语句最佳实践
2014-05-22 08:22 599当执行冗长的for语句时，要保持语句块的尽量简洁，例如： 糟 ... -
获取鼠标在HTML5 Canvas中的坐标
2014-05-21 16:43 2445<!DOCTYPE HTML> <html& ... -
HTML5 Canvas动画模板
2014-05-21 10:59 1073创建HTML5的画布动画，我们可以使用requestAn ... -
HTML5 Canvas 圆弧动画（绕四周运动）
2014-05-14 10:44 2784点击这里可以看到动画效果： http://www.108js. ... -
HTML5 Canvas “红心一棵”
2014-05-08 10:38 1284效果图： 笛卡尔公式: ... -
HTML5 Canvas画印章
2014-05-07 14:33 2289点击这里看效果： http:/ ... -
HTML5 Canvas旋转文本动画
2014-05-05 15:49 1466点这里可以看动画效果: http://www.108js.co ...
相关推荐
JavaScript 广度优先搜索法（BFS）是一种在图或树结构中寻找最短路径的算法，常用于解决像“推箱子”这类基于网格的问题。在这个案例中，开发者使用JavaScript实现了一个自动推箱子的程序，它能理论上解决任意数量的...
总的来说，通过JavaScript实现的广度优先搜索法在"自动推箱子"问题中起到了关键作用，它能够系统性地遍历所有可能的玩家和箱子的移动组合，找到最短的解决方案。理解并掌握这种算法对于提升编程能力，解决类似问题...
易语言源码易语言广度优先搜索实现漫水法源码.rar 易语言源码易语言广度优先搜索实现漫水法源码.rar 易语言源码易语言广度优先搜索实现漫水法源码.rar 易语言源码易语言广度优先搜索实现漫水法源码.rar 易语言...
4. **状态空间搜索**：自动推箱子的核心是遍历所有可能的状态空间，寻找可以成功推箱子到达目标位置的路径。这可能涉及到深度优先搜索（DFS）、广度优先搜索（BFS）或者启发式搜索。 5. **自动寻路算法**：如A*（A-...
本文将深入探讨“人工智能的广度优先搜索”这一重要知识点，以及它与全局和局部优先算法的关系。 **一、广度优先搜索（Breadth-First Search, BFS）** 广度优先搜索是一种在图或树结构中进行遍历的方法，其基本...
邻接表表示的图的深度优先搜索和广度优先搜索程序 这篇文章介绍了使用邻接表表示的图的深度优先搜索和广度优先搜索程序，旨在帮助读者理解图的深度优先搜索和广度优先搜索算法的实现。 首先，文章定义了图的邻接表...
二叉树的深度优先搜索与广度优先搜索实现 二叉树搜索是计算机科学中的一种常见的搜索算法，用于遍历二叉树中的所有节点。二叉树搜索可以分为深度优先搜索和广度优先搜索两种方式。本文将详细介绍二叉树的深度优先...
广度优先搜索例题及代码详解 本资源摘要信息旨在详细解释广度优先搜索的实现机理，并提供了一个实际的代码示例来帮助读者更好地理解广度优先搜索的应用。 在计算机科学中，广度优先搜索（Breadth-First Search，...
"推箱子游戏--（自动推箱子）"是一个经典的逻辑益智游戏，它的目标是通过控制一个角色（通常称为“箱子推手”）在二维网格环境中移动，将所有的箱子推到指定的目标位置。在这个特殊的版本中，提到的是一个自动推箱子...
rust 中实现广度优先搜索 教程.txtrust 中实现广度优先搜索 教程.txtrust 中实现广度优先搜索 教程.txtrust 中实现广度优先搜索 教程.txtrust 中实现广度优先搜索 教程.txtrust 中实现广度优先搜索 教程.txtrust 中...
代码 基于BFS广度优先搜索算法代码代码 基于BFS广度优先搜索算法代码代码 基于BFS广度优先搜索算法代码代码 基于BFS广度优先搜索算法代码代码 基于BFS广度优先搜索算法代码代码 基于BFS广度优先搜索算法代码代码 ...
Problem A【一本通基础广度优先搜索】细胞 Problem B【一本通基础广度优先搜索】 最少步数 Problem C【一本通基础广度优先搜索】The Castle Problem D【一本通基础广度优先搜索】Dungeon Master Problem E【一本通...
其中，BFS（广度优先搜索）是一种常用的策略。本资源“MATLAB源码集锦-基于BFS广度优先搜索算法代码”是专门为MATLAB用户提供的，旨在帮助他们理解和实现BFS算法。 BFS算法的基本思想是从起点开始，首先访问其所有...
图的深度优先搜索（DFS, Depth-First Search）和广度优先搜索（BFS, Breadth-First Search）是图论中的两种基本遍历算法，它们在计算机科学中有着广泛的应用，例如在解决网络爬虫、迷宫求解、社交网络分析等问题时。...
本文以通俗易懂的语言，为初学者详细讲解了如何使用广度优先搜索和启发式搜索解决重排九宫问题。通过案例和代码示例，读者可以快速上手，并在实际项目中应用这些算法。 ### 适用人群 本文适用于所有对算法和编程感...
②使用广度优先搜索来解决八数码问题 ③使用过程式表示和实现八数码问题 以及相关代码详细注释 过程式知识表示是将有关某一问题领域的知识， 连同如何使用这些知识的方法，均隐式的表达为 一个求解问题的过程，每个...
在这个“自动推箱子，数据结构实习课程”中，我们将深入探讨如何利用C/C++语言和数据结构来解决经典的推箱子游戏问题。推箱子游戏是一个策略性的单人益智游戏，玩家需要通过移动一个可推箱子的角色，将所有箱子推到...