128kj
- 浏览: 584791 次
- 来自: ...
-
文章分类
最新评论
-
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 10027效果图： 效果链接：http://www.108js.co ... -
HTML5 Canvas学习笔记(9)俄罗斯方块游戏之三（游戏面板）
2014-07-05 07:13 1374接上一遍《HTML5 Canvas学习笔记(8)俄罗斯方块游戏 ... -
HTML5 Canvas学习笔记(8)俄罗斯方块游戏之二（方块）
2014-07-04 13:08 1662接上一遍《HTML5 Canvas学习笔记(7)俄罗斯方块游戏 ... -
HTML5 Canvas学习笔记(7)俄罗斯方块游戏之一（色块）
2014-07-04 10:53 2336在网上看到一个俄罗斯方块游戏: http://www.108j ... -
HTML5 Canvas学习笔记(6)拼图游戏（数字版）
2014-06-28 17:38 2493今天网上发现了一段代码，只有界面，很不错，学习了并完成了逻辑。 ... -
HTML5 Canvas学习笔记(5)游戏得分动画
2014-06-26 17:11 1080效果图： 点击查看效果： http://www.108js ... -
HTML5 Canvas学习笔记(4)游戏界面的淡入淡出
2014-06-26 11:26 1936效果图： 点击看效果： http://www.108js. ... -
HTML5 Canvas学习笔记(3)加载游戏/动画音乐
2014-06-25 11:20 1663先要准备应付各种浏览器的声音文件，什么.mp3,.ogg ... -
HTML5 Canvas学习笔记(2)菜单高亮显示与像素字体
2014-06-23 23:13 1905看到哪，学到哪，记到哪。见谅，这些笔记就没有顺序和知识上的连贯 ... -
HTML5 Canvas学习笔记(1)处理鼠标事件
2014-06-21 17:48 2925一直在学习HTML5 Canvas相关内容，游戏，动画 ... -
javaScript 广度优先搜索法"自动推箱子"（一）
2014-06-12 09:45 1782用JS写了一个“广度优先搜索法”自动推箱子，理论上无论 ... -
HTML5 Canvas简单淡入淡出游戏启动界面
2014-06-05 12:22 2219欢迎访问博主的网站：http://www.108js.com ... -
HTML5 Canvas贝塞尔曲线动画
2014-05-22 08:35 1400点击这里可以查看动画效果： http://www.108js. ... -
javascript for语句最佳实践
2014-05-22 08:22 548当执行冗长的for语句时，要保持语句块的尽量简洁，例如： 糟 ... -
获取鼠标在HTML5 Canvas中的坐标
2014-05-21 16:43 2411<!DOCTYPE HTML> <html& ... -
HTML5 Canvas动画模板
2014-05-21 10:59 1024创建HTML5的画布动画，我们可以使用requestAn ... -
HTML5 Canvas 圆弧动画（绕四周运动）
2014-05-14 10:44 2736点击这里可以看到动画效果： http://www.108js. ... -
HTML5 Canvas “红心一棵”
2014-05-08 10:38 1242效果图： 笛卡尔公式: ... -
HTML5 Canvas画印章
2014-05-07 14:33 2216点击这里看效果： http:/ ... -
HTML5 Canvas旋转文本动画
2014-05-05 15:49 1419点这里可以看动画效果: http://www.108js.co ...
相关推荐
用JS写了一个“广度优先搜索法”自动推箱子，理论上无论多少箱子都可以求解，但事实上箱子多了以后，就 有需要的拿出发挥，修改，高手就可以跳过了
NULL 博文链接：https://128kj.iteye.com/blog/2078631
易语言源码易语言广度优先搜索实现漫水法源码.rar 易语言源码易语言广度优先搜索实现漫水法源码.rar 易语言源码易语言广度优先搜索实现漫水法源码.rar 易语言源码易语言广度优先搜索实现漫水法源码.rar 易语言...
深度优先与广度优先搜索法.doc，超级实用，希望对学数据结构与算法的人有所帮助！
MATLAB源码集锦-基于BFS广度优先搜索算法代码
广度优先搜索（也称宽度优先搜索，缩写BFS，以下采用广度来描述）是连通图的一种遍历策略。本程序用Matlab语言实现广度优先算法
广度优先搜索例题及代码详解 通过广度优先搜索的题目练习初步掌握广度优先搜索的机理
代码 基于BFS广度优先搜索算法代码代码 基于BFS广度优先搜索算法代码代码 基于BFS广度优先搜索算法代码代码 基于BFS广度优先搜索算法代码代码 基于BFS广度优先搜索算法代码代码 基于BFS广度优先搜索算法代码代码 ...
BFS DFS 深度优先搜索 广度优先搜索 图 输出所有路径 输出最短路径 随便输出一条可能的路径
Problem A【一本通基础广度优先搜索】细胞 Problem B【一本通基础广度优先搜索】 最少步数 Problem C【一本通基础广度优先搜索】The Castle Problem D【一本通基础广度优先搜索】Dungeon Master Problem E【一本通...
二叉树的深度优先搜索与广度优先搜索的非递归方法实现
参考中国大学MOOC,计算机算法与程序设计，5.2节内容，实现Python广度优先求最短路径。课程该章节没有课件，我手敲的代码调试好了，供大家一起学习！！！
广度优先搜索构建迷宫（BFS算法）动态构建过程的python 源代码，详情请移步本人博客<迷宫与寻路可视化（二）广度优先搜索构建迷宫（BFS算法）>
邻接表表示的图的深度优先搜索和广度优先搜索程序
本讲座就最短路径问题、分酒问题、八数码问题三个典型的范例，从问题分析、算法、数据结构等多方面进行了讨论，从而形成图的广度优先搜索解决问题的模式，通过本讲座的学习，能明白什么样的问题可以采用或转化为图的...
广度优先搜索和宽度优先搜索的动画演示，均为gif图，大家可以自行看看，理解思路或者放Ppt里很好用，怎么分数是5分，编辑不了了？ 请管理员修改为1分，谢谢
广度优先搜索动画示意图
资源名：搜索算法_广度优先搜索算法判断图的连通性_matlab 资源类型：matlab项目全套源码 源码说明： 全部项目源码都是经过测试校正后百分百成功运行的，如果您下载后不能运行可联系我进行指导或者更换。 适合人群：...
人工智能的全局和局部优先算法人工智能的全局和局部优先算法人工智能的全局和局部优先算法
迷宫求解，这里的迷宫用的是广度优先搜索，以及队列的存储方式，望同行积极批评