Pathfinding Visualizer

কেন এই প্রজেক্ট

Graphs-bfs-dfs লেসনে BFS-এর level-by-level expansion আর shortest-paths লেসনে Dijkstra-র priority queue — দুটোই ছিল চোখে না দেখা graph-এর উপর ব্যাখ্যা। এই প্রজেক্টে সেই expansion-টা চোখের সামনে ঘটবে: A* কেন Dijkstra-র চেয়ে অনেক কম node ছুঁয়ে একই path-এ পৌঁছায়, zero heuristic দিলে A* ঠিক Dijkstra হয়ে যায় — bookkeeping-এ বিশ্বাস না করে নিজের চোখে দেখুন।

আরেকটা শিক্ষা design-এর: তিনটা algorithm-এর core logic প্রায় এক — শুধু frontier-এর behavior বদলায় (queue, priority queue by g, priority queue by f=g+h)। Generator দিয়ে expansion stream আলাদা করলে renderer, stats, benchmark — সব একই ইন্টারফেসে তিনটা algorithm চালাতে পারে।

ধাপে ধাপে

১. Grid model + maze generator

from dataclasses import dataclass

@dataclass(frozen=True)
class Cell:
    r: int
    c: int

class Grid:
    def __init__(self, rows, cols):
        self.rows, self.cols = rows, cols
        self.wall = [[False] * cols for _ in range(rows)]
        self.cost = [[1] * cols for _ in range(rows)]   # weighted terrain-এর জন্য

    def neighbors(self, cell):
        for dr, dc in ((1,0), (-1,0), (0,1), (0,-1)):
            r, c = cell.r + dr, cell.c + dc
            if 0 <= r < self.rows and 0 <= c < self.cols and not self.wall[r][c]:
                yield Cell(r, c)

Maze generator দুটো রাখুন — random obstacle (প্রতি cell ৩০% wall) আর recursive backtracker (perfect maze, সব cell connected)। Perfect maze-এ BFS-এর path দীর্ঘ ও বাঁকানো হয়, visual comparison তাই সুন্দর।

Checkpoint: একই seed-এ generator deterministic — দুইবার চালিয়ে একই maze। নইলে algorithm তুলনা অর্থহীন।

২. Search cores as generators

from heapq import heappush, heappop
from collections import deque

def bfs(grid, start, goal):
    frontier = deque([start])
    seen = {start}
    while frontier:
        cur = frontier.popleft()
        yield cur
        if cur == goal: return
        for nb in grid.neighbors(cur):
            if nb not in seen:
                seen.add(nb)
                frontier.append(nb)

def dijkstra(grid, start, goal):
    frontier = [(0, start)]
    best = {start: 0}
    while frontier:
        g, cur = heappop(frontier)
        if g > best.get(cur, float('inf')): continue   # stale entry
        yield cur
        if cur == goal: return
        for nb in grid.neighbors(cur):
            ng = g + grid.cost[nb.r][nb.c]
            if ng < best.get(nb, float('inf')):
                best[nb] = ng
                heappush(frontier, (ng, nb))

def astar(grid, start, goal, h=manhattan):
    frontier = [(h(start, goal), 0, start)]            # tie-break: f আগে, তারপর g
    g_best = {start: 0}
    while frontier:
        f, g, cur = heappop(frontier)
        if g > g_best.get(cur, float('inf')): continue
        yield cur
        if cur == goal: return
        for nb in grid.neighbors(cur):
            ng = g + grid.cost[nb.r][nb.c]
            if ng < g_best.get(nb, float('inf')):
                g_best[nb] = ng
                heappush(frontier, (ng + h(nb, goal), ng, nb))

Path reconstruct করতে came_from dict সমান্তরালে রাখুন — yield করার সময় parent record হচ্ছে, শেষে goal থেকে backward walk।

Checkpoint: unweighted grid-এ তিনটার path length এক; BFS-এর came_from tree-টা সরাসরি level order মেনে চলে।

৩. ANSI terminal renderer

CLEAR = '\x1b[H\x1b[J'
HOME  = '\x1b[H'
COLORS = {'wall': '\x1b[37m#\x1b[0m', 'explored': '\x1b[44m \x1b[0m',
          'frontier': '\x1b[103m \x1b[0m', 'path': '\x1b[42m \x1b[0m',
          'start': '\x1b[41mS\x1b[0m', 'goal': '\x1b[45mG\x1b[0m'}

def render(grid, state):
    print(HOME)                        # clear নয়, cursor home — flicker কমে
    for r in range(grid.rows):
        row = ''.join(COLORS[state(r, c)] for c in range(grid.cols))
        print(row)

Frame stepping দুইভাবে: প্রতি K-টা yield-এ এক frame (fast-forward), আর interactive mode-এ Enter চাপলে এক step। Explored আর frontier আলাদা রঙে — closed set আর open set-এর পার্থক্যটা এখানেই দৃশ্যমান।

৪. Stats panel

Renderer-এর নিচে এক লাইন:

expanded=412  frontier=38  path_len=None  elapsed=12ms

Expanded count হলো yield-এর count, frontier size হলো heap/queue-র বর্তমান দৈর্ঘ্য, path length হলো reconstruct-এর ফল। তিন algorithm-কে একই maze- এ পরপর চালিয়ে চূড়ান্ত stats পাশাপাশি রাখুন — পরের ধাপের টেবিলের raw data এটাই।

৫. Heuristic ablation

একই maze, একই start/goal, A* তিনবার — heuristic বদলে:

heuristic	expanded	max frontier	path len
zero	812	96	62
euclidean	402	51	62
manhattan	210	33	62

Path length সব সারিতে এক — admissible heuristic optimality ভাঙে না, শুধু কাজের পরিমাণ কমায়। Manhattan এখানে জেতে কারণ ৪-দিকের movement-এ এটা tight bound; Euclidean diagonal shortcut-এর স্বপ্ন দেখায় যা এই grid-এ অসম্ভব, তাই underestimate বেশি হয় আর expansion বেশি লাগে। Zero heuristic-এর সারিটা Dijkstra-র সঙ্গে exactly মিলবে — এটাই “A* = Dijkstra + informed ordering”-এর প্রমাণ।

Heuristic ইচ্ছে করে inadmissible করুন (Manhattan × ৩) — কোনো maze-এ path ছোট হয়ে যায়, কোনটায় যায় না? Optimality কেন ঝুঁকিতে পড়ল সেটা counter-example হিসেবে জমা রাখুন।

৬. Weighted terrain

Swamp cell cost 5, grass cost 1। এখন BFS আর Dijkstra-র পথ আলাদা:

# BFS: কম ধাপ, কিন্তু swamp-এর মধ্য দিয়ে → total cost 22
# Dijkstra: বেশি ধাপ, grass ঘুরে → total cost 8

BFS ভুল answer দেয় না যতক্ষণ প্রশ্নটা “কম edge” — কিন্তু weighted world-এ প্রশ্নটা “কম cost” হওয়া মাত্রই BFS-এর অনুমতি শেষ। Visualizer- এ এই জুটিটা side-by-side চালিয়ে দুই path আঁকুন।

Checkpoint: Dijkstra-র path cost manually sum করে মেলান; BFS-এর path-ও sum করে দেখান যে বড়। সংখ্যা মিলবে, story complete.

নিজেকে চ্যালেঞ্জ করুন

1. Bidirectional BFS — দুই frontier মাঝপথে মেলে, expanded count কত% কমাল compare করুন
2. Diagonal movement — corner-cutting rule ঠিক করুন, heuristic তখন octile distance
3. Jump Point Search — uniform-cost grid-এ A*-এর symmetric expansion skip করে কীভাবে জেতে
4. Dynamic maze — চলতি search-এর মাঝে wall বসিয়ে D* Lite-জাতীয় repair চেষ্টা করুন
5. GIF export — frames জমিয়ে Pillow দিয়ে animation file
6. Benchmark mode — ১০০টা random maze-এ তিন algorithm-এর median expanded count, ablation table-কে statistical rigor দিন

যা এখানে শিখলেন, পরে যেখানে লাগবে

এখানে	পরে
Frontier abstraction (queue/priority)	Any graph search — dependency resolution, web crawler
Admissible heuristic চিন্তা	Game AI, motion planning, constraint solver-এর pruning
Stale-entry lazy deletion	Priority-queue-based scheduler, event simulation
Generator-driven visualization	Profiler flamegraph, debugger stepping — একই separation
Weighted vs unweighted boundary	Routing protocol-এ link metric কেন একমাত্রিক নয়