Grand Prix F1 Racing
Intelligent F1 racing bot using A* pathfinding algorithm in C for autonomous navigation, collision avoidance, and optimal race strategy in real-time competitions.
Technologies Used
An intelligent Formula 1 racing bot developed in C for a programming competition. The system uses advanced pathfinding algorithms to autonomously navigate race circuits, avoid collisions with opponents, manage fuel consumption, and optimize racing strategies in real-time.
🎯 Project Overview
This project implements a competitive F1 racing AI using the A* pathfinding algorithm with custom heuristics for a programming competition. The bot competes against other AI drivers on various circuits, making real-time decisions about acceleration, braking, overtaking, and fuel management to achieve the fastest lap times.
Main Objectives:
• Reach the finish line as quickly as possible - Minimize circuit completion time by combining speed efficiency with strategic racing decisions • Respect race regulations - Adhere to maximum speed limits, fuel consumption rules, and acceleration constraints imposed by race regulations • Optimal movement algorithm design - Develop an algorithm ensuring the shortest possible path while considering circuit elements and race rules • Multi-circuit validation - Test performance across different circuits to measure arrival times and manage fuel consumption • Code optimization - Improve performance by optimizing source code to increase algorithm efficiency, reduce computation time, and improve race times
🏎️ Core Features
• A Pathfinding Algorithm* - Custom implementation for optimal route finding on race circuits • Real-time Decision Making - Calculates acceleration vectors every turn (sub-second response) • Collision Avoidance - Detects and avoids obstacles and opponent vehicles using line traversal • Fuel Management - Optimizes speed vs. fuel consumption for race completion • Terrain Adaptation - Handles different surface types (track, sand, obstacles) • Multi-opponent Racing - Tracks and responds to up to 2 other AI drivers simultaneously • Boost Strategy - Strategic use of limited turbo boosts (5 per race)
💻 Technical Implementation
Core Algorithms:
• A Search* - Modified A* with Chebyshev heuristic for optimal pathfinding • Collision Detection - Bresenham line algorithm for path clearance checking • Hash Table - Custom hash table (capacity 1000) for closed set optimization • Priority Queue - Min-heap queue for efficient node exploration • Destination Selection - Euclidean distance-based target prioritization
Data Structures:
• GraphNode - Position, velocity, fuel, cost, heuristic, predecessor chain • TerrainMap - 2D grid representation of the circuit • GraphQueue - Priority queue sorted by totalCost (cost + heuristic) • HashTable - Fast lookup for visited nodes with custom hash function • DestinationList - Ordered list of finish line positions
System Architecture:
• Modular design with 9 separate C modules • Graph-based representation of race positions • State space search through position-velocity combinations • Memory-efficient node management with proper cleanup • Round-based execution with time tracking (sub-second per turn)
🧮 Algorithm Details
A Implementation:* • State space: (x, y, vx, vy) - position and velocity vectors • Heuristic: Chebyshev distance (max of dx, dy) to finish line • Cost function: Path length + fuel consumption penalty • Successor generation: 9 acceleration options (-1, 0, +1 for x and y) • Speed constraint: Maximum velocity magnitude of 25 units • Fuel calculation: Based on acceleration magnitude and current speed
Collision Detection: • Line traversal from current to next position • Checks each discrete point along the path • Detects walls (.), obstacles, sand (~), and opponent positions • Avoids positions occupied by other vehicles
Optimization Techniques: • Hash-based closed set prevents revisiting states • Priority queue ensures optimal node exploration order • Path caching and reuse when possible • Sand terrain penalty (extra fuel cost + speed limit) • Dynamic speed adjustment based on remaining fuel
🏁 Race Features
Strategic Elements: • Optimal acceleration calculation from current state • Overtaking maneuvers when opponents block path • Fuel-efficient pathing when low on gas • Speed adaptation for terrain types • Emergency braking for obstacle avoidance
Competition Format: • Real-time stdin/stdout communication with race manager • Position updates every round • Gas consumption tracking • Boost usage optimization • Performance timing per round
📊 Performance Metrics
• Response Time - Calculates moves in under 1 second per turn • Fuel Efficiency - Optimizes path length vs. acceleration costs • Pathfinding Accuracy - Successfully navigates complex circuits • Collision Avoidance - Zero crashes in optimal conditions • Memory Management - Proper allocation/deallocation with no leaks
🛠️ Build System
• Makefile-based compilation • Modular compilation of 9 source files • Compiler flags: -Wall -std=c99 -Wextra -O3 • Math library linking (-lm) • Binary output to drivers directory
📚 Learning Outcomes
• Mastered A* pathfinding algorithm implementation from scratch • Implemented advanced graph search data structures (priority queue, hash table) • Applied algorithmic optimization techniques for real-time constraints • Gained experience with competitive programming and AI decision-making • Developed robust collision detection using computational geometry • Enhanced understanding of state space search and heuristic design • Practiced efficient C programming with manual memory management
Challenges
- Initial node allocation causing memory crashes on large maps due to pre-allocating all nodes in a 2D array
- Computation time constraints: linked list for open set was too slow to find minimum cost node within 1-second deadline
- Collision detection between pilots: identifying when vehicles occupy same position or pass through walls ('teleporting')
- Selecting optimal heuristic: poor heuristic choice led to suboptimal paths and excessive computation time
- Fuel management on difficult terrain: mandatory sand sections made race completion impossible via normal route
Solutions
- Selective node allocation: only allocate memory for nodes when added to open list with competitive f-cost, drastically reducing memory usage
- Priority queue for open list: replaced linked list with min-heap queue for O(log n) operations, meeting time constraints even on large maps
- Hash table for closed list (capacity 1000): replaced linked list with hash table for O(1) lookup to verify visited nodes
- Implemented collisionDetection() using line sweep algorithm and reachableNode() to validate safe, obstacle-free paths
- Chebyshev heuristic: measures max absolute difference between coordinates, treats diagonal movement equal to horizontal/vertical, optimizing corner handling
- Sand avoidance weighting: assigned higher cost to sand terrain in pathfinding to favor normal roads and reduce fuel consumption
Outcomes
- Successfully completed races on various circuit layouts with zero memory crashes
- Achieved optimal pathfinding with sub-second response times (<1s per turn)
- Implemented robust collision avoidance with 3-vehicle tracking and wall penetration prevention
- Reduced computation time significantly through priority queue and hash table optimizations
- Optimized fuel efficiency by intelligently avoiding sand sections while respecting race constraints
- Demonstrated strong algorithm design, data structure optimization, and problem-solving skills