在多个网格上进行A*路径规划

Question

我正在尝试在一个由6个网格组成的立方体周围实现A*寻路算法，为了简单起见，我有4种方法：GetXPlus、GetXMinus、GetYPlus和GetYMinus。每种方法都会检查下一个瓷砖是否在当前网格空间内，如果不是，则切换到适当的网格。

我遇到的问题是，在尝试从与当前网格相反的网格中获取瓷砖时，返回的瓷砖位于相反的一侧。是否有一种方法或方法可以让我避免为每个原始网格和方向编写唯一的逻辑？

为了帮助表达我的问题，在这个例子中，我来自（紫色）网格并使用GetXPlus方法：

当前实现的片段如下（每个网格为64 x 64）：

public Tile GetXPlus( int currentX, int currentY )
{
    var newX = currentX + 1;
    var tile = GetTile( newX , currentY );

    if( newX > 64 ) //Get adjacent XPlus Grid 
    { 
        currentGrid = SetCurrentGrid( XPlusGridIndex );
        tile = GetTile( newX - 64, currentY );
    }

    return tile;
}

背景

这个实现源于对另一个问题的出色回答，建议在此处提供：https://gamedev.stackexchange.com/questions/53866/pathfinding-on-a-uneven-planetary-surface

- Caius Eugene

---

我在我的回答中没有考虑到的一个有趣的问题。 - House

将您的“A*”算法考虑为一系列相邻节点而不是硬编码“增加x，减少x，增加y，减少y”作为相邻节点，可以解决您的问题并使算法更加通用。如果您解决了更一般的问题，则可以在不更改算法的情况下创建更有趣的拓扑结构。 - Eric Lippert

为什么不使用图表？ - Heisenbug

一个图逻辑上只是两个列表：一个节点列表和一条边列表；一条边就是两个节点的组合，有时也带有“代价”。通常情况下，图形是这样实现的，以便于获取包含给定节点的边缘列表非常便宜。因此，要使用“A*”算法，您只需要查看当前节点并询问“我的邻居节点是什么，到那里需要多少代价？” - Eric Lippert

A* 搜索算法 是一种基于 图 而不是 网格 的算法。将其实现为一个 图 算法，然后将其应用于您的 6x6 立方体图中。这比尝试将特定的图结构嵌入算法中要直接得多。 - Timothy Shields

Answer 1

我建议你比前面的答案更进一步。创建一个代表所有平铺的立方体，并缓存每个平铺的相邻平铺。由于平铺之间的关系是固定的，这将节省很多时间。

之后，您可以使用double[,,]或int[,,,]来跟踪已处理的平铺，并基于此向您的Queue<Tile>添加相邻平铺。

如果需要，您还可以实现GetDirection(Tile tile)。该函数只需在方向字典中搜索即可。 public class Cube { private Tile[,,] tiles;

    public Cube(int size)
    {
        tiles = new Tile[size, size, 6];

        // initialize.
        for (var side = 0; side < 6; side++)
        {
            for (var x = 0; x < size; x++)
            {
                for (var y = 0; y < size; y++)
                {
                    tiles[x, y, side] = new Tile(x, y, side);
                }
            }
        }

        // set directions & neighbors
        for (var side = 0; side < 6; side++)
        {
            for (var x = 0; x < size; x++)
            {
                for (var y = 0; y < size; y++)
                {
                    // todo: implement.
                }
            }
        }
    }

    public Tile this[int x, int y, int side]
    {
        get
        {
            return tiles[x, y, side];
        }
    }
}

public class Tile
{
    private Dictionary<DirectionType, Tile> directions = new Dictionary<DirectionType, Tile>();

    private Tile[] neighbors = new Tile[4];

    public Tile(int x, int y, int side)
    {
        this.X = x;
        this.Y = y;
        this.Side = side;
    }

    public int X { get; private set; }
    public int Y { get; private set; }
    public int Side { get; private set; }

    public Tile this[DirectionType dir]
    {
        get
        {
            return directions[dir];
        }
    }



    public Tile[] Neighbors { get { return neighbors; } }
}

public enum DirectionType
{
    // delta: +1, 0
    e,
    // delta: 0, +1
    n,
    // delta: -1, 0
    w,
    // delta: 0, -1
    s,
    // delta: 0, 0
    X
}

- Corniel Nobel

---

要小心数组（与List<>或其他集合类型相反）。它们是不可变的，并且每次传递它们时都会被复制。对于您的示例，这似乎不是问题，但那些不熟悉GC在此实例中如何工作的人可能会很快遇到严重的性能问题。 - 3Dave

@DavidLively 这是一个很好的观点，你总是要记住这一点。但在这种情况下，数组正是你想要的。瓷砖的邻居是不可变的，并且只能间接访问。立方体也是如此。在这种情况下，内存使用和速度的优势是可取的。 - Corniel Nobel

Answer 2

你可以使用函数将由“X坐标”、“Y坐标”和“Tile”组成的一个3D坐标空间映射到另一个空间。

给定一个顺序：

enum TileBorder
{
    Left   = 0,
    Top    = 1,
    Right  = 2,
    Bottom = 3
}

你可以将这些转换存储在你的Tile类的数组中：

class Tile
{
    public Tile[] Neighbors { get; set; }
    public Func<int, int, int>[] XTransitions { get; set; }
    public Func<int, int, int>[] YTransitions { get; set; }

    public void GetXPlus(int x, int y, out int newX, out int newY, out Tile newTile)
    {
        x++;
        if (x <= 64)
        {
            newX = x;
            newY = y;
            newTile = this;
        }
        else
        {
            newX = XTransitions[(int)TileBorder.Right](x, y);
            newY = YTransitions[(int)TileBorder.Right](x, y);
            newTile = Neighbors[(int)TileBorder.Right];
        }
    }
    // ...
}

那么，当您设置结构时，只需要稍加注意即可。例如，假设您的坐标从1到64（包括1和64），您可以这样设置绿色瓷砖。

Tile pink   = new Tile();
Tile green  = new Tile();
Tile orange = new Tile();
Tile purple = new Tile();
Tile blue   = new Tile();

green.Neighbors = new Tile[] 
{ 
    /* left */   orange, 
    /* top */    pink,
    /* right */  blue,
    /* bottom */ purple 
};

green.XTransitions = new Func<int, int, int>[] 
{
    /* left */   (x, y) => 1, 
    /* top */    (x, y) => x,
    /* right */  (x, y) => 64,
    /* bottom */ (x, y) => x 
};

green.YTransitions = new Func<int, int, int>[] 
{
    /* left */   (x, y) => 65 - y, 
    /* top */    (x, y) => 64,
    /* right */  (x, y) => 65 - y,
    /* bottom */ (x, y) => 1
};

请注意，瓷砖过渡函数只是一个查找表，但要完全灵活，您还可以使用以下类型的函数：
Func<int, int, Tile, int> 用于 x 坐标，
Func<int, int, Tile, int> 用于 y 坐标，以及
Func<int, int, Tile, Tile> 用于瓷砖。

- Tilo