Grand Prix F1 Racing

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