libGDX中的自动寻路

本文版权归作者所有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文连接,否则保留追究法律责任的权利。

转载自夜明的孤行灯

本文链接地址: https://www.huangyunkun.com/2016/06/12/libgdx-a-star-path-finder/

Gdx-ai提供了常见的AI算法,当然也包括寻路算法,比如常用的A*。

Gdx-ai自身的API抽象也很易懂,也方便自定义寻路。

首先由Graph和Connection提供图中的连通性和对应连接的开销。 简单一点直接用DefaultConnection,它提供的默认开销为1。

而PathFinder就是具体执行寻路的类,而返回的结果是GraphPath,它包含了路的结果,对应的连接还有其他一些数据。

这是Meritxell Calvo Palanques画的示意图

grafos

 

另外就是Heuristic,它并不是必须的,但是一个有效的Heuristic函数可以加快搜索,不过不方便提供,或者不想提供,最坏的结果无非就是退化为Dijkstra。(我提供的例子会直接返回一个错误的启发函数,不过依然可以获得结果)。

例子就简单一点吧,一般地图的数据是从Tiled地图或者其他格式的文件中获得的,这里我直接用硬编码来。

这个图只有四个点,其中点1,2,3相互连接,点3连接点4,我们要寻找从点1到点4的路径。

首先表示这个图

IndexedGraph<Node> graph = new IndexedGraph<Node>() {
            @Override
            public Array<Connection<Node>> getConnections(Node fromNode) {
                Array<Connection<Node>> connections = new Array<Connection<Node>>();
                switch (fromNode.getId()) {
                    case 1:
                        connections.add(new DefaultConnection<Node>(n1, n2));
                        connections.add(new DefaultConnection<Node>(n1, n3));
                        break;
                    case 2:
                        connections.add(new DefaultConnection<Node>(n2, n1));
                        connections.add(new DefaultConnection<Node>(n2, n3));
                        break;
                    case 3:
                        connections.add(new DefaultConnection<Node>(n3, n4));
                        connections.add(new DefaultConnection<Node>(n3, n1));
                        break;
                    default:
                        connections.add(new DefaultConnection<Node>(n4, n3));
                }
                return connections;
            }

            @Override
            public int getIndex(Node node) {
                return node.getId() - 1;
            }

            @Override
            public int getNodeCount() {
                return 4;
            }
        };

然后使用A*寻路并提供一个随机的启发函数

IndexedAStarPathFinder<Node> pathFinder = new IndexedAStarPathFinder<Node>(graph);
        GraphPath<Connection<Node>> out = new DefaultGraphPath<Connection<Node>>();
        final RandomXS128 randomXS128 = new RandomXS128();
        pathFinder.searchConnectionPath(n1, n4, new Heuristic<Node>() {
            @Override
            public float estimate(Node node, Node endNode) {
                return randomXS128.nextFloat();
            }
        }, out);

最后从GraphPath<Connection<Node>> out获取数据即可

a-star-path-finder

本文版权归作者所有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文连接,否则保留追究法律责任的权利。

转载自夜明的孤行灯

本文链接地址: https://www.huangyunkun.com/2016/06/12/libgdx-a-star-path-finder/

《libGDX中的自动寻路》有3条评论

  1. 灯神,能否再详细点。。。比如Node 这个类。是自己实现还是要做其他的。如果能有个具体的例子,如在tiled map ,一个工程里面 怎么用。。就更好了。。

    回复

回复 匿名 取消回复