1

我正在制作一个基于回合的六角网格游戏。玩家选择单位并在六角网格中移动它们。网格中的每个图块都属于特定的地形类型（例如沙漠、丘陵、山脉等），并且每种单位类型在地形上移动时具有不同的能力（例如，有些可以轻松越过山脉，有些比较困难，有些一点也不）。

每个单位都有一个移动值，每个图块根据其地形类型和单位类型进行一定的移动。例如，在沙漠上移动需要花费 1 辆坦克，在沼泽上需要花费 4 辆，并且无法在所有山脉上移动。飞行单位以 1 为代价移动所有东西。

我遇到的问题是，当一个单位被选中时，我想突出显示它周围的一个区域，显示它可以移动的位置，这意味着计算出通过周围六角形的所有可能路径，每条路径将采取多少移动并点亮基于该信息的瓷砖。

我用递归函数得到了这个，发现计算时间太长了，我把函数移动到一个线程中，这样它就不会阻塞游戏，但线程仍然需要大约 2 秒来计算一个可移动区域单位移动为 8。它的递归超过一百万次，这显然是有问题的。

我想知道是否有人对如何优化这个问题有聪明的想法。

这是我目前正在使用的递归函数（它的 C# 顺便说一句）：

private void CalcMoveGridRecursive(int nCenterIndex, int nMoveRemaining)
{
    //List of the 6 tiles adjacent to the center tile
    int[] anAdjacentTiles = m_ThreadData.m_aHexData[nCenterIndex].m_anAdjacentTiles;

    foreach(int tileIndex in anAdjacentTiles)
    {
        //make sure this adjacent tile exists
        if(tileIndex == -1)
            continue;

        //How much would it cost the unit to move onto this adjacent tile
        int nMoveCost = m_ThreadData.m_anTerrainMoveCost[(int)m_ThreadData.m_aHexData[tileIndex].m_eTileType];

        if(nMoveCost != -1 && nMoveCost <= nMoveRemaining)
        {
            //Make sure the adjacent tile isnt already in our list.
            if(!m_ThreadData.m_lPassableTiles.Contains(tileIndex))
                m_ThreadData.m_lPassableTiles.Add(tileIndex);

            //Now check the 6 tiles surrounding the adjacent tile we just checked (it becomes the new center).
            CalcMoveGridRecursive(tileIndex, nMoveRemaining - nMoveCost);
        }
    }
}

在递归结束时，m_lPassableTiles 包含该单元可能到达的所有图块的索引列表，并且它们会发光。

这一切都有效，只是时间太长了。有谁知道更好的方法？

4

2 回答 2

0

如您所知，使用递归函数，您希望使问题尽可能简单。看起来它仍然试图一次咬掉太多。几个想法：

  1. 尝试使用HashSet结构来存储m_lPassableTiles？您可以通过这种方式避免这种Contains情况，这通常是一项昂贵的操作。

  2. 我还没有在脑海中彻底测试过这个逻辑，但是你能在foreach循环之前设置一个基本案例吗？即，那个nMoveRemaining == 0？

  3. 在不知道您的程序是如何内部设计的情况下，我希望m_anAdjacentTiles无论如何只包含现有的图块，因此您可以消除该检查（tileIndex == -1）。不是一个巨大的性能提升，但使您的代码更简单。

顺便说一句，我认为这样做的游戏，如文明 V，只会在用户建议将单位移动到某个位置时计算移动成本。换句话说，你选择了一块瓷砖，它会显示它需要走多少步。这是一个更有效的操作。

当然，当你移动一个单位时，会显示周围的土地——但我认为它只会显示单位可以在一个“回合”内移动的土地，然后随着它的移动显示更多的土地。如果您选择将几个转弯移动到未知区域，您最好仔细观察或一次转一圈。:)

（之后...）

...等等，一百万次递归？是的，我想这是正确的数学：6^8（8 是可用的动作）——但是你的网格真的那么大吗？1000x1000？该单位实际上可以穿越多少格？假设不同的地形类型，在任何给定方向上平均可能有 4 或 5 个？

如果我错了，请纠正我（因为我不知道你的底层设计），但我认为存在一些重叠......主要重叠。它正在检查已检查的相邻瓷砖的相邻瓷砖。我认为唯一能让你免于无限递归的是检查剩余的动作。

当一个图块被添加到 时m_lPassableTiles，将它从接收到您的函数的任何相邻图块列表中删除。你在你的行中做类似的事情Contains......如果你附加该if语句以包括你的递归调用怎么办？我想，这应该可以将您的递归调用从一百万以上减少到……最多数千。

于 2012-06-25T04:00:25.317 回答
0

感谢大家的意见和建议。我通过用Dijkstra 算法替换递归函数解决了这个问题，它工作得很好。

于 2012-06-26T08:07:13.767 回答