A*寻路算法 - Java，Slick2D库

Question

我正在使用Slick2D制作一款游戏。它拥有TiledMap和实体（像其他游戏一样），我想要一种使用A*算法的方法。但是我不知道如何使用，因为我找不到解释。

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

- user1217946

Answer 1

以下是Slick2D中A星寻路算法的简单示例。在实际游戏中，您可能会有一个更逼真的TileBasedMap接口实现，它实际上查找您的游戏使用的任何地图结构中的可访问性。您还可以根据地图地形返回不同的成本。

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 接口，这样你就可以将其作为用户数据对象传递给 findPath 调用，而不是 null。这将使该对象可通过 ctx.getMover() 从 blocked 和 cost 方法中获得。这样，你可以有一些忽略某些会阻碍移动的障碍物的移动者（比如一个能在水上或墙上飞行的角色或两栖车辆）。希望这能给你一个基本的想法。 编辑 我现在注意到你特别提到了使用 TiledMap 类。该类没有实现 TileBasedMap 接口，不能直接与Slick2D中的A星实现一起使用。（Tiled地图默认没有任何关于阻塞的概念，在执行路径查找时这很重要。）因此，您将不得不自己实现它，使用自己的标准来确定哪个瓦片是阻塞的，哪个不是，并且穿越它们的代价是多少。 编辑2 有几种方法可以定义瓷砖的“阻塞”概念。下面介绍了一些相对直接的方法：

单独的阻塞层

在Tiled地图格式中，您可以指定多个图层。您可以专门为您的阻塞瓦片分配一个图层，然后根据类似于以下内容的方式实现 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) {}

}

基于图块属性的阻挡

在Tiled地图格式中，每种瓷砖类型可以选择性地具有用户定义的属性。您可以轻松地将blocking属性添加到应该被阻挡的瓷砖中，然后在您的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视为阻塞。

此外，以上所有示例仅考虑了阻塞和非阻塞的瓦片。当然，地图上可能还有阻塞和非阻塞对象。你也可能有其他玩家或NPC等阻塞物体。这些都需要以某种方式处理。但这应该能让你有所启发。

- Jiddo

---

好的，谢谢。我还有一个问题，我能让SimpleMap使用TiledMap创建数组吗？这样它们就会相同并且可以工作了吗？ - user1217946

@IvanDonat 这个数组只是一个例子。你需要自己决定如何确定你的 TiledMap 中的瓷砖是否会阻挡。例如，你可以在 TiledMap 中有一个特定的层，其中只包含阻挡物品。然后，你可以通过检查 TiledMap.getTileId(x,y,blockingLayerId) 是否返回零来实现 blocking 方法。或者，你可以为阻挡瓷砖设置一个 __tile 属性__（使用编辑器），然后检查该瓷砖是否具有该属性。我将更新我的答案并提供一些示例，但也有其他方法。 - Jiddo

非常感谢！顺便提一下，我之前使用过阻塞属性，所以我对它很熟悉:D - user1217946

当我使用它时，它总是在你使用路径内部的任何内容的点上返回null。 - me me

我正准备实现非常类似的类，以便让路径查找工作与TiledMap一起使用。你应该真的将那段代码贡献给Slick2D，因为它非常通用：https://bitbucket.org/kevglass/slick。如果你不这样做，我会的 :) - Nico