Grid Race Bot

This repository contains my bot for the Grid Race programming competition. The competition tasks agents with navigating a grid-based racetrack while managing vehicle physics (acceleration and velocity), fog of war, and special terrain types like oil and sand.

Strategy & Implementation

The bot is built to handle all three tiers of the competition. It operates under limited visibility and strict physics constraints, using a custom bounded A* pathfinder combined with an exploration heuristic.

1. Memory and Mapping

Since the bot only receives a limited (2R+1)x(2R+1) window of the map each turn, it builds and maintains a global map in the background.

• It permanently stores walls, free space, the start, goal, oil, and sand once observed.
• Unseen areas are tracked as UNKNOWN, which helps the bot identify unexplored regions and plan where to go next.

2. Pathfinding (Kinodynamic A*)

The primary pathfinder is a bounded A* search over the (position, velocity) state space to account for momentum.

• Targeting: If the goal is known, it paths directly there. Otherwise, it targets "frontiers" (free cells bordering unknown areas) to actively explore the map.
• Cost Map: A Dijkstra distance field is generated backwards from the target. Normal cells cost 1, UNKNOWN cells have a slight risk penalty that scales over time, OIL costs 1.5, and SAND costs 2.0 to encourage routing around hazards.
• Heuristic: The A* heuristic combines the Dijkstra distance with a small penalty for high speed. To stay within turn time limits, the search has a hard expansion cap. It only actually executes the very first acceleration step of the best path it finds.

3. Handling Oil & Sand

The environment overrides normal acceleration inputs on oil and sand tiles. To prevent losing control and crashing when entering these hazards:

• If moving slowly, the bot coasts (0, 0).
• If carrying too much speed (> 1), it applies the brakes to minimize the risk of a high-speed collision while its control is restricted.

4. Visibility-Aware Speed Capping

To avoid crashing into walls hidden in the fog of war, the bot calculates the "runway" ahead (the number of visible free cells in its current direction of travel).

• It caps its speed based on this runway (v_max ≈ floor(sqrt(2 * runway))). This ensures the bot always has enough space to brake safely within the known map.

5. Safety Filters

Every move suggested by the A* planner is passed through a strict safety filter. This ensures the move does not:

• Go out of bounds.
• Clip through a wall corner (checked by supersampling the line between the old and new position to detect diagonal clipping).
• Collide with another known player.
• Violate basic physics rules (like instantly reversing velocity).

If the planner fails to find a safe move, the bot falls back to a hardcoded priority list:

1. Coast (if safe).
2. Accelerate gently (if well below the speed cap).
3. Swerve 90 degrees to avoid immediate obstacles.
4. Apply full brakes.

6. Collision Recovery & Anti-Stuck

• Collision Detection: The bot infers it was penalized by the judge if its velocity unexpectedly drops to 0 without a matching input.
• Bounce Prevention: After a reset, the bot temporarily bans accelerating in the exact direction it just came from to avoid repeatedly hitting the same wall.
• Anti-Ping-Pong: It maintains a short history of recently visited cells. If it detects oscillation (driving back and forth over the same small area), it overrides the planner and forces a 90-degree turn to break the loop.

Running the Bot

You will need the client_bridge.py script provided by the competition to run this locally.

1. Start the Judge (in one terminal):

   python judge/run.py judge/sample_config.json 1

2. Connect the Bot (in a second terminal):

   python bot/client_bridge.py bot/bot.py