Here’s a little demo of the A star (A*) pathfinding algorithm, running on the surface of a sphere. It’s a network of spheres that neighbour each other when they collide at the start of the demo. This demo uses 2048 spheres, probably way too much. Might be nice to push this further and turn it into a navmesh.
As I said earlier, this is by no means efficient, but it does demonstrate the process quite well.
For those of you who haven’t seen this Algorithm in action, the basic idea goes as follows:
NOTE: A network of walkable and unwalkable points (the spheres) must be formed, and each point must have a reference to each of its neighbours.
NOTE: Each point is given three scores:
- a) A GScore which is the basic distance from one point to the next
- b) A HScore which is the Heuristic or simply, a best guess or estimate of distance from the start to the finish point.
- c) An FScore which is the two other scores added together.
The algorithm needs a start point and an end or target point to run.
The first or “start point” is added to an “Open” list for consideration.
This loop keeps looping until there are no points left in the open list or the target is found
- Step 1) The point with the lowest FScore is found in the open list and set as the “Current” point (The first time this runs, it finds the only point, the start point)
- Step 2 A) If the current point is not the target, it is then removed from the open list and added to a “Closed” list. Skip to step 3
- Step 2 B) If the current point is the target, a new list is created by adding the finish point, and then the node it is linked to, and then the node that is linked to…etc, until the start node is found (it wont have a link). This list is then reversed, and that’s your path. Break from loop.
- Step 3) Each of the current point’s neighbours are considered and as long as they are not on the closed list or set as blocked, they will all have their G, H, and F scores computed.
- Step 4) Each neighbour is then added to the open list and the node it came from, or is linked to, in this case, the “current” node, is set for each neighbour.
- Step 5) Loop back to Step 1, where we find the point with the lowest FScore, the point that is closest to our target, and repeat the process.