java - 如何正确填写自定义数据结构以供 A* 算法使用？ (警告 : LONG)

Question

如果您想要没有上下文的 TLDR: 我需要帮助弄清楚如何正确定义和填充寻路算法的 2D 数组中的数据结构。 滚动到我的代码的底部。

我正在开发一款游戏(早期版本可在我的github上查看/玩)对于那些对 map 制作程序特别好奇的人，这里有一个link to that directory on my github .

如果您只是想了解游戏的功能以便更好地掌握，这里有video demo .

游戏本身利用LUA加载 map ，我制作了一个简单的 map 制作器来使用Swing library生成Lua。在Java中。

基本前提:

1. 从指定的起始位置导航到 map 的目标。

2. 一旦玩家开始移动，您就无法停止或改变方向，直到撞到墙壁。而且你不能对角移动。

   

3. 玩家可以制作自己的 map 并挑战他们的 friend 。

我想限制玩家只制作有效(可获胜) map 以避免挫败感。 - 您认为我如何才能最好地实现这一目标？

我认为 A* 算法是此类方法的最佳起点。但是，我需要集中精力定义有效路径。

我的 Java map 当前表示为图像图标的二维数组。 (目前)

按钮可以具有 4 个属性之一:

1. 空 - 代表地板，即 map 的正常可导航部分。
2. Wall - 代表一堵墙，玩家接触时会被阻止。
3. 开始 - 代表玩家在 map 上开始的位置。
4. 目标 - 代表玩家将完成 map 的图 block 。

这是我所拥有的(未包括算法，因为它目前与 wiki 上的典型示例没有什么不同)

    class Tile {

        JLabel payload = null; // wall, empty, goal, start
        Tile up = null;
        Tile down = null;
        Tile left = null;
        Tile right = null;
    }

// Fill and return a list with the information for each tile on the map
public static ArrayList<Tile> checkMapStatus(JLabel[][] map){
    ArrayList<Tile> mapList = new ArrayList<Tile>();

    for(int i = 0; i < map.length; i++){
        for(int j = 0; j < map.length; j++){

        // create the surrounding tiles around the current tile (needs fixing)
        Tile tile = new Tile();
        Tile tileUp = new Tile();
        Tile tileDown = new Tile();
        Tile tileLeft = new Tile();
        Tile tileRight = new Tile();

        tile.payload = map[i][j];

        if(map[j + 1] != null) // prevent accessing inexistant array position
        tileUp.payload = map[i][j+1]; 

        if(j > 0) // prevent accessing inexistant array position
        tileDown.payload = map[i][j-1];

        if(i > 0) // prevent accessing inexistant array position
        tileLeft.payload = map[i-1][j];

        if(map[i + 1] != null) // prevent accessing inexistant array position
        tileRight.payload = map[i+1][j];

        tile.up = tileUp;
        tile.down = tileDown;
        tile.left = tileLeft;
        tile.right = tileRight;

        mapList.add(tile);

        }
    }
        return mapList;
}

上述代码的问题:

我正在创建在技术上没有相互连接的图 block 对象，对吧？也就是说，上下左右的图 block 一旦创建就不会再次被引用，所以我创建了 5 个图 block ，而实际上我应该只创建 1 个图 block 并引用现有的图 block 。我该如何在 Java 中解决这个问题？

提高效率的可能性？对我来说，只定义墙、目标和起始图 block 会更好吗，因为其他图 block 在技术上都是空白的？

Answer 1

我要做的就是从一个 Tile[][] temp 变量开始，以帮助对象相互引用，并在使用时将其展平。它的效率稍低，但如果这只是为了初始化，还不足以担心。

public static ArrayList<Tile> checkMapStatus(JLabel[][] map){
    ArrayList<Tile> mapList = new ArrayList<Tile>();
    Tile[][] temp = new Tile[map.length][];

    for(int i = 0; i < map.length; i++){
        temp[i] = new Tile[map[i].length];
        for(int j = 0; j < map.length; j++){

        // create the surrounding tiles around the current tile (needs fixing)
        Tile tile = new Tile();
        temp[i][j] = tile;

        tile.payload = map[i][j];
        //Just look up and to the left, populate the existing Tiles as you populate the current one
        if(i > 0 && j < temp[i-1].length){
            tile.up = temp[i-1][j];
            temp[i-1][j].down = tile;
        }
        if(j > 0){
            tile.left = temp[i][j-1];
            temp[i][j-1].right = tile;
        }


        mapList.add(tile);

        }
    }
    return mapList;
}