Internship - Week 11 - Jump point search
Hey there,
Last week we brought A* path finding to life, now it is time to make it faster. To increase the speed of A*we will be a using symmetry breaking algorithm called Jump Point Search(referred to as "JPS" from now on). The goal of this algorithm is to "jump" over the nodes that are not necessary to find the quickest path(image 1).
Only the blue nodes(jump points, image 1) are being checked and only the cost for these nodes will be calculated. In A*, every node(white and blue) in between the start point and end point would be checked and have it's cost calculated. I hope that you can see how this would greatly increase the speed of the algorithm.
Image 1: path finding with JPS. Jump points are shown in blue.
I never explained how A* worked because it is so widely know. This however, is less known and I will explain how it works. In A* you constantly check all the neighbors of the current node, calculate their cost and add them to the open list. JPS replaces the part of the code that gets the neighbors of the current node and only returns the jump points.
Lets see how the algorithm finds the jump points. JPS searches for jump points in all 8 directions: horizontal, vertical and diagonal. it will continue searching in a direction until it either finds a dead end or it comes across an jump point. these jump points then have their cost calculated and are added to the open list. the search pattern for JPS can be seen in image 2. The thing to remember here is that every step you go diagonally, you also search vertically and horizontally.
Image 2: search directions.
Every direction can give one of two results, a dead(image 3) end or a jump point(image 4). There is only two ways to detect: one way for horizontal and vertical and one way for diagonal.
Image 3: dead end. Image 4: jump point.
Image 5 shows the correct way to detect a vertical jump point(horizontal works the same only rotated). if the left neighbor of the node we just came from is not walkable(in this case "W") and the left neighbor of the current node is walkable(in this case "E"), the current node is a jump point. This works the same for the right side, as seen in image 4.
Image 5: showing correct way to detect vertical and horizontal jump points.
Image 6 shows the correct way to detect a diagonal jump point. If one of the diagonal neighbors of the current node is not walkable(in this case "W") and the neighbors that are shared between "J" and "W"(in this case, both "E's") are walkable, the current node is a jump point. this works for all the directions as long as you're searching diagonally.
Image 6: showing correct way to detect diagonal jump points.
Last part to explain and then we're done. when searching diagonally and either the horizontal or vertical search finds a jump point. You will need to return two points. first the diagonal node, the vertical or horizontal search started from(image 7 - point 1), and then the jump point found by the vertical or horizontal search(image 7 - point 2).
