A maze with walls of varying thickness, three pathfinding algorithms racing to cross it, and an isometric 3D look — built entirely on Python's turtle module, which was never meant to do any of this. The pathfinding half is the "expected" part of the assignment; the rendering half turned into its own small research project, since turtle has no concept of depth, layering, or anything beyond flat 2D lines.
The project implements several routing algorithms to find optimal paths under different constraints.
This is used to find the absolute shortest path in a graph with non-negative edge weights. In our grid, the "cost" of moving from one cell to another is determined by the thickness of the wall separating them. Dijkstra's algorithm systematically expands outwards to find the optimal path that requires the least effort to break through.
Bellman-Ford is provided as an alternative algorithm. It iteratively relaxes all edges in the graph, ensuring that the optimal path is discovered. This is particularly useful as a benchmark for accuracy and for graphs where different weight structures might be tested.
We implemented a Greedy Best-First Search algorithm using the Manhattan Distance to the target node as the heuristic. This algorithm dynamically explores its neighbors in all four directions. It provides a fast, locally optimal path that contrasts with the systematic expansion of Dijkstra's algorithm.
Visualizing the algorithms presented specific challenges, particularly when relying on Python's native turtle module to achieve an isometric aesthetic.
Instead of drawing standard straight grid lines, we implemented a fractal generation technique (get_fractal_points) that subdivides edges to give the walls a textured appearance.
- The Challenge: Drawing walls continuously without creating overlapping areas or gaps at intersections.
- The Solution: We rendered the floors and cutouts rather than the walls themselves. By generating the fractal polygons for the interior of each cell (the floor) and placing them over a solid background block, the walls naturally emerge as the negative space between the rooms.
To give the grid a 3D block appearance, the fractal boundaries of the rooms are mathematically projected downward and to the right (x + depth_x, y - depth_y). Drawing these projected polygons in darker, shaded colors before drawing the top canvas simulates isometric shadows.
- The Challenge: We needed the path-routing animations to appear on the floor of the maze. Because Turtle draws sequentially, drawing the path last results in the line rendering over the 3D walls, breaking the depth effect.
- The Solution: Turtle's API does not natively support Z-indexing. To resolve this, we accessed its underlying GUI framework, Tkinter (
cv = t.Screen().getcanvas()), and tagged the Z-order position of the grid's top canvas (z_marker). During the path animation, we executecv.tag_raise(path_item, z_marker)for every line segment. This correctly layers the path segment underneath the walls during the real-time drawing phase.
To get started with the Magic Grid project:
- Clone the project repository from GitHub:
git clone https://github.com/ferhat-ramdani/The-Magic-Grid.git
- Install the required dependencies. Make sure you have Python installed on your machine.
pip install turtle
- Navigate to the project directory:
cd magic-grid - Run the main Python file to execute the grid modeling program:
python main.py
Once the program is running, interact with the grid through the graphical interface:
- Drag and Drop: Click and drag the Start (Green) and End (Red) markers to position them anywhere on the grid.
- Find Best Path: Click the "Find best path" button to trigger the algorithms.
- Observe: Watch as the paths are simultaneously animated beneath the walls.
- Regenerate: Click the "Regenerate Grid" button that appears below the dashboards to wipe the board and start a new layout.