A* with jump point search slower than regular A* in XNA?

Edit: In order to help viewers of this question become answerers, I'll note that the problem seems to be in the diagonal case of Jump. What in that method, when run recursively, could cause a slowdown? End of edit. In a XNA game I'm developing I use A* + JPS algorithm to navigate over a uniform square grid each frame. I learned about JPS here and here. However, when I run the game, the frame rate drops. The frame rate is so low that it makes the game unplayable. Removing the call to the Jump Point Search 'jump', and going with regular A* instead, fixed the problem for large enough square sizes. According to the article, JPS is supposed to be greatly more efficient than regular A*. The cause of the slowdown seems to be the two calls to Jump in the "Diagonal Case" (line 15-29 of the Jump method). Obviously, there must be something wrong/inefficient in my implementation. But what is it? Code: The Jump method is the implementation of the JPS recursive jump function. public Vector2? Jump(Vector2 current, Vector2 direction, Vector2 start, Vector2 end) { // Position of new node we are going to consider: Vector2 next = current + direction * SquareSize; // If it's blocked we can't jump here if (IsBlocked(next)) return null; // If the node is the goal return it if (next.X == end.X && next.Y == end.Y) return next; // Diagonal Case if (direction.X != 0 && direction.Y != 0) { Vector2 horizontalBehind = current - new Vector2(direction.X * SquareSize, 0); Vector2 verticalBehind = current - new Vector2(0, direction.Y * SquareSize); if (IsBlocked(horizontalBehind) || IsBlocked(verticalBehind)) { return current; } // Check in horizontal and vertical directions for forced neighbors // This is a special case for diagonal direction if (Jump(next, new Vector2(direction.X, 0), start, end) != null || Jump(next, new Vector2(0, direction.Y), start, end) != null) { return current; } } else { // Horizontal case if (direction.X != 0) { Vector2 topBehind = current - new Vector2(direction.X * SquareSize, SquareSize); Vector2 above = current - new Vector2(0, SquareSize); Vector2 bottomBehind = current + new Vector2(-direction.X * SquareSize, SquareSize); Vector2 below = current + new Vector2(0, SquareSize); if (IsBlocked(topBehind) || IsBlocked(above) || IsBlocked(bottomBehind) || IsBlocked(below)) { return current; } } else { Vector2 leftBehind = current - new Vector2(SquareSize, direction.Y * SquareSize); Vector2 left = current - new Vector2(SquareSize, 0); Vector2 rightBehind = current + new Vector2(-SquareSize, direction.Y * SquareSize); Vector2 right = current - new Vector2(SquareSize, 0); if (IsBlocked(leftBehind) || IsBlocked(left) || IsBlocked(rightBehind) || IsBlocked(right)) { return current; } } } // If forced neighbor was not found try next jump point return Jump(next, direction, start, end); } #endregion } Navigate is the method that implements A*, from the 'start' parameter to the 'end' Parameter. PriorityQueue is a generic implementation based on this article. It's Enqueue and Dequeue methods have O(log2(n)) complexity. public Vector2? Navigate(Vector2 start, Vector2 end) { PriorityQueue<float, Vector2> openSet = new PriorityQueue<float, Vector2>(); List<Vector2> closedSet = new List<Vector2>(10); Dictionary<Vector2, Vector2> cameFrom = new Dictionary<Vector2, Vector2>(10); Dictionary<Vector2, float> gScores = new Dictionary<Vector2, float>(10); gScores[start] = 0; openSet.Enqueue(H(start, end), start); while (openSet.Count != 0) { Vector2 current = openSet.Dequeue().Value; if (WorldMap.InSquare(current) == WorldMap.InSquare(end)) return ReconstructPath(cameFrom, current, start); List<Vector2> neighbours = WorldMap.GetNeighbours(current, start, end); closedSet.Add(current); foreach(Vector2 neighbour in neighbours) { if (closedSet.Contains(neighbour)) continue; float tenativeGScore = gScores[current] + Vector2.Distance(current, neighbour); if(!gScores.ContainsKey(neighbour) || gScores[neighbour] > tenativeGScore)//Discover a new node || Find a better path to a node { cameFrom[neighbour] = current; gScores[neighbour] = tenativeGScore; float fScore = tenativeGScore + H(neighbour, end);//Calculate F. openSet.Enqueue(fScore, neighbour); } } } return null; } GetNeighbours is a method that returns the neighbours of the node 'vector'. A* version: public List<Vector2> GetNeighbours(Vector2 point, Vector2 start, Vector2 end) { Vector2[] directions = new Vector2[8]; List<Vector2> neighbours = new List<Vector2>(8); directions[0] = Vector2.UnitX;//right directions[1] = -Vector2.UnitX;//left directions[2] = Vector2.UnitY;//down directions[3] = -Vector2.UnitY;//up directions[4] = Vector2.UnitX + Vector2.UnitY;//down right directions[5] = -Vector2.UnitX + Vector2.UnitY;//down left directions[6] = Vector2.UnitX - Vector2.UnitY;//up right directions[7] = -Vector2.UnitX - Vector2.UnitY;//up left foreach(Vector2 direction in directions) { Vector2 neighbour = point + direction * SquareSize; if (!IsBlocked(neighbour)) neighbours.Add(neighbour); } return neighbours; } Jump Point Search version: public List<Vector2> GetNeighbours(Vector2 point, Vector2 start, Vector2 end) { Vector2[] directions = new Vector2[8]; List<Vector2> neighbours = new List<Vector2>(8); directions[0] = Vector2.UnitX;//right directions[1] = -Vector2.UnitX;//left directions[2] = Vector2.UnitY;//down directions[3] = -Vector2.UnitY;//up directions[4] = Vector2.UnitX + Vector2.UnitY;//down right directions[5] = -Vector2.UnitX + Vector2.UnitY;//down left directions[6] = Vector2.UnitX - Vector2.UnitY;//up right directions[7] = -Vector2.UnitX - Vector2.UnitY;//up left foreach(Vector2 direction in directions) { //The only difference between this GetNeighbours and the other one //is that this one calls Jump here. Vector2? jp = Jump(point + direction * SquareSize, direction, start, end); if (jp != null) neighbours.Add((Vector2)jp); } return neighbours; } InSqaure is a method that returns the Vector2 that represents the square a Vector2 is in. It has O(1) complexity. IsBlocked is a method that checks if a Vector2 is inside the map or not, and also it is in a blocked square ("blocked" means a square that has an obstacle in it). It has O(log2(n)) complexity. Additional Information: I currently only checked this in situations where there are no obstacles between the goal and the start point. This means the JPS algorithm only expands 1 square. Meanwhile, the regular A* expands 8 to find a path from (100, 100) to (0, 0) but 2325 squares when finding the distance between (100, 100) to (-800, -580). In that last case, there is a noticable frame rate drop that makes the game almost unplayable. Frame rate is unlocked. There is no visible stutter in grids with less than about 1200 squares, the game has a slight, acceptable frame rate drop up to about 1600. If there's need for any more information I will provide it happily, Thanks in advance!