Posted on 2014-12-02 10:37
TWaver 阅读(6677)
评论(0) 编辑 收藏
前段时间有个客户说他们想在我们的3D的机房中找从A点到B点的最短路径,然而在2D中确实有很多成熟的寻路算法,其中A*是最为常见的,而这个Demo也是用的A*算法,以下计算的是从左上角到右下角的最短路径:
具体的实现方式是,先将地板进行了分割,分成一个数组,然后再计算该点上是否有3D的对象,若是有,就置成该点不能通过的标记,否则就表示该点可以通过(如果你分割的越细那么算的就越精确,但是算的当然也就慢一些,关键看你的要求),以下是分割地板的代码:
1 | var size = {x: 100 , y: 100 }; // 100*100 |
2 | var topLeft = {x: 228 , y: 53 }; |
5 | var dw = width / size.x; |
6 | var dh = height / size.y; |
12 | for (var i = 0 ; i < size.x; i++) { |
14 | var x = topLeft.x + dw * i |
15 | for (var j = 0 ; j < size.y; j++) { |
16 | var y = topLeft.y + dh * j; |
17 | if (isHasObj(x, y)) { //判断该点上是否有物体 |
25 | graph = new Graph(nodes, { |
30 | //这里是找一条从(0,0)到(79,80)的路径。 |
31 | start = graph.grid[ 0 ][ 0 ]; |
分割好地板后就相当于将3D中的寻路转换成了2D中的寻路,此时就可以直接使用A*算法来进行寻路了,这里的A*寻路算法如下:
1 | function search(graph, start, end, options) { |
4 | options = options || {}; |
5 | var heuristic = options.heuristic || astar.heuristics.manhattan, |
6 | closest = options.closest || false ; |
8 | var openHeap = getHeap(), |
9 | closestNode = start; // set the start node to be the closest if required |
11 | start.h = heuristic(start, end); |
15 | while (openHeap.size() > 0 ) { |
17 | var currentNode = openHeap.pop(); |
19 | if (currentNode === end) { |
20 | return pathTo(currentNode); |
23 | // Normal case -- move currentNode from open to closed, process each of its neighbors. |
24 | currentNode.closed = true ; |
26 | // Find all neighbors for the current node. |
27 | var neighbors = graph.neighbors(currentNode); |
29 | for (var i = 0 , il = neighbors.length; i < il; ++i) { |
30 | var neighbor = neighbors[i]; |
32 | if (neighbor.closed || neighbor.isWall()) { |
33 | // Not a valid node to process, skip to next neighbor. |
36 | var gScore = currentNode.g + neighbor.getCost(currentNode), |
37 | beenVisited = neighbor.visited; |
39 | if (!beenVisited || gScore < neighbor.g) { |
41 | neighbor.visited = true ; |
42 | neighbor.parent = currentNode; |
43 | neighbor.h = neighbor.h || heuristic(neighbor, end); |
45 | neighbor.f = neighbor.g + neighbor.h; |
49 | if (neighbor.h < closestNode.h || (neighbor.h === closestNode.h && neighbor.g < closestNode.g)) { |
50 | closestNode = neighbor; |
55 | // Pushing to heap will put it in proper place based on the 'f' value. |
56 | openHeap.push(neighbor); |
59 | openHeap.rescoreElement(neighbor); |
66 | return pathTo(closestNode); |
看似实现了,如果你细心的话,你可以会发现在3D中存在类似像门那样的可以穿过的物体,或者说有两层楼,那这就不好转换了,确实是存在这样的问题,但是我们可以改进isHasObj这个方法,假如我们寻路的是一个人的话,那么我们人是有高度的,设置高度为man.height,我们判断某点上是否存在物体的话,然后在该点上“发射”一条Ray的方式(具体实现牵涉到一些数学知识,这里不多讲,下次可以单独弄了blog讲解),然后会返回的参数中有一个“距离”的属性,该属性就是我们地板上的点到该点上面那个物体的距离,因此我们可以通过这个距离来和man的身高的关系来确定该点是否可以通过,代码如下:
1 | function isHasObj(x, y) { |
2 | var obj = getElementsByPosition(x, y); |
3 | if (obj && obj.length > 1 ) { //length > 1, bc is must a obj that is shapenode |
4 | for (var i = 0 ; i < obj.length; i++) { |
5 | if (obj[i] && !(obj[i].element instanceof mono.ShapeNode) && obj[i].element != man) { |
7 | console.log( "x:" + x + ";y:" + y + ";distance:" + obj[i].distance); |
8 | if (obj[i].distance < (man.height + 10 )) { |
如下是通过一个ShapePath这样的物体:
该Demo主要是想表达这个意思,美化方面还有改进的空间,比如可以考虑用我们的mono创建一个人的模型,还可以去判断该通过物体的宽度等等!