Evolving Genetic Neural Network Optimizes Poly Bridge Problems
I made a genetic algorithm that can solve and optimize Poly Bridge puzzles with artificial evolution.
This Project's Source Code:
github.com/sam-astro/Genetic-...
Support:
● Patreon: / astrosam
● Ko-fi: ko-fi.com/astrosam
● Monero: 4AAjyAHKnYwCsgJp16v1YeeDPA1Z51QKUfCMWsiCDxkNBFCtbUfDHD7K5sZDrFH2pnGsDAH989XwXdudcoC4iqtVC9QLk8r
--------------------------------------------------
Related Links:
● Streaming Channel: / @astrosamstreams
● Itch.io: astrosam.itch.io/
● Github: github.com/sam-astro
● Discord Server: / discord
--------------------------------------------------
All Music was provided by Epidemic Sound (www.epidemicsound.com)
--------------------------------------------------
Chapters:
0:00 Intro
0:29 Remaking the game
2:06 Making genetic alg.
3:51 Managing agents
5:26 Calculating fitness
6:41 Mass, cost, and strength
7:37 Testing
7:53 Bug fixes
8:05 Real training
8:54 Funny first tries
9:00 Problems with genetic algs.
9:33 Outro
--------------------------------------------------
This video is not sponsored.
#programming
#neuralnetworks
#unity
#polybridge3
As Michael reeves put it: "I made a 5 hour long problem into a 2 and a half month long problem, cause I'm a programmer and that's what we do"
but now it can be reused every time you need to solve the 5 hour problem, while taking just 4.5 hours, and it works (almost) every time.
@@eduardokerber2931you captured the minimal worth value programming thinking
HEY! HEY! Why did the Java programmer wear glasses? Because...he can't C#. Thank you, thank you, I'll be here all week.
not funny
@@danimgmd3510 shortest autobiography ever
5:48 I can't believe you really just went "assume a spherical car"
Glad someone else caught that 😂
Google “peel trident”
Physics problems on tests be like
2:00 As an engineer i can confirm that architects will show you some magical item/building that defies the laws of physics and expect you to build it.
Lol it's kinda telling that MC Escher wanted to be an architect and actually enrolled in a school for architecture and decorative arts.
@@revwroth3698 I can imagine being told to make an escher design. I would die.
@@kerz5383 not to mention having to implement building codes, imagine having to design wheelchair ramps for all those staircases. That sounds awful to me and I'm not an engineer.
As an engineer I affirm your statement and would like to add "salesmen" to the list.
Summoning Real Civil Engineer..
Respect for the architect dig ❤
It had to be done
The man himself!
Yo wassup rce love your vids
I like that real engineers treat Civil engineers the same way you treat architects.
Hi rce love your videos and architects are the worst and honestly my sister wants to be an architect and I want to be an engineer
"But there is a problem, I am way too busy to be playing this right now" - AstroSam Also AstroSam: recreate the whole game
'i didn't have time to play polybridge so I recreated polybridge exactly so am AI can simulate it and solve it for me.'
@@justinwhite2725 sounds like a normal programmer to me.
Well, he was technically busy redoing the whole game and training an AI to solve it.
comically overcomplicating a small issue to solve it in unnecessary and often slower ways gotta be my favorite genre of youtube videos
have you seen Harder Drive by suckerpinch? my absolute favorite when it comes to this
Would also recommend Harder Drive; Tom7 (suckerpinch) commits horrific crimes against maths and computing.
This concept applied to Structural Engineering would be amazing.
Just remember 16 hours of coding can save 20 minutes on planning and/or just actually doing it
@@oliverwaldock9710 If this is done for actual bridges, it'd save a lot of time and money due to optimization.
Damn, nice video! About 7:09: Yours didn't performed like Poly Bridge probably because Poly Bridge has its own custom physics engine, this was done because the Unity3D physics engine is not deterministic, which caused a lot of problems on Poly Bridge 1, not only rerunning the simulation will give you a different result, but game speed also affects the outcome. So for Poly Bridge 2 and on, they're using their own physics engine.
Yes, I did some research on it and found many differences, so my version is pretty different. One way I get around it not being deterministic is by running the simulation multiple times and taking the mean of the fitness, although this obviously takes more time.
@@AstroSamDev Part 2 yes no??
@@AstroSamDev and for Android
Since Polybridge is made in unity, I wonder if some bepin tool could extract enough of the physics engine to implement this as an actual solver.
@@TlalocTemporalsince poly bridge is written in c# you can almost certainly access the physics engine through dependency injection.
"Im way to busy to be playing the game" 0:09 " To start off im going to need to replicate the entire game" 0:30
yeah bro was so lazy to run 1km that he ran a whole Earth lap 💀
"now one problem we have is it is indestructible. Clearly it was made by engineers. So in order to fix this, we just need some architects" sounds like real civil engineer EDIT: holy shoot 2.1k likes I think that's the most I've gotten before thanks a bunch
RCE would be proud of him
RCE was an architect all along
RCE was the #1 architect hater until he became the #1 architect
RCE FTW!
We are only missing some strong shapes!
As someone who has played a ton of Poly Bridge, this is very cool! Also, I dunno if this has been clarified yet, but there is a 1:4 ratio between polygrams and unity's mass units.
Oh I see. Since I recorded the audio, I actually changed the weights a lot, and it seems they actually did almost reflect that. But it is good to know now 😁
@@AstroSamDev Certainly lol. Also, I don't know how well this can translate into your system, but I might be able to give you the current strengths and weights of each material, along with possibly some models from the game if you plan to make any follow-up videos!
Ah ok
You are like if Real Civil Engineer and CodeBullet had a child and I love it
I’m instantly going to subscribe to both of those based on this sentence alone 😊
your not wrong...
Thought the exact same!
@@StephenOwen If you like real engineering stuff i would recommend PracticalEngineering too.
I like how this AI shows that trial and error can result in so seemingly complex things like the swining bridge that seemed delibertly made while its just the result of failing many times prior. Just like evolution
Yeah i really found it beautiful and honestly, i tyink it can really be compared to a very young child, just trial and error the lifd
"I don't have time to play the game, so I spent time to program the game in unity and trained an ai to play it"
HE’S BACK!!!
Yooooooooooo
Fnilanyyyyyy!
"this bridge is indestructible since it was made with engineers, so we just need need some architects" utterly comedic
Did you get the reference bro
@@gamecoder3833probably not
when the world needed him the most, he returned
The purpose was destroyed by AI holding the car hostage.
Around 4:22 wouldn't it be better for visualization and filming purposes to do a 10x10 grid of bridges?
It actually uses unity's 2d physics system, so having multiple rows moving back in the z axis would overlap collisions, and stacking them vertically could make the ball interfere or bridge pieces. The only way to prevent that would be to build extra barriers or delete falling things, which would reduce performance. And for visualization, it wouldn't be possible to show all of them at once on screen, and I think just showing a single one evolving gets the point across well.
To clarify, it would be possible to show them all at once, but they would be too small. And if you were talking only about the video, I wanted to show what the simulation actually looked like.
@@AstroSamDev I understand! Was just a friendly suggestion from someone who gets 0 out of unity Thanks for explaining 😁
@@AstroSamDev great video btw! I'm always amazed to see NN getting to the hardest and coolest solution and thinking "Hmm , that's perfect" haha
@@Rodasboyy Thank you!
multiple everything by deltaTime or you're comiting a crime
no >:(
@@AstroSamDev i know lol
I was really hoping for more from this video. Not sure if I'm being unrealistic but it just felt like it started to gather momentum then stopped dead
i feel robbed, this video kinda ended abruptly, i was expecting to see more out of the evolution and it figuring out different scenarios
Honestly, half this stuff went over my head, but i can totally get on board with the concept of spending 5x as long avoiding doing something than the original task. Fascinating stuff.
I hope there's a second part showing it solving various levels
We gave something like this as an assignment to students in an evolutionary computation class a while back, and it was a lot of fun. We used a "maximum load" fitness function (keep adding weight until the bridge collapses), and also had students add a cost minimization objective at one point for NSGA-II, though that ran into some fun problems (What bridge minimizes cost? The one where you delete the whole bridge, of course!). On one test problem we were getting really weird results only to find that our scenario was missing one of the two anchor points on the sides of the bridge, so the evolutionary algorithms were desperately trying to keep a huge cantilevered pier from falling over with surprising success!
I think if you made closeness to the flag an exponential reward, that might help incentivize reaching the goal. And if you also awarded points for bridge rigidity, that could be good for preventing dangling messes. The rigidity could be scored based on least amount of average travel for each joint node.
Oh man, you would get along so well with RCE. "This bridge is indestructible- clearly it was made by engineers." "To fix this, we need architects." 😂
6:10 : connecting to all points gives a better bridge Meanwhile polybridge players: 😅
Weight!!!!!!! Money!!!!!!!!!!!!!!!!!!!
That was really well done and enjoyable to watch. I wonder if Poly Bridge 3 has an easily-understood save file format -- you might be able to use that (plus some hairy automation helpers) to test candidate solutions in the real game environment, although it would probably be a lot slower and might suffer from the nondeterministic physics update you mentioned. Unless the PB3 devs have also done work to make their custom physics model fully deterministic (maybe it works out the physics interactions before playing back the animations? Presumably they would need something like this to be able to replay solutions consistently).
My guy really said "if you didn't like the video, dislike it" you deserve my sub
When the AI discovers the physics of the game to cheat:
very good video, only downside I found is that it felt "incomplete" I'd absolutely LOVE to see more of this, tweaking, adding different materials, etc etc it is a pretty good concept and execution, so you definitely could invest some more resources into it. Will definitely turn out to be very good content. Keep up the good work!
I would love to see a part 2. Maybe try solving some actual levels with the algorithm and seeing if it would work?
2:00 he CLEARLY watched RCE
Could you maybe make a part 2? This is an awesome video, and I would love to see how you will improve this project!
I imagine it'd be very fun to see the algorithm that got the car to the end goal in the slowest way possible
How long did it take you to write the code? Could you also use an adaptive large neighborhood search?
Super interesting! I don't know much about programming, but you explained it in just enough detail to understand the process.
As an architect who worked with engineers in an A/E firm for 20+ years, I love your dig at us starting at about the 1:55 mark. I had many engineer coworkers who I still call my friends -- a couple very good friends -- but professionally we drove each other crazy.
I once heard that an algorithm had been designed to assist in choosing the most efficient route for a road across London. When the program was tested, it came up with an answer in less time than expected - straight down the river.
I like that this video demonstrated a safer example of the paperclip optimiser problem at the end. AI's goal isn't specific enough, so it does something ridiculous instead of what was intended. That could be stopping the ball from crossing the space instead of helping it to do so, or it could be consuming the entire galaxy to turn everything into paperclips...
Mans like "I don't got time to play" but has time to remake the entire game
"Clearly it was built by engineers, to break it you would need an architect" 💀💀
Ahh yes, immediately figures out dangling roads. It’s already a true Polybridge player
MY MAN! I saw you just a while ago making videos getting less than 1000 views WTF HAPPENED? you blew tf up congrats! I hope you have the best game dev journy ever!
Use a checkpoint system for reward at crossing every point on the bridge, instead of end result only, maybe that will determine the AI to solve the crossing the bridge problem and build an actual bridge.
I expected a super barebones explanation of how it worked, but I think I know a little bit more about machine learning now as a non-coding layman. great stuff
There already is a fixed update function in unity for doing physics calculations
Change the reword function such that time to cross is a factor so that by failing to complete in a timely manner it greatly impedes the reward. Time to cross over cost maybe?
"as long as the bridge doesn't fall down and cars don't crash you will be paid" engineers: "ChatGPT, design me a 4 lane, 423 meter long bridge east to west..."
never expected a cool poly bridge video, it's amazing
Would be awesome if you made a follow up video improving it to set records in game
Having a maximum penalty for lost balls is an effective improvement; it shouldn't be (much) worse than a ball that hasn't moved at all. As the evaluation function is already composite (anchors, ball distance...), I'd also consider a non-linear evaluation on the ball distance. Closer to the finish should be very important and perhaps the distance should be rated exponentially. Another thing that could be interesting is average velocity of the ball; lower average velocity means smoother bridge. I would love to see a followup with improvements on the evaluation (perhaps my suggestions :))
reading the comments and just reminded me of the swinging bridge and throw result. a nice simple way to overcome that would be to have 2 balls one after the other test the same bridge like traffic.
I would love to see sequel for the vid.
There is also Bridge Constructor series. I played Portal, and it was fun
hopnestly I thought we were going to see some amazing designs, but we got amazing TLDR's!
I'd be curious to see if any of the designs would work in the actual game
2:41 Looking up at the sun in minecraft be like:
Really liked the more code based style of this video! Got one question tho could you slide me that vs theme name?
Thank you! The theme is called Monokai++, an extension for VSCode, and I made a port of it to Visual Studio which you can find here: github.com/sam-astro/monokai-plus-plus
@@AstroSamDev Thank you very much!
damn this dude is insane😮
bro really went 😮
Interesting timing. I just made a genetic algorithm library in Go and am in te process of optimizing its performance.
"I dont have enough time to play the game so il make a new version of it from scratch"
"It isn't the solution we wanted" I instantly thought "It is the solution you deserved." :)
I was lowkey expecting you to recreate one of the result bridges in the original game
You have to use double precision fitness values or you get stuck in local minima.
I thought I was, but because it is all behind the scenes in a class I don't often edit and see that. Now that I look, I see that it is a double type, but I think when I add to it and set it from the Agent's class it is as a float. So I will fix this in a future revision
a follow up video on this but it minimized stress would be really interesting
It would be interesting to see what happens if you take some of the more successful bridges and recreate them in Poly Bridge.
I was hoping for another step of adjustments to refine the reward system after you brought it up as an issue but was kinda left hanging like the bridge supports made of wood. 😂 I think (as someone glancing in from the outside) an issue was that your setup wasn't really rewarding the system for using supports in any constructive ways. If you come back to this at all, I personally would like to see refinement of the reward system to encourage more connectivity with supports back onto the road structure, and also to refrain from using road material outside of the direct path. Those are obviously just my thoughts, and either way, love the content.
Cool! And it's a great foundation to build on. Would you try to improve the model with more realistic criteria? 1. Two-way crossing so that the solution can be symmetrical. 2. Vibration measurement, its minimization... 3. And anything else I didn't think of.
I think I just may in a future video. Thanks for watching!
2:48 "new Vector4" I didnt even know Unity had that lol
Great for when you are making 4D games, as we all do.
@@AstroSamDev I should have been doing this from the start! I have been using 2 separate vector2s instead!!!
Ooh just tought it would be really cool if the AstroSam logo closes at the end instead of fading out It would close exactly in the same way that it opened at the beginning
How is the Elapse function different from fixedUpdate? I imagine it is otherwise you wouldntve bothered but how is it different?
is there a way to inject the Neural Network controls directly into the game? could even reach out to the devs and see if they can make a special build of Poly Bridge 3 that allows for injection?
without reverse engineering the game, the easiest way i can think off is tracking the image of the game while played for the simulation part, for the building it think his code may be able to be adapted to work, biggest problem is the amount of time it would take to train it on a single instance running at a time
Very cool. I’ve been thinking about doing something like this but haven’t had the time or energy to put into it
This is like a mix of code bullet and real civil engineer😂😂 you got a new sub
Excuse me kind mortal, but what is the name of the song used at 8:05? I looked everywhere but can't seem to find it. Thanks.
When creating fitness functions, I’ll often find multiple ways to score it, such as, for example: ‘distance traveled exceeds 5 units’ and ‘minimum distance to goal’ Scoring perfect gets you one point for each. 1 point for a minimum distance of 0, 1 point for traveling 5 units. I’ll then take all these disparate fitness scores and multiply them together for the final fitness score for the bridge. so if the ball never leaves the start (0 points for 0 of 5 units moved) and the ball never gets closer to the goal (0 points for goal proximity) - 0 * 0 = 0… which fair, bad example. the point is, any single fitness function doing poorly penalizes the overall score, and none of these functions need to ‘pass’ before other functions start getting considered. There’s some finagling to do (what if all functions start scoring at zero?) … but the point is, don’t limit yourself to just a linear score. Powers, logs, priorities use what works for you.
This is pretty interesting and I think that if you make a few adjustments you could make a really cheap bridge for some levels in poly bridge and I would love to see that
The genetic algorithm should be choosing which ones survive differently, each ai makes a bridge, then they have to walk across their bridge's 100 times with the simulation wearing down pieces over time, any of them that fall die, the other ones move on. If they all die repopulate it with another 100 random ais.
You should make a video about the dynamic bridges, would like to see more
Kinda wanted to see the final bridge in polybridge. D: Oh well. Lol
What if you tweaked it to measure the total distance each part of the bridge moved during the simulation, and the less the bridge moved give it a higher score / the more the bridge moved the lower the score? Could also have it on some iterations remove a random non-road part to the bridge and if the score doesn't decrease massively, continue from there. Try to remove some of the additional clumps.
So i'm sure you already thought of this, but I think the AI would have a better chance if piece placement was changed to emulate the Arc tool. Like if the distance between two points it chooses is greater than material.maxLength, add a third point halfway between the two and offset it by a random number * the line's normal (weighted toward 0 offset) to define an arc, then create floor(arcLength/material.maxLength) connections and equally space them along the curve. It would probably still be a mess, but it would likely get it closer faster and is closer to how real players think when they plan a bridge.
Oh, thought you were gonna elaborate on the cheating thing and maybe do something about it but alright.
"I need to get the ball over there" "But If the ball falls into the abyss, i lose.." "Imma hold it"
I have never seen you before but i should be taking notes You’re the only programmer on yt that i know of that Shows what they’re doing
Sebastian Lague
I wondered where my boing ball went.
Would be really cool if someone did this but hooked into the actual game and used that to simulate everything. Seems like it may be easier than reimplementing them too
that would get you banned
@@daefin9993But they wont be used ng online anyways.
@daefin9993 you can literally pirate the game
@@mloxard hadnt thought of that but piracy is illegal and modifying a multiplayer game is against most tos's
In 3:45 ,why using void Elapse() when we can use FixedUpdate()? Curious about it , hope someone can explain to me .
3:37 doesn't Unity have a built in update function that *does* run at a fixed rate? Was there a specific reason that you didn't use FixedUpdate()?
So many questions: 1. Why not specify in fitness function, that "car" should cross the bridge? 2. Where 3d red connection point come from at the bottom? 3. Why not use gravity and shape for the "car"? 4. Why not use probability function, bases on fitness to decide parents? 5. How many spicies do you create per generation?
I hope the poly bridge devs see this and give you a chance to actually test an AI in the real game!
Architecture, AI, is this a prequel to a Neil Breen movie?
The AI got very close to a very real bridge design. The jumbled wood members and some of the legths were the problem but overall you can actually make a bridge with a single column and just a few supporitng struts.
as they say, "be careful what you wish for"
"this bridge is indestructible clearly it was made by engineers so in order to fix this we just need some architects" RCE would be proud
hey I wonder where that z# stuff went, did you finish it?
I fear for humanity. In the future, lowest cost is paramount. All new bridges are dynamic swing bridges.
That ball who sits there and does nothing while thinking he is winning is just like me
Are there any games that have AI agents trained like this? I was thinking of adding predator / prey entities into my game and have the predator rewarded by enemies eaten, and the prey rewarded by time survived