Dynamic Terrain Navigation Using A* Pathfinding

The Scene

The scene contains a series of island meshes that act as obstacles, with an ocean entity mapping over the nodes the boat can travel over to reach a designation.
The ocean was created using aspects of the cloth class from Assignment 5, where we can create a grid with a flexible number of rows and columns.

The Grid

The grid comprises of an array of nodes arranged in an equal number of rows and columns, similar to the setup of the cloth from Assignment 5. Every node in this grid contains the following variables:

• The initial position upon debugging
• The position at the current frame
• The initial velocity upon debugging (every node will have a velocity of 0)
• The velocity at the current frame
• A boolean indicating whether this node is blocked

The x and z axes will always be kept constant throughout the program runtime, but but will oscallate on the y-axis to simulate a wave.
In the main program file, two of these nodes will be labeled as a "start" and "end" point, which will be used in the A* class to calculate the best route between these two points.

A* Search Algorithm

The pathfinding algorithm utilized in this program is A* search. Here we have a square grid, that may contain obstacles, and starting from one node we want to get to the target node as quickly as possible.
In every step A* takes, it picks up the node that has the lowest f-cost, which is a variable in a struct that equals the sum of two other parameters – g-cost and h-cost.

• g-cost = the movement cost to move from the starting point to the given square on the grid
• h-cost = the movement cost to move from the end point to the given square on the grid. Often referred to as the heuristic

To get the distances for the g and h costs, we use the getDistance() function, which use the grid, the start point, and the end point as the parameters. In the algorithm, we use an open and closed list, which indicates which nodes are available in proximity to the start node (from GeeksforGeeks):

1. Initialize the open and closed list
2. While the open list is not empty
   1. Find the node with the smallest f-cost on the open list, denoted as q
   2. Pop off q in the open list
   3. Generate every successor node surrounding q, and setting their parent value to q
   4. In every surrounding node:
      1. If that successor is the target node, we stop our search
      • We use the tracePath() function, which traces the path from the source to designation using the node's parent node pointers
      2. Compute the g and h-cost for every successor
      3. If a node with the same position as successor is in the open list which has a lower f-cost than successor, then skip that successor.
      4. If a node with the same position as successor is in the closed list with a lower f-cost than successor, skip this successor otherwise, then add the node to the open list
3. Add q to the closed list
4. End loop