Hey all. I have a math paper about AI pathfinding due Friday, and I figured that a few people here might know a thing or two about these algorithms. I am having trouble understanding two algorithms: A* and Jump Point Search. I have already written and calculated on Dijkstra's, which seems to be the most straightforward of the three. Below is what I have so far for the step-by-step outline of each algorithm. As far as I can tell, my descriptions are extremely flawed.
A*1. Assign a cost value of zero to all nodes.
2. Consider the position of the start node to be at the origin.
3. Allow the start node to be the active node.
4. Calculate the distance from the each adjacent node in the open set to the goal node.
5. Set the adjacent node with the smallest distance to the goal as the active node, and add the previous node to the closed set.
6. Let the cost of the active node be the distance from the node to the goal node plus the g score.
7. Let the g score of the neighboring nodes be the cost of the active node.
8. Let the neighboring node with the lowest g score be the active node, unless an adjacent node is the goal.
9. Add the previous node to the closed set.
10. Repeat steps 4-9 until the goal node is reached or there are no remaining nodes in the open set.
Jump Point Search: (this is wrong)
1. Give all nodes a distance value of infinity except for the start node, which is given a distance value of zero.
2. Consider the start node to be at the origin.
3. Allow the start node to become the active node.
4. Calculate the angle from the active node to the end node. (referred to as the end angle)
5. Calculate the angle of each adjacent node in the open set.
6. If the angle to an adjacent node is equal to the last angle, automatically make the adjacent node the active node, and skip step 7.
7. Let the node with the angle closest to that of the end angle become the active node.
8. Remove the previous active node from the open set, and add it to the closed set.
9. Repeat steps 4-7 until the end node is reached or until there are no remaining nodes in the open set.
10. Return the first path found.
Internet resources:A*Jump Point SearchThe setup I am using for my example problem:
Any help figuring out how these work would be greatly appreciated! (images are welcome!)