c++ - 游戏寻路算法

我在大学里有这样的经历，在那里我得到了涉及寻路的C++游戏的代码。寻路是使用wave函数进行的，并且设置要求我对寻路的工作方式进行某些更改。

分配需要寻路，以始终选择距离除空白区域之外的任何物体最远的路径。如这里所示:



到目前为止，这是我得到的结果:



在下面，我已经发布了更新功能中与寻路有关的部分，因为我很确定那是我必须进行更改的地方。

for (int y = 0, o = 0; y < LEVEL_HEIGHT; y++) {
    for (int x = 0; x < LEVEL_WIDTH; x++, o++) {
        int nCost = !bricks[o].type;
        if (nCost) {
            for (int j = 0; j < 4; j++)
            {
                int dx = s_directions[j][0], dy = s_directions[j][1];
                if ((y == 0 && dy < 0)
                    || (y == LEVEL_HEIGHT - 1 && dy > 0)
                    || (x == 0 && dx < 0)
                    || (x == LEVEL_WIDTH - 1 && dx > 0)
                    || bricks[o + dy * LEVEL_WIDTH + dx].type)
                {
                    nCost = 2;
                    break;
                }
            }
        }
        pfWayCost[o] = (float)nCost;
    }
}

如果需要进一步说明该问题，还可以使用Wave function。

我非常感谢任何有关如何进行的想法，因为我已经为此苦苦挣扎了很长时间。

最佳答案

您的问题可以简化为称为minimum-bottle-neck-spanning-tree的问题。

对于减少，请执行以下操作:

将空间中每个点/单元的成本计算为到物体的最小距离。

绘制一个图形，其中边缘对应于空间中的点，边缘的权重为上一步中计算的成本。图的顶点对应于单元格之间的边界。

对于具有4个像元的成本为10、20、3、5的一维空间:

|10|20|3|5|

该图如下所示:

 A--(w=10)--B--(w=20)--C--(w=3)--D--(w=5)--E

节点A-E对应于单元的边界。

运行例如Prim's algorithm来找到MST。您正在寻找从结果树中的入口点(在上面的示例中)到导出点(E)的直接方法。

关于c++ - 游戏寻路算法，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/34827707/