0

シナリオはターンベースの状況で、プレイヤーはソース ロケーション A からロケーション B に向かって移動する必要がありますが、最大量のユニットしか移動できません。

たとえば、B は A から 24 ユニット離れており (BFS を使用して計算)、スコアは 12 でした。12 移動ユニットしか離れていない B への最適なパスを見つけるにはどうすればよいでしょうか?

ノート：

  • 斜め移動不可
  • 大きな障害物がある

編集:これは 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 つだけ知りたい場合は、返されたパスを選択できます。パスには開始点が含まれているため、最適なステップはパスの長さ - 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 に答える