Programming Challenge: Optimize a Pathfinding Algorithm (Dec 30, 2024)

Objective

Implement a pathfinding algorithm (e.g., Dijkstra’s or A*) to find the shortest path between two points on a grid.

Requirements

1. Grid Representation:

   • Create a 2D grid where each cell represents walkable terrain or an obstacle.

2. Algorithm:

   • Implement a pathfinding algorithm like Dijkstra’s or A*.
   • The algorithm should find the shortest path between a start and an end point, avoiding obstacles.

3. Visualization:

   • Print the grid showing the path taken. For example:
     • S for start
     • E for end
     • X for obstacles
     • * for the shortest path

4. Input:

   • Allow the user to define the grid size, starting and ending points, and obstacle placement.

5. Error Handling:

   • Validate inputs (e.g., ensure the start and end points are not obstacles).

6. Stretch Goals:

   • Add support for weighted cells (e.g., some cells take more "time" to cross).
   • Create a graphical visualization if you're using a framework like Pygame or JavaScript with Canvas.

Example

Input:

Grid Size: 5x5
Start Point: (0, 0)
End Point: (4, 4)
Obstacles: (2, 2), (3, 2)

Output:

S * * * *
  X X * *
  X X * E

Submission Instructions

• Share your code and an example of how it works.
• For graphical solutions, provide a screenshot or link.