首页 文章

给定n耐力计算图表上的所有终点？

提问于
浏览 次
0

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

问题是，现在我试图通过递归地沿着图表导航并手动检查每个有效的移动来强制解决方案 .

Pseudocode:

// 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 的增加，这种方法开始变得超级冗余 . 这是因为玩家可以一遍又一遍地圈地移动，以指数方式增加潜在终点的数量 .

我的问题是， what can be done to decrease redundancy in the above function?

recursion graph maze

1 回答

  • 1

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

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

    在图算法方面

    这类似于图形上的广度优先搜索，其顶点是状态，并且其边缘将状态连接到其后继状态 . 但是，在这里我们不会忽略一个状态的新（更长）路径，因为某些位置可能只能通过循环返回（完全 $stamina 步骤！） . 还可以包括该状态下的剩余耐力（并且定义没有边缘离开0左移的状态）;然后你会进行正常的图搜索并收集所有的叶子 .

    在任何一种情况下，这些都可能是implicit graphs，但算法更直接实现，而不是图形 .

    回复于

相关问题