December 3, 2009 by Alex.

The current game project, “The Mortal Realm”, involves a battle system which is turn based and played on a hex grid.  Thus, it requires an AI opponent.  Currently, the outline of the AI mind is fairly simple.

Firstly, there is the long-term plan.  This is achieved via a genetic algorithm.  A computer player would have a number of units, up to ten, that can be fielded into a battle at any given time.  The genetic algorithm determines the long-term goal of each unit.  Note that, this does not determine the turn to turn actions of a unit.  The general setup of this one goes like this:

a) The Solution Representation is, like most other genetic algorithms, an array, where each slot represents the long term goal of a unit.  The long-term goals are typically actions such as “Take and Hold x Position” or “Set up Ambush at x Position” or “Charge recklessly at the enemy army”.

b) Mutations simply change a value of a long-term goal in a random slot inside a solution.  For instance, slot 6 might be “Take and Hold x Position”.  It could change to “Take and Hold y Position” or “Set up Ambush at x position”.

c) Crossover is a simple single point crossover.  Choose a random slot, between 1-10, as the crossover point.  The first child takes all the genes of the first parent before the crossover point and all the genes of the second parent after the crossover point.

As a simple explantion, the genetic algorithm works something like this.  First, you have a population of solutions.  In my case, that means I have a collection of arrays, each array representing a long-term battle plan.  Each slot in an array is considered a gene, the long term plan for a single unit.  The initial population is created at random, that is, the solutions I come up with are completely arbitrary.  Then, I have a method, called the objective function, which calculates the value of a solution.  This objective function takes into account the terrain, the position of enemy troops and also the particular arrangement of friendly troops.  Noting that I have to take into account the arrangement of friendly troops, you cannot calculate the value of a gene independently because it changes based on what the other genes are.  So now I have a population of randomly created “individuals” (solutions) and I have a way to calculate their fitness with my objective function (que Nazi references).

Next, you create the next generation of individuals.  This is a stochastic process based on fitness.  The more fit an individual is, the more likely it gets to reproduce.  In order to create offspring, two individuals are selected at random, with a higher preference given to people who have higher fitness.  They then create offspring via the crossover method.  Two parents produce two children via crossover (ie. each child will somehow share the genes of its parents).  After enough offspring is created for the next generation we then check if any will undergo a mutation.  Unlike real-life, genetic algorithms do not allow mutations to produce non-viable offspring.  A mutant is always viable.  However, the rate of mutation is very low.

Now you have the next generation of offspring, some of which may have mutated.  Then you decide which of the parents and offspring survive to make the next generation.  Like before, it is a stochastic process where individuals are randomly chosen, with a preference toward higher fitness levels.  Then once this is complete, you repeat the process.

Once you are done (it may take hundreds of generations to produce a good solution) you’ve proven evolution.  Also, we have a long-term battle plan for the computer opponent.  This battle plan shapes the turn to turn actions it takes with its units, as it tries to stick to the plan and also react to transient issues.  Next post, I’ll talk about how the computer opponents determines its turn to turn actions for each unit.

-Alex

Posted in AI, The Mortal Realm, C/C++ | No Comments »

December 3, 2009 by Mark.

I’m converting my blog to something a bit more useful. My long rants about my game engine were all leading towards a game of some sort. In the process I have recruited a friend to help me realize that dream. So, give a kind welcome to Alex.

Our first title will be a strategy turned-based war game by the name of ‘The Mortal Realm.’ It will feature my 3D engine and a robust battle system. As far as complexity goes, this game is one of the simplest we have come up with. It’s a simple point and click style of game with very minimal artwork. I’m hoping it will be a great test bed for my engine as well as Alex’s AI.

Posted in The Mortal Realm, Radiant, 3D Stuff, C/C++, Stuff | No Comments »