Evolving Waves

A while ago I worked a bit with a few friends on a video game. I worked on the Artificial Intelligence side of things. One of the tasks was to find a decent path that enemies could follow through a map that minimizes their distance from objects the player might go near (like treasure) while maintaining a decently realistic path (no sharp turns). To do this, I created a simple genetic algorithm that evolves waves over time that change depending on where the treasure objects are located. Try clicking in the box (at the bottom of the page) to create treasure (red dots) and look at the path created (green line). Note that sometimes odd paths can be made for small numbers of treasure, so if the path looks weird try adding more objects. An interesting note is that every time you run it, even if you click in exactly the same place, the program can output different things. This is due to the inherent randomness of how it works, but to understand that, a little bit of explanation into how the code works is needed. Essentially, the code stores a “population” of different waves. These are stored as multiple arrays holding the length, height, vertical and horizontal shifts. For example:

len = [4, 2, 5, 7....
height = [2, 3, 7, 2.....
v_shift = [9, 0, 1, 3......
h_shift = [2, 1, 1, 4....

In this case, “creature” number 0 would be a wave with length 4, height 2, shifted 9 units up and 2 to the right. Now that we have a population, we need a way to actually change these values over time so that they become closer to the points clicked by the user. To do this, we first find the two best waves. In order to do that, we need to find a way to asses a waves “fitness” or how close it gets to the points. The fitness can be found by simply iterating over every point clicked, and determining how far the wave is from the point when it has the same X value. For example: The first wave in our list has length 4, height 2, shifted 9 units up and 2 to the right. So its equation would be:

f(x) = y = 9 + Sin(2 + (2 * pi * x / 4)) * 2

If our points are: (3, 2), (5, 7) and (10, 1) Then our fitness is calculated as: |2 - f(3)| + |7 - f(5)| + |1 - f(10)| We use the absolute value because it doesn’t really matter if our function is too high or too low, all that matters is that the function is off by some amount. So now that we are able to find how close each wave gets to the points, we get to the fun part: evolution. If we start with a population size of 50, we iterate through every single “creature” and evaluate its fitness. What we are looking for in this step are the two creatures with the best fitness (lowest score generated from the function we talked about above). Then we can take the values associated with these two best waves and combined and mutate them. For example: say our two best waves were:

len = 5
height = 3
v_shift = 4
h_shift = 2

and

len = 3
height = 4
v_shift = 0
h_shift = 3

Now lets say we need to generate the length of a “child” wave, one that is loosely based on the parent waves. We have a few options:

1. use the value of the first wave, 5
2. use the value of the second wave 3
3. use the average value between the two

So we choose a random number between 1 and 3 and use that as our option. Next we need to mutate it, we do that by adding a random value to it. In this case I chose to use a random value in the array [-50, -10, -4, -3, -2, -1, -1, 0, 1, 1, 2, 3, 4, 10, 50]. This way it can evolve very fast on occasion (if it picks -50 or 50), but generally evolves slowly (7 values are between -2 and 2 inclusive). So we combined and mutate every value in order to generate a new wave. Now we need to populate our new generation. To do this we can add in the parents (this ensures that the next generation can’t be worse than the current one. Every other value in the array can be created using the combined and mutate methods. Now the new population has been created so the entire process can start over.

Click anywhere in the canvas to add points.

Reset