snake*search.exe

The project began with a simple question: How do game characters navigate complex environments so efficiently? During my studies in distributed systems and graph algorithms, I became fascinated by pathfinding methods like DFS, BFS, and Dijkstra's Algorithm. But it was A*search—a hybrid of heuristic-driven and cost-based navigation—that stood out for its balance of speed and accuracy.

I started with a Pygame tutorial (Coder Space, 2022) to create the core mechanics:

• Snake movement (grid-based, WASD controls).
• Food spawning (random coordinates).
• Collision detection (walls, self).

Key Steps:

1. Grid Representation:
   • Treated the game window as a graph where each pixel was a node.
   • Defined neighbors (up/down/left/right) with a Manhattan distance heuristic.
2. Path Calculation:
   • Used A* to find the shortest path from the snake's head to the food, avoiding:
     • Its own body (snake_body list).
     • Randomly placed obstacles (obstacle_positions).
3. Dynamic Adaptation:
   • Recalculated the path after every move to account for the growing body.

def A_Star(start, goal, grid_size, snake_body, obstacle_positions):
    open_set = {start}
    came_from = {}  # Tracks the optimal path
    g_score = {start: 0}  # Cost from start
    f_score = {start: m_distance(start, goal)}  # Estimated total cost
    ...

• Initially, food appeared inside obstacles, causing instant collisions.
• Solution: Added validation to regenerate food until it spawned in a valid location.

• A* slowed when the snake grew long (many body segments to avoid).
• Optimization: Limited path recalculation to every N frames and prioritized recent moves.

• Debugging paths was hard without visual aids.
• Fix: Added temporary debug lines to display A*'s chosen path (removed in the final version).

To make the game engaging, I:

• Added Assets: Replaced rectangles with pixel-art sprites (snake, food, obstacles).
• Fine-Tuned Gameplay: Adjusted snake speed (time_step) and obstacle density.
• Scoring System: +10 points per food, with a reset on collision.

1. Theory vs. Practice:
   • A*'s elegance in textbooks didn't account for real-world edge cases (e.g., dead ends).
   • Debugging forced me to deeply understand heuristic trade-offs.
2. Adaptability Matters:
   • My initial plan to compare multiple algorithms was scrapped due to time, but A* alone taught me more about optimization.
3. User Experience:
   • Even a technical demo benefits from polish (e.g., sprites, score displays).

1. Advanced AI:
   • Replace A* with Q-learning to let the snake learn from mistakes.
2. Multi-Algorithm Mode:
   • Let users toggle between A*, Dijkstra, and BFS to see differences in real time.
3. Hardware Integration:
   • Port the game to a Raspberry Pi and connect it to a physical robotic snake.

Snake*Search evolved from a simple coding exercise into a deep dive into algorithmic decision-making. The project honed my skills in Python, Pygame, and heuristic design, while teaching me to embrace iterative problem-solving. Most importantly, it proved that even classic games can become gateways to advanced computational thinking.