3

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

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

4

1 回答 1

16

这是 Slick2D 中的 A-star 路径查找如何工作的简单示例。在真正的游戏中，您可能会有一个更真实的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接口，以便您可以将其作为用户数据对象而不是调用null传递。findPath这将使该对象可通过blocked和cost方法使用ctx.getMover()。这样你就可以让一些移动器忽略一些，否则会阻塞，障碍物等。（想象一个飞行角色或两栖车辆，可以在水中或在其他阻塞的墙壁上方移动。）我希望这能给出一个基本的想法。

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

编辑 2

有几种方法可以定义 tile 被阻塞的概念。下面介绍了几种相对直接的方法：

单独的阻挡层

在平铺地图格式中，您可以指定多个图层。您可以只为您的阻塞图块专用一层，然后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) {}

}

基于平铺属性的阻塞

在平铺地图格式中，每种平铺类型都可以选择具有用户定义的属性。您可以轻松地将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 等阻止。所有这些都需要以某种方式处理。但是，这应该可以帮助您入门。

于 2012-03-16T21:49:39.313 回答