Writing math paper~ Need help with AI Pathfinding Algorithms!

[Wesley Williams]

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 Search

The setup I am using for my example problem:

Any help figuring out how these work would be greatly appreciated! (images are welcome!)

[Ad Bot]

[Starzy]

A lot of people on the forums know about A* not sure about Jump Point Search though, ask Port.

[Port]

Hi! I've implemented both A* and JPS in Blockland.

A* is pretty simple - I don't see why you're talking about angles in your description. All you need is an origin, a destination, a heuristic function (h), and to keep track of the parent, g score and state of each node. It's quite a bit more simple if you just talk about it in terms of a functional process.

Initialization:

   Set the state of the starting node to open (add it to the open set).
  Consider unset values to be 0.

Main algorithm:

   As long as the open set is not empty:
      Take the node in the open set where h(node, goal) is lowest.

      If the node is the goal, a path has been found. Walk backwards through the tree of parents from this node,
      adding to a resultant list in reverse order as you do. This is the result, stop the algorithm early and return it.

      Set the node as closed (remove it from the open set and add it to the closed set).
      
      For each neighbor connected in the graph to the current node,
         If it's closed, skip it
         If it's not in the open set, add it

         Let cost be g[node] + h(node, neighbor)

         If g[neighbor] is not set, or cost is less than g[neighbor],
            Let g[neighbor] be cost
            Let the parent of neighbor be node
  
   If the open set ends up being empty, there is no valid path from the start to the goal.

I'd write up something about JPS too if I wasn't so tired. It might actually be the case that I got something wrong in my description due to how tired I am, so I recommend checking up on it first. :p

[Port]

I can't recommend using the Wikipedia article on A* as you linked in the OP. See some of the papers it references instead.

http://en.wikipedia.org/wiki/A*#References

[Wesley Williams]

Thanks for the help! I'm wondering how the heuristic function is calculated, however. The distance from the start node to the active node is added with the distance from the active node to the goal?

[Port]

The heuristic function is literally just as the name says, a heuristic of the cost.

You can replace it with any generic distance calculation you want - you can even use a uniform-cost heuristic (always returns 1 or similar) if you want, though that obviously won't lead to optimal paths. Generally, the precision of the function is symbiotic with the quality of the result.

My implementation uses simple Euler distance (on vector positions), as in:

    |b_pos - a_pos|

This is obviously not applicable to every case, as A* does not have to operate in physical space, or even normal Euclidean space.

[Wesley Williams]

Ok that makes good sense. I am first calculating an example 2D problem, hence D = √((x2-x1 )^2+(y2-y1 )^2) I will also discuss how to calculate the shortest path using A* for 3D problems with vectors, but am thankfully not doing examples of those by hand.

My only uncertainty is the g score. You are setting the neighbors' g scores equal to the cost of the active node? The g scores of the first neighbors would all be the distance to from the start to the end, then?

[Wesley Williams]

So in my case, the g values of each of the first neighbors will be the distance from the start node to the end node? (Start node has a g score of 0?)

[Wesley Williams]

Would this work as a step-by-step example of A*?

1.   Assign a g-score of infinity to all nodes.
2.   Consider the position of the start node to be at the origin.
3.   Let the cost of the start node be equal to the distance from the start node to the goal.
4.   Allow the start node to be the active node in the open set.
5.   If the cost of the active node is less than the g-score of an adjacent node in the open set, calculate the cost for the adjacent node by adding the node’s g-score with a heuristic function (in our case, the distance from the adjacent node to the goal node).
6.   Set the adjacent node with the smallest cost as the active node, and add the previous node to the closed set (removing it from the open set).
7.   Repeat steps 5-6 until the end node is reached or until the open set is empty.
8.   Return the path with the shortest distance.

Thanks for any help!