A* algorithm

"""
The A* (A-star) algorithm is an efficient pathfinding and graph traversal algorithm. It finds the shortest path from the start node to a goal node by using a heuristic to estimate the cost from the current node to the goal, thus prioritizing paths that appear to be leading closer to the goal.

Below is a concise example of the A* algorithm in Python. This implementation assumes you have a graph where nodes are connected by weighted edges and you have a heuristic function that estimates the cost from any node to the goal node. We'll use a simple heuristic function: the Euclidean distance (for a grid-based graph), or you can adjust it according to your specific use case.

There are two concepts used to determine the best path from a start node to a goal node: weight and heuristic. Let's clarify each of these:
- Weight is a measure of the effort, distance, or resource consumption required to move between nodes directly connected in the graph. It is a concrete measure based on the actual layout and characteristics of the graph.
- The heuristic function is used to estimate the cost from a given node to the goal node, providing an informed guess about the remaining distance or cost. The heuristic function does not reflect the actual shortest path cost between two nodes, but rather provides an optimistic estimate, which guides the A* algorithm in its search for the shortest path.

- The total cost of a path through a given node is evaluated as f(n) = g(n) + h(n), where g(n) is the actual cost from the start node to node n (accumulated weights), and h(n) is the heuristic estimate from node n to the goal.
- The algorithm maintains a priority queue (or a heap in this code) that sorts nodes based on their f(n) values, meaning nodes with lower estimated total costs are explored first.

Nathan's notes: This is basically just like a BFS except using a heap to order the vertices to be explored by their estimated total cost.

Mnemonic summary: A* algorithm is just like Dijkstra's algorithm, the only difference is that A* tries to look for a better path by using a heuristic function, which gives priority to nodes that are supposed to be better than others while Dijkstra's just explores all possible ways.
"""
import heapq
from random import randint

class Node:
    def __init__(self, name, x, y, neighbors=None):
        self.name = name
        self.x, self.y = x, y
        self.neighbors = neighbors if neighbors else {}  # dict to Node: weight

def astar(start, goal, heuristic):
    # Heap of (estimated_total_cost, cost_to_start, node, path)
    open_heap = [(heuristic(start, goal), 0, start, [start.name])]
    while open_heap:
        current_est, current_cost, current_node, path = heapq.heappop(open_heap)
        if current_node == goal:
            return path  # Goal reached, return the path
        for neighbor, weight in current_node.neighbors.items():
            new_cost = current_cost + weight
            estimated_total_cost = new_cost + heuristic(neighbor, goal)
            heapq.heappush(open_heap, (estimated_total_cost, new_cost, neighbor, path + [neighbor.name]))
    return None  # No path found

def heuristic(node, goal):
    """Example heuristic: Euclidean distance."""
    return ((node.x - goal.x) ** 2 + (node.y - goal.y) ** 2) ** 0.5

# Example usage
# Creating a simple graph (with dummy heuristic values as placeholders)
node_a = Node('A', randint(0, 10), randint(0, 10))
node_b = Node('B', randint(0, 10), randint(0, 10))
node_c = Node('C', randint(0, 10), randint(0, 10))
node_d = Node('D', randint(0, 10), randint(0, 10))
node_e = Node('E', randint(0, 10), randint(0, 10))

# Cost from each node to its neighbor (e.g. the speed of travel on a particular segment of road)
node_a.neighbors = {node_b: 1.0, node_c: 3.0}
node_b.neighbors = {node_d: 1.0}
node_c.neighbors = {node_d: 1.0, node_e: 5.0}
node_d.neighbors = {node_e: 1.0}

# Find path from A to E
path = astar(node_a, node_e, heuristic)
print("Path from A to E:", path)