JPS+ in C++
JPS+ Demo
Jump Point Search (JPS) is a recently devised optimal pathfinding algorithm that can speed up searches on uniform cost grid maps by up to an order of magnitude over traditional A* [Harabor 12]. However, by statically analyzing a map and burning in directions to Walls and Jump Points, it is possible to dramatically speed up searches even further, up to two orders of magnitude over traditional A*. To illustrate the difference in speed on a particular 40x40 map, A* found an optimal solution in 180.05ns, JPS in 15.04ns, and JPS+ in 1.55ns. In this example, JPS+ was 116x faster than traditional A*, while remaining perfectly optimal. This increase in performance is derived from the vastly reduced number of nodes considered when pathfinding to a location.
A restriction is that JPS and JPS+ both use a state-space pruning strategy that only works for grid search spaces where the cost of traversal is uniform with regard to distance.
In one of my classes at DigiPen (CS380 -- AI Behavior and Pathfinding) each student had to implement JPS+. At the time, only approximately 50 people in the world had successfully completed this pathfinding algorithm. The project took around 6 hours to implement.
References
[Harabor 12] Harabor, D. and Grastien, A. 2012. The JPS Pathfinding System. In Proceedings of the 5th Symposium on Combinatorial Search (SoCS), Niagara Falls, Canada, available online at http://users.cecs.anu.edu.au/~dharabor/data/papers/harabor-grastien-socs12.pdf (accessed Sept 10, 2014).
The code below illustrates how one would sweep a grid space in order to burn in to each grid node the distances to Walls and Jump Points. It also shows how one would check for Forced Neighbors in order to identify Primary Jump Points.
Code Sample
// This is an enum containing all possible 8 directions present on a grid //
enum Directions
{
South,
Southeast,
East,
Northeast,
North,
Northwest,
West,
Southwest
};
// This Function Sweeps all the Cardinal Directions and Diagonal Directions // // in order to burn into the entire grid the distances of Walls and Jump Points //
// in every single direction possible. //
void SweepingFunction(int mapWidth)
{
/////////////////////////////////////////////////
// Cardinals //
////////////////////////////////////////////////
// North Direction //
for (int c = 0; c < mapWidth; ++c)
{
int count = -1;
bool jumpPointLastSeen = false;
for (int r = mapWidth - 1; r >= 0; --r)
{
if (g_terrain.IsWall(r, c))
{
count = -1;
jumpPointLastSeen = false;
g_terrain.jpsNodeGrid[r][c]->North = 0;
continue;
}
count++;
if (jumpPointLastSeen)
{
g_terrain.jpsNodeGrid[r][c]->North = count;
}
else // Wall last seen //
{
g_terrain.jpsNodeGrid[r][c]->North = -count;
}
if (g_terrain.jpsNodeGrid[r][c]->NorthJP)
{
count = 0;
jumpPointLastSeen = true;
}
}
}
// West Direction //
for (int r = 0; r < mapWidth; ++r)
{
int count = -1;
bool jumpPointLastSeen = false;
for (int c = 0; c < mapWidth; ++c)
{
if (g_terrain.IsWall(r, c))
{
count = -1;
jumpPointLastSeen = false;
g_terrain.jpsNodeGrid[r][c]->West = 0;
continue;
}
count++;
if (jumpPointLastSeen)
{
g_terrain.jpsNodeGrid[r][c]->West = count;
}
else // Wall last seen //
{
g_terrain.jpsNodeGrid[r][c]->West = -count;
}
if (g_terrain.jpsNodeGrid[r][c]->WestJP)
{
count = 0;
jumpPointLastSeen = true;
}
}
}
// South Direction //
for (int c = 0; c < mapWidth; ++c)
{
int count = -1;
bool jumpPointLastSeen = false;
for (int r = 0; r < mapWidth; ++r)
{
if (g_terrain.IsWall(r, c))
{
count = -1;
jumpPointLastSeen = false;
g_terrain.jpsNodeGrid[r][c]->South = 0;
continue;
}
count++;
if (jumpPointLastSeen)
{
g_terrain.jpsNodeGrid[r][c]->South = count;
}
else // Wall last seen //
{
g_terrain.jpsNodeGrid[r][c]->South = -count;
}
if (g_terrain.jpsNodeGrid[r][c]->SouthJP)
{
count = 0;
jumpPointLastSeen = true;
}
}
}
// East Direction //
for (int r = 0; r < mapWidth; ++r)
{
int count = -1;
bool jumpPointLastSeen = false;
for (int c = mapWidth - 1; c >= 0; --c)
{
if (g_terrain.IsWall(r, c))
{
count = -1;
jumpPointLastSeen = false;
g_terrain.jpsNodeGrid[r][c]->East = 0;
continue;
}
count++;
if (jumpPointLastSeen)
{
g_terrain.jpsNodeGrid[r][c]->East = count;
}
else // Wall last seen //
{
g_terrain.jpsNodeGrid[r][c]->East = -count;
}
if (g_terrain.jpsNodeGrid[r][c]->EastJP)
{
count = 0;
jumpPointLastSeen = true;
}
}
}
//////////////////////////////////////////////////
// Diagonals //
/////////////////////////////////////////////////
// NorthEast Direction //
for (int c = mapWidth - 1; c >= 0; --c)
{
for (int r = mapWidth - 1; r >= 0; --r)
{
if (!g_terrain.IsWall(r, c))
{
if (r == mapWidth - 1 ||
c == mapWidth - 1 ||
g_terrain.IsWall(r + 1, c) ||
g_terrain.IsWall(r, c + 1) ||
g_terrain.IsWall(r + 1, c + 1))
{
// Wall one away //
g_terrain.jpsNodeGrid[r][c]->NorthEast = 0;
}
else if (!g_terrain.IsWall(r + 1, c) &&
!g_terrain.IsWall(r, c + 1) &&
(g_terrain.jpsNodeGrid[r + 1][c + 1]->North > 0 ||
g_terrain.jpsNodeGrid[r + 1][c + 1]->East > 0))
{
// Straight jump point one away //
g_terrain.jpsNodeGrid[r][c]->NorthEast = 1;
}
else
{
// Increment from last //
int jumpDistance = g_terrain.jpsNodeGrid[r + 1][c + 1]->NorthEast;
if (jumpDistance > 0)
{
g_terrain.jpsNodeGrid[r][c]->NorthEast = 1 + jumpDistance;
}
else
{
g_terrain.jpsNodeGrid[r][c]->NorthEast = -1 + jumpDistance;
}
}
}
}
}
// NorthWest Direction //
for (int c = 0; c < mapWidth; ++c)
{
for (int r = mapWidth - 1; r >= 0; --r)
{
if (!g_terrain.IsWall(r, c))
{
if (r == mapWidth - 1 ||
c == 0 ||
g_terrain.IsWall(r + 1, c) ||
g_terrain.IsWall(r, c - 1) ||
g_terrain.IsWall(r + 1, c - 1))
{
// Wall one away //
g_terrain.jpsNodeGrid[r][c]->NorthWest = 0;
}
else if (!g_terrain.IsWall(r + 1, c) &&
!g_terrain.IsWall(r, c - 1) &&
(g_terrain.jpsNodeGrid[r + 1][c - 1]->North > 0 ||
g_terrain.jpsNodeGrid[r + 1][c - 1]->West > 0))
{
// Straight jump point one away //
g_terrain.jpsNodeGrid[r][c]->NorthWest = 1;
}
else
{
// Increment from last //
int jumpDistance = g_terrain.jpsNodeGrid[r + 1][c - 1]->NorthWest;
if (jumpDistance > 0)
{
g_terrain.jpsNodeGrid[r][c]->NorthWest = 1 + jumpDistance;
}
else
{
g_terrain.jpsNodeGrid[r][c]->NorthWest = -1 + jumpDistance;
}
}
}
}
}
// SouthWest Direction //
for (int c = 0; c < mapWidth; ++c)
{
for (int r = 0; r < mapWidth; ++r)
{
if (!g_terrain.IsWall(r, c))
{
if (r == 0 ||
c == 0 ||
g_terrain.IsWall(r - 1, c) ||
g_terrain.IsWall(r, c - 1) ||
g_terrain.IsWall(r - 1, c - 1))
{
// Wall one away //
g_terrain.jpsNodeGrid[r][c]->SouthWest = 0;
}
else if (!g_terrain.IsWall(r - 1, c) &&
!g_terrain.IsWall(r, c - 1) &&
(g_terrain.jpsNodeGrid[r - 1][c - 1]->South > 0 ||
g_terrain.jpsNodeGrid[r - 1][c - 1]->West > 0))
{
// Straight jump point one away //
g_terrain.jpsNodeGrid[r][c]->SouthWest = 1;
}
else
{
// Increment from last //
int jumpDistance = g_terrain.jpsNodeGrid[r - 1][c - 1]->SouthWest;
if (jumpDistance > 0)
{
g_terrain.jpsNodeGrid[r][c]->SouthWest = 1 + jumpDistance;
}
else
{
g_terrain.jpsNodeGrid[r][c]->SouthWest = -1 + jumpDistance;
}
}
}
}
}
// SouthEast Direction //
for (int c = mapWidth - 1; c >= 0; --c)
{
for (int r = 0; r < mapWidth; ++r)
{
if (!g_terrain.IsWall(r, c))
{
if (r == 0 ||
c == mapWidth - 1 ||
g_terrain.IsWall(r - 1, c) ||
g_terrain.IsWall(r, c + 1) ||
g_terrain.IsWall(r - 1, c + 1))
{
// Wall one away //
g_terrain.jpsNodeGrid[r][c]->SouthEast = 0;
}
else if (!g_terrain.IsWall(r - 1, c) &&
!g_terrain.IsWall(r, c + 1) &&
(g_terrain.jpsNodeGrid[r - 1][c + 1]->South > 0 ||
g_terrain.jpsNodeGrid[r - 1][c + 1]->East > 0))
{
// Straight jump point one away //
g_terrain.jpsNodeGrid[r][c]->SouthEast = 1;
}
else
{
// Increment from last //
int jumpDistance = g_terrain.jpsNodeGrid[r - 1][c + 1]->SouthEast;
if (jumpDistance > 0)
{
g_terrain.jpsNodeGrid[r][c]->SouthEast = 1 + jumpDistance;
}
else
{
g_terrain.jpsNodeGrid[r][c]->SouthEast = -1 + jumpDistance;
}
}
}
}
}
}
// This Function is a Function Helper for IdentifyPrimaryJumpPoints. It returns true // // if there is a Forced Neighbor. //
bool CheckForForcedNeighbors(int r, int c, int switchNum, int mapWidth)
{
switch (switchNum)
{
case South:
if (!g_terrain.IsWall(r + 1, c) &&
r + 1 < mapWidth &&
c - 1 >= 0 &&
g_terrain.IsWall(r + 1, c - 1) &&
!g_terrain.IsWall(r, c - 1))
{
return true;
}
if (!g_terrain.IsWall(r + 1, c) &&
r + 1 < mapWidth &&
c + 1 < mapWidth &&
g_terrain.IsWall(r + 1, c + 1) &&
!g_terrain.IsWall(r, c + 1))
{
return true;
}
break;
case East:
if (c - 1 >= 0 &&
!g_terrain.IsWall(r, c - 1) &&
r - 1 >= 0 &&
g_terrain.IsWall(r - 1, c - 1) &&
!g_terrain.IsWall(r - 1, c))
{
return true;
}
if (c - 1 >= 0 &&
!g_terrain.IsWall(r, c - 1) &&
r + 1 < mapWidth &&
g_terrain.IsWall(r + 1, c - 1) &&
!g_terrain.IsWall(r + 1, c))
{
return true;
}
break;
case North:
if (!g_terrain.IsWall(r - 1, c) &&
r - 1 >= 0 &&
c - 1 >= 0 &&
g_terrain.IsWall(r - 1, c - 1) &&
!g_terrain.IsWall(r, c - 1))
{
return true;
}
if (!g_terrain.IsWall(r - 1, c) &&
r - 1 >= 0 &&
c + 1 < mapWidth &&
g_terrain.IsWall(r - 1, c + 1) &&
!g_terrain.IsWall(r, c + 1))
{
return true;
}
break;
case West:
if (!g_terrain.IsWall(r, c + 1) &&
c + 1 < mapWidth &&
r - 1 >= 0 &&
g_terrain.IsWall(r - 1, c + 1) &&
!g_terrain.IsWall(r - 1, c))
{
return true;
}
if (!g_terrain.IsWall(r, c + 1) &&
c + 1 < mapWidth &&
r + 1 < mapWidth &&
g_terrain.IsWall(r + 1, c + 1) &&
!g_terrain.IsWall(r + 1, c))
{
return true;
}
break;
}
return false;
}
// This Function checks if a Forced Neighbor exists at each row and coloum grid //
// space. If the spot is a Forced Neighbor then that spot will be a Primary Jump //
// Point in the direction it checked. //
void IdentifyPrimaryJumpPoints(int mapWidth)
{
// Forced Neighbor Sweeping //
for (int r = 0; r < mapWidth; r++)
{
for (int c = 0; c < mapWidth; c++)
{
if (!g_terrain.IsWall(r, c))
{
// if East //
if (CheckForForcedNeighbors(r, c, East, mapWidth))
g_terrain.jpsNodeGrid[r][c]->EastJP = true;
// if West //
if (CheckForForcedNeighbors(r, c, West, mapWidth))
g_terrain.jpsNodeGrid[r][c]->WestJP = true;
// if North //
if (CheckForForcedNeighbors(r, c, North, mapWidth))
g_terrain.jpsNodeGrid[r][c]->NorthJP = true;
// if South //
if (CheckForForcedNeighbors(r, c, South, mapWidth))
g_terrain.jpsNodeGrid[r][c]->SouthJP = true;
}
}
}
}