Simulate a self-driving car ("Hero") deciding whether it is safe to change lanes, modulating its acceleration when it is not, and stepping the whole scene forward in time using basic longitudinal kinematics. ## Scenario - Hero (our car) drives in the **right lane** of a straight, two-lane, one-way road. There is no other car in the right lane. - Hero wants to execute a lane change into the **left lane**. - Some cars ("entities") are already driving in the left lane. They may block Hero's lane change. - **Only longitudinal (along-the-road) dynamics are modeled.** Lateral motion is abstracted away — a lane change is "allowed" when, looking only at along-the-road positions and speeds, there is a safe gap. Every car's motion state is: ```cpp struct State { double x = 0; // position along the road, in meters (absolute, NOT relative to Hero) double vx = 0; // speed along the road, in m/s double ax = 0; // acceleration along the road, in m/s^2 }; ``` You are given two controller helper functions and must use them (do not invent your own control law): ```cpp // Use this to drive at a target speed. Returns the desired ax to track vx_desired. double velocityController(double vx_current, double vx_desired) { static constexpr double kp = 0.5; vx_current = std::max(vx_current, 0.0); double vx_error = vx_desired - vx_current; return kp * vx_error; } // Use this to fall in behind a leading entity, settling at a target following // distance. current_distance and desired_distance are gaps (meters); vx_relative // is Hero's speed minus the entity's speed (m/s). Returns the desired ax. double fallBehindController(double current_distance, double desired_distance, double vx_relative) { static constexpr double kp_vx = 0.5; static constexpr double kp_ax = 0.2; double vx_relative_desired = kp_vx * (desired_distance - current_distance); double ax_desired = kp_ax * (vx_relative_desired - vx_relative); return -ax_desired; } ``` ## Part 1 — Lane-change feature Implement a class `LaneChangeFeature` exposing two methods plus an accessor. **(a) `void checkLaneChangeAllowedAndPopulateTargets(const State& hero, const std::vector<State>& entities)`** Decide whether changing lanes at the *current* timestep is safe. Hero's policy is: if a car ahead in the target lane is within Hero's safety buffer, Hero slows to fall in behind it and waits for the gap to open; once all entities are clear of the buffer the lane change is committed. Maintain a reasonable **longitudinal safety buffer** around Hero throughout the maneuver. - Treat an entity as **relevant** (i.e. blocking, must be tracked) when its along-the-road position falls within Hero's safety buffer — that is, the entity is currently beside Hero or close enough fore that merging now would violate the buffer. Only entities that are **ahead of or beside Hero** ($x_\text{entity} \geq x_\text{hero}$) need be considered as blocking targets; entities that have already passed Hero are not relevant. - Set the boolean member `lane_change_active_` to `true` when the lane change is safe to commit at this timestep (no relevant entity blocks the buffer), and `false` otherwise. - Populate the member `std::vector<State> relevant_targets_` with the blocking entities, so the acceleration logic can react to them. - Define and document any safety-buffer constant you introduce. A value in the range $[8, 25]$ meters is physically reasonable for highway speeds. **(b) `double calculateAx(const State& hero, double vx_speed_limit)`** Compute Hero's desired longitudinal acceleration for this timestep. - For each relevant target, use `fallBehindController` to get the acceleration that would let Hero settle behind that target at the safety buffer distance. The **gap** passed to the controller is $x_\text{entity} - x_\text{hero}$ (a positive number when the entity is ahead). - Also compute the acceleration from `velocityController` that keeps Hero at the speed limit. - Hero must stay between `vx_speed_limit` and **50% of the speed limit**: clamp the desired behavior so the commanded acceleration does not drive Hero above `vx_speed_limit` or below `0.5 * vx_speed_limit`. - Output the **most conservative** (smallest, i.e. most decelerating / least accelerating) acceleration among these candidates. - When there are no relevant targets, Hero simply tracks the speed limit (subject to the speed bounds). **(c) `bool LaneChangeActive() const`** — returns `lane_change_active_`. ## Part 2 — Simulation Implement the time-stepping loop that advances the whole scene. - Initial conditions: - Hero: `x = 30`, `vx = 15`, `ax = 0` - Entities (left lane): `{x = 35, vx = 18, ax = 0}` and `{x = 90, vx = 20, ax = 0}` - Speed limit: `vx_speed_limit = 20` (constant) - Time: start `t = 0`, end `t_end = 10`, step `dt = 0.1` - On each step: 1. Call `checkLaneChangeAllowedAndPopulateTargets` and `calculateAx` to get Hero's acceleration for this step; assign it to `hero.ax`. 2. Advance every car with the standard constant-acceleration kinematic equations over `dt`: update position from speed (and acceleration) and update speed from acceleration. The **other entities keep `ax == 0`** (constant speed); only Hero accelerates/decelerates. 3. Print the timestamp, all positions, all speeds, Hero's `ax`, and the lane-change flag. 4. If the lane change has become active, print that it was triggered and stop the simulation. ### Required output format Each timestep prints exactly one line in this form (Hero first, then each entity, in order): ``` t <t> x (<hero.x>, <entity0.x>, <entity1.x>) vx (<hero.vx>, <entity0.vx>, <entity1.vx>) ax <hero.ax> lc <0 or 1> ``` When the lane change activates, print on the following line: ``` Lane change triggered! ``` and terminate. ## Constraints & Assumptions - Use only the two provided controllers for acceleration; do not introduce a different control law. - Distances/gaps are computed from absolute `x` positions (positions are *not* stored relative to Hero). For `fallBehindController`, the gap to a leading entity is $x_\text{entity} - x_\text{hero}$ (always positive when the entity is ahead). - Only entities with $x_\text{entity} \geq x_\text{hero}$ are eligible blocking targets; use `fallBehindController` only for such entities. - Floating-point output may be printed with default formatting; exact decimal rendering is not graded, but the sequence of decisions must be correct and the lane change must trigger at an interior simulation step (not at $t = 0$). - The safety buffer is a design choice you must make explicit and document. A buffer in $[8, 25]$ m is acceptable. With the given initial conditions (entity e0 starts only 5 m ahead of Hero), e0 is inside any reasonable buffer at $t = 0$, so the lane change is blocked initially and triggers later as e0 pulls ahead — you should observe the trigger between $t \approx 1$ s and $t \approx 7$ s depending on your buffer choice.