我要评论本文实例讲述了js/html5游戏常用算法之路径搜索算法 a*寻路算法。分享给大家供大家参考，具体如下：
原理可参考：
完整实例代码如下：
<!doctype html>
<html lang="en">
<head>
<meta name="viewport" content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=0">
<meta charset="utf-8">
<title>a*寻路算法</title>
<style>
#stage {
border: 1px solid lightgray;
}
</style>
</head>
<body>
<canvas id="stage"></canvas>
</body>
<script>
window.onload = function () {
var stage = document.queryselector('#stage'),
ctx = stage.getcontext('2d');
stage.width = 600;
stage.height = 600;
var row = 7, column = 7, r = 40;
//取区域随机数x>=min && x<max
function randint(min, max) {
max = max || 0;
min = min || 0;
var step = math.abs(max - min);
var st = (arguments.length < 2) ? 0 : min;//参数只有一个的时候，st = 0;
var result;
result = st + (math.ceil(math.random() * step)) - 1;
return result;
}
//普里姆算法生成连通图的二维数组 row 行 column 列
function primmaze(r, c) {
//初始化数组
function init(r, c) {
var a = new array(2 * r + 1);
//全部置1
for (let i = 0, len = a.length; i < len; i++) {
var cols = 2 * c + 1;
a[i] = new array(cols);
for (let j = 0, len1 = a[i].length; j < len1; j++) {
a[i][j] = 1;
}
}
//中间格子为0
for (let i = 0; i < r; i++)
for (let j = 0; j < c; j++) {
a[2 * i + 1][2 * j + 1] = 0;
}
return a;
}
//处理数组，产生最终的数组
function process(arr) {
//acc存放已访问队列，noacc存放没有访问队列
var acc = [], noacc = [];
var r = arr.length >> 1, c = arr[0].length >> 1;
var count = r * c;
for (var i = 0; i < count; i++) {
noacc[i] = 0;
}
//定义空单元上下左右偏移
var offs = [-c, c, -1, 1], offr = [-1, 1, 0, 0], offc = [0, 0, -1, 1];
//随机从noacc取出一个位置
var pos = randint(count);
noacc[pos] = 1;
acc.push(pos);
while (acc.length < count) {
var ls = -1, offpos = -1;
offpos = -1;
//找出pos位置在二维数组中的坐标
var pr = pos / c | 0, pc = pos % c, co = 0, o = 0;
//随机取上下左右四个单元
while (++co < 5) {
o = randint(0, 5);
ls = offs[o] + pos;
var tpr = pr + offr[o];
var tpc = pc + offc[o];
if (tpr >= 0 && tpc >= 0 && tpr <= r - 1 && tpc <= c - 1 && noacc[ls] == 0) {
offpos = o;
break;
}
}
if (offpos < 0) {
pos = acc[randint(acc.length)];
}
else {
pr = 2 * pr + 1;
pc = 2 * pc + 1;
//相邻空单元中间的位置置0
arr[pr + offr[offpos]][pc + offc[offpos]] = 0;
pos = ls;
noacc[pos] = 1;
acc.push(pos);
}
}
}
var a = init(r, c);
process(a);
return a;
//返回一个二维数组，行的数据为2r+1个,列的数据为2c+1个
}
//栅格线条
function drawgrid(context, color, stepx, stepy) {
context.strokestyle = color;
context.linewidth = 0.5;
for (var i = stepx + 0.5; i < context.canvas.width; i += stepx) {
context.beginpath();
context.moveto(i, 0);
context.lineto(i, context.canvas.height);
context.stroke();
}
for (var i = stepy + 0.5; i < context.canvas.height; i += stepy) {
context.beginpath();
context.moveto(0, i);
context.lineto(context.canvas.width, i);
context.stroke();
}
}
//方块创造方法
function createrect(x, y, r, c) {
ctx.beginpath();
ctx.fillstyle = c;
ctx.rect(x, y, r, r);
ctx.fill();
}
//定义点对象【a*点对象】
function point(x, y) {
this.x = x;
this.y = y;
this.parent = null;
this.f = 0;
this.g = 0;
this.h = 0;
//当前点状态，0：表示在openlist 1:表示closelist,-1表示还没处理
this.state = -1;
//flag表明该点是否可通过
this.flag = 0;
}
//把普通二维数组(全部由1，0表示)的转换成a*所需要的点数组
function convertarrtoas(arr) {
var r = arr.length, c = arr[0].length;
var a = new array(r);
for (var i = 0; i < r; i++) {
a[i] = new array(c);
for (var j = 0; j < c; j++) {
var pos = new point(i, j);
pos.flag = arr[i][j];
a[i][j] = pos;
}
}
return a;
}
//a*算法,patharr表示最后返回的路径
function findpatha(patharr, start, end, row, col) {
//添加数据到排序数组中
function addarrsort(descsortedarr, element, compare) {
var left = 0;
var right = descsortedarr.length - 1;
var mid = (left + right) >> 1;
while (left <= right) {
var mid = (left + right) >> 1;
if (compare(descsortedarr[mid], element) == 1) {
left = mid + 1;
}
else if (compare(descsortedarr[mid], element) == -1) {
right = mid - 1;
}
else {
break;
}
}
for (var i = descsortedarr.length - 1; i >= left; i--) {
descsortedarr[i + 1] = descsortedarr[i];
}
descsortedarr[left] = element;
}
//判断两个点是否相同
function pequal(p1, p2) {
return p1.x == p2.x && p1.y == p2.y;
}
//获取两个点距离，采用曼哈顿方法
function posdist(pos, pos1) {
return (math.abs(pos1.x - pos.x) + math.abs(pos1.y - pos.y));
}
function between(val, min, max) {
return (val >= min && val <= max)
}
//比较两个点f值大小
function comppointf(pt1, pt2) {
return pt1.f - pt2.f;
}
//处理当前节点
function processcurrpoint(arr, openlist, row, col, currpoint, destpoint) {
//get up,down,left,right direct
var ltx = currpoint.x - 1;
var lty = currpoint.y - 1;
for (var i = 0; i < 3; i++){
for (var j = 0; j < 3; j++) {
var cx = ltx + i;
var cy = lty + j;
if ((cx === currpoint.x || cy === currpoint.y) && between(ltx, 0, row - 1) && between(lty, 0, col - 1)) {
var tp = arr[cx][cy];
if (tp.flag === 0 && tp.state !== 1) {
if (pequal(tp, destpoint)) {
tp.parent = currpoint;
return true;
}
if (tp.state === -1) {
tp.parent = currpoint;
tp.g = 1 + currpoint.g;
tp.h = posdist(tp, destpoint);
tp.f = tp.h + tp.f;
tp.state = 0;
addarrsort(openlist, tp, comppointf);
}
else {
var g = 1 + currpoint.g;
if (g < tp.g) {
tp.parent = currpoint;
tp.g = g;
tp.f = tp.g + tp.h;
openlist.quicksort(comppointf);
}
}
}
}
}
}
return false;
}
//定义openlist
var openlist = [];
//定义closelist
var closelist = [];
start = patharr[start[0]][start[1]];
end = patharr[end[0]][end[1]];
//添加开始节点到openlist;
addarrsort(openlist, start, comppointf);
var finded = false;
while ((openlist.length > 0)) {
var currpoint = openlist.pop();
currpoint.state = 1;
closelist.push(currpoint);
finded = processcurrpoint(patharr, openlist, row, col, currpoint, end);
if (finded) {
break;
}
}
if (finded) {
var farr = [];
var tp = end.parent;
farr.push(end);
while (tp != null) {
farr.push(tp);
tp = tp.parent;
}
return farr;
}
else {
return null;
}
}
//定位屏幕坐标到数组位置
function mapscpos(i, j) {
return [i / r | 0, j / r | 0];
}
//检测数组中的位置是否存在方块
function maphasrect(map, i, j) {
return (map[i][j]);
}
var maparr = primmaze(row, column);
var startrect = {
x: function () {
for (var i = 0, len = maparr.length; i < len; i++) {
for (var j = 0, len1 = maparr[i].length; j < len1; j++) {
if (!maparr[i][j]) {
return j * r;
break;
}
}
}
}(),
y: function () {
for (var i = 0, len = maparr.length; i < len; i++) {
for (var j = 0, len1 = maparr[i].length; j < len1; j++) {
if (!maparr[i][j]) {
return i * r;
break;
}
}
}
}(),
pos: function () {
return [this.x, this.y];
}
},
endrect = {
hascreate:false,
x:null,
y:null,
pos: function () {
return [this.x, this.y];
}
},
startpoint = mapscpos(startrect.pos()[1], startrect.pos()[0]),
endpoint,
path = null,
next = null;
//计算路经
function update() {
ctx.clearrect(0, 0, 600, 600);
drawgrid(ctx, 'lightgray', r, r);
//根据地图二维数组创建色块
for (var i = 0, len = maparr.length; i < len; i++) {
for (var j = 0, len1 = maparr[i].length; j < len1; j++) {
if (maparr[i][j]) {
createrect(j * r, i * r, r, "black");
}
}
}
//绘制开始方块
createrect(startrect.x, startrect.y, r, "red");
if (endrect.hascreate) {
//绘制跟随方块
createrect(endrect.pos()[0], endrect.pos()[1], r, "blue");
endpoint = mapscpos(endrect.pos()[1], endrect.pos()[0]);
if(path === null){
var asmap = convertarrtoas(maparr);
path = findpatha(asmap, startpoint, endpoint, asmap.length, asmap.length);
}else{
next = path.pop();
startrect.y = next.x * r;
startrect.x = next.y * r;
if(path.length===0){
startpoint = mapscpos(startrect.pos()[1], startrect.pos()[0]);
path = null;
endrect.hascreate = false;
}
}
}
requestanimationframe(update);
}
update();
stage.addeventlistener('click', function () {
//标准的获取鼠标点击相对于canvas画布的坐标公式
var x = event.clientx - stage.getboundingclientrect().left,
y = event.clienty - stage.getboundingclientrect().top;
var endrectpos = mapscpos(y, x);//[i,j]
endrect.x = endrectpos[1]*r;
endrect.y = endrectpos[0]*r;
if (maphasrect(maparr, endrectpos[0], endrectpos[1])) {
console.log('这个位置已经有方块啦！');
} else {
endrect.pos();
endrect.hascreate = true;
}
})
};
</script>
</html>
使用在线html/css/javascript代码运行工具：，测试运行上述代码，可得到如下运行效果：
更多关于javascript相关内容感兴趣的读者可查看本站专题：《javascript数学运算用法总结》、《javascript数据结构与算法技巧总结》、《javascript数组操作技巧总结》、《javascript排序算法总结》、《javascript遍历算法与技巧总结》、《javascript查找算法技巧总结》及《javascript错误与调试技巧总结》
希望本文所述对大家javascript程序设计有所帮助。
您可能感兴趣的文章:
如您对本文有疑问或者有任何想说的，请点击进行留言回复，万千网友为您解惑！
网友评论