java - A* 寻路 - Java，Slick2D 库

Question

所以我使用 Slick2D 制作游戏。它有一个 TiledMap 和实体(与任何其他游戏一样)，我想要一种使用 A* 的方法。我真的不知道如何使用它，因为我找不到解释。

对于那些不使用 Slick 的人来说，它已经有我使用的 AStarPathFinding 和 TiledMap 类。

Answer 1

这是一个简单的示例，说明 Slick2D 中的 A-star 路径查找是如何工作的。在真实游戏中，您可能会更实际地实现 TileBasedMap 接口(interface)，该接口(interface)实际上会在您的游戏使用的任何 map 结构中查找可访问性。您还可以根据例如您的 map 地形返回不同的成本。

import org.newdawn.slick.util.pathfinding.AStarPathFinder;
import org.newdawn.slick.util.pathfinding.Mover;
import org.newdawn.slick.util.pathfinding.Path;
import org.newdawn.slick.util.pathfinding.PathFindingContext;
import org.newdawn.slick.util.pathfinding.TileBasedMap;


public class AStarTest {

    private static final int MAX_PATH_LENGTH = 100;

    private static final int START_X = 1;
    private static final int START_Y = 1;

    private static final int GOAL_X = 1;
    private static final int GOAL_Y = 6;

    public static void main(String[] args) {

        SimpleMap map = new SimpleMap();

        AStarPathFinder pathFinder = new AStarPathFinder(map, MAX_PATH_LENGTH, false);
        Path path = pathFinder.findPath(null, START_X, START_Y, GOAL_X, GOAL_Y);

        int length = path.getLength();
        System.out.println("Found path of length: " + length + ".");

        for(int i = 0; i < length; i++) {
            System.out.println("Move to: " + path.getX(i) + "," + path.getY(i) + ".");
        }

    }

}

class SimpleMap implements TileBasedMap {
    private static final int WIDTH = 10;
    private static final int HEIGHT = 10;

    private static final int[][] MAP = {
        {1,1,1,1,1,1,1,1,1,1},
        {1,0,0,0,0,0,1,1,1,1},
        {1,0,1,1,1,0,1,1,1,1},
        {1,0,1,1,1,0,0,0,1,1},
        {1,0,0,0,1,1,1,0,1,1},
        {1,1,1,0,1,1,1,0,0,0},
        {1,0,1,0,0,0,0,0,1,0},
        {1,0,1,1,1,1,1,1,1,0},
        {1,0,0,0,0,0,0,0,0,0},
        {1,1,1,1,1,1,1,1,1,0}
    };

    @Override
    public boolean blocked(PathFindingContext ctx, int x, int y) {
        return MAP[y][x] != 0;
    }

    @Override
    public float getCost(PathFindingContext ctx, int x, int y) {
        return 1.0f;
    }

    @Override
    public int getHeightInTiles() {
        return HEIGHT;
    }

    @Override
    public int getWidthInTiles() {
        return WIDTH;
    }

    @Override
    public void pathFinderVisited(int x, int y) {}

}

在您的游戏中，您可能还希望让寻路角色类实现 Mover 接口(interface)，以便您可以将其作为用户数据对象而不是 null 传递给findPath 调用。这将使该对象通过 ctx.getMover() 从 blocked 和 cost 方法可用。这样你就可以让一些移动器忽略一些，否则会阻挡，障碍物等。(想象一个飞行角色或两栖车辆可以在水中或在其他阻挡墙壁上方移动。)我希望这能给出一个基本的想法。

编辑我现在注意到您特别提到您正在使用 TiledMap 类。该类没有实现TileBasedMap接口(interface)，不能直接与Slick2D中的A-star实现一起使用。 (Tiled map 在默认情况下没有任何阻塞 的概念，这是执行路径查找时的关键。)因此，您必须自己实现这一点，使用您自己的标准来判断何时 tile 阻塞或不是以及遍历它们应该花费多少。

编辑 2

您可以通过多种方式定义 block 阻塞 的概念。下面介绍了一些相对直接的方法:

分离阻挡层

在平铺 map 格式中，您可以指定多个图层。您可以只为阻塞图 block 指定一层，然后根据如下内容实现 TileBasedMap:

class LayerBasedMap implements TileBasedMap {

    private TiledMap map;
    private int blockingLayerId;

    public LayerBasedMap(TiledMap map, int blockingLayerId) {
        this.map = map;
        this.blockingLayerId = blockingLayerId;
    }

    @Override
    public boolean blocked(PathFindingContext ctx, int x, int y) {
        return map.getTileId(x, y, blockingLayerId) != 0;
    }

    @Override
    public float getCost(PathFindingContext ctx, int x, int y) {
        return 1.0f;
    }

    @Override
    public int getHeightInTiles() {
        return map.getHeight();
    }

    @Override
    public int getWidthInTiles() {
        return map.getWidth();
    }

    @Override
    public void pathFinderVisited(int arg0, int arg1) {}

}

基于 Tile 属性的阻塞

在分块 map 格式中，每个分块类型都可以选择具有用户定义的属性。您可以轻松地将 blocking 属性添加到应该阻塞的图 block ，然后在您的 TileBasedMap 实现中检查它。例如:

class PropertyBasedMap implements TileBasedMap {

    private TiledMap map;
    private String blockingPropertyName;

    public PropertyBasedMap(TiledMap map, String blockingPropertyName) {
        this.map = map;
        this.blockingPropertyName = blockingPropertyName;
    }

    @Override
    public boolean blocked(PathFindingContext ctx, int x, int y) {
        // NOTE: Using getTileProperty like this is slow. You should instead cache the results. 
        // For example, set up a HashSet<Integer> that contains all of the blocking tile ids. 
        return map.getTileProperty(map.getTileId(x, y, 0), blockingPropertyName, "false").equals("true");
    }

    @Override
    public float getCost(PathFindingContext ctx, int x, int y) {
        return 1.0f;
    }

    @Override
    public int getHeightInTiles() {
        return map.getHeight();
    }

    @Override
    public int getWidthInTiles() {
        return map.getWidth();
    }

    @Override
    public void pathFinderVisited(int arg0, int arg1) {}

}

其他选项

还有很多其他选择。例如，您可以为图层本身设置属性，而不是将图层 ID 设置为阻挡层，以指示它是否是阻挡层。

此外，上述所有示例都只考虑了阻塞与非阻塞tiles。当然，您在 map 上也可能有阻塞和非阻塞对象。您也可能有其他玩家或 NPC 等正在阻挡。所有这些都需要以某种方式处理。但是，这应该可以帮助您入门。