SmartMaze

Overview

SmartMaze is an robotics project that integrates procedural maze generation, intelligent pathfinding, and realistic physical simulation in a 3D environment. The system generates configurable random mazes and uses AI algorithms to plan optimal paths for a robot to collect objects and reach the exit.

System Architecture

Simulation Environment (Godot 4)

• 3D mazes generated dynamically
• Manual or autonomous robot control
• Collectible objects placed in the maze
• Real-time visualization of the optimal path

Maze Generation

Wilson’s Algorithm (godotProject/src/algorithms/wilson_algorithm.gd):

• Produces unbiased uniform mazes
• Based on random walk with loop detection
• Ensures full connectivity between cells

Configurable parameters:

• maze_width, maze_height – grid size
• cell_size – physical cell size
• seed_value – deterministic generation (optional)

Intelligent Pathfinding

Optimized A* (godotProject/src/pathfinding/astar_pathfinding.gd):

• Shortest path computation between points
• TSP-like optimization for object collection

Optimization strategy:

1. Precompute distances between key points
2. Brute force for small instances (≤5 objects)
3. Greedy nearest-neighbor heuristic for larger mazes
4. Path reconstruction from optimal segments

Robot Simulation

Implemented in Python (notebook/lib/system/cart.py):

• Cart2D: Basic cylindrical robot
• TwoWheelsCart2D: Differential drive
• TwoWheelsCart2DEncoders: Encoders for odometry
• TwoWheelsCart2DEncodersOdometry: Full odometry integration
• AckermannSteering: Ackermann vehicle model

Features:

• Force and torque dynamics
• Linear and angular friction
• Inertia-based motion
• Odometry estimation

Control System

PID Controllers (notebook/lib/system/controllers.py):

• P, PI (with anti-windup), and PID control

DDS Communication:

• Real-time data exchange between Godot and Python
• Waypoint transmission with acknowledgment
• Continuous telemetry updates

Workflow

1. Initialization

   • Godot generates maze and objects
   • A* with TSP optimization computes the route

2. Communication

   • DDS handshake between Godot and Python
   • Waypoints sent, acknowledgments received

3. Simulation

   • Python simulates robot motion with physical models
   • PID controllers ensure path following

4. Visualization

   • Godot updates robot position in 3D
   • Displays real-time path progress

Controls

• F – Follow view
• P – Top-down view
• Enter – Regenerate maze
• Esc – Toggle solution path