StringEvolver: Evolving strings with a genetic algorithm

This is my first attempt at experimenting with a genetic algorithm. The following is an application that evolves a string given a destination to converge to.



Here is an example run:

> StringEvolver -m 0.25 -s 0.6 -c 2000 -e 0.1 --fitness=hamming --ctype=one -t 0.3 "Charles Darwin was right!"

Evolution Destination: Charles Darwin was right!
Mutation Rate: 25%
Crossover Rate: 60%
Truncation Rate: 30%
Chromosomes / population: 2000
Elitism / population: 200 (0.1%)
Fitness Calculator: Hamming Distance
Crossover Type: One Point

    1: L<eI`Y@ D#raF'JKJ7DUAg"GR
    2: L<eI`Y@ D#raF'JKJ7DUAg"GR
    3: chNOLe"5]={Iiyrgk*,rEpE/!
    4: L<eI`Y@ D#ra nR$C1SrYqha+
    5: L<eI`Y@ D#ra nR$C1SrYqha+
    6: lpa5`Y@ D#ra nR$C8y.iqrt5
    7: C]Y&hJ1 %aRwi< aaB,r_Zh68
    8: 1s[r.ts %aGwi< _a"=rjXyN!
    9: chNOlFsyD#rwi< }aB,r_Zh68
   10: chNO9e" D#rwi< }aB=rPgh6!
   11: chNO9e" D#rwi< }aB=rPgh6!
   12: 1s[r.Ks D#ra n}way rAght!
   13: C}hplFs D#rwi.}way rPgh6!
   14: C'aclos Da{]inrwas r.ghx!
   15: C'aclos Da{]inrwas r.ghx!
   16: ChNrlFs Da>win}was  `gha!
   17: ChNrlFs Da>winlwas r;gh6!
   18: Ch[rlFs Da>wi< was rAght!
   19: Chacle@ D#rwin was rjght!
   20: Chacle@ D#rwin was rjght!
   21: ChNrles Darwin}was rAght!
   22: ChNrles Darwin}was rAght!
   23: Charles Darwin}was r`ght!
   24: Charles Darwin}was r`ght!
   25: Charles Darwin was rAght!
   26: Charles Darwin was rAght!
   27: Charles Darwin was rAght!
   28: Charles Darwin was rAght!
   29: Charles Darwin was rAght!
   30: Charles Darwin was right!

Found in 30 generations
Time Taken: 00:00:00.4730271

Source

You can download the source from github: https://github.com/dreasgrech/StringEvolver

Command Line arguments

-m, --mutation=VALUE
A value between 0-1

The mutation rate determines the probability of how often a selected chromosome mutates. Mutation is very important in a genetic algorithm because it helps in keeping diversity in the population, thus avoid local minima which can slow or even halt further evolution.

The application currently uses a mutation operator called Single Point Mutation. For our current application, it works by randomly selecting a point in the string and switching the character at that point to another random character.

As an example, say the chromosome to be mutated currently contains the string "aBcdE". The single point mutation operator then randomly chooses position 2 (0-based) and replaces the character 'c' with the randomly chosen character 'W'.

This way, the chromosome "aBcdE" has now been mutated to "aBWdE".

-s, --crossover=VALUE
A value between 0-1

The crossover rate determines how often two selected chromosomes are sexually combined to produce two separate offspring.

For this application, there are two available crossover operations: One Point Crossover and Two Point Crossover. These operators are discussed further in the ctype argument.

-e, --elitism=VALUE
A value between 0-1

The elitism rate determines the number of the fittest solutions that are directly (untouched) transferred to the advancing population.

Elitism can help in preventing the potential loss of possibly good solutions and can lead to quicker convergence.

-c, --crcount=VALUE
A value greater than 1

The chromosome count determines the number of chromosomes that each population will have. The greater the number of chromosomes, the more time a population takes to advance to the next.

--fitness=VALUE
VALUE = sum, levenshtein or hamming

The fitness calculator determines which algorithm is used to calculate how fit a given chromosome is.

There are currently three fitness calculators to choose from:

Sum
The sum calculator calculates the ASCII difference between each character of the target strings.

public override double CalculateFitness(Chromosome ch)
{
    var distanceToTarget = Target.Select((t, i) => Math.Abs(t - ch.Value[i])).Sum();
    return 1.0 / distanceToTarget;
}

Levenshtein Distance
The Levenshtein distance between two strings is the minimum number of edits needed to transform one string into the other. The transformation can include insertion, deletion and substitution. This distance is also referred to as the edit distance.

public override double CalculateFitness(Chromosome ch)
{
    return 1.0 / LevenshteinDistance(ch.Value, Target);
}

Hamming Distance
The Hamming distance between two strings of equal length is the number of positions at which the corresponding symbols are different. The reason Hamming distance requires the strings to be of equal length is because unlike the Levenshtein distance, the Hamming distance only allows substitutions.

As an example, the Hamming distance between "janica" and "jenixo" is 3.

public override double CalculateFitness(Chromosome ch)
{
    if (ch.Value.Length != Target.Length)
    {
        return 1.0 / double.PositiveInfinity;
    }

    var difference = 0;
    for (int i = 0; i < Target.Length; i++)
    {
        if (ch.Value[i] != Target[i])
        {
            difference++;
        }
    }
    return 1.0 / difference;
}

--ctype=VALUE
VALUE = one or two

The crossover type determines which crossover operator is to be used when sexually combining two chromosomes.

There are currently two available methods to choose from:

One
The One-Point Crossover method chooses a random point (called a locus) in the string and all the data beyond that point in either chromosome is swapped between the parent chromosomes. The resulting two chromosomes are the children.

public Tuple<Chromosome, Chromosome> Crossover(Chromosome c1, Chromosome c2)
{
    var locus = random.Next(0, c1.Value.Length + 1);
    string ch1 = c1.Value.Substring(0, locus) + c2.Value.Substring(locus),
           ch2 = c2.Value.Substring(0, locus) + c1.Value.Substring(locus);

    return new Tuple<Chromosome, Chromosome>(new Chromosome(ch1, fitnessCalculator), new Chromosome(ch2, fitnessCalculator));
}

Two
The Two-Point Crossover method is very similar to the One-Point Crossover method but this one chooses two random points along the string rather than one. The data between the two points is swapped and the resulting chromosomes are the children.

public Tuple<Chromosome, Chromosome> Crossover(Chromosome c1, Chromosome c2)
{
    int locus1 = random.Next(0, c1.Value.Length),
        locus2 = random.Next(locus1, c1.Value.Length),
        distance = locus2 - locus1;

    string ch1 = c1.Value.Substring(0, locus1) + c2.Value.Substring(locus1, distance) + c1.Value.Substring(locus2),
           ch2 = c2.Value.Substring(0, locus1) + c1.Value.Substring(locus1, distance) + c2.Value.Substring(locus2);

    return new Tuple<Chromosome, Chromosome>(new Chromosome(ch1, fitnessCalculator), new Chromosome(ch2, fitnessCalculator));
}

-t, --truncate=VALUE
0 < VALUE <= 1

The Truncation value determines how many chromosomes of the current population should be kept and used for the selection, crossover and mutation operations. Note that before the truncation is performed, the chromosomes in the population are sorted in descending order by their fitness, so the fittest chromosomes are kept after the truncation.

A value of 1 uses all of the chromosomes and a value of 0.5 uses half of the population (the better half, of course)

The A* algorithm in XNA

The A* search algorithm ("A star") is used for path finding and graph traversal. The following is my implementation in XNA.

The A* algorithm itself is very similar to Dijkstra's algorithm but the A* uses heuristics to achieve better performance.

Screenshots

Usage

Left Mouse Click - Create a barrier
CTRL + Left Mouse Click - Set the source
ALT + Left Mouse Click - Set the destination
Space - Toggle grid lines
Enter - Start pathfinding!
` - Open the developer console

Heuristics

The A* algorithm uses a heuristic to improve performance by trying to "guess" the best path, although this will not, unlike Dijkstra's which does not use a heuristic, guarantee the shortest path.

Diagonal Distance

public int GetEstimate(Point source, Point destination)
{
    return Math.Max(Math.Abs(destination.X - source.X), Math.Abs(destination.Y - source.Y));
}

Manhattan Distance

public int GetEstimate(Point source, Point destination)
{
    return Math.Abs(destination.X - source.X) + Math.Abs(destination.Y - source.Y);
}

Euclidean Distance

public int GetEstimate(Point source, Point destination)
{
    return (int)Math.Sqrt(Math.Pow(source.X - destination.X,2) + Math.Pow(source.Y - destination.Y,2));
}

Dijkstra

When the heuristic is 0, the A* algorithm turns into Dijkstra's algorithm

public int GetEstimate(Point source, Point destination)
{
    return 0;
}

Try it!

The source can be found on github: https://github.com/dreasgrech/AStarXNA

A String.Format for JavaScript

The following is my implementation of a miniature version of .NET's String.Format:

String.format = String.format || function (format) {
    var params = [].splice.call(arguments, 1), nextOpen, nextClose = 0, index, plValue, spaces, totalSpaces,
        removeCharAt = function (text, pos) {
            return text.substr(0, pos) + text.substr(pos + 1, text.length);
        };

    while ((nextOpen = format.indexOf('{', nextClose)) >= 0) {
        if (isNaN(+format[nextOpen+1])) { 
            if (format[nextOpen+1] === "{") {
                format = removeCharAt(format, nextOpen + 1);
                format = removeCharAt(format, format.indexOf('}', nextOpen-1));
                nextClose++;
                continue;
            }
            nextClose = nextOpen + 1;
            continue;
        }
        
        nextClose = format.indexOf('}', nextOpen);
        index = format.substring(nextOpen + 1, nextClose);
        if (index.indexOf(',') > 0) {
            spaces = +index.substring(index.indexOf(',') + 1);
            index = +index.substring(0, index.indexOf(','));
        }
        plValue = params[index] + '';
        if (spaces) {
            totalSpaces = new Array(Math.abs(spaces) - plValue.length + 1).join(" ");
            plValue = spaces > 0 ? totalSpaces + plValue : plValue + totalSpaces;
        }
        format = format.substring(0, nextOpen) + ((!plValue && plValue !== 0) ? "" : plValue) + format.substring(nextClose + 1);
        nextClose = nextOpen + plValue.length - 1;
        spaces = 0;
    }
    return format;
};

Usage

String.format("Hello {0} {1}", "Andreas", "Grech");  // "Hello Andreas Grech"

for (var i = 0; i <= 1000; i += 200) {
    String.format("{0, 5}. Something", i);
}

/* Output:
    0. Something
  200. Something
  400. Something
  600. Something
  800. Something
 1000. Something
*/

String.format("Padded from {0, 7} left", "the");  // "Padded from     the left"
String.format("{{0}}", "Ignored");  // "{0}"
String.format("{{{0}}}", "Not ignored");  // "{Not ignored}"
String.format("{{{{0}}}}", "Seeing the pattern?");  // "{{0}}"
String.format("{{{{{0}}}}}", "This is getting mental"); // "{{This is getting mental}}"

You can fork this project at github: https://github.com/dreasgrech/JSStringFormat

A Developer Game Console plugin for XNA Games

This is a project I was recently working on and it's a developer console for XNA games. It can easily be added to any XNA game and modified

Screenshots

Quick Start

Add the compiled XnaGameConsole dll as a reference and initialize the GameConsole:

GameConsole console = new GameConsole(this, spriteBatch); // where `this` is your `Game` class

By default, the console is opened with the ` (OemTilde key) but this, amongst other settings, can be changed via the Options property.

You can then add commands and customize the console.

Features

• Add your own commands
• Customizable Options
• Clipboard Support
• External Writing
• Command Auto-Complete
• Command History

Source and Downloads

You can checkout a copy of the source at the Google Code page: http://code.google.com/p/xnagameconsole/

The compiled dll of XNAGameConsole can also be downloaded from here: http://code.google.com/p/xnagameconsole/downloads/list

Notes

Clipboard Support

The console supports pasting via CTRL+V but this requires the game to be running in a Single Threaded Apartment.

To do this, add the STAThread attribute to the entry point of your game:

static class Program
{
    /// <summary>
    /// The main entry point for the application.
    /// </summary>
    [STAThread]
    static void Main(string[] args)
    {
        using (Game1 game = new Game1())
        {
            game.Run();
        }
    }
}

Adding Commands

There are currently 2 ways how to add custom commands to the console:

1. Using IConsoleCommand

Console commands can be built via the IConsoleCommand interface.
The following is an example of a command:

class MovePlayerCommand:IConsoleCommand
{
    public string Name
    {
        get { return "move"; }
    }

    public string Description
    {
        get { return "Moves the player"; }
    }

    private Player player;
    public MovePlayerCommand(Player player)
    {
        this.player = player;
    }

    public string Execute(string[] arguments)
    {
        var newPosition = new Vector2(float.Parse(arguments[0]), float.Parse(arguments[1]));
        player.Position = newPosition;
        return "Moved player to " + newPosition;
    }
}

Such a command can then be added to the console like such:

console.AddCommand(new MovePlayerCommand(player));

2. Via a Func<string, string>

Commands can also be added without using IConsoleCommand, like the following:

console.AddCommand("rotRad", a =>
                                 {
                                     var angle = float.Parse(a[0]);
                                     player.Angle = angle;
                                     return String.Format("Rotated the player to {0} radians", angle);
                                 }, "Rotates the player");

The advantage of adding a command like this is that in the Func<> you have access to the variables outside the closure.

Writing to the Console

You can dynamically write to the console via the WriteLine method:

console.WriteLine("Writing from the code");

Console Options

The console can be customized with a number of options. These options can be accessed through the GameConsoleOptions class.

To set the initial options, instantiate a new GameConsoleOptions class, set your desired options and pass it through one of the GameConsole's overloaded constructors:

GameConsoleOptions options = new GameConsoleOptions { FontColor = Color.Crimson, Prompt = ">", BackgroundColor = Color.DarkGreen };
GameConsole console = new GameConsole(this, spriteBatch, options);

The options can also be changed dynamically through the Options property of GameConsole:

console.Options.Height = 200;

The following are the current available options:

ToggleKey (Microsoft.Xna.Framework.Input.Keys)

Gets or sets the key that is used to show / hide the console

Default: Keys.OemTilde

BackgroundColor (Microsoft.Xna.Framework.Graphics.Color)

Gets or sets the color for the background of the console

Default: new Color(0, 0, 0, 125)

FontColor (Microsoft.Xna.Framework.Graphics.Color)

Sets the same specified color for all of the following properties:

• BufferColor
• PastCommandColor
• PastCommandOutputColor
• PromptColor
• CursorColor

Default: Color.White

BufferColor (Microsoft.Xna.Framework.Graphics.Color)

Gets or sets the color of the text in the buffer

Default: Color.White

PastCommandColor (Microsoft.Xna.Framework.Graphics.Color)

Gets or sets the color of the past commands

Default: Color.White

PastCommandOutputColor (Microsoft.Xna.Framework.Graphics.Color)

Gets or sets the color of the past command outputs

Default: Color.White

PromptColor (Microsoft.Xna.Framework.Graphics.Color)

Gets or sets the color of the prompt

Default: Color.White

CursorColor (Microsoft.Xna.Framework.Graphics.Color)

Gets or sets the color of the cursor

Default: Color.White

AnimationSpeed (float)

Gets or sets the speed by which the console opens/closes

Default: 1

CursorBlinkSpeed (float)

Gets or sets the speed by which the cursor blinks

Default: 0.5f

Height (int)

Gets or sets the height of the console, in pixels

Default: 300

Prompt (string)

Gets or sets the prompt

Default: $

Cursor (char)

Gets or sets the cursor display character

Default: _

Padding (int)

Gets or sets the padding, in pixels, between the border of the console and the inner text

Default: 30

Margin (int)

Gets or sets the margin, in pixels, between the left and right side of the screen to the console border

Default: 30

OpenOnWrite (bool)

Gets or sets a boolean value that indicates whether to open the console, if it's closed, when writing to the console

Default: true

Font (Microsoft.Xna.Framework.Graphics.SpriteFont)

Gets or sets the font that is used in the console

Default: Consolas, Regular, 11pt

Drawing lines and rectangles in XNA

In my last project, I needed a way to draw a grid with lines in XNA but I had some trouble in actually finding a way how to draw a simple line.  In this post, I will explain how to accomplish this.

First, create a new Texture2D with size: 1x1

Texture2D pixel = new Texture2D(GraphicsDevice, 1, 1, 1, TextureUsage.None, SurfaceFormat.Color);

You can access the GraphicsDevice from your Game (game.GraphicsDevice)

We then set the colour of this 1x1 texture to White. This allows us to choose what colour it should be drawn later on.

pixel.SetData(new[] { Color.White });

Now we can draw this texture by specifying a Rectangle holding the position and size:

spriteBatch.Draw(pixel, new Rectangle(10, 20, 100, 50), Color.DarkGreen);

The above snippet will draw a dark green 100x50 rectangle at {X: 10, Y: 20}

Handling single keyboard strokes in XNA

In a game, there are times where you need to handle single key strokes, rather than repeating ones. Examples are of a Pause key or a 'Press any key to start' scenario.

Unfortunately, XNA does not directly offer this functionality.

Therefore I wrote this very simple event-driven class that does exactly that:

using System;
using Microsoft.Xna.Framework;
using Microsoft.Xna.Framework.Input;

namespace XNASingleStroke
{
    public class SingleKeyStroke : GameComponent
    {
        public event EventHandler<KeyDownEventArgs> KeyDown = delegate { };

        private int pressedKeys;
        public SingleKeyStroke(Game game) : base(game) { }

        public override void Update(GameTime gameTime)
        {
            var pressed = Keyboard.GetState().GetPressedKeys();
            var keys = 0;
            foreach (var key in pressed)
            {
                var num = 1 << (int)key;
                keys |= num;
                if ((pressedKeys & num) != num)
                {
                    KeyDown(this, new KeyDownEventArgs(key));
                }
            }
            pressedKeys = keys;
            base.Update(gameTime);
        }
    }
}

And this is KeyDownEventArgs that's used in the event handler:

using System;
using Microsoft.Xna.Framework.Input;

namespace XNASingleStroke
{
    public class KeyDownEventArgs:EventArgs
    {
        public Keys Key { get; set; }
        public KeyDownEventArgs(Keys key)
        {
            Key = key;
        }
    }
}

Usage is also very simple:

protected override void Initialize()
{
    // ...
    SingleKeyStroke singleStroke = new SingleKeyStroke(this); //where 'this' is your Game
    singleStroke.KeyDown += (o, e) => {
        switch (e.Key)
        {
            case Keys.Space:Console.WriteLine("Space was pressed"); break;
            case Keys.Enter:Console.WriteLine("Enter was pressed"); break;
        }
   };
   Components.Add(singleStroke);
}

A simple menu for a Gosu game in ruby

For The Lost Battle, I wrote a very simple menu system that would allow me to add in-game menus. This allowed me to instantiate a menu and then add items to it and let the menu take care of the drawing.

The menu also takes care of notifying me when an item has been clicked via a callback, and also offsets the position of the item on hover.

The following is the basic gist of how it can be used:

@menu = Menu.new(self) #instantiate the menu, passing the Window in the constructor

@menu.add_item(Gosu::Image.new(self, "item.png", false), 100, 200, 1, lambda { self.close }, Gosu::Image.new(self, "item_hover.png", false))
@menu.add_item(Gosu::Image.new(self, "item2.png", false), 100, 250, 1, lambda { puts "something" }, Gosu::Image.new(self, "item2_hover.png", false))

The arguments of add_item are the image showed when the item is in its normal state, the x position, y position, z-order, the callback that will be invoked when that item is clicked and finally an optional parameter of an image that is used when the item is hovered upon.

Then hook to the button_down event of your Window, and inform the menu that the mouse has been clicked:

def button_down (id)
    if id == Gosu::MsLeft then
        @menu.clicked
    end
end

Finally, just draw and update the menu in the hooked methods:

def update
    @menu.update
end

def draw
    @menu.draw
end

I made a simple demo of this and you can download it from here.

---

The following is the source of the two aforementioned classes:

class Menu
    def initialize (window)
        @window = window
        @items = Array.new
    end

    def add_item (image, x, y, z, callback, hover_image = nil)
        item = MenuItem.new(@window, image, x, y, z, callback, hover_image)
        @items << item
        self
    end

    def draw
        @items.each do |i|
            i.draw
        end
    end

    def update
        @items.each do |i|
            i.update
        end
    end

    def clicked
        @items.each do |i|
            i.clicked
        end
    end
end

class MenuItem
    HOVER_OFFSET = 3
    def initialize (window, image, x, y, z, callback, hover_image = nil)
        @window = window
        @main_image = image
        @hover_image = hover_image
        @original_x = @x = x
        @original_y = @y = y
        @z = z
        @callback = callback
        @active_image = @main_image
    end

    def draw
        @active_image.draw(@x, @y, @z)
    end

    def update
        if is_mouse_hovering then
            if !@hover_image.nil? then
                @active_image = @hover_image
            end

            @x = @original_x + HOVER_OFFSET
            @y = @original_y + HOVER_OFFSET
        else 
            @active_image = @main_image
            @x = @original_x
            @y = @original_y
        end
    end

    def is_mouse_hovering
        mx = @window.mouse_x
        my = @window.mouse_y

        (mx >= @x and my >= @y) and (mx <= @x + @active_image.width) and (my <= @y + @active_image.height)
    end

    def clicked
        if is_mouse_hovering then
            @callback.call
        end
    end
end

Note that both the code and the method in general can be greatly improved and refactored. Just take a look at the code and modify it as you see fit :)