Most feedback we have is from game players, but we are often contacted by people who are making their own games. Of this group of visitors I am asked one question more than any other. 'How did you do the AI for the computer controlled Karts in Matica Karts?'.
We can't give away our source code as this is our livelihood, but a good programmer should be able to work their own solution from our following explanation. Game players, may be interested in how the Karts they are racing came to life.
Our first attempt at the AI for the computer controlled Karts came to a dead end. The Kart navigated around the track very well but there were 2 main problems. Firstly it was boring and lifeless, we didn't want a robotic feel to the computer controlled Karts. Secondly as soon as you had more that one Kart on the track everything got crazy.
In short the method used was to project out 2 'feeler' beams from the front of the Kart. Each feeler looks forward until it finds the edge of the track or some other obstruction. From the length of these 2 beams the Kart can figure out which way it needs to turn to avoid the obstruction, and how far away the obstruction is. Sampling this information 24 times per second it can work out when to brake and which way to steer.
The AI just didn't know how to deal with the aftermath of bad collisions with other Karts. If a Kart got knocked off track it missed sections of the track. If it got knocked the wrong way around it was slow to realise and turn around. If it hit a stationary obstacle it had no idea how to recover. I liked these errors, they were interesting. In fact I found it quite fun to drive around and cause problems for them, but I wanted to try a new approach.
More than likely we could have addressed all the problems with the AI, but I find Genetic Algorithms so interesting I use them at every opportunity I have.
Another option was to use a Neural Network. We have an experimental football (soccer for those of you outside GB) game that uses a Neural Network, but it runs at such a slow speed and has taken so long to develop very simple skills, which ruled it out for use at this time in Matica Karts.
Don't be put off by the phrase 'Genetic Algorithm' it's very easy to understand. In fact I use them as an easy way out when I find a problem I feel is going to be too complicated and time consuming to figure out my own algorithm. A genetic algorithm does the hard work by evolving a good solution to a particular problem. It's my lazy way out.
You start with a pool of contestants (often called the population), each with their own system/plan to solve a particular problem. These systems are usually just random guesses to start with. For us the initial population were a set of 100 drivers with random rules for driving the course.
Next you come up with a way to measure how well each contestant has done so you can give each a score (usually called fitness). We gave points for the time each Kart managed to stay on the track and deducted points for going off track or hitting an obstacle. Points were awarded for making progress in the correct direction, and bonus points were given for the speed of progress around the track.
You can then let the contestants (Karts in our case) run wild for a time to test out their particular solutions to the problem (driving around the track in this case).
Rather than the chaos of 100 poorly trained Karts racing around, we had 10 races with 10 karts per race. The races lasted a fixed amount of time (5 minutes). At this stage the Karts were pretty much hopeless, some worse than others though.
After the first races we were left with 100 Karts with different scores. The next step was to create the next generation of 100 Karts.
These will be the children of the generation before. This is achieved by 'breeding' from a pair of the old generation to produce 2 new children for the next generation. Repeat 50 times and we end up with the same population of 100 Karts.
To create 2 new children from 2 of the old generation (parents) we did the following. For each parent we split the rules they were using into 2 sets. The point at which we split the rules was random. So we may have one set with 10 percent of the rules and the other set with 90 percent, or one with 60 percent and the other with 40 percent.
One child would be created using the first set of rules from one parent and the last set from the other parent. The other child would be created with the exact opposite.
The idea being that if each parent had some good rules and bad rules, one of their children may inherit a lot of the good rules from both and only very few of the bad rules from both. Making that child much more successful than either of it's parents.
The next stage is mutation. You pick a small set of rules from each new child, again where you take this from and the size of it is random. You then replace this set of rules with a random set of new rules. This mutation may do very little, it may improve the success of the child, or it may reduce the success of the child when tested.
To recap, you start with a population of individuals who each have a random solution to a certain problem. You let each one have a try at the problem and give each individual a score. A new population is bred from the old, each individual of the new generation inherits part of their solution to the problem from one parent from the previous generation, and the other from another parent. Their final solution is mutated by randomly changing part of it.
How pairs of parents are selected for breeding the next generation is the key to the whole process. The more successful an individual was at the task (called fitness) the more chance they have of being selected as a parent.
This weeds out bad mutations, and children who have inherited poor rules from their parents. It promotes children who inherited good rules from their parents, and mutations that are beneficial. It's a crude copy of biological evolution, but it gets results. From generation to generation the Karts evolved better driving skills.
Well done for sticking with us this far, we imagine we will only have the true fans of the game still with us by now. Click the link below for the final part.
© 2011-2024 Alex Aylesbury & Clare Jarvis, All rights reserved. Web Design Agency23