麻辣堂|资源主站|开发论坛|在线手册
首页 │ Apache │ Linux│ Java│ MySQL│ 注册│帮助 
PHP项目开发组是PHP开发资源网于2007组年建成立的项目开发团队，目前核心开发成员有27人, 项目协作成员8名.下设7个开发组，主要承接大/中型网站项目开发任务。 由于开发任务较多，人员比较紧张，现面向社会招聘全职或者兼职开发人员，不管你是在校大学生，还是全职开发人员，以及SOHO都可以联系本站，我们可以长期合作，并为您带来丰厚的报酬。
  您现在的位置：PHP开发资源网 > 麻辣堂 > 详细资料
待解决
A*算法[js]游戏设计基础之"最短路径"探讨
悬赏分：20 - 2007年08月22日

根据Ａ＊算法

CODE:
<html>
<head>
<title> A* 寻径算法 </title>
<style type="text/css">
#screen{width:400px;height:400px;border:1px solid #CCFF99;padding:0px;background:#eeeeee}
#screen td{background:#fff;font-size:8pt;}
</style>
<script language="javascript">
var cells = rows = 30;
var zaw = [[8,10],[4,10],[5,10],[6,10],[7,10],[8,13],[11,10],[8,16],[8,18],[8,14],[8,17],[8,21],[4,22],[4,13],[4,11],[8,12],[8,11],[8,9],[7,13],[8,13],[6,13],[5,13],[4,13],[4,12]]
var status = '';
var prev_start;
var prev_end;
var start_pos;
var openlist = [];
var closedlist = [];
var parents = [];
var gw = 14;
var g = 10;
var h = 10;
var f = [];
var timer;
var finded = false;
var p_x;
var p_y;
var prev_v_temp;
var number=0;
function cret_screen()
{
var elem_body = document.getElementsByTagName("body").item(0);
var elem_tble = document.createElement("table");
elem_tble.id = "screen";
var elem_tbdy = document.createElement("tbody");
for(var i=0;i<=rows;i++)
{
var elem_tr = document.createElement("tr");
for(var j=0;j<=cells;j++)
{
var elem_td = document.createElement("td");
elem_tr.appendChild(elem_td);
elem_td.value="1#"+i+"#"+j;
elem_td.onclick = setPos;
}
elem_tbdy.appendChild(elem_tr);
}
elem_tble.appendChild(elem_tbdy);
elem_body.appendChild(elem_tble);
for(var k=0;k<zaw.length;k++)
{
$("screen").rows[zaw[k][0]].cells[zaw[k][1]].style.backgroundColor="#6633CC";
$("screen").rows[zaw[k][0]].cells[zaw[k][1]].value="3#"+i+"#"+j;
}

}

function setStart()
{
status = "start";
}
function setEnd()
{
status = "end";
}
function getRound()
{
var pos_obj = openlist[0].split("#");
//父结点加入关闭列表中
closedlist[closedlist.length] = openlist[0];
pos_obj[1] = parseFloat(pos_obj[1]);
pos_obj[2] = parseFloat(pos_obj[2]);
pos_obj[0] = parseFloat(pos_obj[0]);
p_x = pos_obj[1];
p_y = pos_obj[2];
$("screen").rows[p_x].cells[p_y].value = 3+"#"+p_x+"#"+p_y;
$("screen").rows[p_x].cells[p_y].style.backgroundColor="#000000";
openlist = [];
if(++number%42==0)
{
$("msg").innerHTML="当前位置=>row:"+pos_obj[1]+"cell:"+pos_obj[2]+"<br />";
}
else
{
$("msg").innerHTML+="当前位置=>row:"+pos_obj[1]+"cell:"+pos_obj[2]+"<br />";
}
//获得相邻结点 接下来计算f = h + g 判断下级的路线
if(pos_obj[1]-1>=0&&pos_obj[2]-1>=0&&pos_obj[1]-1<=rows&&pos_obj[2]-1<=cells)
{
if(parseFloat($("screen").rows[pos_obj[1]-1].cells[pos_obj[2]-1].value.split("#")[0])!= 3)
{
openlist[openlist.length] = $("screen").rows[pos_obj[1]-1].cells[pos_obj[2]-1].value;
$("screen").rows[pos_obj[1]-1].cells[pos_obj[2]-1].style.backgroundColor = "#ff00cc";
f[openlist.length-1] = parseFloat(Math.abs(pos_obj[2]-1-prev_end["cell"])*parseFloat(h)+Math.abs(pos_obj[1]-1-prev_end["row"])*parseFloat(g)+parseFloat(gw));
}

}
if(pos_obj[1]-1>=0&&pos_obj[1]-1<=rows&&pos_obj[2]>=0&&pos_obj[2]<=cells)
{

if(parseFloat($("screen").rows[pos_obj[1]-1].cells[pos_obj[2]].value.split("#")[0])!= 3)
{
openlist[openlist.length] = $("screen").rows[pos_obj[1]-1].cells[pos_obj[2]].value;
$("screen").rows[pos_obj[1]-1].cells[pos_obj[2]].style.backgroundColor = "#ff0000";
f[openlist.length-1] = parseFloat(Math.abs(pos_obj[2]-prev_end["cell"])*parseFloat(h)+Math.abs(pos_obj[1]-1-prev_end["row"])*parseFloat(g)+g);
}
else
{
closedlist[closedlist.length] = $("screen").rows[pos_obj[1]-1].cells[pos_obj[2]].value;
}

}
if(pos_obj[1]-1>=0&&pos_obj[1]-1<=rows&&pos_obj[2]+1>=0&&pos_obj[2]+1<=cells)
{

if(parseFloat($("screen").rows[pos_obj[1]-1].cells[pos_obj[2]+1].value.split("#")[0])!= 3)
{
openlist[openlist.length] = $("screen").rows[pos_obj[1]-1].cells[pos_obj[2]+1].value;
$("screen").rows[pos_obj[1]-1].cells[pos_obj[2]+1].style.backgroundColor = "#ff0000";
f[openlist.length-1] = parseFloat(Math.abs(pos_obj[2]+1-prev_end["cell"])*parseFloat(h)+Math.abs(pos_obj[1]-1-prev_end["row"])*parseFloat(g)+parseFloat(gw));
}
else
{
closedlist[closedlist.length] = $("screen").rows[pos_obj[1]-1].cells[pos_obj[2]+1].value;
}
}
if(pos_obj[1]>=0&&pos_obj[1]<=rows&&pos_obj[2]-1>=0&&pos_obj[2]-1<=cells)
{

if(parseFloat($("screen").rows[pos_obj[1]].cells[pos_obj[2]-1].value.split("#")[0])!= 3)
{
openlist[openlist.length] = $("screen").rows[pos_obj[1]].cells[pos_obj[2]-1].value;
$("screen").rows[pos_obj[1]].cells[pos_obj[2]-1].style.backgroundColor = "#ff0000";
f[openlist.length-1] = parseFloat(Math.abs(pos_obj[2]-1-prev_end["cell"])*parseFloat(h)+Math.abs(pos_obj[1]-prev_end["row"])*parseFloat(g)+parseFloat(g));
}
else
{
closedlist[closedlist.length] = $("screen").rows[pos_obj[1]].cells[pos_obj[2]-1].value;
}
}
if(pos_obj[1]>=0&&pos_obj[1]<=rows&&pos_obj[2]+1>=0&&pos_obj[2]+1<=cells)
{

if(parseFloat($("screen").rows[pos_obj[1]].cells[pos_obj[2]+1].value.split("#")[0])!= 3)
{
openlist[openlist.length] = $("screen").rows[pos_obj[1]].cells[pos_obj[2]+1].value;
$("screen").rows[pos_obj[1]].cells[pos_obj[2]+1].style.backgroundColor = "#ff0000";
f[openlist.length-1] = parseFloat(Math.abs(pos_obj[2]+1-prev_end["cell"])*parseFloat(h)+Math.abs(pos_obj[1]-prev_end["row"])*parseFloat(g)+parseFloat(g));
}
else
{
closedlist[closedlist.length] = $("screen").rows[pos_obj[1]].cells[pos_obj[2]+1].value;
}
}
if(pos_obj[1]+1>=0&&pos_obj[1]+1<=rows&&pos_obj[2]-1>=0&&pos_obj[2]-1<=cells)
{
if(parseFloat($("screen").rows[pos_obj[1]+1].cells[pos_obj[2]-1].value.split("#")[0])!= 3)
{
openlist[openlist.length] =$("screen").rows[pos_obj[1]+1].cells[pos_obj[2]-1].value;
$("screen").rows[pos_obj[1]+1].cells[pos_obj[2]-1].style.backgroundColor = "#ff0000";
f[openlist.length-1] = parseFloat(Math.abs(pos_obj[2]-1-prev_end["cell"])*parseFloat(h)+Math.abs(pos_obj[1]+1-prev_end["row"])*parseFloat(g)+parseFloat(gw));
}
else
{
closedlist[closedlist.length] = $("screen").rows[pos_obj[1]+1].cells[pos_obj[2]-1].value;
}

}
if(pos_obj[1]+1>=0&&pos_obj[1]+1<=rows&&pos_obj[2]>=0&&pos_obj[2]<=cells)
{

if(parseFloat($("screen").rows[pos_obj[1]+1].cells[pos_obj[2]].value.split("#")[0])!= 3)
{
openlist[openlist.length] = $("screen").rows[pos_obj[1]+1].cells[pos_obj[2]].value;
$("screen").rows[pos_obj[1]+1].cells[pos_obj[2]].style.backgroundColor = "#ff0000";
f[openlist.length-1] = parseFloat(Math.abs(pos_obj[2]-prev_end["cell"])*parseFloat(h)+Math.abs(pos_obj[1]+1-prev_end["row"])*parseFloat(g)+parseFloat(g));
}
else
{
closedlist[closedlist.length] = $("screen").rows[pos_obj[1]+1].cells[pos_obj[2]].value;
}


}
if(pos_obj[1]+1>=0&&pos_obj[1]+1<=rows&&pos_obj[2]+1>=0&&pos_obj[2]+1<=cells)
{
if(parseFloat($("screen").rows[pos_obj[1]+1].cells[pos_obj[2]+1].value.split("#")[0])!= 3)
{
openlist[openlist.length] = $("screen").rows[pos_obj[1]+1].cells[pos_obj[2]+1].value;
$("screen").rows[pos_obj[1]+1].cells[pos_obj[2]+1].style.backgroundColor = "#ff0000";
f[openlist.length-1] = parseFloat(Math.abs(pos_obj[2]+1-prev_end["cell"])*parseFloat(h)+Math.abs(pos_obj[1]+1-prev_end["row"])*parseFloat(g)+parseFloat(gw));
}
else
{
closedlist[closedlist.length] = $("screen").rows[pos_obj[1]+1].cells[pos_obj[2]+1].value;
}

}

}
function getF()
{
var have =0;
var o = 0;
var prev_f=0;
var prev_v=0;
getRound();
for(var i=0;i<openlist.length;i++)
{

var x = openlist[i].split("#");

if(x[0] == 4)
{
finded = true;
}

//如果是障碍物或者是已经走过的结点，那么放弃搜索;
for(var j=0;j<closedlist.length;j++)
{
if(openlist[i].toString == closedlist[j].toString)
{
continue;
}
}

//检测最小的路径结点
if(parseFloat(prev_f)==0)
{
prev_f = f[i];
prev_v = openlist[i];

}
else
{
//找寻最短路径
if(prev_f>f[i])
{
prev_f = f[i];
prev_v = openlist[i];
//parents[parents.length] = openlist[i];
have = 1;
}
}

}
//如果卡在同一位,则退回上一个结点,并且卡住的结点位置作废.
if(prev_v == prev_v_temp)
{
closedlist[closedlist.length] = prev_v;
openlist[0] = parents[parents.length-1];
prev_v_temp = openlist[0];
}
else if(prev_v!=0)
{
parents[parents.length] =prev_v;//存储其路径
var xx = prev_v.split("#");
$("screen").rows[xx[1]].cells[xx[2]].value = 5+"#"+xx[1]+"#"+xx[2];
$("screen").rows[xx[1]].cells[xx[2]].style.backgroundColor="#669933";
//获得唯一最短路径点
openlist[0] = prev_v;
prev_v_temp = prev_v;
}
else
{
finded = "fail";
}
}

function find()
{
getF();
if(finded == false)
{
timer = setTimeout("find()",10);
}
else if(finded == "fail")
{
alert("没有可走的通道！");
clearTimeout(timer);
}
else
{
alert("找到了！");
clearTimeout(timer);
}
}
function setPos()
{
if(status == "start")
{
if(typeof prev_start == "object")
{
prev_start.value="1";
prev_start.style.backgroundColor="#ffffff";
}
prev_start = this;
var prev_value = this.value;
var temp_arry = prev_value.split("#");
this.value=2+"#"+temp_arry[1]+"#"+temp_arry[2];
this.style.backgroundColor="#99CC66";
openlist[0] = this.value;//父节点
}
else if(status == "end")
{
if(typeof prev_end == "object")
{
prev_end.value="1";
prev_end.style.backgroundColor="#ffffff";
}
prev_end = this;
var prev_value = this.value;
var temp_arry = prev_value.split("#");
prev_end["row"] = parseFloat(temp_arry[1]);
prev_end["cell"] = parseFloat(temp_arry[2]);
this.value=4+"#"+temp_arry[1]+"#"+temp_arry[2];
this.style.backgroundColor = "blue";
}
}

function $(obj)
{
return document.getElementById(obj);
}
</script>
</head>

<body onload = "cret_screen();">
<div id="msg" style="position:absolute;top:20px;left:560px;background:#eeeeee;border:1px solid gray;width:200px;height:100px;"></div>
<input type="button" value="设置起点" onclick="javascript:setStart();"/>
<input type="button" value="设置终点" onclick="javascript:setEnd();"/>
<input type="button" value="寻找路径" onclick="javascript:find();"/>
</body>
</html>

[ 本帖最后由 瞎逛悠 于 2007-4-18 03:11 PM 编辑 ]

提问者：瞎逛悠   08-22 15:03
答复
路过。。。顺便帮顶:)
回答者：玉米づ冰冻可乐 - 瓦岗村民 8-22 09:10
我也来回答：
不管你有没有帮助我们，瓦岗寨8万村民将感谢你。。。。。

为防止灌水，您需要计算一道数学题： 答案：
27 + 50 = ? 请将计算结果填在上面

 
[]
©2007 PhpRes.COM