TWaver - 专注UI技术

http://twaver.servasoft.com/
posts - 171, comments - 191, trackbacks - 0, articles - 2
  BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

如何在MONO 3D寻找最短路路径

Posted on 2014-12-02 10:37 TWaver 阅读(6672) 评论(0)  编辑  收藏

前段时间有个客户说他们想在我们的3D的机房中找从A点到B点的最短路径，然而在2D中确实有很多成熟的寻路算法，其中A*是最为常见的，而这个Demo也是用的A*算法，以下计算的是从左上角到右下角的最短路径：
左上
具体的实现方式是，先将地板进行了分割，分成一个数组，然后再计算该点上是否有3D的对象，若是有，就置成该点不能通过的标记，否则就表示该点可以通过（如果你分割的越细那么算的就越精确，但是算的当然也就慢一些，关键看你的要求），以下是分割地板的代码：

1var size = {x: 100, y: 100}; // 100*100
2var topLeft = {x: 228, y: 53};
3var width = 524;
4var height = 400;
5var dw = width / size.x;
6var dh = height / size.y;
7var start;
8var end;
9var graph;
10function to2d() {
11    var nodes = [];
12    for (var i = 0; i < size.x; i++) {
13        var nodeRow = [];
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)) { //判断该点上是否有物体
18                nodeRow.push(0);
19            } else {
20                nodeRow.push(1);
21            }
22        }
23        nodes.push(nodeRow);
24    }
25    graph = new Graph(nodes, {
26        closest: null,
27        diagonal: false
28    });
29 
30    //这里是找一条从(0,0)到(79,80)的路径。
31    start = graph.grid[0][0];
32    drawPath(79, 80);
33}


分割好地板后就相当于将3D中的寻路转换成了2D中的寻路，此时就可以直接使用A*算法来进行寻路了，这里的A*寻路算法如下：

1function  search(graph, start, end, options) {
2        astar.init(graph);
3 
4        options = options || {};
5        var heuristic = options.heuristic || astar.heuristics.manhattan,
6            closest = options.closest || false;
7 
8        var openHeap = getHeap(),
9            closestNode = start; // set the start node to be the closest if required
10 
11        start.h = heuristic(start, end);
12 
13        openHeap.push(start);
14 
15        while(openHeap.size() > 0) {
16 
17            var currentNode = openHeap.pop();
18 
19            if(currentNode === end) {
20                return pathTo(currentNode);
21            }
22 
23            // Normal case -- move currentNode from open to closed, process each of its neighbors.
24            currentNode.closed = true;
25 
26            // Find all neighbors for the current node.
27            var neighbors = graph.neighbors(currentNode);
28 
29            for (var i = 0, il = neighbors.length; i < il; ++i) {
30                var neighbor = neighbors[i];
31 
32                if (neighbor.closed || neighbor.isWall()) {
33                    // Not a valid node to process, skip to next neighbor.
34                    continue;
35                }
36                var gScore = currentNode.g + neighbor.getCost(currentNode),
37                    beenVisited = neighbor.visited;
38 
39                if (!beenVisited || gScore < neighbor.g) {
40 
41                    neighbor.visited = true;
42                    neighbor.parent = currentNode;
43                    neighbor.h = neighbor.h || heuristic(neighbor, end);
44                    neighbor.g = gScore;
45                    neighbor.f = neighbor.g + neighbor.h;
46 
47                    if (closest) {
48                        
49                        if (neighbor.h < closestNode.h || (neighbor.h === closestNode.h && neighbor.g < closestNode.g)) {
50                            closestNode = neighbor;
51                        }
52                    }
53 
54                    if (!beenVisited) {
55                        // Pushing to heap will put it in proper place based on the 'f' value.
56                        openHeap.push(neighbor);
57                    }
58                    else {
59                       openHeap.rescoreElement(neighbor);
60                    }
61                }
62            }
63        }
64 
65        if (closest) {
66            return pathTo(closestNode);
67        }
68 
69        return [];
70    }

看似实现了，如果你细心的话，你可以会发现在3D中存在类似像门那样的可以穿过的物体，或者说有两层楼，那这就不好转换了，确实是存在这样的问题，但是我们可以改进isHasObj这个方法，假如我们寻路的是一个人的话，那么我们人是有高度的，设置高度为man.height，我们判断某点上是否存在物体的话，然后在该点上“发射”一条Ray的方式（具体实现牵涉到一些数学知识，这里不多讲，下次可以单独弄了blog讲解），然后会返回的参数中有一个“距离”的属性，该属性就是我们地板上的点到该点上面那个物体的距离，因此我们可以通过这个距离来和man的身高的关系来确定该点是否可以通过，代码如下：

1function 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) {
6                if (isCheckHeight) {
7                    console.log("x:" + x + ";y:" + y + ";distance:" + obj[i].distance);
8                    if (obj[i].distance < (man.height + 10)) {
9                        return true;
10                    } else {
11                        return false;
12                    }
13                } else {
14                    return true;
15                }
16            }
17        }
18    }
19    return false;
20}

如下是通过一个ShapePath这样的物体：
cross a Path

该Demo主要是想表达这个意思，美化方面还有改进的空间，比如可以考虑用我们的mono创建一个人的模型，还可以去判断该通过物体的宽度等等！



只有注册用户登录后才能发表评论。
网站导航: