本文版权归作者所有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文连接,否则保留追究法律责任的权利。
转载自夜明的孤行灯
本文链接地址: 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画的示意图
另外就是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获取数据即可
本文版权归作者所有,欢迎转载,但未经作者同意必须保留此段声明,且在文章页面明显位置给出原文连接,否则保留追究法律责任的权利。
转载自夜明的孤行灯
本文链接地址: https://www.huangyunkun.com/2016/06/12/libgdx-a-star-path-finder/
灯神,能否再详细点。。。比如Node 这个类。是自己实现还是要做其他的。如果能有个具体的例子,如在tiled map ,一个工程里面 怎么用。。就更好了。。
node类是自己实现的
恩,这个知道了,把GitHub上的 例子down下来,看到了。但是那个行为树的例子。。灯神要不要也来一个。。官方的太高大上。。= = 都看不懂。。