如何修改递归算法以找到最短路径？

Question

https://vimeo.com/70999946

我实现了递归路径查找算法.该递归算法基于连接在一起的预先设定的节点而工作.每个节点有四个包含更多方向的指针:Top,Button,Left和Right.递归算法简单地遍历每个节点并逐个寻找这四个方向中的每一个以到达其最终目的地; 举例说明,考虑以下7个节点:A,B,C,D,E,F,G,H.

    A (Button->D, Right->B)
    B (Right->C, Left->B)
    C (Left->B)
    D (Button->G, Right->E, Top->A)
    E (Right->F, Left->D)
    F (Left->E)
    G (Right->H, Top->D)
    H (Left->G)

进入整体视图时,这些节点将显示下图.

A—B—C
|
D—E—F
|
G—H

在此示例中,假设walker已启动节点为节点A,并且希望将节点H作为其最终目标.节点A按顺序查看自己的Right,Button,Left和Top; 它的右边指向节点B,因此他选择去节点B; 相同模式的节点B选择向右移动,节点C.当步行者到达节点C时; 当它的右边,顶部和按钮被阻塞时,节点C恢复到节点B.同样,节点B恢复节点A.步行器再次返回起始点.然后节点A根据订单转到其按钮节点; 这意味着它进入节点D.节点D进入其右侧节点E,然后进入节点F.节点F被阻止; 它返回到节点E和节点D.然后,节点D根据步行器顺序选择其按钮,节点G. 从那里节点G进入节点H.最后,步行者到达其最终目的地.

Pseudocode: Recursive Path Finding Algorithm
ArrayList findPath(GameObject currentPoint , GameObject targetPoint , ArrayList InputArrayList)
{
1-Duplicate InputArrayList as tempArrayList

2-If the currentPoint equals to target Point return inputArrayList
//*** End Condition found target

3-If the Right side of the currentPoint is empty goto step 4
3.1- Add currentPoint to tempArrayList
//*** Call Right
3.2- tempArrayList = findPath(currentpoint.Right, targetPoint, tempArrayList);
3.3- If tempArrayList is not null return tempArrayList
4-If the Button side of the currentPoint is empty goto step 5
4.1- Add currentPoint to tempArrayList
//*** Call Button
4.2- tempArrayList = findPath(currentpoint.Button, targetPoint, tempArrayList);
4.3- If tempArrayList is not null return tempArrayList
5-If the Left side of the currentPoint is empty goto step 6
5.1- Add currentPoint to tempArrayList
//*** Call Left
5.2- tempArrayList = findPath(currentpoint.Left, targetPoint, tempArrayList);
5.3- If tempArrayList is not null return tempArrayList
6-If the Top side of the currentPoint is empty goto step 7
6.1- Add currentPoint to tempArrayList
//*** Call Top
6.2- tempArrayList = findPath(currentpoint.Top, targetPoint, tempArrayList);
6.3- If tempArrayList is not null return tempArrayList
7-Return null;
//*** End Condition does not found target
}

注意:实际代码在C#中,您可以从此链接下载.

案例研究中问题的出现:正如您对此代码的理解; 它有一个弱点,以说明它; 考虑以下节点的整体视图,假设起始节点是节点A,最终目的地是节点H.

A—B—C
|
D—E—F—I
|   | |
G—H—J—K

虽然最佳路径解是(A,D,G,H),但解释的递归路径寻找算法找到(A,D,E,F,I,K,J,H)作为其解; 这真的看起来机器人是一个愚蠢的机器人:D!

图1:递归路径查找算法

图2:具有学习能力的递归路径查找算法

我通过添加节点的学习能力来解决问题.您可以从此链接中看到问题的详细信息.但是,我想知道是否有人可以修改递归算法以找到最短路径.

谢谢,

Answer 1

当您想做的是广度优先搜索时，您正在进行深度优先搜索。后者将需要队列而不是递归。wiki 页面很好地解释了如何实现它，所以我在这里不再重复。

从那里开始，实施A*就不再需要太多工作，这应该会加快您的结果。这将需要一个优先级队列而不是一个队列；C# 的基础库中没有优先级队列，但幸运的是，我是专门用于寻路的优化 C# 优先级队列实现的作者。

另外，既然您提到了 Unity，我将指出有许多专门为 Unity 构建的寻路库。这可能是最安全的路线，因为视频游戏中的高效寻路并非易事。