0

该场景是基于回合的情况，玩家必须从源位置 A 向位置 B 移动，但只能移动最大数量的单位。

例如，B 与 A 相距 24 个单位（使用 BFS 计算），我的得分为 12。如何找到距离 B 仅 12 个运动单位的最佳路径？

笔记：

  • 不能对角移动
  • 有很大的障碍

编辑：这适用于类似于 Clue / Cluedo 的游戏，但只有文本，因此玩家将选择一个“朝向”移动的方向。

这是我尝试过的：

示例网格：（◘ 是障碍物，○ 不是）

○○○○○○○○○○
○○○○○○○○◘◘
○○○◘◘◘○○◘◘
○○○◘◘◘○○B◘
○A○◘◘◘○○◘◘

算法：

if paces == 0, return
try moving col closer to dest.col:
    if col == dest.col, move row closer to dest.row
    else if adjacent is blocked, move row away from start

这在纸上可以正常工作，除非我自己跑到角落里：

○A→◘◘○○◘◘◘
○○↓◘◘○○B◘◘
○○↓◘◘○○◘◘◘
○○↓◘◘○○↑◘◘
○○↓→→→→→◘◘

解决方案：

public ArrayList<Location> shortestPath(final Location start, final Location dest) {
    HashSet<Location> visits = new HashSet<>();
    HashMap<Location, Location> links = new HashMap<>();

    PriorityQueue<Location> queue = new PriorityQueue<>(Board.GRID_COLS * Board.GRID_ROWS,
            new Comparator<Location>() {

                @Override
                public int compare(Location a, Location b) {
                    return Integer.compare(getHeuristic(a, dest), getHeuristic(b, dest));
                }
            });

    queue.add(start);

    while (!queue.isEmpty()) {
        Location current = queue.remove();
        if (current.equals(dest)) {
            ArrayList<Location> path = reconstruct(current, new LinkedList<Location>(), links);
            path.add(dest);
            return path;
        }

        visits.add(current);
        for (Location neighbour : getNeighbours(current)) {
            if (!visits.contains(neighbour)) {
                queue.add(neighbour);
                visits.add(neighbour);
                links.put(neighbour, current);
            }
        }

    }
    return null; // failed
}

// Manhattan distance
private int getHeuristic(Location src, Location dest) {
    return Math.abs(dest.row - src.row) + Math.abs(dest.col - src.col);
}

private ArrayList<Location> reconstruct(Location current, LinkedList<Location> list, HashMap<Location, Location> links) {
    if (links.containsKey(current)) {
        list.addFirst(links.get(current));
        return reconstruct(links.get(current), list, links);
    } else {
        return new ArrayList<>(list);
    }
}

private ArrayList<Location> getNeighbours(Location current) {
    ArrayList<Location> neighbours = new ArrayList<>();

    if (current.row < GRID_ROWS - 1) {
        Location n = LOCATIONS[current.row + 1][current.col];
        if (isAccessible(n, current)) neighbours.add(n);
    }
    if (current.row > 0) {
        Location n = LOCATIONS[current.row - 1][current.col];
        if (isAccessible(n, current)) neighbours.add(n);
    }
    if (current.col < GRID_COLS - 1) {
        Location n = LOCATIONS[current.row][current.col + 1];
        if (isAccessible(n, current)) neighbours.add(n);
    }
    if (current.col > 0) {
        Location n = LOCATIONS[current.row][current.col - 1];
        if (isAccessible(n, current)) neighbours.add(n);

    }
    return neighbours;
}
4

2 回答 2

2

听起来对A*来说是一份完美的工作。

在您的图表上，它基本上与广度优先搜索（在算法上）相同，但使用优先级队列（按 排序f(x)）而不是队列。

于 2012-08-07T03:18:52.403 回答
1

一些有用的注释，游戏板的左上角应该是坐标(0, 0)。如果您有兴趣只知道一条路径，您可以选择任何返回的路径。最佳步长是路径的长度 - 1，因为路径包括起点。希望它会帮助你。

using System;
using System.Collections.Generic;
using System.Drawing;

namespace Game
{
    class Program
    {
        /// <summary>
        /// Find a matrix with all possible optimum paths from point A to point B in the game board
        /// </summary>
        /// <param name="board">Game board</param>
        /// <param name="moves">Allowed moves</param>
        /// <param name="matrix">Resulting matrix</param>
        /// <param name="A">Point A</param>
        /// <param name="B">Point B</param>
        private static void FindMatrix(List<List<char>> board, List<Point> moves, out List<List<int>> matrix, out Point A, out Point B)
        {
            matrix = new List<List<int>>();
            A = new Point(-1, -1);
            B = new Point(-1, -1);
            //Init values of the matrix
            for (int row = 0; row < board.Count; row++)
            {
                matrix.Add(new List<int>());
                for (int col = 0; col < board[row].Count; col++)
                {
                    matrix[matrix.Count - 1].Add(board[row][col] == '◘' ? -1 : 0);
                    switch (board[row][col])
                    {
                        case 'A':
                            {
                                A.X = col;
                                A.Y = row;
                                matrix[row][col] = -1;
                                break;
                            }
                        case 'B':
                            {
                                B.X = col;
                                B.Y = row;
                                break;
                            }
                    }
                }
            }
            if ((A.X >= 0) && (A.Y >= 0) && (B.X >= 0) && (B.Y >= 0)) //To check if points A and B exist in the board
            {
                var pairs = new List<Point>[2] { new List<Point>(), new List<Point>() };
                int index = 0;
                int level = 0;
                pairs[index].Add(A);
                while ((pairs[index].Count > 0) && (pairs[index][pairs[index].Count - 1] != B))
                {
                    pairs[Math.Abs(1 - index)].Clear();
                    level++;
                    foreach (var pair in pairs[index])
                        foreach (var move in moves) //Test all possible moves
                            if ((pair.Y + move.Y >= 0) && (pair.Y + move.Y < board.Count) && (pair.X + move.X >= 0) && (pair.X + move.X < board[pair.Y + move.Y].Count) && (matrix[pair.Y + move.Y][pair.X + move.X] == 0)) //Inside the board? Not visited before?
                            {
                                pairs[Math.Abs(1 - index)].Add(new Point(pair.X + move.X, pair.Y + move.Y));
                                matrix[pair.Y + move.Y][pair.X + move.X] = level;
                            }
                    index = Math.Abs(1 - index);
                }
                matrix[A.Y][A.X] = 0;
            }
        }

        /// <summary>
        /// Finds all possible optimum paths from point A to point B in the game board matix
        /// </summary>
        /// <param name="matrix">Game board matrix</param>
        /// <param name="moves">Allowed moves</param>
        /// <param name="A">Point A</param>
        /// <param name="B">Point B</param>
        /// <param name="result">Resulting optimum paths</param>
        /// <param name="list">Temporary single optimum path</param>
        private static void WalkMatrix(List<List<int>> matrix, List<Point> moves, Point A, Point B, ref List<List<Point>> result, ref List<Point> list)
        {
            if ((list.Count > 0) && (list[list.Count - 1] == B)) //Stop condition
            {
                result.Add(new List<Point>(list));
            }
            else
            {
                foreach (var move in moves)
                    if ((A.Y + move.Y >= 0) && (A.Y + move.Y < matrix.Count) && (A.X + move.X >= 0) && (A.X + move.X < matrix[A.Y + move.Y].Count) && (matrix[A.Y + move.Y][A.X + move.X] == matrix[A.Y][A.X] + 1)) //Inside the board? Next step?
                    {
                        list.Add(new Point(A.X + move.X, A.Y + move.Y)); //Store temporary cell
                        WalkMatrix(matrix, moves, list[list.Count - 1], B, ref result, ref list);
                        list.RemoveAt(list.Count - 1); //Clean temporary cell
                    }
            }
        }

        /// <summary>
        /// Finds all possible optimum paths from point A to point B in the game board
        /// </summary>
        /// <param name="board">Game board</param>
        /// <returns>All possible optimum paths</returns>
        public static List<List<Point>> FindPaths(List<List<char>> board)
        {
            var result = new List<List<Point>>();
            var moves = new List<Point> { new Point(1, 0), new Point(0, 1), new Point(-1, 0), new Point(0, -1) }; //Right, Down, Left, Up (clockwise)
            List<List<int>> matrix; //Matrix temporary representation of the game to store all possible optimum paths
            Point A;
            Point B;
            FindMatrix(board, moves, out matrix, out A, out B);
            if ((A.X >= 0) && (A.Y >= 0) && (B.X >= 0) && (B.Y >= 0)) //To check if points A and B exist in the board
            {
                List<Point> list = new List<Point>();
                list.Add(A);
                WalkMatrix(matrix, moves, A, B, ref result, ref list);
            }
            return result;
        }

        static void Main(string[] args)
        {
            List<List<char>> board = new List<List<char>> //An example of game board
            {
                new List<char>("○○○○○○○○○○"),
                new List<char>("○○○○○○○○◘◘"),
                new List<char>("○○○◘◘◘○○◘◘"),
                new List<char>("○○○◘◘◘○○B◘"),
                new List<char>("○A○◘◘◘○○◘◘")
            };
            List<List<Point>> paths = FindPaths(board);
        }
    }
}
于 2012-08-07T05:58:05.317 回答