Search code examples
algorithmgraph-algorithmpath-findinga-star

Unexplored nodes with A* JPS (Jump Point Search)

I'm working on an implementation of A* JPS (Jump Search Point), and although I understood the basics of it, it seems that I'm still missing a point.

Here is an attempt (see attached image) trying to find a path between a start node (marked S) and a goal node (marked G). Cells with a black checkerboard are the explored nodes while white ones with an arrow are the Jump points (with associated direction). All cells have a travel cost of 1, except blue ones which are obstacles.

However, as you can see, some areas aren't explored, and thus it fails finding goal node altough path exists. It seems that it's caused because it doesn't explore diagonally on some jump points, but from what I understood, we should only consider current direction (i.e. follow arrows on the picture).

So my question is, what's wrong in this attempt ? Have I missed Jump points or misunderstood the way it works ?

Attached image : A* JPS attempt (can't embed image yet :P)

Thanks for your answers.

Linear (both vertical and horizontal, but not diagonals) forced neighbors were missing. C.f. figure 2 of BlueRaja's post

Solution

  • You seem to be missing the forced neighbors step described in the paper. The unexplored nodes adjacent to arrows in your picture should be enqueued as forced neighbors.

    See figures 2 and 3 here.

    Forced neighbors