Intro
There are a couple of things I’m always interested in. Video games are one, AI is another. I recently started once again on a little project to try combining both, and the result is Gravitoids. While I’ve had a grand idea for it all along, as I usually do, it has proceeded in a few simple steps. First, I copied the source of Pond Game and used it for the basis. I cleaned it up a little and started hacking. First I added the ability to draw the simple circles I’m using to draw things, then I simulated gravity. I’m now working on the AI part.
The source is licensed under the BSD License
You will need Java 1.5 or newer to run Gravitoids. No special libraries are necessary.
Downloads
Description
On the screen, you will see many spheres. Each has mass, radius, and speed. Some are pinned and can’t move, others are free to move based on gravity. The only objects with free will are the little blue spheres. You will also see red and blue lines.
Each little ship (blue sphere) has two lines. The blue line points out the object that it is currently reacting to. That may be another sphere (planet), or it may be a wall. The red line (often very small) is the direction that the ship is thrusting towards at the moment, length showing how strong. These can be turned on and off by pressing M (for motivation) and T (for thrust).
When the game starts up, 200 random ships are created. They are given random brains (see Theory section). We then run trials. Each trial generated random planets (up to 10) which are placed in the universe, taking care to leave a section in the middle of the screen clear. Each ship is placed in the exact center of the window, and gravity and logic takes over. When a ship hits a wall or planet, it’s dead and taken out. When all the ships are gone, a new trial starts. Note that the ships can’t see or collide with each other.
When 10 trials are over, we generate new ships. We take the 10 who lived the longest over the trials and bring them on. We then breed the top 10 ships together a few ways to produce around 100 offspring. We then add the 10 worst ships from the last trial, and 10 random ships from the last set. The rest of the 200 ships we need are randomly generated.
To breed ships, we take two at a time. Their DNA is just a bunch of doubles, ranging from -1.0 to 1.0. We iterate through all of them, randomly choosing one parent to take that double from. At the end of all this, we replace a few randomly, and randomly make a few stronger/weaker. This is enough to allow evolution to work.
Changelist
- Version 0.2 (2008-03-16):
- Added the K key to force a death if the simulation reaches a stable state
- Added “thrust momentum” so that the little guys can only change their thrust by so much in a single turn, making their movements a little less erratic
- Tweaked the way their fear is shown and calculated (note: there seems to be an error in this code, I wouldn’t trust the fear display lines too much)
- Made it so that they always devote more thrust to the object they are more afraid of
- Some general source cleanups, turning things into functions instead of copy & pasted code
- Versino 0.1 (2008-02-22):
- Initial release
What You See
When you first run the program, it will run through 10 or so generations incredibly fast as nearly every ship manages to kill it’s self almost instantly. Soon, a ship or two will get DNA that tells it not to just thrust at 100% (which is WAY to fast to be usable) and it survives a little. After 10 trials, it breeds and their are a few. This continues until the steady state is reach, which is a fair number of ships survives each trial for more than a few frames. At this point they (slowly) start getting smarter and lasting longer until they hit their evolutionary wall. It’s all surprising fun and addictive to watch.
Basic Theory
Gravity is simulated using standard physics formulas. The important thing here is the AI. It’s actually a Genetic Algorithm. It’s been providing me quite a challenge. While I know how these things work, I also know that trying to come up with the right equations to allow the evolution to actually work is challenging.
My first tries didn’t work at all. They were fine in theory, but I had a couple of typos in my code. After fixing that, a tiny tiny bit of a glimmer of hope appeared. The little objects (ships) did evolve. They went from brain dead, to almost brain dead. It may have still have been completely random and I was just reading into it.
I tweaked a few things, and things might have improved. But when I changed the generations from spawning after each trial to a total of 10 trials per generation, things suddenly appeared. The random variations (where one trial would kill nearly everyone instantly) lost enough of their influence that it became possible to see actual improvement. As I type this, a little set of evolved ships is dodging objects with a glimmer of hope; no longer blindly running into things.
Brain Theory
What is in here will change, since this is the heart of the program.
Right now, each ship is given a list of every object in the universe (all the planets). We then artificially insert two more objects, the closest horizontal wall and the closest vertical wall.
For each object, we calculate a few things:
- Distance from us
- Mass
- Direction of movement
- Relative speed
- Size
- If it’s allowed to move
Each of these is calculated, then multiplied through a simple formula (a2x + bx + c) to get a number. We sum the numbers to get a fear index. The coefficients (a, b, and c) are the doubles in the ship’s DNA. Each check (distance, mass, etc.) gets different coefficients.
After doing this, we find the object the ship is most afraid of. That is used to calculate a direction to move (using the same equation and more coefficients) and how much thrust to use. We save those two things, and the simulation takes care of the rest.
Note that walls don’t have a few of those things, so they are given an additional property (fear of walls) to make up for it.
