Is Jump Point Search strictly better than A*?

Question

According to many related information, it seems that Jump Point Search is strictly better than A* when meet required conditions(uniform-cost grid etc.)

But after some practical tests, I've found that Jump Point Search takes almost same search time as A*(or even worse...), I'm not so sure about this ... (implementation problem ? random grid ?)

search implementations are from here, and test codes are listed below :

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 codes here :

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);
        }
    }
}

some test results are also listed below :

| 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

Jump Point Search reduces the size of the priority queues from A* significantly but the time taken to find each individual jump point itself is much more. However, it saves a lot of time because it doesn't need to store and maintain the large priority queues that can be generated from A* where the push operation to keep it sorted can be expensive. The smaller size of queues will also help with cache lines. But Jump Point Search can end up expanding a lot more nodes than A* even though they don't get added to the open list/ priority queue.

To answer the question about whether it is strictly better in terms of run-time, it really depends on the implementation of the algorithm as well as the given map. The memory use will be generally better as the size of the open list is much smaller. The speed in general decreases if the grid is like a maze or has a lot of obstacle as it will end up adding a lot of jump points which can be expensive.

I bench-marked my implementation of jump point search against A* (https://github.com/YashTrikannad/mpl/blob/master/include/mpl/jps.h) and jump point search was running about 10 times faster on average on 1000x1000 2d grids tested for 1000 runs with 4-5 large size obstacles (not a maze).