JS/HTML5游戏常用算法之路径搜索算法 A*寻路算法完整实例
本文实例讲述了JS/HTML5游戏常用算法之路径搜索算法 A*寻路算法。分享给大家供大家参考，具体如下：
原理可参考：https://www.jb51.net/article/152744.htm
完整实例代码如下：
<!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代码运行工具：http://tools.jb51.net/code/HtmlJsRun，测试运行上述代码，可得到如下运行效果：
更多关于JavaScript相关内容感兴趣的读者可查看本站专题：《JavaScript数学运算用法总结》、《JavaScript数据结构与算法技巧总结》、《JavaScript数组操作技巧总结》、《JavaScript排序算法总结》、《JavaScript遍历算法与技巧总结》、《JavaScript查找算法技巧总结》及《JavaScript错误与调试技巧总结》
希望本文所述对大家JavaScript程序设计有所帮助。
相关推荐
-
node.js与C语言 实现遍历文件夹下最大的文件，并输出路径，大小
node.js版 遍历文件夹下最大的文件,并输出路径,大小 实现代码: /* 遍历文件夹下最大的文件,并输出路径,大小 */ function findmax(basepath){ //只能执行一次 if(findmax.s) return; findmax.s = true; var fs = require('fs'); var maxfile = 0; var count = 0; var begin = new Date().getTime(); function Travers
-
JS使用Dijkstra算法求解最短路径
一.Dijkstra算法的思路 Dijkstra算法是针对单源点求最短路径的算法. 其主要思路如下: 1. 将顶点分为两部分:已经知道当前最短路径的顶点集合Q和无法到达顶点集合R. 2. 定义一个距离数组(distance)记录源点到各顶点的距离,下标表示顶点,元素值为距离.源点(start)到自身的距离为0,源点无法到达的顶点的距离就是一个大数(比如Infinity). 3. 以距离数组中值为非Infinity的顶点V为中转跳点,假设V跳转至顶点W的距离加上顶点V至源点的距离还小于顶点W至源点
-
JS/HTML5游戏常用算法之路径搜索算法 随机迷宫算法详解【普里姆算法】
本文实例讲述了JS/HTML5游戏常用算法之路径搜索算法 随机迷宫算法.分享给大家供大家参考,具体如下: 路径搜索算法在游戏中非常常见,特别是在 RPG.SLG 中经常用到.在这些游戏中,通过鼠标指定行走目的地,人物或者NPC就会自动行走到目标地点,这就是通过路径搜索或者称为寻路算法来实现的.通俗地说,就是在一张地图中,如何让主角自动行走到指定的地点,如图6-21所示,假设主角在A处,然后玩家在地图中点击B处,要求主角能够从A点自动找寻一条到 B 点的路径,然后自动移动到 B处,要求就这么简单.
-
JS/HTML5游戏常用算法之路径搜索算法 A*寻路算法完整实例
本文实例讲述了JS/HTML5游戏常用算法之路径搜索算法 A*寻路算法.分享给大家供大家参考,具体如下: 原理可参考:https://www.jb51.net/article/152744.htm 完整实例代码如下: <!DOCTYPE html> <html lang="en"> <head> <meta name="viewport" content="width=device-width, initial-s
-
JS/HTML5游戏常用算法之碰撞检测 包围盒检测算法详解【凹多边形的分离轴检测算法】
本文实例讲述了JS/HTML5游戏常用算法之碰撞检测 包围盒检测算法.分享给大家供大家参考,具体如下: 概述 分离轴定理是一项用于检测碰撞的算法.其适用范围较广,涵盖检测圆与多边形,多边形与多边形的碰撞:缺点在于无法检测凹多边形的碰撞.本demo使用Js进行算法实现,HTML5 canvas进行渲染. 详细 一.准备工作,熟悉分离轴定理 算法原理 从根本上来讲,分离轴定理(以及其他碰撞算法)的用途就是去检测并判断两个图形之间是否有间隙.分离轴定理中用到的方法使算法本身显得十分独特. 我所听到过分
-
JS/HTML5游戏常用算法之追踪算法实例详解
本文实例讲述了JS/HTML5游戏常用算法之追踪算法.分享给大家供大家参考,具体如下: 追踪算法在动作游戏中非常常见,从很早的游戏<吃豆人>到大型的街机机战类游戏,到处可见追踪效果的身影.一个好的追踪算法将会大大提高游戏的可玩性和玩家的兴趣. [简单算法] 先来看一个简单的跟踪算法,如下图所示,假设在canvas坐标系中存在物体A和B,物体A将把B作为追踪目标,物体在二维空间中的运动可以分解为坐标系中X.Y轴的运动,其在X和Y方向的速度决定了物体运行的方向和速率.别忘了,速度是有方向和大小的,
-
JS/HTML5游戏常用算法之碰撞检测 像素检测算法实例详解
本文实例讲述了JS/HTML5游戏常用算法之碰撞检测 像素检测算法.分享给大家供大家参考,具体如下: 使用像素碰撞检测法算是最精确的算法了,当然,带来的代价也是比较明显的,那就是效率上的低下.除非是在极为特殊的情况下,要求使用非常精确的碰撞,否则,一般情况下在游戏中是不建议使用这种算法,特别是在运行效率不太高的HTML5游戏中. 一般来说在使用像素碰撞检测之前会使用AABB矩形包围盒先检测两个精灵是否有碰撞,如果AABB包围盒检测没有碰撞,那一定是没有碰撞到,反之,则不一定,需要进一步进行像素检
-
JS/HTML5游戏常用算法之碰撞检测 地图格子算法实例详解
本文实例讲述了JS/HTML5游戏常用算法之碰撞检测 地图格子算法.分享给大家供大家参考,具体如下: 这种算法经常用于RPG(早期的<最终幻想>.<DQ>.<仙剑奇侠传>).SLG(<炎龙骑士团>.<超级机器人大战>).PUZ(<俄罗斯方块>.<宝石谜阵>)类型的游戏.这类游戏中,通常情况下整个地图都是由一些地图块元素组成,在制作的时候首先给制作出地图所需要的最基本的元素进行编号,然后把这些编号的地图块组合起来就可以根据需
-
JS弹出可拖拽可关闭的div层完整实例
本文实例讲述了JS弹出可拖拽可关闭的div层完整实现方法.分享给大家供大家参考.具体实现方法如下: 复制代码 代码如下: <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> <html xmlns="http://www.w3.org/1999/xh
-
js实现的全国省市二级联动下拉选择菜单完整实例
本文实例讲述了js实现的全国省市二级联动下拉选择菜单.分享给大家供大家参考.具体如下: 运行效果截图如下: 在线演示地址如下: http://demo.jb51.net/js/2015/js-province-city-cho-menu-codes/ 具体代码如下: <!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-
-
js版本A*寻路算法
说到做游戏,必不可少的需要用到寻路算法,一般游戏里的寻路算法大多数都以A*算法为主,这里也就实现了js里采用a*寻路的程序,在51js和蓝色都开了帖. 程序是以前写的,后来也没有修正或者精简,有冗余之处大家还见谅一下. 当然,这个寻路算法也不是最优化的,像幻宇开发的"交点寻径法"也是个中精品,两者可谓各有千秋,只是如果地图很大的情况下,我们会惊讶于"交点寻径法"的迅速. use A* to find path... /* written by 百晓生 email:j
-
js+html5实现可在手机上玩的拼图游戏
本文实例讲述了js+html5实现可在手机上玩的拼图游戏.分享给大家供大家参考.具体如下: 手机版的拼图.pc上用Chrome 或者 Firefox var R=(function(){ /*右边菜单*/ function fa(){ if(mo.style.right!='0px'){ mo.style.right='0px'; mco.rcss('','cmck'); }else{ mo.style.right='-100px'; mco.rcss('cmck',''); } } on(mc