浏览 2008 次
|
锁定老帖子 主题：简单的迷宫算法学习
精华帖 (0) :: 良好帖 (0) :: 新手帖 (0) :: 隐藏帖 (0)
|
|
|---|---|
| 作者 | 正文 |
|
发表时间：2011-10-24
<!DOCTYPE html>
<html>
<head>
<style>
body,html{
background-color:black;
}
#box{
width:656px;
height:656px;
margin:100px auto;
}
.normal{
float:left;
background-color:#fff;
border:1px solid #ddd;
width:80px;
height:80px;
position:relative;
}
.start{
background-color:red;
}
.end{
background-color:yellow;
}
.stop{
background-color:black;
}
#control{
position:absolute;
right:0;
top:300px;
color:white;
font-size:12px;
cursor:pointer;
}
.g,.h,.f{
font-size:12px;
position:absolute;
}
.f{
top:2px;
left:2px;
}
.g{
bottom:2px;
left:2px;
}
.h{
right:2px;
bottom:2px;
}
</style>
</head>
<body>
<div id="control">
<span id="fgh">Find Path</span>
</div>
<div id="box">
</div>
<script>
var map = [
[0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0],
[0,0,0,0,1,0,0,0],
[0,0,0,0,1,0,0,0],
[0,5,0,0,1,0,8,0],
[0,0,0,0,1,0,0,0],
[0,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0]
];
init();
function $(){
return document.getElementById(arguments[0]);
}
function init(){
var html = "";
for(var i = 0 ; i < map.length ; i++){
for(var j = 0 ; j < map[i].length ; j++){
if(map[i][j] == 0){
html += '<div class="normal" id="b'+i+'_'+j+'"></div>';
}else if(map[i][j] == 5){
html += '<div class="normal start" id="b'+i+'_'+j+'"></div>';
}else if(map[i][j] == 8){
html += '<div class="normal end" id="b'+i+'_'+j+'"></div>';
}else if(map[i][j] == 1){
html += '<div class="normal stop" id="b'+i+'_'+j+'"></div>';
}
}
}
$("box").innerHTML = html;
}
var startx = 4,
starty = 1,
endx = 4,
endy = 6;
var openlist = ["b4_1"];
var trueopenlist = [];
var closelist = [];
$("fgh").onclick = function(){
var copen = openlist[0],
x = copen.replace("b","").split("_")[0],
y = copen.replace("b","").split("_")[1];
closelist.push(copen);
openlist.pop(copen);
pushIntoOpenlist(x,y);
drawFGH();
}
function pushIntoOpenlist(x,y){
x = parseInt(x,10);
y = parseInt(y,10);
openlist.push("b"+(x-1)+"_"+y);
openlist.push("b"+(x+1)+"_"+y);
openlist.push("b"+x+"_"+(y+1));
openlist.push("b"+x+"_"+(y-1));
}
function drawFGH(){
var lower = 100000,
lowerxy = null;
for(var i = 0 ; i < openlist.length ; i++){
var copen = openlist[i],
x = copen.replace("b","").split("_")[0],
y = copen.replace("b","").split("_")[1];
var g = 10 * closelist.length,//parseInt(Math.sqrt(Math.pow(Math.abs(x - startx),2) + Math.pow(Math.abs(y - starty),2)) * 10,10),
h = 10*(Math.abs(x - endx) + Math.abs(y - endy)),
f = g + h;
if(x == endx && y == endy){
alert("Done");
console.log(closelist);
showResult();
}
if($(copen).className == "normal stop"){
continue;
}
var lo = true;
for(var m = 0 ; m < closelist.length ; m++){
if(copen == closelist[m]){
lo = false;
break;
}
}
if(!lo){
continue;
}
if(f < lower){
lower = f;
lowerxy = copen;
}
console.log(copen);
trueopenlist.push(copen);
$(copen).innerHTML = "<div class='f'>"+f+"</div><div class='g'>"+g+"</div><div class='h'>"+h+"</div>";
}
updateList(lowerxy);
}
function updateList(data){
openlist = [];
openlist.push(data);
//closelist.push(data);
trueopenlist.pop(data);
}
function showResult(){
var i = 0 ;
var t = setInterval(function(){
if(closelist.length > 0){
var copen = closelist[0];
$(copen).style.backgroundColor = "pink";
$(copen).innerHTML = "<p style='font-size:20px;font-weight:bold;text-align:center;line-height:42px;'>"+(i+1)+"</p>";
closelist.shift();
i++;
}else{
clearInterval(t);
}
},500);
}
</script>
</body>
</html>
声明：ITeye文章版权属于作者，受法律保护。没有作者书面许可不得转载。
推荐链接
|
| 返回顶楼 | |
|
发表时间：2011-10-25
能不能把算法的要领写出来？
|
| 返回顶楼 | |
|
发表时间：2011-10-26
其实比较简单，比如走到某一步的时候，计算里面的F值
也就是Drawfgh函数里面的f变量 等于g+h的那个 g为到达当前位置已经走的格子数目 h为当前格子离终点的距离 取周围4个方向的点分别计算f值，然后取最小的f值来走下一步 其实就这个原理 |
| 返回顶楼 | |
