如何正确填充我的自定义数据结构以用于 A* 算法？（警告：长）

Question

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

我正在开发一款游戏（github) For those curious about the map making program specifically, here is a link to that directory on my github 上 viewing/playing 的早期版本可用。

如果你只是想看看游戏功能如何更好地掌握，这里有一个video demo。

游戏本身使用 LUA 加载地图，我制作了一个简单的地图制作工具，使用 Java 中的 Swing library 生成 Lua。

基本前提：

从指定的起始位置导航到地图的目标。
一旦玩家开始移动，您就不能停下来或改变方向，直到撞到墙上。也不能沿对角线移动。
玩家可以制作自己的地图，挑战好友

我想限制玩家只制作有效（可获胜）地图以避免挫败感。 - 我如何最好地完成这个你的意见？

我认为 A* 算法是我使用这种方法的最佳起点。但是，我需要全神贯注于定义有效路径。

我在 Java 中的地图目前表示为图像图标的 2D 数组。（现在）

按钮可以具有 4 个属性中的 1 个：

空 - 表示楼层，IE 是地图的正常可导航部分。
Wall - 代表一堵墙，当玩家接触到时会停止。
开始 - 表示玩家将在地图上开始的位置。
目标 - 代表玩家将完成地图的板块。

这是我所拥有的（不包括算法，因为它目前与 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 对象在技术上彼此没有联系，对吗？也就是说，上下左右的图块一旦创建就不会再被引用，所以我创建了 5 个图块，而实际上我应该只创建 1 个并引用现有的图块。我如何在 Java 中解决这个问题？

提高效率的可能性？我只定义墙、球门和起始地块会不会更好，因为其他地块在技术上是空的space？

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;
}

如何正确填充我的自定义数据结构以用于 A* 算法？（警告：长）

How do I properly fill my custom data structure for use in the A* algorithm? (WARNING: LONG)

java

algorithm

a-star

如何正确填充我的自定义数据结构以用于 A* 算法？ （警告：长）

How do I properly fill my custom data structure for use in the A* algorithm? (WARNING: LONG)

java

algorithm

a-star

如何正确填充我的自定义数据结构以用于 A* 算法？（警告：长）