Show HN: Space invaders, but the invaders evolve with genetic algorithm
github.com
github.com
The evolving enemy concept made me look up an old boss-rushing shooter that selected the next boss's upgrades based on your performance[1]. Is this something you're interested in refining further?
With so many invaders spawning at the same time, and the 'bullet' you shoot moving so slow, the last invader to be destroyed seems to me to be a result of random choice (which one did you get around to shooting last) rather than it being any 'healthier' than the other invaders.
I don't really have a suggestion on how to improve it other than maybe slow down the vertical progress of the invaders and speed up the bullet so that distance made vertically is actually tied more closely to it's ability to evade your shots.
Here is a proposal for another fitness score: everytime a bullet is shot, raise the score of every survivor, weighted by the distance between the survivor and the bullet. The closer the bullet the better the fitness.
Intuitively, I think this would select for better dodgers.
There’s a simple strategy that guarantees you won’t be the first to die: hide behind the back of your biggest buddy.
I think that would be my strategy, plus “if a bullet that’s going to kill your ‘shield’ is on its way, figure out whether you can find a new shield; if not, make a run for it.
The existence of such a strategy shows the result isn’t completely random.
(Of course, there also is a prisoner’s dilemma here: if everybody follows that strategy, the swarm would run away from you, and nobody would gain any fitness)
I would say just give a try at slowing down the vertical progress, remove the one bullet at a time restriction, and see how that goes.
Not trying to be negative at all, I think it's a great project and the code looks to be very clean. Nice work.
I've used GAs before in school. One example way to do even session-less evolution faster would be a distributed client/server model where the indivual survivors across all game instances who are lasting the longest are crossbred but that would take longer to code ....
> With so many invaders spawning at the same time, and the 'bullet' you shoot moving so slow, the last invader to be destroyed seems to me to be a result of random choice (which one did you get around to shooting last) rather than it being any 'healthier' than the other invaders.
I couldn't disagree more. The fitness score is correct, because the invader wins by covering distance.
What happens by chance early will happen by design late -- that is nearly the entire concept of evolutionary approaches. They always improve on their fitness function, and what matters is that you chose the right one. In this case, improving on the distance invaders travel is the point of being an invader, and the point of the game, so that distance is very obviously the correct fitness function.
The invader wins by crossing the baseline. This fitness function lets me use evolution against the invaders by letting the dumbest ones approach the baseline before killing them, making future waves easier than if I killed the easiest invaders first.
Perhaps the fitness score could include the number of projectiles that passed nearby without impacting, as a measure of difficulty to hit.
> The invader wins by crossing the baseline.
Both are true, but covering distance is a better fitness function because it is continuous and crossing the baseline is discrete (and not just discrete -- binary). Your strategy can make the difficulty rise more slowly than otherwise, but it can't make the difficulty plateau or drop.
Yes, it's slow and I didn't end up playing more than a few rounds, but the core idea is a Good One.
Thank you for making and sharing!
It would be nice if there was genome display or something, so you could see how the population was evolving. Towards the generations that were multiples of 7, it would look like the population started to converge. So some sort of display information about that would be interesting.
It would negatively effect gameplay because it would be essentially a cheat for the human, but it would be an interesting visualization none the less.
But, knowing the algorithm, I tried to shoot the hard ones first and wait as long as I could to shoot the easy ones by just letting them descent :)
So for a small demo it's probably better to just use arrows as this will work everywhere, and there won't be a need to support all keyboard layouts out there.
EDIT: Data point of 1: I'm German and use a QWERTZ layout because it's a hassle to type umlauts on QWERTY even with a compose key. If I were French that'd mean I'd be using AZERTY.
I switched to qwerty about 2 years ago, but almost everyone I know uses azerty here (as software engineers).
Personally, I don't expect it to be supported though. But it should at least have a fallback like the arrow keys.
It's an interesting idea, but I think the implementation needs more tuning.
I'm finding that I can barely last 7 generations to be able to see it 'evolving'. Handicapping the player by waiting for the previous shot to hit before firing again and making the move speed ridiculously slow makes this game too hard even before the genetic algorithm makes an impact.
Also, because the player's move speed is so slow, the easy tactic for the algorithm to head towards is to simply push each enemy to opposite ends of the screen -- ie: hug the wall. If you're clearing one side, the player won't be able to reach the other end of the board even if you move as fast as possible.
TLDR: Interesting concept but to really demo this concept you need to make the game a little easier for the player / don't handicap so much.
Player.prototype.shoot = function shoot() { this.bullet = {x: this.x+this.s/2, y: this.y, s: 3}; this.isShooting = true }; Player.prototype.update = function update() { if (this.x > 0 && this.isMovingLeft) { this.x -= 0.02 * dt; }; if (this.x < w/4-this.s && this.isMovingRight) { this.x += 0.02 * dt; }; if (this.isShooting) { this.bullet.y -= 0.1 * dt; if (this.bullet.y < 0) { this.isShooting = false; this.bullet = {}; } } }In any case, the real problem here is that either the player is good enough to last a long time (in which case most waves are probably killed very quickly, thus randomness dominating the fitness function and you won't see evolution) or the game won't last long enough to see a lot of evolution happening.
I’ve also tried it on my iPhone and it’s easily playable too.
"victorribeiro.com’s server IP address could not be found"