Pathfinding algorithms are designed to find the shortest or most efficient path between two points. They are widely used in fields like robotics, video games, and map navigation. There are several algorithms available, each with its strengths and use cases.

1. Dijkstra's Algorithm : Finds the shortest path from a single source to all other nodes in a graph. It's efficient but does not consider the direction of the goal, potentially leading to longer processing times.

2. Breadth-First Search (BFS) : Explores neighbor nodes first before moving to the next-level neighbors. It's great for finding the shortest path in unweighted graphs but can be inefficient in larger spaces.

3. Depth-First Search (DFS) : Explores as far as possible along a branch before backtracking. It's not guaranteed to find the shortest path, but it can be useful in scenarios where space is limited.

4. A-Star (A) Algorithm * : Combines features of Dijkstra's and BFS, using heuristics to improve performance. It's efficient and guarantees the shortest path, making it popular for grid-based pathfinding.

The A-Star (A*) Algorithm

A* is a popular choice for pathfinding thanks to its efficiency and accuracy. It uses heuristics to estimate the distance from the current node to the goal, reducing the number of explored nodes.

Components of A*:

1. G Cost (Actual Cost) : The cost of moving from the start node to a given node along the best known path.

2. H Cost (Heuristic Cost) : An estimated cost from that node to the goal. Common heuristics include Euclidean distance and Manhattan distance.

3. F Cost : The sum of G Cost and H Cost (F = G + H). This cost is used to prioritize the node exploration.

Algorithm Steps:

1. Initialize : Put the start node in an open and closed list . The open list will contain the nodes discovered but not evaluated and the closed list will contain the nodes that have already been evaluated.

2. Loop :

   1. Choose the node with the lowest F Cost from the open list.

   2. Switch it to the closed list (processed nodes).

   3. For each neighbor of this node:

      • If it's not walkable or in the closed list, ignore it.

      • If it’s not on the open list, add it. Calculate G, H, and F costs.

      • If it’s in the open list but the new G cost is lower, update its costs and parent.

3. Goal Reached : If the goal is added to the closed list or the open list is empty, the algorithm ends.

4. Path Reconstruction : Trace the path from the goal node back to the start node using parent references.

1. G Cost (Actual Cost) :

   • The G Cost is a measure of the actual cost of the path from the start node to a given node.

   • It represents the exact cost (or distance) traveled from the start node to the current node.

   • In a grid, this could be the sum of the distances of all the moves made (counting each move as a unit step or more if diagonal steps have a higher cost).

   • The G Cost is cumulative; as the algorithm progresses, the G Cost of each node reflects the total cost of getting to that node from the start.

2. H Cost (Heuristic Cost) :

   • The H Cost is an estimate of the cost from the current node to the goal node.

   • This is a heuristic measure and not an exact calculation (since the exact cost is unknown until the goal is reached).

   • Common heuristics include the Euclidean distance (straight-line distance) in non-grid environments or the Manhattan distance (sum of the absolute values of the horizontal and vertical differences) in grid-based environments.

   • The heuristic is a critical part of A*, as it helps prioritize which paths are more likely to lead to the shortest overall route.

3. F Cost (Total Cost) :

   • The F Cost of a node is simply the sum of its G Cost and H Cost: F = G + H .

   • It represents a node's combined cost with respect to the start node and the estimated cost to reach the goal node.

   • The F Cost is used to compare the nodes and decide which node should be explored next. The node with the lowest F Cost is chosen as the most promising node to lead to the optimal path.

Let's look at the main function in our example files:

def a_star_search(self):
    # Check if the algorithm is still running
    if self.running:  
        
        # Check if there are nodes to process
        if len(self.stack) > 0:
            # Find the cell in the open stack with the lowest F cost
            current_cell = self.find_closest_f(self.stack)
            
            # Check if the current cell is the goal
            if current_cell == self.end_node:
                println("Goal Reached!")
                self.running = False  # Stop the algorithm
                self.path_found = True  # Mark that the path has been found
                self.reconstruct_path(current_cell)  # Reconstruct the path from end to start
                
            # Move the current cell from the open stack to the closed stack
            self.stack.remove(current_cell)
            self.closed_stack.append(current_cell)
            
            # Iterate through all neighboring cells of the current cell
            for neighbor in current_cell.get_neighbors():
                # Skip if the neighbor is already processed or is an obstacle
                if neighbor in self.closed_stack or neighbor.isObstable:
                    continue
                # Calculate tentative G cost (distance from start)
                tentative_g = current_cell.g + 1
                new_path = False  # Flag to check if a better path is found
                
                # If the neighbor is already in the open stack, check if this new path is better
                if neighbor in self.stack:
                    if tentative_g < neighbor.g:
                        neighbor.g = tentative_g
                        new_path = True
                else:
                    # If the neighbor is not in the open stack, add it
                    neighbor.g = tentative_g
                    new_path = True
                    self.stack.append(neighbor)
                
                # If a new path is found or the neighbor is new, calculate F and H costs, and set the parent
                if new_path:
                    neighbor.h = dist(neighbor.pos.x, neighbor.pos.y, self.end_node.pos.x, self.end_node.pos.y)
                    neighbor.f = neighbor.g + neighbor.h
                    neighbor.parent = current_cell
        
        else:
            # If there are no nodes to process and the goal hasn't been reached, no solution is found
            println("No solution!")
            self.running = False  # Stop the algorithm

• Running Check : The algorithm runs as long as self.running is True.

• Processing Nodes : The algorithm maintains two lists: self.stack (open stack) and self.closed_stack (closed stack). The open stack contains nodes to be processed, and the closed stack contains nodes already processed.

• Finding the Lowest F Cost Node : The function self.find_closest_f finds the node in the open stack with the lowest F cost (sum of G and H costs).

• Goal Check : If the current node is the goal node, the algorithm reconstructs the path from the end node to the start node.

• Updating Costs and Parents : For each unprocessed neighbor of the current node, the algorithm calculates G, H, and F costs. If a shorter path to a neighbor is found (or if the neighbor is new), it updates these costs and sets the current node as the parent of the neighbor.

• Termination : If the open stack is empty and the goal hasn't been reached, the algorithm concludes that there is no solution.

Usage

This method is used in scenarios where you need to find an optimal path through a grid or graph, such as in maze-solving applications, robotics navigation, or game AI for movement. The A* algorithm is particularly effective because it uses heuristics (H cost) to guide the search, making it more efficient than algorithms like Dijkstra's, which do not use heuristics.