path-gen.py

import numpy as np
import cmath
import heapq
import matplotlib.pyplot as plt
import time

# USER INPUT
size = int(input("Enter grid size"))

print("Enter start position (row col):")
sx, sy = map(int, input().split())

print("Enter goal position (row col):")
gx, gy = map(int, input().split())


# GRID GRAPH
def build_grid(n):
    graph = {}
    cost = {}

    for x in range(n):
        for y in range(n):
            neighbors = []
            for dx, dy in [(-1,0),(1,0),(0,-1),(0,1)]:
                nx, ny = x+dx, y+dy
                if 0 <= nx < n and 0 <= ny < n:
                    neighbors.append((nx, ny))
                    cost[((x,y),(nx,ny))] = 1
            graph[(x,y)] = neighbors

    return graph, cost


graph, cost = build_grid(size)



# QUANTUM PATHFINDER

class QuantumPathfinder:
    def __init__(self, graph, cost):
        self.graph = graph
        self.cost = cost
        self.nodes = list(graph.keys())
        self.index = {node: i for i, node in enumerate(self.nodes)}

    def transition(self, u, v):
        c = self.cost.get((u, v), 1)
        return cmath.exp(1j * c) / len(self.graph[u])

    def run(self, start, iterations=30, visualize=False, size=5):
        amplitude = np.zeros(len(self.nodes), dtype=complex)
        amplitude[self.index[start]] = 1

        for step in range(iterations):
            new_amp = np.zeros(len(self.nodes), dtype=complex)

            for u in self.nodes:
                for v in self.graph[u]:
                    new_amp[self.index[v]] += (
                        amplitude[self.index[u]] * self.transition(u, v)
                    )

            norm = np.linalg.norm(new_amp)
            if norm != 0:
                new_amp /= norm

            amplitude = new_amp

            # VISUALISATION (wave animation)
            if visualize:
                grid = np.zeros((size, size))
                for (x,y), idx in self.index.items():
                    grid[x][y] = abs(amplitude[idx])**2

                plt.imshow(grid, cmap='viridis')
                plt.title(f"Quantum Wave Step {step}")
                plt.colorbar()
                plt.pause(0.1)
                plt.clf()

        return amplitude

    def extract_path(self, start, goal, amplitude):
        path = [start]
        current = start
        visited = set()

        while current != goal:
            visited.add(current)
            neighbors = self.graph[current]

            best = None
            best_prob = -1

            for v in neighbors:
                if v in visited:
                    continue
                prob = abs(amplitude[self.index[v]])**2
                if prob > best_prob:
                    best_prob = prob
                    best = v

            if best is None:
                break

            path.append(best)
            current = best

        return path



# A* ALGORITHM
def heuristic(a, b):
    return abs(a[0]-b[0]) + abs(a[1]-b[1])

def astar(graph, start, goal):
    pq = [(0, start)]
    came_from = {}
    cost_so_far = {start: 0}

    while pq:
        _, current = heapq.heappop(pq)

        if current == goal:
            break

        for neighbor in graph[current]:
            new_cost = cost_so_far[current] + 1

            if neighbor not in cost_so_far or new_cost < cost_so_far[neighbor]:
                cost_so_far[neighbor] = new_cost
                priority = new_cost + heuristic(goal, neighbor)
                heapq.heappush(pq, (priority, neighbor))
                came_from[neighbor] = current

    # PATH RECONSTRUCTION
    path = []
    cur = goal
    while cur != start:
        path.append(cur)
        cur = came_from.get(cur, start)
        if cur == start:
            break
    path.append(start)
    path.reverse()

    return path

# ALGORITHM COMPARISION

start = (sx, sy)
goal = (gx, gy)

qp = QuantumPathfinder(graph, cost)

print("\nRunning Quantum Algorithm...")
amp = qp.run(start, visualize=True, size=size)
q_path = qp.extract_path(start, goal, amp)

print("Quantum Path:", q_path)

print("\nRunning A* Algorithm...")
a_path = astar(graph, start, goal)
print("A* Path:", a_path)



# FINAL VISUALIZATION

grid = np.zeros((size, size))

for x,y in q_path:
    grid[x][y] = 0.7

for x,y in a_path:
    grid[x][y] = 1.0

sx, sy = start
gx, gy = goal

grid[sx][sy] = 0.5
grid[gx][gy] = 0.9

plt.imshow(grid, cmap='coolwarm')
plt.title("Final Paths (Quantum vs A*)")
plt.colorbar()
plt.show()