我们一直致力于寻求一种高性能的图形渲染方法,以便将其用于最终的游戏。而路径查找则是一个非常有用的功能,可以用于创建道路或显示角色从A 点到B 点的过程。简言之,路径查找算法就是要在n 维(通常是2D 或3D)空间中找出两点间的最短路线。

通常,只有少数人才能实现准确的路径查找;换句话说,很多人(但愿不包括我们)都无法保证计算结果的准确性。可以说这是一项计算量很大的工作,而最有效的解决方案就是根据我们的产品修改算法,以便得到最合用的方法。

处理路径查找的一种最佳算法叫做A*,是迪杰斯特拉(Dijkstra)算法的变体。路径查找(或者类似的计算时间超过数毫秒的操作)的问题在于,它们会导致JavaScript 产生一种名为“界面锁定”的效果,也就是在操作完成以前,浏览器将一直被冻结。

幸运的是,HTML5 规范也提供了一个名为Web Workers 的新API。Web Workers(通常称为“worker”)可以让我们在后台执行计算量相对较大以及执行时间较长的脚本,而不会影响浏览器的主用户界面。

worker 不是银弹,不能魔幻般地让原来吃掉100% 的CPU 处理能力的任务变得轻而易举。只要是常规手段下计算量大的任务,使用worker 可能照样还是计算量大,最终还是会影响到用户体验。不过,如果是只消耗了30%的CPU 处理能力的任务,利用worker 并行来处理还是可以把用户界面的影响降到最低的。

当然,也有一些限制:

  • 由于每个worker 都运行在与执行它们的页面完全独立、线程安全的环境下(也• 叫“沙盒”),因此它们不能访问DOM 和window 对象;

  • 尽管已有的worker 可以再产生新的worker(谷歌的Chrome 不支持这个功能),但使用起来必须多加小心,因为这样一来,如果产生bug 将会很难调试。

要创建worker,可以使用以下语法:

var worker = new Worker(PATH_TO_A_JS_SCRIPT);

其中的PATH_TO_A_JS_SCRIPT 可以是一个脚本文件, 比如astar.js。在创建了worker 之后,任何时候调用worker.close() 都可以终止它的执行。如果终止了一个worker,然后又需要执行一个新操作,那么就得再创建一个新的worker 对象。

Web Workers 之间的通信是通过在worker.onmessage 事件的回调函数中调用worker.postMessage(object) 来实现的。此外,还可以通过onerror 事件处理程序来处理worker 的错误。与普通的网页类似,Web Workers 也支持引入外部脚本,使用的是importScripts()函数。这个函数接受零个或多个参数,如果有参数,每个参数都应该是一个JavaScript文件。

本书在线代码库的ex17-grid-astar.html 中有一个用JavaScript 实现的A* 算法,其中使用了Web Worders。图4-2 展示了这个示例的运行效果。程序示例4-4 和程序示例4-5 展示了网页及A* 算法的JavaScript 实现。

enter image description here

程序示例4-4 路径查找HTML

<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8" />
<title>Example 17 - (A* working on a grid with unset indexes using
web workers)</title>
<script>
window.onload = function () {
var tileMap = [];
var path = {
start: null,
stop: null
}
var tile = {
width: 6,
height: 6
}
var grid = {
width: 100,
height: 100
}
var canvas = document.getElementById('myCanvas');
canvas.addEventListener('click', handleClick, false);
var c = canvas.getContext('2d');
// 随机生成1000 个元素
for (var i = 0; i < 1000; i++) {
generateRandomElement();
}
// 绘制整个网格
draw();
function handleClick(e) {
// 检测到鼠标单击后,把鼠标坐标转换为像素坐标
var row = Math.floor((e.clientX - 10) / tile.width);
var column = Math.floor((e.clientY - 10) / tile.height);
if (tileMap[row] == null) {
tileMap[row] = [];
}
if (tileMap[row][column] !== 0 && tileMap[row][column] !== 1) {
tileMap[row][column] = 0;
if (path.start === null) {
path.start = {x: row, y: column};
} else {
path.stop = {x: row, y: column};
callWorker(path, processWorkerResults);
path.start = null;
path.stop = null;
}
draw();
}
}
function callWorker(path, callback) {
var w = new Worker('astar.js');
w.postMessage({
tileMap: tileMap,
grid: {
width: grid.width,
height: grid.height
},
start: path.start,
stop: path.stop
});
w.onmessage = callback;
}
function processWorkerResults(e) {
if (e.data.length > 0) {
for (var i = 0, len = e.data.length; i < len; i++) {
if (tileMap[e.data[i].x] === undefined) {
tileMap[e.data[i].x] = [];
}
tileMap[e.data[i].x][e.data[i].y] = 0;
}
}
draw();
}
function generateRandomElement() {
var rndRow = Math.floor(Math.random() * (grid.width + 1));
var rndCol = Math.floor(Math.random() * (grid.height + 1));
if (tileMap[rndRow] == null) {
tileMap[rndRow] = [];
}
tileMap[rndRow][rndCol] = 1;
}
function draw(srcX, srcY, destX, destY) {
srcX = (srcX === undefined) ? 0 : srcX;
srcY = (srcY === undefined) ? 0 : srcY;
destX = (destX === undefined) ? canvas.width : destX;
destY = (destY === undefined) ? canvas.height : destY;
c.fillStyle = '#FFFFFF';
c.fillRect (srcX, srcY, destX + 1, destY + 1);
c.fillStyle = '#000000';
var startRow = 0;
var startCol = 0;
var rowCount = startRow + Math.floor(canvas.width / tile.
width) + 1;
var colCount = startCol + Math.floor(canvas.height / tile.
height) + 1;
rowCount = ((startRow + rowCount) > grid.width) ? grid.width :
rowCount;
colCount = ((startCol + colCount) > grid.height) ? grid.height :
colCount;
for (var row = startRow; row < rowCount; row++) {
for (var col = startCol; col < colCount; col++) {
var tilePositionX = tile.width * row;
var tilePositionY = tile.height * col;
if (tilePositionX >= srcX && tilePositionY >= srcY &&
tilePositionX <= (srcX + destX) &&
tilePositionY <= (srcY + destY)) {
if (tileMap[row] != null && tileMap[row][col] != null) {
if (tileMap[row][col] == 0) {
c.fillStyle = '#CC0000';
} else {
c.fillStyle = '#0000FF';
}
c.fillRect(tilePositionX, tilePositionY, tile.width,
tile.height);
} else {
c.strokeStyle = '#CCCCCC';
c.strokeRect(tilePositionX, tilePositionY, tile.width,
tile.height);
}
}
}
}
}
}
</script>
</head>
<body>
<canvas id="myCanvas" width="600" height="300"></canvas>
<br />
</body>
</html>

程序示例4-5 A* 算法的JavaScript 实现

// 这个worker 处理负责aStar 类的实例
onmessage = function(e){
var a = new aStar(e.data.tileMap, e.data.grid.width, e.data.grid.height,
e.data.start, e.data.stop);
postMessage(a);
}
// 基于非连续索引的tileMap 调整后的A* 路径查找类
/**
* @param tileMap: A 2-dimensional matrix with noncontiguous indexes
* @param gridW: Grid width measured in rows
* @param gridH: Grid height measured in columns
* @param src: Source point, an object containing X and Y
* coordinates representing row/column
* @param dest: Destination point, an object containing
* X and Y coordinates representing row/column
* @param createPositions: [OPTIONAL] A boolean indicating whether
* traversing through the tileMap should
* create new indexes (default TRUE)
*/
var aStar = function(tileMap, gridW, gridH, src, dest, createPositions) {
this.openList = new NodeList(true, 'F');
this.closedList = new NodeList();
this.path = new NodeList();
this.src = src;
this.dest = dest;
this.createPositions = (createPositions === undefined) ? true :
createPositions;
this.currentNode = null;
var grid = {
rows: gridW,
cols: gridH
}
this.openList.add(new Node(null, this.src));
while (!this.openList.isEmpty()) {
this.currentNode = this.openList.get(0);
this.currentNode.visited = true;
if (this.checkDifference(this.currentNode, this.dest)) {
// 到达目的地 :)
break;
}
this.closedList.add(this.currentNode);
this.openList.remove(0);
// 检查与当前节点相近的8 个元素
var nstart = {
HTML5声音及处理优化 | 219
x: (((this.currentNode.x - 1) >= 0) ? this.currentNode.x - 1 : 0),
y: (((this.currentNode.y - 1) >= 0) ? this.currentNode.y - 1 : 0),
}
var nstop = {
x: (((this.currentNode.x + 1) <= grid.rows) ? this.currentNode.
x + 1 : grid.rows),
y: (((this.currentNode.y + 1) <= grid.cols) ? this.currentNode.
y + 1 : grid.cols),
}
for (var row = nstart.x; row <= nstop.x; row++) {
for (var col = nstart.y; col <= nstop.y; col++) {
// 在原始的tileMap 中还没有行,还继续吗?
if (tileMap[row] === undefined) {
if (!this.createPositions) {
continue;
}
}
// 检查建筑物或其他障碍物
if (tileMap[row] !== undefined && tileMap[row][col] === 1) {
continue;
}
var element = this.closedList.getByXY(row, col);
if (element !== null) {
// 这个元素已经在closedList 中了
continue;
} else {
element = this.openList.getByXY(row, col);
if (element !== null) {
// 这个元素已经在closedList 中了
continue;
}
}
// 还不在任何列表中,继续
var n = new Node(this.currentNode, {x: row, y: col});
n.G = this.currentNode.G + 1;
n.H = this.getDistance(this.currentNode, n);
n.F = n.G + n.H;
this.openList.add(n);
}
}
}
while (this.currentNode.parentNode !== null) {
this.path.add(this.currentNode);
this.currentNode = this.currentNode.parentNode;
}
}
aStar.prototype.checkDifference = function(src, dest) {
return (src.x === dest.x && src.y === dest.y);
}
aStar.prototype.getDistance = function(src, dest) {
return Math.abs(src.x - dest.x) + Math.abs(src.y - dest.y);
}
function Node(parentNode, src) {
this.parentNode = parentNode;
this.x = src.x;
this.y = src.y;
this.F = 0;
this.G = 0;
this.H = 0;
}
var NodeList = function(sorted, sortParam) {
this.sort = (sorted === undefined) ? false : sorted;
this.sortParam = (sortParam === undefined) ? 'F' : sortParam;
this.list = [];
this.coordMatrix = [];
}
NodeList.prototype.add = function(element) {
this.list.push(element);
if (this.coordMatrix[element.x] === undefined) {
this.coordMatrix[element.x] = [];
}
this.coordMatrix[element.x][element.y] = element;
if (this.sort) {
var sortBy = this.sortParam;
this.list.sort(function(o1, o2) { return o1[sortBy] - o2[sortBy]; });
}
}
NodeList.prototype.remove = function(pos) {
this.list.splice(pos, 1);
}
NodeList.prototype.get = function(pos) {
return this.list[pos];
}
NodeList.prototype.size = function() {
return this.list.length;
}
NodeList.prototype.isEmpty = function() {
return (this.list.length == 0);
}
NodeList.prototype.getByXY = function(x, y) {
if (this.coordMatrix[x] === undefined) {
return null;
} else {
var obj = this.coordMatrix[x][y];
if (obj == undefined) {
return null;
} else {
return obj;
}
}
}
NodeList.prototype.print = function() {
for (var i = 0, len = this.list.length; i < len; i++) {
console.log(this.list[i].x + ' ' + this.list[i].y);
}
}

本文摘自《深入HTML5应用开发》