java - 如何正确填充我的自定义数据结构以用于 A* 算法？ (警告 : LONG)

Question

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

我正在开发一款游戏(早期版本可在我的 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 目前表示为图像图标的 2D 数组。 (现在)

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

1. 空 - 代表楼层，即 map 的正常可导航部分。
2. Wall - 代表一堵墙，玩家在接触时会停止。
3. Start - 表示玩家将在 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;
}

上述代码的问题:

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

提高效率的可能性？我只定义墙、球门和起始地 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;
}