跳转点搜索严格比A *好吗？

Question

根据许多相关信息，当满足所需条件（均匀成本网格等）时，跳转点搜索似乎严格优于A *

但是经过一些实际测试后，我发现跳转点搜索所花的搜索时间几乎与A *（甚至更糟...）相同，我对此不太确定...（实现问题？随机网格？）

搜索实现来自here，下面列出了测试代码：

int profileCount = 256;
long elapsedJumpPoint = 0;
long elapsedAStar = 0;

for (int i = 0; i < profileCount; ++i)
{
    // random set obstacles here
    RandomizeGrid(searchGrid);

    {
        searchGrid.Reset();

        var stopWatch = Stopwatch.StartNew();
        jumpParam.DiagonalMovement = (DiagonalMovement)cbbJumpType.SelectedIndex;
        jumpParam.CurIterationType = cbUseRecursive.Checked ? IterationType.RECURSIVE : IterationType.LOOP;
        jumpParam.Reset(startPos, endPos);
        var path = JumpPointFinder.FindPath(jumpParam);
        elapsedJumpPoint += stopWatch.ElapsedMilliseconds;
    }

    {
        searchGrid.Reset();

        var stopWatch = Stopwatch.StartNew();
        starParam.DiagonalMovement = (DiagonalMovement)cbbJumpType.SelectedIndex;
        starParam.SetHeuristic(HeuristicMode.EUCLIDEAN);
        starParam.Reset(startPos, endPos);
        var path = AStarFinder.FindPath(starParam);
        elapsedAStar += stopWatch.ElapsedMilliseconds;
    }
}

MessageBox.Show(string.Format("JP time : {0}ms\nA* time : {1}ms", elapsedJumpPoint / (float)profileCount, elapsedAStar / (float)profileCount));

RandomizeGrid代码在这里：

void RandomizeGrid(BaseGrid searchGrid, float randomPercent = 0.2f)
{
    if (searchGrid != null)
    {
        var width = searchGrid.width;
        var height = searchGrid.height;

        for (int i = 0; i < width; ++i)
        {
            for (int j = 0; j < height; ++j)
            {
                searchGrid.SetWalkableAt(new GridPos(i, j), true);
            }
        }

        var random = new Random();
        for (int i = 0; i < width * height * randomPercent; ++i)
        {
            var randWidth = random.Next(0, width);
            var randHeight = random.Next(0, height);
            searchGrid.SetWalkableAt(new GridPos(randWidth, randHeight), false);
        }
    }
}

一些测试结果也在下面列出：

| randomPercent | JP | A * |

| 0.05 | 〜8.7ms | 〜8.2ms |

| 0.1 | 〜11ms | 〜14.3ms |

| 0.2 | 〜15ms | 〜13.7ms |

| 0.5 | 〜20.5ms | 〜22ms |

Answer 1

跳转点搜索大大降低了A *的优先级队列的大小，但是查找每个单独的跳转点本身所花费的时间却更多。但是，它节省了很多时间，因为它不需要存储和维护可以从A *生成的大优先级队列，在该队列中，将其排序的推式操作可能会很昂贵。较小的队列大小也将有助于缓存行。但是，即使跳点搜索没有被添加到开放列表/优先级队列中，它们最终也可以比A *扩展更多的节点。

要回答关于在运行时方面是否严格更好的问题，它实际上取决于算法的实现以及给定的映射。由于打开列表的大小要小得多，因此内存使用情况通常会更好。如果网格像迷宫一样或有很多障碍物，速度通常会降低，因为它最终会增加很多跳转点，而这可能是昂贵的。

我用A *（https://github.com/YashTrikannad/mpl/blob/master/include/mpl/jps.h）标出了我的跳转点搜索实现的基准，并且在1000x1000 2d网格上测试了4-5个大尺寸障碍物（对于1000次运行），跳转点搜索的平均运行速度大约快10倍。迷宫）。