Watch cars evolve using genetic algorithm | Hacker News Reader

Watch cars evolve using genetic algorithm

rednuht.org

484 pointsmemalign73 comments

I wrote the original version of this nearly 20 years ago. Cool to see it still pop up here from time to time.

Still runs in the browser thanks to Ruffle:

https://peteshadbolt.co.uk/posts/ga/

On Firefox here, the "Save Local Population" option seems to crash. Any idea why that might be happening? (Amazing site btw - every time it pops up I end up spending much too long with it).

Where do you see the "Save Local Population" option? When you say it "seems to crash", do you mean Firefox or the Flash animation?

What would be the consequences of adding a hitbox on the structure (or springs?) as well, as opposed to having it only on the load?

Do you have some examples of results when running this for a few days?

Or perhaps, 20 years? ;-)

Or another civilization wrote it a few, billion years ago. We might see the results fly by our planet this week.

I remember running this in the background any time I was in the computer lab at school. Thanks for making this back in the day :).

There were a few genetic algorithm "polygons approximate picture" pages back in that era as well.

I worked on Adobe’s Flash Player team at that time and I remember using your Flash movie as a test case. :)

Wow, thank you for sharing this. Means a lot

As internet distractions go, the original was one of the most memorable I ever came across. A friend and I used to leave them running over lunch and see who was winning when we got back. Thanks for the fun :-)

Thanks for writing this all those years ago. It made for a fun demonstration when I was learning genetic algos in college.

It seems to always get into a rut where one design lucks out and dominates generation after generation, with no mutations producing anything even close to working. Like, the top ten don't change after hundreds of generations. Maybe this is just an attribute of genetic algorithms. They quickly zero in on something kind of good, and then get stuck at this local maxima. Or maybe I need to just play around with the Mutation Rate and Mutation Size settings.

Sounds like you're running with a single elite clone. That's a really bad idea in genetic heuristics for exactly the phenomenon you mention.

Is the correct number 0 or >1?

Note my use of the term "heuristic" and not "algorithm." There is not a correct number. The correct approach is to fiddle with the parameters; record good populations; occasionally restart from scratch... we call this "hyperparameter tuning" to make ourselves feel better about the process.

>Maybe this is just an attribute of genetic algorithms

It happened to crocodiles and it could happen to you too.

Crabs too https://en.m.wikipedia.org/wiki/Carcinisation

More improvement needs wild environment changes.

If you keep going long enough they'll probably turn into crabs.

In general, one should keep the mutation rate really low to allow the population slowly change over time. High mutation rate will lead to local optima quickly but also very hard to get out. Low mutation rate will require significant more generations but in general result in better adaptation.

It seems like more should change than just the shape. I'd wager that a slower car with more power may be less likely to get stuck in ruts. But it seems that the power and speed don't vary, just (barely, after a few generations) the shape.

Edit, I scrolled down and it covers the genome:

• Shape (8 genes, 1 per vertex)

• Wheel size (2 genes, 1 per wheel)

• Wheel position (2 genes, 1 per wheel)

• Wheel density (2 genes, 1 per wheel) darker wheels mean denser wheels

• Chassis density (1 gene) darker body means denser chassis

It basically lands on a two-wheeled medium-bodied shape and doesn't seem to make much progress after that. Power and speed would be interesting variations.

This is why I said it needed crossover and got downvoted into oblivion :) turns out it at least tries to have crossover, so maybe the genome doesn't translate to crossover doing anything relevant.

I wasn't fooling. Think about it for a second, if your process involves a lot of crossover that means large sections of working genome will be passed on. If the ONLY mechanism for changing anything is mutation, then mostly you're just breaking what works.

That's what you're describing, so I'd look at how the genome is constructed to understand why it's not doing more.

What happens in an evolutionary algorithm depends on what you write it for. This is a fun toy, but what it does specifically is explore a very limited simulation of evolution by natural selection. Metaheuristics aimed at optimization have a lot of techniques aimed at not stalling out on a prematurely converged design, as well as improving other desirable properties of the population, at the expense of any pretense of fidelity to real-world evolution processes.

this is fun, even though the speed controls aren't super intuitive. You can press "Surprise" to speed things up and go through a bunch of iterations quickly.

The mutation rate (likelihood that g changes) and mutation size (Δg) are fun hyperparameters to tweak while watching the population evolve over time.

It would be interesting to see a gene for "compliance" so the cars could have some kind of suspension. EVerything more or less evolved into a sort of tron-bike shape for most of the runs I tried.

> EVerything more or less evolved into a sort of tron-bike shape for most of the runs I tried.

I ran it in the background for a very high mutation rate for a long time and it managed to come up with something very different---a little wheel attached to a big wheel, which bounces around and goes over all the obstacles.

Old discussions:

https://news.ycombinator.com/item?id=5942757 (664 points | Jun 2013 | 169 comments)

https://news.ycombinator.com/item?id=10600486 (162 points | Nov 2015 | 57 comments)

So boxcar2d, but without flash.

https://news.ycombinator.com/item?id=2196747

I knew I had seen something like this over a decade ago!

This html5 version has also been around for longer than a decade already. It's what inspired me to take a class on Genetic Algorithms and Evolutionary Computing in university back then.

...and apparently all the suspension parameters stripped out for some bizarre reason.

The physics simulation clearly uses inelastic collisions, which is wildly unrealistic and why so many otherwise passable 'cars' don't pass the course. Also seems to use a very low coefficient of friction - most of my cars couldn't make it up a two-segement slope.

... Apparently boxcar2d works perfectly in Ruffle, which the Internet Archive automatically loads :)

https://web.archive.org/web/20240428203838/http://boxcar2d.c...

Slight bug: there's no road past about 280m, all cars fall into an endless pit

Time comes for us all

The Great Filter

Just wait a little longer for the flying cars.

> evolve random two-wheeled shapes into cars over generations

Where I come from, we call two-wheeled automobiles motorbikes. Very cool simulation though!

The simulation that these cars are driving in has no third dimension for the vehicle to fall over into (or where to put another pair of wheels). So, like a traditional four-wheeled car, these vehicles do not tip over at 0 velocity. I think that property is enough to qualify their behaviour as more similar to four-wheeled cars than motorbikes.

It is a very visual and entertaining visualization, I love it.

It inspired me to experiment with a genetic algorithm in "Self-parking car evolution":

https://trekhleb.dev/self-parking-car-evolution/

Reminds me of a phenomenal Android app called Cell Lab where you could create all kinds of multi- or single-celled organisms to live in a petri dish. You could crank up the radiation levels to let things mutate and evolve if so desired.

If you like things like this, join us at https://old.reddit.com/r/WatchMachinesLearn/

Cool topic, but it doesn't seem to be a terribly active sub. The newest post is from 3 years ago :-/

Am I correct that it’s impossible for this system to evolve any kind of a suspension mechanism, no matter what the mutation parameters are?

Interesting. Is there a way to do this in a 3d physics based simulation environment. It would be cool to see if a genetic algorithm could be used to discover new aerodynamic configurations for drones/other platforms in simulation.

I don't know enough about genetic algorithms to say for certain. Anyone have any reference materials for someone that's just started looking into this?

Not exactly what you're asking but Topology Optimization is now a standard feature of the big CAD packages. It allows the designer to express various constraints and goals, then a combination of gradient methods and genetical algorithms are used to find an optimized part. Example: https://www.solidworks.com/media/topology-optimization

It’s the simulation and fitness function that are difficul not the genetic algorithm really.

I’ve done a bunch of playing around with NEAT, a variant of GA using NNs, for various things. Typically for GA stuff though you have a genome, aka some set of instructions for an individual, a fitness function for scoring them, and then you generate new individuals from those genomes for the next population.

Original Paper on NEAT here:

https://nn.cs.utexas.edu/downloads/papers/stanley.ec02.pdf

Lots of good resources here.

https://nn.cs.utexas.edu/

I love the NEAT algorithm. I did version of it for my senior project in high school, and have done a few iterations since, mostly with bugs that eat food and avoid predators. I'm about due for another round.

Reminds me dirt bike on Apple Macintosh -- you could edit pretty much every aspect of your dirt bike. Would be fun to make a car/bike game where you play against the GA. https://www.youtube.com/watch?v=siiho5IVAdg

I spent hours as a kid playing with Boxcar 2D. This brings back memories, and I'm not even that old!

might go much faster if it recorded a set of states where ancestors died shortly after and then test all the new candidates against those states.

The new candidate might actually survive because its prior history kept it from ever getting into that particular death state, but I think biasing towards designs that don't immediately die in those hard cases is good anyways, since given a long enough run it would likely encounter a similar state.

One could co-evolve the test case collection by simulating only the best candidates according to the test cases, and then retaining test cases based on a running score for how well they predicted the actual performance.

Recessive genes, essentially.

It references Box2D as the physics engine, but it seems to be a JavaScript port of Box2D. I'm unfamiliar with the JavaScript ports, but if it is a copy of one of the existing ports, the port should be referenced instead.

Btw, how much AI goes into designing the exterior of a car (panels, lights, windows, grill) ? Can they just drag a slider for "How much muscle do you want" from "Yes" to "Beige" ?

Very little. It's heavily computer aided, but the overall design is largely done by humans with some marginal input by engineers for annoying realities like aerodynamics and sensors.

I don’t think they use generative AI much in automotive design today, but you can play with stable diffusion and embeddings and make a slider for muscle cars in the textual weights.

so whats the optimal design?

Probably just two wheels and almost no "body".

That, or one BIG wheel, a very tiny second wheel, and almost no "body".

Why are the cars so spiky and why do they stay that way? Mostly what I saw was the wheels move and change size.

Looks like their shape is always defined by eight triangles. The page doesn't say what the genome defines about those triangles (only that there are eight vertices in the genome), but if it's just random angles and distances, it'd kind of make sense that they start as random spiky shapes.

I don't know why they stay that way. My first thought would be that it might be beneficial for the shape to be relatively low for stability, but with the shape between the wheels being concave for clearance. That doesn't quite seem to happen, except for the concave clearance to an extent.

Maybe the rest of the shape doesn't really matter for the simulation, so there's no selective pressure towards not having a spiky shape.

Both runs I did the cars looked like a child drawing a car from Mad Max.

My best guess is sort of adjacent to yours: a lot of cars flip on the initial drop and I think the spikes are helping them land right side up. Overfitting T=[0,1]

A big spike sticking out the top could change the center of mass and the moment of inertia. Both of those could affect how the car handles even if the spike never touches anything.

Oh, and they can affect the mass. If the grip of the wheels takes into account the normal force, extra weight may help with traction.

Hmm, and a 4th thing: some cars have a spike sticking out back behind the back wheels. These spikes sometimes function like wheelie bars, which are used on drag racers to prevent the car from flipping if the front end lifts off the ground. The wheelie bar kind of braces it but also lifts the traction wheels off the ground so they stop rotating it at the wrong moment.

Considering the 2D nature of the simulation, aren't they more motorbikes than cars?

Or maybe they are cars rather than motorbikes, if a bike is a vehicle that requires balance to stay vertical.

Funny how the landscape never changes, even though the generations come and go.

It's an option on the page to change the landscape

Thanks, I didn't see it.

This isn't genetic algorithm, though. It's mutation.

To do it with a serious model of a genetic algorithm, you need crossover, not mutation. It's fun, but this is sort of a lottery of randomized cars with some capacity for copying winning ones over to successive runs.

Breed the cars ;)

Why is this not a genetic algorithm? Genetic evolution does not require crossover.

It does have crossover, doesn't it?

There's a GitHub link at the bottom which gives us this:

https://github.com/red42/HTML5_Genetic_Cars/blob/master/src/...

And that seems to call into createCrossBreed() in here:

https://github.com/red42/HTML5_Genetic_Cars/blob/master/src/...

And that gets a parentChooser callback, which seems to be cw_chooserParent() from here:

https://github.com/red42/HTML5_Genetic_Cars/blob/master/src/...

And that has some swap points and a thing that toggles between parents when some index matches one of two values.

I'm not really a JS programmer or a GA expert, but it looks like crossover to me.

Reminds me of that game Detroit

How many generations does it take to start destroying communities? :)

Ok, that's proof evolution isn't real. lol

Did the worst candidate make the longest distance?

Or "overfitting as a service".

Reply on news.ycombinator.com