4

我在算法中被困了 4 天。我正在开发麻将 Safari 类型的游戏（http://www.pogo.com/games/mahjongsafari），我想在两个瓷砖之间开发路径，并且瓷砖数量最少。

我已经在曼哈顿 Hueristic 中应用了 A* 算法，但它会生成有很多转弯的最短路径。不需要最短路径，我只需要最小转弯的路径（最好是2）。下面是来自 Mahjong Safari 游戏的图像，它在 2 个磁贴之间生成路径。您会注意到从 A 到 B 的路径和从 B 到 A 的路径是不同的。

在此处输入图像描述

请以任何代码或任何算法名称或任何您认为可行的逻辑帮助我。

编辑：我申请的解决方案：

我首先使用真正的 A* 算法来寻找最短路径，并使用曼哈顿距离作为启发式目标估计。为了使路径更直，并选择转弯次数最少的路径，我在每次迭代中使用了以下策略：

Tile first = currentNode.parent;
Tile curr  = currentNode;
Tile last  = successorOfCurrentNode;
if (first != null)
{
    if ((first.X == curr.X && first.Y != curr.Y) && (curr.Y == last.Y && curr.X != last.X))
    {
        // We got turn
    currentNode.Cost += 10;
    currentNode.calcuateTotalCost();

        successorOfCurrentNode.Cost += 5;
    successorOfCurrentNode.calcuateTotalCost();
    }
    else if ((first.X != curr.X && first.Y == curr.Y) && (curr.X == last.X && curr.Y != last.Y))
    {
        // We got turn
    currentNode.Cost += 10;
    currentNode.calcuateTotalCost();

        successorOfCurrentNode.Cost += 5;
    successorOfCurrentNode.calcuateTotalCost();
    }

}

4

3 回答 3

0

您可以使用Dijkstra 的最短路径算法，但在每个节点中，您不仅应该存储最短路径，还应该存储该路径的方向，这样您就知道是否需要增加计数。

再想一想，我想您需要在每个节点中存储所有最短路径及其方向，以便选择最佳路径。

于 2013-03-12T12:33:13.277 回答
0

您的问题比使用启发式方法更简单，因为您不需要期望，但是如果您的搜索不是“完整”的，它可以提高找到最优值的速度......而是您只想要最小转弯的路径，因此，您可以使用贪婪搜索，其中：

h(A) > h(B) ~ turns(A) < turns(B)

h* = MIN(turns(x))

h(x): heuristic of path X

turns(x): number of turns in path X

h*: highest possible heuristic, path with minimum number of turns

下面是一个简单的 Java 代码，用于说明：

class TileGame
{
    // example of a game board
    int [][] matrix = new int [10][10];

    // return possible next-state
    public ArrayList<Path> next (Path p)
    {
        // based on your rules, you decide valid transitions
        ArrayList<Path> n = new ArrayList<Path>();
        ArrayList<Point> t = new ArrayList<Point>();

        // add up, down, right, and left
        t.add(new Point(p.current.x+1, p.current.y));
        t.add(new Point(p.current.x-1, p.current.y));
        t.add(new Point(p.current.x, p.current.y+1));
        t.add(new Point(p.current.x, p.current.y-1));

        // don't allow going back to previous tile, cause infinite loops
        t.remove(p.previous);

        for (Point i : t)
        {
            if (i.x == p.current.x == p.previous.x || i.y == p.current.y == p.previous.y)
                n.add(new Path(i, p.current, p.turns));
            else
                n.add(new Path(i, p.current, p.turns+1));
        }

        return n;
    }

    // ..

}

private class Path
{
    public Point current, previous;
    public int turns;

    public Path(Point curr, Point prev, int tur)
    {
        current = curr;
        previous = prev;
        turns = tur;
    }
}
于 2013-03-13T08:20:17.903 回答
0

我为此申请的解决方案：

我首先使用真正的 A* 算法来寻找最短路径，并使用曼哈顿距离作为启发式目标估计。为了使路径更直，并选择转弯次数最少的路径，我在每次迭代中使用了以下策略：

enter code here

Tile first = currentNode.parent;
Tile curr  = currentNode;
Tile last  = successorOfCurrentNode;
if (first != null)
{
    if ((first.X == curr.X && first.Y != curr.Y) && (curr.Y == last.Y && curr.X != last.X))
    {
        // We got turn
        currentNode.Cost += 10;
        currentNode.calcuateTotalCost();

        successorOfCurrentNode.Cost += 5;
        successorOfCurrentNode.calcuateTotalCost();
    }
    else if ((first.X != curr.X && first.Y == curr.Y) && (curr.X == last.X && curr.Y != last.Y))
    {
        // We got turn
        currentNode.Cost += 10;
        currentNode.calcuateTotalCost();

        successorOfCurrentNode.Cost += 5;
        successorOfCurrentNode.calcuateTotalCost();
    }

}
于 2013-03-14T10:04:12.330 回答