Line Following Algorithm

Project Overview

Designed for competitive speed, this line-following robot relies on a deterministic 100Hz memory-based algorithm. Unlike simple reactive bots that just follow the line, this system maps the track geometry as it traverses it, enabling it to predict curves, accelerate on straightaways, and optimize full path runs after the first pass.

The algorithm was developed in Python for prototyping and simulation, then ported to optimized C++ firmware on the microcontroller for real-time execution.

Track Mapping & Memory

At every detected intersection node, the robot logs its turn decision to memory. After completing the first traversal, a path simplification algorithm compresses redundant decisions — turning a sequence like Left → U-Turn → Right into a single straight pass, eliminating that dead end entirely on subsequent runs.

void optimizePath() {
    for (int i = 0; i < pathLength - 2; i++) {
        // L-U-R → U  (dead end: went left, reversed, went right)
        if (path[i]=='L' && path[i+1]=='U' && path[i+2]=='R') {
            path[i] = 'U';
            removePath(i+1, 2);
            i--; // Recheck from current position
        }
        // L-U-S → R  (another equivalent simplification)
        else if (path[i]=='L' && path[i+1]=='U' && path[i+2]=='S') {
            path[i] = 'R';
            removePath(i+1, 2);
            i--;
        }
    }
}

Python Simulation & Porting

The path optimization algorithm was first built and validated in Python with a simulated track input, making it easy to iterate on edge cases without flashing hardware. Once logic was proven, it was ported to C++ for the embedded controller, keeping the same algorithmic structure but optimized for fixed memory arrays instead of Python lists.

def optimize_path(path: list) -> list:
    i = 0
    while i < len(path) - 2:
        combo = path[i] + path[i+1] + path[i+2]
        replacements = {
            'LUR': 'U', 'LUS': 'R',
            'SUL': 'R', 'LUL': 'S',
        }
        if combo in replacements:
            path[i] = replacements[combo]
            del path[i+1:i+3]
        else:
            i += 1
    return path