给定 n 个耐力，计算图表上的所有端点？

Question

我正在尝试为游戏创建寻路算法。基本上，在玩家掷出一个数字后，我需要确定玩家可以在网格上结束的所有可能位置。玩家在给定步后不能直接向后移动，玩家每步只能移动一个方格。

问题是，现在我正试图通过沿图递归导航并手动检查每个有效移动来暴力破解解决方案。

伪代码：

// Recursive function for navigating one step at a time.
function navigate($stamina, $coords, $coords_previous)
{
    // If the movement stamina has not been spent.
    if ($stamina != 0)
    {
        // Note: there may be less than four neighboring
        // cells in a given location due to obstacles.
        foreach ($neighboring_cells as $coords_neighboring)
        {
            // If the coordinates of the neighbor are not the same as the
            // coordinates of the previous move (we can't move backwards)
            if ($coords_neighboring != $coords_previous)
            {
                $stamina--;

                // Recurse.
                navigate($stamina, $coords_neighboring, $coords);
            }
        }
    }
    else
    {
        // No more stamina.
        // Add $coords to our array of endpoints.
    }
}

这适用于小卷（低 $stamina 值）。然而，随着 $stamina 的增加，这种方法开始变得超级冗余。这是因为玩家可以一遍又一遍地绕圈移动，从而以指数方式增加潜在端点的数量。

我的问题是，如何减少上述函数的冗余？

Answer 1

将状态定义为网格位置和朝向的组合（即，玩家移动到达那里的方向).这很有用，因为我们可以定义给定状态的后继者：特别是那些在相邻网格位置（具有适当的面）而不是玩家刚刚来自的那些。

然后计算可在 n 步内到达的状态集。对于 n=0，这只是玩家的初始位置（如果第一步可以在任何方向，则具有特殊的 "no facing" 值）。要为 n+1 计算它，从前一组中的每个状态生成所有有效移动，丢弃任何重复项。当您到达 $stamina 步的集合时，只需丢弃饰面（以及任何重复的位置）。

图算法方面

这类似于图的广度优先搜索，该图的顶点是状态并且其边将状态连接到其后继状态。然而，在这里我们不忽略到状态的新（更长）路径，因为某些位置可能只能通过循环到达（在 exactly $stamina 步中！）。还可以包括状态中剩余的耐力（并定义没有边缘远离状态，剩余 0 步）；然后你将执行正常的图形搜索并收集所有叶子。

在任何一种情况下，这些都可能是 implicit graphs，但算法更清晰地直接实现而不是根据图表。

给定 n 个耐力，计算图表上的所有端点？

Calculate all end points on a graph given n stamina?

recursion

maze

graph

图算法方面