42-在带权值节点的地图里使用A星寻路算法
8.15.4 在带权值节点的地图里使用A*寻路算法
在例8-16中,为节点设置不同的权值。首先,需要为之前例子中使用的地图添加新的草地。如果后面再使用A*寻路算法,就会主动的避开草地,因为草地的权值大于普通的区块的权值。
给节点赋予一个比1大的数,可以增加它的权值。创建的图片表可以很容易实现这个变化。图片表中第3个区块是草地,它的编号是2,用户可以将编号作为权重。对于astar.as而言,只要节点的权值比0大,该节点就是可通过的。一条通过迷宫的路径,如果其经过的节点的权值之和最小,则该路径为最优路径。为了证明这一点,可在地图中添加一些草地。下面的代码是例8-16作出的修改。虽然此处将穿越对角线的功能移除了,但是读者可以选择保留。例8-17将会重新增加该功能。
//例8-16基于例8-15的变化
var mapRows=15;
var mapCols=15;
var tileMap=[
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
,[0,1,2,1,1,1,1,1,1,1,1,1,1,1,0]
,[0,1,0,1,0,0,1,0,1,0,0,1,0,1,0]
,[0,1,0,1,0,0,1,0,1,0,0,1,0,1,0]
,[0,1,0,1,0,0,1,1,1,0,0,1,0,1,0]
,[0,2,1,1,1,1,0,0,0,1,1,1,1,1,0]
,[0,1,0,0,0,1,0,0,0,1,0,0,0,1,0]
,[0,1,1,1,2,1,0,0,0,1,1,1,1,1,0]
,[0,0,0,0,0,1,1,1,1,1,0,0,0,0,0]
,[0,1,1,1,1,1,0,0,0,1,1,1,1,1,0]
,[0,1,0,1,0,0,1,1,1,0,0,1,0,1,0]
,[0,1,0,1,0,0,2,0,1,0,0,1,0,1,0]
,[0,1,0,1,0,0,1,0,1,0,0,1,0,1,0]
,[0,1,1,1,1,1,1,2,1,1,1,1,1,1,0]
,[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
];
//设置 a* graph
var graph = new Graph(tileMap);
var startNode={x:4,y:1}; //使用将地图翻转后的值
var endNode={x:13,y:10};
//创建节点列表
var start = graph.nodes[startNode.x][startNode.y];
var end = graph.nodes[endNode.x][endNode.y];
var result = astar.search(graph.nodes, start, end, false);
如图8-16所示,因为原来的路径的总权值比现在的路径的权值更大,所以路径在经过一块草地之后,被迫更换了路线。
例8-16 添加在草地后的A*最优路径
<!doctype html>
<html lang="en">
<head>
<meta charset="UTF-8">
<title>Chapter 8 Example 16 - Larger A* Example with Grass Tiles</title>
<script src="modernizr.js"></script>
<script type='text/javascript' src='graph.js'></script>
<script type='text/javascript' src='astar.js'></script>
<script type="text/javascript">
window.addEventListener('load', eventWindowLoaded, false);
function eventWindowLoaded() {
canvasApp();
}
function canvasSupport () {
return Modernizr.canvas;
}
function canvasApp(){
if (!canvasSupport()) {
return;
}else{
var theCanvas = document.getElementById('canvas');
var context = theCanvas.getContext('2d');
}
//设置区块地图
var mapRows=15;
var mapCols=15;
var tileMap=[
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
,[0,1,2,1,1,1,1,1,1,1,1,1,1,1,0]
,[0,1,0,1,0,0,1,0,1,0,0,1,0,1,0]
,[0,1,0,1,0,0,1,0,1,0,0,1,0,1,0]
,[0,1,0,1,0,0,1,1,1,0,0,1,0,1,0]
,[0,2,1,1,1,1,0,0,0,1,1,1,1,1,0]
,[0,1,0,0,0,1,0,0,0,1,0,0,0,1,0]
,[0,1,1,1,2,1,0,0,0,1,1,1,1,1,0]
,[0,0,0,0,0,1,1,1,1,1,0,0,0,0,0]
,[0,1,1,1,1,1,0,0,0,1,1,1,1,1,0]
,[0,1,0,1,0,0,1,1,1,0,0,1,0,1,0]
,[0,1,0,1,0,0,2,0,1,0,0,1,0,1,0]
,[0,1,0,1,0,0,1,0,1,0,0,1,0,1,0]
,[0,1,1,1,1,1,1,2,1,1,1,1,1,1,0]
,[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
];
//设置 a* graph
var graph = new Graph(tileMap);
var startNode={x:4,y:1}; //使用将地图翻转后的值
var endNode={x:13,y:10};
//创建节点列表
var start = graph.nodes[startNode.x][startNode.y];
var end = graph.nodes[endNode.x][endNode.y];
var result = astar.search(graph.nodes, start, end, false);
//加载图片表
var tileSheet=new Image();
tileSheet.addEventListener('load', eventSheetLoaded , false);
tileSheet.src="tiles.png";
function eventSheetLoaded() {
drawScreen()
}
function drawScreen() {
for (var rowCtr=0;rowCtr<mapRows;rowCtr++) {
for (var colCtr=0;colCtr<mapCols;colCtr++){
var tileId=tileMap[rowCtr][colCtr];
var sourceX=Math.floor(tileId % 5) *32;
var sourceY=Math.floor(tileId / 5) *32;
context.drawImage(tileSheet, sourceX, sourceY,32,32,
colCtr*32,rowCtr*32,32,32);
}
}
//在起始点绘制绿色圆圈
context.beginPath();
context.strokeStyle="green";
context.lineWidth=5;
context.arc((startNode.y*32)+16, (startNode.x*32)+16, 10, 0,
(Math.PI/180) *360,false);
context.stroke();
context.closePath();
//在终点绘制红色圆圈
context.beginPath();
context.strokeStyle="red";
context.lineWidth=5;
context.arc((endNode.y*32)+16, (endNode.x*32)+16, 10, 0,
(Math.PI/180) *360,false);
context.stroke();
context.closePath();
//在路径上绘制黑色圆圈
for (var ctr=0;ctr<result.length-1;ctr++) {
var node=result[ctr];
context.beginPath();
context.strokeStyle="black";
context.lineWidth=5;
context.arc((node.y*32)+16, (node.x*32)+16, 10, 0,
(Math.PI/180) *360,false);
context.stroke();
context.closePath();
}
}
}
</script>
</head>
<body>
<div style="position: absolute; top: 50px; left: 50px;">
<canvas id="canvas" width="500" height="500">
Your browser does not support the HTML5 Canvas.
</canvas>
</div>
</body>
</html>
如图8-16所示,例8-16中尽管经过了一块草地,总权值增加了1,但仍是到达目标节点的最短路径。例8-17将重新添加穿越对角线的功能,这样,坦克将克服草地的影响,因为A*寻路算法可以找到一条总权值比之前路径更小的路径。