Let's Build: Road Traffic Simulation
# 2024-08-02
# Building a prototype for a simulation of road traffic.
I have an ambitious vision of an accurate top-down simulation of road traffic. I'm talking lane changes, roundabouts, overtaking cars, egregious speed limit violations, drunk drivers, car crashes. With enough detail and accuracy along with decent user control, software like this could aid in testing the designs for new road junctions or networks and planning diversions. In this post, we'll create a prototype for such a system and just see how it goes.
First, we need to pick the tools. Since this is a graphical application JavaScript is a very good place to start, and since I'm expecting this project to get quite complex, the TypeScript typing system would be helpful for development. Due to the fact we are aiming at a large web-application with a high degree of user-interactivity, using a front-end framework is a probably sensible idea. I'll use Svelte purely because I personally find it very ergonomic and the framework I'm most familiar with.
We can scaffold a new project with Vite:
npm create vite@latest
Cars
Obviously cars are central to this program. We need a car and we need to get it moving.
First we'll build out the rough idea of a car as a new class. Since we'll work on a 2D plane with a top-down view, the car will exist in a point in space with a (x, y) coodinate. We also have the car's current velocity to hold on to. A positive for driving forwards and negative for reversing. Finally, since velocity considers direction, we need to store the what the car currently considers as 'forwards'. We can do this using a radians value or a vector, but we'll stick with radians for reasons that will later become apparent.
The car will need the ability to accelerate, brake (essentially deceleration with a cap after velocity hits zero) and steer.
type Vector = {
x: number;
y: number;
};
export default class Car {
#velocity = 0;
#direction = 0;
#position: Vector = { x: 0, y: 0 };
static #distanceUnit = 0.1;
accelerate(amount: number) {
this.#velocity += amount * Car.#distanceUnit;
}
brake(amount: number) {
if (this.#velocity === 0) {
return 0;
}
const change = this.#brakingChange(amount);
this.#velocity -= change;
return change;
}
#brakingChange(amount: number) {
let change = amount * Car.#distanceUnit;
// Limit braking if velocity hits zero...
change = Math.min(change, Math.abs(this.#velocity));
// If reversing, ensure we bring velocity closer to zero...
if (this.#velocity < 0) {
change *= -1;
}
return change;
}
steer(radians: number) {
this.#direction += radians * Car.#steerUnit;
}
}
We've stored the position as a Vector type. Confusingly, a vector can represent both a point in space as well as a direction. If we are at (1, 1) and move by a vector (2, 3), we arrive at a new point (3, 4).
We have chosen to use radians to represent the direction, but every radians value has an equivalent vector. The length of a vectors can be stretched longer or shorter by its magnitude, but vector (1, 2) and (3, 6) represent the same direction. Since we only care about the direction of this vector, we can denote the magnitude as r, and then our current radians direction of theta=0 is equivalent to x = r*cox(theta) = r and y = r*sin(theta) = 0, so (r, 0), or (1, 0) with a magnitude of 1. Essentially, our car will begin by facing towards the right.
Accelerating, steering and braking will only update the value stored for our current velocity and direction. We haven't actually gone anywhere yet. We need to be able to step through a unit of time and actually apply our currently velocity (considering its current direction) to update the car's real position on the screen.
update() {
// Calculate the translation vector...
const movement = this.#translationVector();
this.#position = Car.#sumVectors(this.#position, movement);
}
#translationVector(): Vector {
const translateX = this.#velocity * Math.cos(this.#direction);
const translateY = this.#velocity * Math.sin(this.#direction);
return { x: translateX, y: translateY };
}
static #sumVectors(a: Vector, b: Vector): Vector {
return { x: a.x + b.x, y: a.y + b.y };
}
Now we need to ground this abstract idea of a car into something the user can see. If we graphically represent the car as a div within our webpage and store a reference to the div within the model of our car, we can update the div appropriately whenever we take action on the car.
attach(element: HTMLDivElement) {
if (element instanceof HTMLDivElement) {
this.#element = element;
}
}
Now when after we have instantiated a car, we can attach it to our div. Doing it this way creates some separation between the graphical representation of the car and the way we have decided to represent the model internally; the car can still exist without requiring a html element to latch on to.
<script lang="ts">
import { onMount } from 'svelte';
import Car from './car';
let car: Car = new Car();
let carDiv: HTMLDivElement | undefined;
onMount(() => {
car.attach(carDiv);
});
</script>
<main>
<div id="car" bind:this={carDiv}></div>
</main>
<style scoped>
#car {
background: red;
width: 15px;
height: 10px;
border-radius: 2px;
}
</style>
If we launch our program with npm run dev, we can see our beautiful red car parked and stationary in the middle of the page ready to go.
We now need to adapt our code to also update the div with any animation changes (if the car has been attached to a div).
When an animation is fairly simple, CSS is often a very effective way to achieve it. Something tells me a lot of JavaScript will be running within this application. If we can hand some work over to the browser's rendering engine, it may make things easier down the line. Browsers are highly optimised for CSS animations so it will likely result in smoother animations.
We can translate the car by our position vector and then rotate by the direction with a CSS transform to move its position on the screen. The order matters here since an initial rotation will also rotate the div's x and y-axis along which we perform our translations and send our car in the wrong direction. With CSS, the transformations are relative to the div rather than external canvas or environment, meaning we are not rotating about an origin point, so this may seem counter-intuitive.
update() {
// Calculate the translation vector...
const movement = this.#translationVector();
this.#position = Car.#sumVectors(this.#position, movement);
this.#updateCarElement();
}
#updateCarElement() {
if (this.#element !== null) {
// Apply the rotation and translation...
this.#element.style.transform = Car.#translationStyle(this.#position, this.#direction);
}
}
static #translationStyle(position: Vector, direction: number) {
return `translate(${position.x}px, ${position.y}px) rotate(${direction}rad)`;
}
To make this more realistic we'll need to include the effects of engine breaking and drag on the car, otherwise the driver would accelerate to the speed limit and then never have to accelerate again. Every time we update the position of the car, we can reduce its current velocity by a small coefficient of its speed (since the faster you go the more drag you should experience).
The drag force from air resistance follows:
Drag Force Formula:
Fd = (1/2) · ρ · Cd · A · v2
Where:
Fdis the drag forceρis the air densityCdis the drag coefficientAis the frontal area of the carvis the velocity of the car
But to make things simpler we can lump together the air density, drag coefficient and frontal area all into a single drag coefficient value stored against the car.
We also have engine braking, which I'm just going to assume is a constant.
Finally as F = m · a we just need to divide by the mass of the car to get its deceleration.
update() {
// Apply the drag to slow down the car...
this.#velocity -= Math.min(this.#dragDeceleration, this.#velocity);
// Calculate the translation vector...
const movement = this.#translationVector();
this.#position = Car.#sumVectors(this.#position, movement);
this.#updateCarElement();
}
get #dragDeceleration() {
return this.#drag / this.#mass;
}
get #drag() {
return this.#airResistance + this.#engineBraking;
}
get #airResistance() {
return this.#dragCoefficient * Math.pow(this.#velocity, 2);
}
Let's Move
Now a car isn't much without a driver. Cars hold the potential to move but drivers make them move.
A driver is the brains behind the operation. A driver will have a car, and be able to control it using the API exposed by the car (accelerate, brake and steer).
import Car from "./car";
export default class Driver {
#car: Car = new Car();
get car() {
return this.#car;
}
nextMove() {
this.randomSteer();
this.randomAccelerate();
this.car.update();
}
randomSteer() {
const p = Math.random();
// 70% chance of steering...
if (p < 0.7) {
// Randomly steer left or right by a small amount...
const scale = 0.1;
const amount = (Math.random() - 0.5) * scale;
this.steer(amount);
}
}
randomAccelerate() {
if (this.car.velocity > 0.5) {
this.brake(0.3);
} else {
this.accelerate(0.5);
}
}
accelerate(amount: number) {
this.#car.accelerate(amount);
}
brake(amount: number) {
this.#car.brake(amount);
}
steer(amount: number) {
this.#car.steer(amount);
}
}
<script lang="ts">
import Driver from './driver';
let environment: HTMLDivElement;
const drivers: Driver[] = [];
onMount(() => {
for (let i = 0; i < 5; i++) {
createDriver();
}
});
function createDriver() {
const driver = new Driver();
const element = document.createElement("div");
element.id = `car-${drivers.length}`;
element.classList.add("car");
driver.car.attach(element);
environment.appendChild(element);
drivers.push(driver);
setInterval(() => {
driver.nextMove(car);
}, 10);
}
</script>
<main>
<div class="container">
<div bind:this={environment}></div>
</div>
</main>
<style scoped>
/* Must be global as cars are created dynamically and not part of this component's DOM tree */
:global(.car) {
position: absolute;
width: 15px;
height: 10px;
border-radius: 3px;
top: 0;
}
.container {
position: relative;
text-align: left;
}
</style>
We have moving cars! With no real aim or sense of purpose... they wander across the canvas like ants, off into the distance.
If we change the function responsible for steering to take a random left turn 70% of the time instead, we get a lovely koi pond effect :)
The driver's nextMove() method is where we'll need to focus our work in order to improve how the cars behave. We'll need to build this up over time to consider a wide range of factors such as the current velocity the driver's driving ability (speed, steering), driving style (cautious, heavy footed?), driver state (tiredness, eyesight, alertness, intoxication), potentially previous actions taken by the driver (if you have just turned the steering wheel slightly left, changes are your next move will not be a sudden extreme turn to the right - although I've been in plenty of Ubers before). To avoid pricey insurance premiums, drivers will need to do their best to avoid hitting other cars. Once roads are included the driver will need to do all this while following the direction of the road, following speed limits, braking at junctions, turning on to new roads, and changing lanes. It's a lot to ask of our drivers, but I'm sure we can get there. This is sounding more like a 5-part series!
We can also adjust features of the car. Not all cars are equal, some are better than others with better acceleration, top speeds, handling etc. Not to mention aesthetic changes like sizes and colours.
Roads!
Drawing simple lines to the screen is something a html canvas does very well.
const canvas = document.getElementById("canvas");
const ctx = canvas.getContext("2d");
// Start a new path...
ctx.beginPath();
ctx.moveTo(0, 0);
ctx.lineTo(300, 150);
// Draw the path...
ctx.stroke();
Each driver will need to be able to observe the current road ahead of them to make decisions for steering and acceleration, or even when to change from one road to another. We will need to keep track of every road we create in order for it to be accessible to drivers later on.
We can capture the idea of a road within a class, and give it the ability to be drawn to a canvas. Then we can build up a list of roads we can keep to hand. It also means if we ever need to wipe the canvas clean, we can very easily redraw each road.
import type { Vector } from "./vector";
export default class Road {
#start: Vector;
#end: Vector;
constructor(start: Vector, end: Vector) {
this.#start = start;
this.#end = end;
}
draw(ctx: CanvasRenderingContext2D) {
ctx.beginPath();
ctx.moveTo(this.#start.x, this.#start.y);
ctx.lineTo(this.#end.x, this.#end.y);
ctx.stroke();
}
get start() {
return this.#start;
}
get end() {
return this.#end;
}
}
Each car will need to store the road it is currently 'on' so its driver can follow it. The driver can access this information through the car they have. To keep things simple, we can set the car to be considered 'on' the road with the nearest start or end point. Then the driver has somewhere to aim for.
setRoad(roads: Road[]) {
this.#road = this.#nearestRoad(roads);
}
#nearestRoad(roads: Road[]) {
const best: { road: Road | null, distance: number } = {
road: null,
distance: Infinity,
};
for (const road of roads) {
const distance = Math.min(this.distanceTo(road.start), this.distanceTo(road.end));
if (distance < best.distance) {
best.road = road;
best.distance = distance;
}
}
return best.road;
}
distanceTo(position: Vector) {
const dx = this.#position.x - position.x;
const dy = this.#position.y - position.y;
return Math.sqrt(dx * dx + dy * dy);
}
Over in our Svelte component, once we have created all the roads we need, we can then tell the car initialise its road with the nearest at the point of creation and continue to refresh the road choice after every movement to drive from one road to the next.
<script lang="ts">
import { onMount } from "svelte";
import { Driver } from "./driver";
import { Road } from "./road";
import type { Vector } from "./vector";
let canvas: HTMLCanvasElement;
const drivers: Driver[] = [];
const roads: Road[] = [];
onMount(() => {
const ctx = canvas.getContext("2d");
if (ctx === null) {
throw new Error("Could not get 2d context");
}
createRoad(ctx, { x: 100, y: 100 }, { x: 550, y: 900 });
createDriver();
});
function createRoad(
ctx: CanvasRenderingContext2D,
start: Vector,
end: Vector
) {
const road = new Road(start, end);
roads.push(road);
road.draw(ctx);
}
function createDriver() {
const driver = new Driver();
// Assign car to the nearest road...
driver.car.setRoad(roads);
// Create a new car element...
const element = document.createElement("div");
element.id = `car-${drivers.length}`;
element.style.background = getCarColour();
element.classList.add("car");
// Attach the new driver's car to this element for them to control...
driver.car.attach(element);
// Add the car element to the canvas to be visible...
canvas.appendChild(element);
drivers.push(driver);
setInterval(() => {
driver.nextMove();
// In case we have reached the end of the road, move to the next nearest road...
driver.car.setRoad(roads);
}, 10);
}
const getCarColour = (() => {
const colours = ["red", "blue", "green", "yellow", "purple"];
return () => {
return colours[Math.floor(Math.random() * colours.length)];
};
})();
</script>
<main>
<div class="container">
<canvas width="1000" height="1000" bind:this={canvas}></canvas>
</div>
</main>
<style scoped>
:global(.car) {
position: absolute;
width: 15px;
height: 10px;
border-radius: 3px;
top: 0;
}
.container {
position: relative;
text-align: left;
}
canvas {
margin: 0;
}
</style>
All that's left is to do is improve our driver's nextMove() so that they steer towards the road that their car is currently on.
There are two sides to this, however:
- If the car is far away from the road, the driver needs to drive straight towards the nearest point on that road.
- If the car is already 'on' the road, the driver need to drive towards a point further down along the road in the direction the car is facing.
For this we're going to have to give our driver a splash of intelligence.
import Car from "./car";
import Intelligence from "./intelligence";
export class Driver {
#car: Car = new Car();
#intelligence: Intelligence = new Intelligence();
// ...
nextMove() {
const { steer, accelerate, brake } = this.#intelligence.nextMove(this);
this.car.steer(steer);
this.car.accelerate(accelerate);
this.car.brake(brake);
this.car.update();
}
// ...
}
import type Driver from "./driver";
import Road from "./road";
import {
addVectors,
dotProduct,
magnitude,
multiplyVectorByScalar,
normalize,
subtractVectors,
crossProduct,
type Vector,
} from "./vector";
type Move = {
steer: number;
accelerate: number;
brake: number;
};
export default class Intelligence {
nextMove(driver: Driver) {
const steer = this.#towardsNearestRoad(driver.car);
const { accelerate, brake } = this.#controlSpeed(driver.car, 0.3);
const move: Move = { steer, accelerate, brake };
return move;
}
#towardsNearestRoad(car: Car) {
const road = car.road;
if (road === null) {
return 0;
}
const { position, directionVector } = car;
// Get the nearest point on the line road and its distance from the car...
const nearestPoint = this.#nearestPointOnLineSegment(
position,
road.start,
road.end
);
const distanceToNearestPoint = magnitude(
subtractVectors(nearestPoint, position)
);
// If the point is near to us, instead take a point further down the road...
const targetPoint =
distanceToNearestPoint < 20
? this.#furthestPointWithinRadius(road, position, directionVector, 35)
: nearestPoint;
// Get the directional vector for this target point...
const shortestPath = subtractVectors(targetPoint, position);
// Cross product gives us a good signal for steering...
const steerSignal = crossProduct(directionVector, shortestPath);
const tolerance = 0.05;
if (Math.abs(steerSignal) < tolerance) {
// Do not steer...
return 0;
}
const steerIntensity = 0.01;
if (steerSignal < 0) {
// Steering left...
return -steerIntensity;
} else {
// Steering right...
return steerIntensity;
}
}
#nearestPointOnLineSegment(
position: Vector,
lineStart: Vector,
lineEnd: Vector
) {
const AB = subtractVectors(lineEnd, lineStart);
const AP = subtractVectors(position, lineStart);
const dotProd = dotProduct(AP, AB);
const lengthSq = dotProduct(AB, AB);
let t = dotProd / lengthSq;
t = Math.max(0, Math.min(1, t)); // Clamping t to the line segment
return addVectors(lineStart, multiplyVectorByScalar(AB, t));
}
#furthestPointWithinRadius(
road: Road,
position: Vector,
direction: Vector,
radius: number
) {
const AB = subtractVectors(road.end, road.start);
const directionNormalized = normalize(direction);
const best: { point: Vector; distance: number } = {
point,
distance: 0,
};
// Sample points along the road at regular intervals...
for (let t = 0; t <= 1; t += 0.05) {
const pointOnRoad = addVectors(road.start, multiplyVectorByScalar(AB, t));
const vectorToPoint = subtractVectors(pointOnRoad, position);
const distance = magnitude(vectorToPoint);
// Check if the point is within the search radius...
// and if the point is in the direction of the car...
// and if the point is the furthest found so far...
if (
distance <= radius &&
dotProduct(directionNormalized, vectorToPoint) > 0 &&
distance > best.distance
) {
// Store the furthest recorded point...
best.distance = distance;
best.point = pointOnRoad;
}
}
return best.point;
}
#controlSpeed(car: Car, speedLimit: number) {
if (car.velocity > speedLimit) {
return { accelerate: 0, brake: 0.3 };
} else if (car.velocity < speedLimit) {
return { accelerate: 0.5, brake: 0 };
}
return { accelerate: 0, brake: 0 };
}
}
It's a miracle. Our car materialises into the world and heads straight towards the road. When it gets there it starts following the straight path across the canvas. Once it runs off the end of the road, it eventually does a U-turn.
Finding bugs will be much quicker if we add some interactivity and have the ability to create new roads dynamically with the mouse. We can set up an event listener to record the mouse position for every click and release, and spawn a new road from that.
onMount(() => {
// ...
const { handleMouseDown, handleMouseUp } = setupMouseHandler(ctx);
canvas.addEventListener("mousedown", handleMouseDown);
canvas.addEventListener("mouseup", handleMouseUp);
// ...
});
function setupMouseHandler(ctx: CanvasRenderingContext2D) {
let startMouseX: number;
let startMouseY: number;
const handleMouseDown = (event: MouseEvent) => {
startMouseX = event.clientX;
startMouseY = event.clientY;
};
const handleMouseUp = (event: MouseEvent) => {
const endMouseX = event.clientX;
const endMouseY = event.clientY;
createRoad(
ctx,
{ x: startMouseX, y: startMouseY },
{ x: endMouseX, y: endMouseY }
);
};
return { handleMouseDown, handleMouseUp };
}
Bézier Roads
Roads are very rarely straight. We need to give our drivers a challenge.
Bézier curves are proabably the best way for a computer to represent a curved line. On top of a start and end point, all we need are two additional points floating in space that control the curvature of the line.
Canvas offers a Bézier curves, and they're very easy to create.
const canvas = document.getElementById("canvas");
const ctx = canvas.getContext("2d");
// Define the points...
const start = { x: 50, y: 20 };
const end = { x: 250, y: 100 };
const cp1 = { x: 230, y: 30 };
const cp2 = { x: 150, y: 80 };
// Cubic Bézier curve...
ctx.beginPath();
ctx.moveTo(start.x, start.y);
ctx.bezierCurveTo(cp1.x, cp1.y, cp2.x, cp2.y, end.x, end.y);
// Draw the path...
ctx.stroke();
We'll have to adapt our road to accomodate these extra control points.
import type { Vector } from "./vector";
export class Road {
#start: Vector;
#end: Vector;
#control1: Vector | null;
#control2: Vector | null;
constructor(
start: Vector,
end: Vector,
control1: Vector | null = null,
control2: Vector | null = null
) {
this.#start = start;
this.#end = end;
this.#control1 = control1;
this.#control2 = control2;
}
draw(ctx: CanvasRenderingContext2D) {
ctx.beginPath();
ctx.moveTo(this.#start.x, this.#start.y);
if (this.#control1 !== null && this.#control2 !== null) {
ctx.bezierCurveTo(
this.#control1.x,
this.#control1.y,
this.#control2.x,
this.#control2.y,
this.#end.x,
this.#end.y
);
} else {
ctx.lineTo(this.#end.x, this.#end.y);
}
ctx.stroke();
}
get start() {
return this.#start;
}
get end() {
return this.#end;
}
get control1() {
return this.#control1;
}
get control2() {
return this.#control2;
}
isBezier(): this is { control1: Vector; control2: Vector } {
return this.#control1 !== null && this.#control2 !== null;
}
}
We'll have to adapt our code to handle steering in two ways:
- When the car is searching for the nearest point on the road it is currently set to
- When we find the car is actually on the road, finding a point further down the road in the direction the car is facing
Both of these sections involve sampling points along the path of the road. Previously, this was pretty straightforward, but now we need to find Bézier points.
Here is our function for determining the steer value our driver should take:
#towardsNearestRoad(car: Car) {
const road = car.road;
if (road === null) {
console.log(`Car ${car.id}: Road is null`)
return 0;
}
const { position, directionVector } = car;
const nearestPoint = this.#nearestPointOnRoad(position, road);
if (nearestPoint === null) {
return 0;
}
const distanceToClosestPoint = magnitude(subtractVectors(nearestPoint, position));
const targetPoint = distanceToClosestPoint < Intelligence.targetRoadDistance ?
this.#furthestPointWithinRadiusOnRoad(road, position, directionVector, Intelligence.furthestPointRadius) :
nearestPoint;
const shortestPath = subtractVectors(targetPoint, position);
const steerSignal = crossProduct(directionVector, shortestPath);
if (Math.abs(steerSignal) < Intelligence.steerTolerance) {
return 0;
}
return steerSignal < 0 ? -Intelligence.steerIntensity : Intelligence.steerIntensity;
}
We need to update #nearestPointOnRoad() and #furthestPointWithinRadiusonRoad() to work correctly if the road is curved.
For both parts, we will need to sample along the curve, calculating the Bézier point at each step t using the Bézier curve formula.
#bezierPoint(t: number, lineStart: Vector, lineEnd: Vector, control1: Vector, control2: Vector) {
// Cubic Bézier curve formula
const x = Math.pow(1 - t, 3) * lineStart.x +
3 * Math.pow(1 - t, 2) * t * control1.x +
3 * (1 - t) * Math.pow(t, 2) * control2.x +
Math.pow(t, 3) * lineEnd.x;
const y = Math.pow(1 - t, 3) * lineStart.y +
3 * Math.pow(1 - t, 2) * t * control1.y +
3 * (1 - t) * Math.pow(t, 2) * control2.y +
Math.pow(t, 3) * lineEnd.y;
return { x, y };
}
First getting the nearest point on the road we are assigned to.
#nearestPointOnRoad(position: Vector, road: Road) {
if (road.isBezier()) {
return this.#nearestPointOnBezierCurve(position, road.start, road.end, road.control1, road.control2)
} else {
return this.#nearestPointOnLineSegment(position, road.start, road.end);
}
}
#nearestPointOnBezierCurve(position: Vector, lineStart: Vector, lineEnd: Vector, control1: Vector, control2: Vector) {
const best: { point: Vector | null, distance: number } = {
point: null,
distance: Infinity
}
// Sample points along the curve at regular intervals...
for (let t = 0; t <= 1; t += Intelligence.stepSize) {
const pointOnCurve = this.#bezierPoint(t, lineStart, lineEnd, control1, control2);
const distance = distanceSquared(pointOnCurve, position);
if (distance < best.distance) {
best.distance = distance;
best.point = pointOnCurve;
}
}
return best.point;
}
Next getting the point further along down the road than our current position.
#furthestPointWithinRadiusOnRoad(road: Road, position: Vector, direction: Vector, radius: number) {
const directionNormalized = normalize(direction);
const best: { point: Vector, distance: number } = {
point,
distance: 0
};
// Sample points along the road at regular intervals...
for (let t = 0; t <= 1; t += Intelligence.stepSize) {
// Get the point on the road at step t whether curved or straight...
const pointOnRoad = this.#pointOnRoad(road, t);
const vectorToPoint = subtractVectors(pointOnRoad, position);
const distance = magnitude(vectorToPoint);
// Check if the point is within the radius...
// and if the point is in the direction of the car...
// and if the point is the furthest found so far...
if (
distance <= radius
&& dotProduct(directionNormalized, vectorToPoint) > 0
&& distance > best.distance
) {
best.distance = distance;
best.point = pointOnRoad;
}
}
return best.point;
}
#pointOnRoad(road: Road, t: number) {
if (road.isBezier()) {
return this.#bezierPoint(t, road.start, road.end, road.control1, road.control2)
} else {
const AB = subtractVectors(road.end, road.start);
return addVectors(road.start, multiplyVectorByScalar(AB, t));
}
}
Things are getting complex pretty quickly. To give us some better insight into what's actually happening when we're running our program, with every car position update, I'll draw a green line from the car to the point on the road that the driver is aiming for (targetPoint). I'll also blip a red dot at the point we consider to be the nearest point on the road to each car (nearestPoint).
A Quick Clean Up
Obviously, we can find plenty of problems with this current version of the program. That's the beauty of iterative design. We've reached a good milestone to clean up some minor but clear problems with our current iteration.
We've been focusing on getting things working and correct before focusing on performance. Which is the correct order. For the time being it's running pretty smooth. We can profile our code later on and redesign some slower sections. I have a feeling that sampling points across the road to find the nearest point could be optimised greatly.
First, let's address some obvious problems.
An Absolute Car Crash
The first problem you may have noticed: Cars can overlap. Driving right through each other. In terms of realism, this is pretty bad.
Drivers need to be aware of other drivers and feed this information into our intelligence system.
nextMove(drivers: Driver[]) {
// When the driver takes their next move, provide a list of all drivers (including this one)
// We also need to make sure we identify ourselves
const { steer, accelerate, brake } = this.#intelligence.nextMove(this, drivers);
this.car.steer(steer);
this.car.accelerate(accelerate);
this.car.brake(brake);
this.car.update();
}
Then, within our intelligence module, we need to check the position of all other cars relative to our own car when we're deciding our acceleration. Cars are contained within our driver object, so we can grab these as we need.
The direction of our car is also a consideration; we would only need to brake if we are facing another car, and the distance between us is too close.
#controlSpeed(car: Car, cars: Car[], speedLimit: number) {
if (this.#headingTowardsOtherCar(car, cars)) {
// Slam on the brakes!
console.log(`Car ${car.id} braking to avoid crash`)
return { accelerate: 0, brake: 10 };
}
if (car.velocity > speedLimit) {
return { accelerate: 0, brake: 0.3 };
} else if (car.velocity < speedLimit) {
return { accelerate: 0.5, brake: 0 };
}
return { accelerate: 0, brake: 0 };
}
#headingTowardsOtherCar(car: Car, cars: Car[]) {
for (const otherCar of cars) {
if (otherCar.id === car.id) {
continue;
}
const vectorToDriver = subtractVectors(otherCar.position, car.position);
const distance = magnitude(vectorToDriver);
// If distance is too close and facing towards the car...
if (distance < 20 && dotProduct(car.directionVector, vectorToDriver) > 0) {
return true;
}
}
return false;
}
Changing Roads
Especially with longer roads, cars will suddenly abandon their current road in favour of another. This is because when we assign a car to the nearest road, we are only considering a road's start and end points. Mid-way through the current road, a car can build quite some distance from its starting point. We could do with changing to a method that samples points spanning the entire road.
#nearestRoad(roads: Road[]) {
const best: { road: Road | null, distance: number } = {
road: null,
distance: Infinity,
};
for (const road of roads) {
// Sample points along the road at regular intervals...
for (let t = 0; t <= 1; t += Intelligence.stepSize) {
const pointOnRoad = road.pointOnRoad(t);
const distance = this.distanceTo(pointOnRoad);
if (distance < best.distance) {
best.road = road;
best.distance = distance;
}
}
}
return best.road;
}
Stuck
After updating our drivers to brake naively to avoid collisions, an unfortunate situation is now possible. If two drivers ever drive into each other head on, they will both slam on the brakes, and just sit there. We need some way to recover from this. The drivers could also steer? But what if they steer the same way?
If this happened in real life, we would probably slap it into reverse to build some space, and then steer away from the other car. We've not even used the reverse gear yet. Let's set this up.
In order to recover from a situation like this, we need to be able to first detect when it has occurred.
Driving is two-way process. The driver inputs their actions into the car, the car feeds back information to the driver in the form of speed, engine sound, steering movement, and the driver can decide what to do next. In situations where the car isn't behaving as expected based on previous experience, e.g. skidding on ice, heavy steering, bumpy ride, slow acceleration, these signs are particularly important.
For a driver to know when the car is in this situation, they would need to be able to monitor the car and detect when their car hasn't moved in a while, even though their actions have been trying to get it moving. Our drivers need some memory of what they have been doing so they can tell if the car isn't behaving as expected.
We can create an new structure to store the last N number of actions taken by a driver in a circular array.
enum ActionType {
Acceleration,
Steering,
}
type ActionHistoryEpoch = {
type: ActionType;
value: number;
result: number;
};
export class ActionHistory {
#history: ActionHistoryEpoch[];
#index: number = 0;
constructor(size: number = 50) {
if (size <= 0) {
throw new Error("Size must be greater than 0");
}
this.#history = new Array(size);
}
get size() {
return this.#history.length;
}
add(type: ActionType, value: number, result: number) {
this.#history[this.#index] = { type, value, result };
this.#increment();
}
#increment() {
this.#index = (this.#index + 1) % this.#history.length;
}
getLastAction(n: number = 1): ActionHistoryEpoch {
const size = this.#history.length;
const lastIndex = (this.#index - n + size) % size;
return this.#history[lastIndex];
}
}
Then our drivers can record any actions they take within their recent memory. Whenever they take an action we can add another action to memory, including what action was taken (acceleration/deceleration or steering) the amount attempted, as well as what actually happened which we recieved as feedback from using the car.
export default class Driver {
#car: Car = new Car();
#memory: ActionHistory = new ActionHistory();
// ...
accelerate(amount: number) {
const changed = this.car.accelerate(amount);
this.#memory.add(ActionType.Acceleration, amount, changed);
}
brake(amount: number) {
const changed = this.car.brake(amount);
this.#memory.add(ActionType.Acceleration, -amount, -changed);
}
steer(amount: number) {
const changed = this.car.steer(amount);
this.#memory.add(ActionType.Steering, amount, changed);
}
}
Now based on this action history of the driver, we need to be able infer whether the driver is stuck. Off the top of my head, I can think of two states we could monitor for that would make it pretty likely the driver is stuck:
- If the driver is trying to accelerate, but the car isn't moving
- If the driver is caught continuously braking
#driverStuck(driver: Driver) {
return this.#failingToAccelerate(driver) || this.#continuouslyBraking(driver);
}
#failingToAccelerate(driver: Driver) {
const maxFailedAccelerations = 5;
let failedAccelerations = 0;
for (let i = 0; i < driver.memory.size; i++) {
const action = driver.memory.getLastAction(i);
if (action === undefined) {
continue;
}
// Successful acceleration found
if (this.#successfulAcceleration(action)) {
return false;
}
// Record failed acceleration
if (this.#failedAcceleration(action)) {
failedAccelerations++;
}
// Driver is stuck if their last 5 attempts to accelerate failed
if (failedAccelerations > maxFailedAccelerations) {
console.log(`Car ${driver.car.id} is failing to accelerate`);
return true;
}
}
return false;
}
#failedAcceleration(action: ActionHistoryEpoch) {
return action.type === ActionType.Acceleration && action.value > 0 && action.result === 0;
}
#successfulAcceleration(action: ActionHistoryEpoch) {
return action.type === ActionType.Acceleration && action.value > 0 && action.result > 0;
}
#continuouslyBraking(driver: Driver) {
for (let i = 0; i < driver.memory.size; i++) {
const action = driver.memory.getLastAction(i);
if (action === undefined || !this.#brakingAction(action)) {
return false;
}
}
console.log(`Car ${driver.car.id} is continuously braking`);
return true;
}
#brakingAction(action: ActionHistoryEpoch) {
return action.type === ActionType.Acceleration && action.value < 0;
}
We're ignoring a third option, the driver starts idelling the car. They remain stationary and don't attempt to steer or accelerate or brake. They are still taking actions on the car, but always posting zero values. We haven't created a flow of execution that would produce this result, and it's unlikely we would ever intend to. But the more I thought about it the more I thought it wouldn't hurt to prepare for it. In this scenario we need to make sure we check the car is actually stationary, since it would be reasonable to idle car when travelling at the speed limit for example.
#driverStuck(driver: Driver) {
return driver.car.velocity === 0 && (this.#failingToAccelerate(driver) || this.#continuouslyBraking(driver) || this.#idelling(driver));
}
// ...
#idelling(driver: Driver) {
for (let i = 0; i < driver.memory.size; i++) {
const action = driver.memory.getLastAction(i);
if (action === undefined || !this.#idleAction(action)) {
return false;
}
}
console.log(`Car ${driver.car.id} is idling`);
return true;
}
#idleAction(action: ActionHistoryEpoch) {
return action.value === 0;
}
Now we have this all together, we can use this driverStuck to check for this problem when controlling speed. If we find it to be a problem, we can attempt to reverse to gain some distance from the car in front.
#controlSpeed(driver: Driver, drivers: Driver[], speedLimit: number) {
// Check if driver is unable to move...
if (this.#driverStuck(driver)) {
console.log(`Car ${driver.car.id} is stuck, attempting to reverse`);
// Check for any cars immediately behind us before reversing...
if (this.#headingTowardsOtherDrivers(driver, drivers, true)) {
console.log(`Car ${driver.car.id} is stuck, unable to reverse`);
return { accelerate: 0, brake: 0 }; // Forced to wait for other cars to move
}
return { accelerate: -0.2, brake: 0 };
}
// Check if driving into another car...
const reversing = driver.car.velocity < 0;
if (this.#headingTowardsOtherDrivers(driver, drivers, reversing)) {
// Slam on the brakes!
console.log(`Car ${driver.car.id} braking to avoid crash`);
return { accelerate: 0, brake: 10 };
}
if (driver.car.velocity > speedLimit) {
return { accelerate: 0, brake: .3 };
} else if (driver.car.velocity < speedLimit) {
return { accelerate: 0.5, brake: 0 };
}
return { accelerate: 0, brake: 0 };
}
#headingTowardsOtherDrivers(driver: Driver, drivers: Driver[], reversing: boolean = false) {
const car = driver.car;
const cars = drivers.map(d => d.car);
const { position, directionVector } = car;
for (const otherCar of cars) {
if (otherCar.id === car.id) {
continue; // Skip if the same car
}
const vectorToDriver = subtractVectors(otherCar.position, position);
const distance = magnitude(vectorToDriver);
const dp = dotProduct(directionVector, vectorToDriver);
const inDrivingDirection = reversing ? dp > 0 : dp;
if (distance < 20 && inDrivingDirection) {
return true;
}
}
return false;
}
Svelte-y
Our main App.svelte component isn't very svelte. We're using the standard JavaScript document.createElement() and manually tagging it with attributes instead of leveraging the powerful reactivity features that makes Svelte great. We can separate the driver into its own Svelte component. When we add a new driver to our list, Svelte can render them onto the screen for us.
<script lang="ts">
import { onMount } from "svelte";
import Driver from "./lib/driver";
import DriverElement from "./lib/Driver.svelte";
import Road from "./lib/road";
import RoadElement from "./lib/Road.svelte";
import type { Vector } from "./lib/vector";
import { dimensions } from "./lib/consts";
let canvas: HTMLCanvasElement;
let ctx: CanvasRenderingContext2D;
let drivers: Driver[] = [];
let roads: Road[] = [];
onMount(() => {
ctx = getContext();
const { handleMouseDown, handleMouseUp } = setupMouseHandler();
canvas.addEventListener("mousedown", handleMouseDown);
canvas.addEventListener("mouseup", handleMouseUp);
createRoad({ x: 100, y: 100 }, { x: 550, y: 900 });
createRoad(
{ x: 900, y: 550 },
{ x: 200, y: 200 },
{ x: 500, y: 500 },
{ x: 100, y: 200 },
);
createRoad({ x: 1200, y: 500 }, { x: 100, y: 600 });
for (let i = 0; i < 1; i++) {
createDriver();
setTimeout(() => {
createDriver();
}, 1000);
}
});
function getContext() {
const ctx = canvas.getContext("2d");
if (ctx === null) {
throw new Error("Could not get 2d context");
}
return ctx;
}
function setupMouseHandler() {
let startMouseX: number;
let startMouseY: number;
const handleMouseDown = (event: MouseEvent) => {
startMouseX = event.clientX;
startMouseY = event.clientY;
};
const handleMouseUp = (event: MouseEvent) => {
const endMouseX = event.clientX;
const endMouseY = event.clientY;
createRoad({ x: startMouseX, y: startMouseY }, { x: endMouseX, y: endMouseY });
};
return { handleMouseDown, handleMouseUp };
}
function createRoad(start: Vector, end: Vector, control1?: Vector, control2?: Vector) {
const road = new Road(start, end, control1, control2);
road.draw(ctx);
roads = [...roads, road];
}
function createDriver() {
const driver = new Driver();
drivers = [...drivers, driver];
}
</script>
<main>
<div class="container">
<canvas
width={dimensions.x}
height={dimensions.y}
bind:this={canvas}
>
</canvas>
{#each drivers as driver}
<DriverElement {driver} {drivers} {roads} />
{/each}
</div>
</main>
<style scoped>
.container {
position: relative;
text-align: left;
}
canvas {
margin: 0;
}
</style>
<script lang="ts">
import { onMount } from "svelte";
import type Driver from "./driver";
import type Road from "./road";
let element: HTMLDivElement;
// Random color selection for each car
const colors = ["red", "blue", "green", "yellow", "purple"];
const color = colors[Math.floor(Math.random() * colors.length)];
onMount(() => {
driver.car.setRoad(roads);
driver.car.attach(element);
startMovement();
});
function startMovement() {
setInterval(() => {
driver.nextMove(drivers);
driver.car.setRoad(roads);
}, 10);
}
export let driver: Driver, drivers: Driver[], roads: Road[];
</script>
<div bind:this={element} style={`background: ${color}`} class="car"></div>
<style scoped>
.car {
position: absolute;
width: 15px;
height: 10px;
border-radius: 3px;
top: 0;
}
</style>
Now whenever a new Driver object is added to the drivers list, Svelte will automatically create a new DriverElement component, which contains our driver's div and everything needed to get the driver moving.
{#each drivers as driver}
<DriverElement {driver} {drivers} {roads} />
{/each}
Svelte detects the need to re-render this loop via assignment to any variables involved, which is why we must perform a full re-assignent to drivers with drivers = [...drivers, driver] instead of drivers.push(driver) in order to trigger this.
Finally, we can make the animations slightly smoother by using requestAnimationFrame instead of setInterval, which is better optimsed for UI updates. It will align our animations with the browsers refresh rate, usually 60fps (equivalent to 16.7ms intervals). This means we don't have to set an arbitrary interval value that could cause unnecessary repaints. If we hand this responsibility back to the browser, the speed of a car is now solely controllable by its velocity, which moves us in the direction of simplicity.
If we also keep track of the ID returned from requestAnimationFrame, we can cancel it if the component is ever destroyed, avoiding a potential memory leak.
onMount(() => {
driver.car.setRoad(roads);
driver.car.attach(element);
element.style.backgroundColor = color;
startMovement();
});
function startMovement() {
const move = () => {
driver.nextMove(drivers);
driver.car.setRoad(roads);
animationId = requestAnimationFrame(move);
};
animationId = requestAnimationFrame(move);
}
let animationId: number;
onDestroy(() => cancelAnimationFrame(animationId));
This feels like a good place to stop off. We'll pick this back up in a future post for further improvements and features.
This project is hosted on GitHub. The code is by no means perfect, if you think you can improve on it, you're probably right!
When tackling a challenging problem with lots of moving parts (sometimes literally), it's easy to quickly feel overwhelmed. The classic answer is to break the problem down into smaller problems, and solve them one at a time. But it really does work!
Before we started, we knew we had to have some kind of window that the user could open on their machine and run the program. For this we relied on a browser. This could have easily been a native desktop app, an iOS or Android app, or even run in the terminal!
After choosing the browser as the platform to carry our program, since our program is graphical, we needed to find some way to display our graphical elements on the screen. The HTML canvas is very useful for drawing custom shapes onto the screen, such as roads.
JavaScript is the sane choice when working in a browser, but it's also very good at manipulating graphical elements and updating the state of the canvas. It's very expressive and can represent everything we could ever need to represent about a cars, roads, drivers etc and store the current state of the simulation. We took this one step further and included type-safety with TypeScript.
Svelte is arguably not needed here, but it makes the development process more ergonomic. At the moment, it has made it easier to grab and maniuplate the canvas element as needed and helps us package the canvas into an abstract component that makes the code easier to navigate. As the project continues to grow in size and get more complex, it will likely pay dividens.
The more projects you start, the easier this decision process will be, and it won't feel so daunting.
Here we've used HTML, TypeScript & Svelte, but it doesn't matter about the technology stack. Using a different stack would not make the final solution any better or worse. Usually this decision vastly outweighted by personal preference, the current codebase or team conventions. If you are lucky enough to have a choice, use what makes you feel comfortable.
Happy coding 👋