在Java中寻找二维整数数组中的最短路径

Question

我正在制作一个贪吃蛇游戏，蛇需要穿过一个二维整数数组作为地形。2D数组中存储的值表示穿越所需的时间（以秒为单位）。

例如，

int[][] MAP = { 
    { 1, 1, 1, 2, 2 },
    { 1, 2, 2, 2, 2 },
    { 3, 2, 2, 3, 1 },
    { 1, 1, 3, 2, 1 },
    { 1, 1, 3, 2, 1 }
 };

从 map[0][0] 到 map[0][4] 花费了 1 + 1 + 2 + 2 秒。我该如何编写一个算法，以找到蛇从位置 map[startX][startY] 到 map[endX][endY] 的最短路径？这不是一项作业任务，我只是为了好玩而制作游戏，并希望学习如何做到这一点。

- Sam Liokumovich

---

使用最佳路径剪枝的暴力算法实现递归似乎很容易。你尝试过什么，问题出在哪里？ - Durandal

你应该研究一下A*寻路算法。 - Jacob G.

我研究了A*算法，但是我找不到任何使用不同值作为数组位置的解决方案。大多数解决方案只有1和0。 - Sam Liokumovich

这显然更多是一个约定问题；如果您在节点上有权重而不是边缘上，您可以假设节点的所有入边都具有节点的权重。 - Codor

一个好的A*寻路视频：这里 - Liam Larsen

Answer 1

这是一个在讨论“动态规划”时比较常见的问题，甚至类似于旧帖子。

不过，我还没有找到一个同时打印出最短路径的解决方案，所以：

public class FastestPathCalculator {

    private final int[][] map;

    public FastestPathCalculator(int[][] map) {
        this.map=map;
    }

    public static void main(String[] args) {
        int[][] map = new int[][]{
                {1, 1, 1, 4, 2},
                {1, 2, 5, 2, 2},
                {3, 2, 2, 3, 1},
                {1, 1, 3, 2, 1},
                {3, 1, 3, 2, 1}
        };

        FastestPathCalculator c = new FastestPathCalculator(map);
        boolean[] result = c.computeFastestPath(map);
        c.printPath(result);
    }

这里，布尔数组表示从（0,0）到（4,4）所采取的步骤。TRUE的值表示向右走，FALSE表示向下走。 在这个例子中，数组有8个单元。

    public boolean[] computeFastestPath(int[][] map) {
        int pathLength = map.length + map[0].length - 2;
        boolean[] result = new boolean[pathLength];

        int[][] mapOfMinimalSums = buildMapOfMinimalSums();

        int x = map.length-1;
        int y = map[0].length-1;

        for (int i = pathLength - 1 ; i >= 0; i--) {
            if (x == 0)
                result[i] = true;
            else if (y == 0)
                result[i] = false;
            else if (mapOfMinimalSums[x][y] == map[x][y] + mapOfMinimalSums[x][y-1]) {
                result[i] = true;
                y--;
            }
            else {
                result[i] = false;
                x--;
            }
        }

        return result;
    }

    public void printPath(boolean[] result) {
        String[][] newPath = new String[map.length][map[0].length];
        int x = 0;
        int y = 0;

        newPath[x][y] = String.valueOf(map[x][y]);

        for (int i = 0 ; i < result.length; i++) {
            if (result[i]) {
                y++;
            } else {
                x++;
            }
            newPath[x][y] = String.valueOf(map[x][y]);
        }

        for (int i = 0 ; i < map.length; i++) {
            for (int j = 0 ; j < map[0].length; j++) {
                if (newPath[i][j] == null) {
                    System.out.print(" , ");
                } else {
                    System.out.print(newPath[i][j] + ", ");
                }
            }
            System.out.println();
        }
        System.out.println();
    }

    private int[][] buildMapOfMinimalSums() {
        int[][] mapOfSums = new int[map.length][map[0].length];
        for (int i = 0 ; i < map.length; i++) {
            for (int j = 0 ; j < map[0].length; j++) {
                if (i == 0 && j == 0)
                    mapOfSums[i][j] = map[i][j];
                else if (i == 0) {
                    mapOfSums[i][j] = mapOfSums[i][j - 1] + map[i][j];
                }
                else if (j == 0)
                    mapOfSums[i][j] = mapOfSums[i-1][j] + map[i][j];
                else
                    mapOfSums[i][j] = Math.min(mapOfSums[i-1][j], mapOfSums[i][j-1]) + map[i][j];
            }
        }
        return mapOfSums;
    }
}

- Ossin Java guy